Relating Vertex and Global Graph Entropy in Randomly Generated Graphs
| Autor: | Ian Wakeman, George Parisis, Luc Berthouze, Philip Tee |
|---|---|
| Rok vydání: | 2018 |
| Předmět: |
Computational complexity theory
Computer science Graph entropy computational_mathematics graph entropy General Physics and Astronomy lcsh:Astrophysics 02 engineering and technology 01 natural sciences Article 010305 fluids & plasmas Set (abstract data type) 0103 physical sciences lcsh:QB460-466 0202 electrical engineering electronic engineering information engineering Entropy (information theory) Chromatic scale lcsh:Science Greedy algorithm random graphs Random graph Discrete mathematics 020206 networking & telecommunications chromatic classes lcsh:QC1-999 Graph Vertex (geometry) lcsh:Q lcsh:Physics |
| Zdroj: | Entropy, Vol 20, Iss 7, p 481 (2018) Entropy Volume 20 Issue 7 |
| ISSN: | 1099-4300 |
| DOI: | 10.20944/preprints201805.0302.v1 |
| Popis: | 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. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|