Relating vertex and global graph entropy in randomly generated graphs

Tee, Philip, Parisis, George, Berthouze, Luc and Wakeman, Ian (2018) Relating vertex and global graph entropy in randomly generated graphs. Entropy, 20 (7). ISSN 1099-4300

[img] PDF - Published Version
Available under License Creative Commons Attribution.

Download (726kB)

Abstract

Combinatoric measures of entropy capture the complexity of a graph but rely upon the calculation of its independent sets, or collections of non-adjacent vertices. This decomposition of the vertex set is a known NP-Complete problem and for most real world graphs is an inaccessible calculation. Recent work by Dehmer et al. and Tee et al. identified a number of vertex level measures that do not suffer from this pathological computational complexity, but that can be shown to be effective at quantifying graph complexity. In this paper, we consider whether these local measures are fundamentally equivalent to global entropy measures. Specifically, we investigate the existence of a correlation between vertex level and global measures of entropy for a narrow subset of random graphs. We use the greedy algorithm approximation for calculating the chromatic information and therefore Körner entropy. We are able to demonstrate strong correlation for this subset of graphs and outline how this may arise theoretically.

Item Type: Article
Schools and Departments: School of Engineering and Informatics > Informatics
Research Centres and Groups: Evolutionary and Adaptive Systems Research Group
Foundations of Software Systems
Depositing User: Georgios Angelos Parisis
Date Deposited: 22 Jun 2018 13:15
Last Modified: 22 Jun 2018 13:15
URI: http://srodev.sussex.ac.uk/id/eprint/76678

View download statistics for this item

📧 Request an update