CoChat
Sign Up
Cited by 161Complex Network Analysis TechniquesStatistical Mechanics and EntropyGraph theory and applications

Spectral Entropies as Information-Theoretic Tools for Complex Network Comparison

Open access
De Domenico, Manlio, Biamonte, Jacob·2016·Physical Review X
DOI 10.1103/physrevx.6.041062
Open this paper in CoChat — free account

Abstract

Any physical system can be viewed from the perspective that information is implicitly represented in its state. However, the quantification of this information when it comes to complex networks has remained largely elusive. In this work, we use techniques inspired by quantum statistical mechanics to define an entropy measure for complex networks and to develop a set of information-theoretic tools, based on network spectral properties, such as Renyi q-entropy, generalized Kullback-Leibler and Jensen-Shannon divergences, the latter allowing us to define a natural distance measure between complex networks. First we show that by minimizing the Kullback-Leibler divergence between an observed network and a parametric network model, inference of model parameter(s) by means of maximum-likelihood estimation can be achieved and model selection can be performed appropriate information criteria. Second, we show that the information-theoretic metric quantifies the distance between pairs of networks and we can use it, for instance, to cluster the layers of a multilayer system. By applying this framework to networks corresponding to sites of the human microbiome, we perform hierarchical cluster analysis and recover with high accuracy existing community-based associations. Our results imply that spectral based statistical inference in complex networks results in demonstrably superior performance as well as a conceptual backbone, filling a gap towards a network information theory.

The claims and statistics of this paper haven’t been checked yet.

Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.

A few free checks a day · papers already verified open instantly · results are public

Integrity signals

Registry

Crossref · 10.1103/physrevx.6.041062

Cites

117 of 117 references verified0 citation errors · 0 not checkable

Statistics

Claims the paper makes

The claims and statistics of this paper haven’t been checked yet.

Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.

A few free checks a day · papers already verified open instantly · results are public

Claims other papers make about this one

Each is checked against this paper’s own text: does it say what the citing paper says it does?

  • Certain quantum systems have been shown to exhibit complex features related to classical systems, as well as novel mechanisms and principles that interrelate complex features in quantum systems.

    “Certain quantum systems have been shown to indeed exhibit complex features related to classical systems, as well as novel mechanisms and principles that interrelate complex features in quantum systems 6 -12,32 .”

    From Complex networks from classical to quantum (2019) · cites this paper as [32]

    The Introduction (p. 1) describes applying complex-network ideas to quantum systems, including node centrality in quantum walks and community structures in quantum systems. That supports a connection between classical network features and quantum systems, but the paper does not report novel mechanisms or principles that interrelate complex features in quantum systems; the Conclusions (p. 11) frame further quantum applications as prospective. (LLM, conf=0.78)

    Experimental — accuracy not yet measured

  • The same tools can be appropriately modified to apply to traditional complex networks, suggesting the existence of a framework - network information theory - suitable for application to both classical and quantum networked systems.

    “Interestingly, the same tools can then be appropriately modi fi ed to apply to traditional complex networks, suggesting the existence of a framework -network information theory -suitable for application to both classical and quantum networked systems 32,41,42 .”

    From Complex networks from classical to quantum (2019) · cites this paper as [32]

  • This undesirable feature can be addressed by means of a more grounded definition, whose rationale is to measure the entropy of a network by exploiting how information diffuses through its topology.

    “This undesirable feature can be addressed by means of a more grounded de fi nition 32 , whose rationale is to measure the entropy of a network by exploiting how information diffuses through its topology.”

    From Complex networks from classical to quantum (2019) · cites this paper as [32]

  • Quantum-inspired tools, such as information entropies and quantum distance measures, have been successfully applied to practical problems concerning classical complex networks.

    “quantum-inspired tools, such as information entropies and quantum distance measures, have been successfully applied to practical problems concerning classical complex networks 32 .”

    From Complex networks from classical to quantum (2019) · cites this paper as [32]

  • A research line is emerging that seeks to quantify networked systems in terms of implicit information processing capacity, with applications to social, technological, and biological systems.

    “In fact, a research line is emerging now that seeks to quantify, in terms of implicit information processing capacity, networked systems, with several applications to social, technological, and biological systems 32,41,42,90,91 .”

    From Complex networks from classical to quantum (2019) · cites this paper as [32]

Self-check

Percentages, sums and reported differences re-computed from the paper’s own numbers.

The self-check needs the paper’s full text.

Cites

Flagged first, then by citations

2 of the 119 references couldn’t be matched to a known paper.

Research works printed but not linked: 34

  1. [1]C. Shannon, Bell System Technical Journal 27 , 379 (1948).
  2. [5]C. H. Bennett and P. W. Shor, IEEE transactions on information theory 44 , 2724 (1998).
  3. [8]P. Bernaola-Galv´ an, I. Grosse, P. Carpena, J. L. Oliver, R. Rom´ an-Rold´ an, and H. E. Stanley, Physical Review Letters 85 , 1342 (2000).
  4. [29]M. Cuquet and J. Calsamiglia, Physical review letters 103 , 240503 (2009).
  5. [40]N. L¨ udtke, S. Panzeri, M. Brown, D. S. Broomhead, J. Knowles, M. A. Montemurro, and D. B. Kell, Journal of The Royal Society Interface 5 , 223 (2008).
  6. [44]S. Johnson, J. J. Torres, J. Marro, and M. A. Munoz, Physical Review Letters 104 , 108702 (2010).
  7. [45]K. Anand, G. Bianconi, and S. Severini, Physical Review E 83 , 036109 (2011).
  8. [48]M. Kivel¨ a, A. Arenas, M. Barthelemy, J. P. Gleeson, Y. Moreno, and M. A. Porter, Journal of Complex Networks 2 , 203 (2014).
  9. [52]E. Estrada and N. Hatano, Physical Review E 77 , 036111 (2008).
  10. [53]E. Estrada, D. J. Higham, and N. Hatano, Physical Review E 78 , 026102 (2008).
  11. [54]E. Estrada and D. J. Higham, SIAM review 52 , 696 (2010).
  12. [55]P. Grindrod, M. C. Parsons, D. J. Higham, and E. Estrada, Physical Review E 83 , 046120 (2011).
  13. [57]E. Estrada and J. G´ omez-Garde˜ nes, Physical Review E 89 , 042819 (2014).
  14. [59]S. L. Braunstein, S. Ghosh, and S. Severini, Annals of Combinatorics 10 , 291 (2006).
  15. [65]J. C. Baez, ArXiv e-prints (2011), arXiv:1102.2098 [quant-ph]. · arXiv
  16. [67]A. Majtey, P. Lamberti, and D. Prato, Physical Review A 72 , 052310 (2005).
  17. [68]P. Lamberti, A. Majtey, A. Borras, M. Casas, and A. Plastino, Physical Review A 77 , 052311 (2008).
  18. [69]J. Bri¨ et and P. Harremo¨ es, Physical review A 79 , 052311 (2009).
  19. [71]H. Akaike, in Second International Symposium on Information Theory , edited by B. N. Petrov and F. Csaki (Akad´ emiai Kiado, Budapest, 1973) pp. 267-281.
  20. [72]J. J. Rissanen, IEEE transactions on information theory 42 , 40 (1996).
  21. [73]M. A. Pitt, I. J. Myung, and S. Zhang, Psychological review 109 , 472 (2002).
  22. [78]N. Stanley, S. Shai, D. Taylor, and P. Mucha, IEEE Transactions on Network Science and Engineering 3 , 95 (2016).
  23. [80]P. Bientinesi, I. S. Dhillon, and R. A. Van De Geijn, SIAM Journal on Scientific Computing 27 , 43 (2005).
  24. [88]L. Zdeborov´ a and F. Krzakala, arXiv:1511.02476 (2015). · arXiv
  25. [90]H. Jeffreys, Proc. Roy. Soc. of London A 186 , 453 (1946).
  26. [92]S.-I. Amari, IEEE transactions on information theory 47 , 1701 (2001).
  27. [93]S. L. Braunstein and C. M. Caves, Physical Review Letters 72 , 3439 (1994).
  28. [94]P. Zanardi, P. Giorda, and M. Cozzini, Physical Review Letters 99 , 100603 (2007).
  29. [95]A. T. Rezakhani, D. F. Abasto, D. A. Lidar, and P. Zanardi, Physical Review A 82 , 012321 (2010).
  30. [96]M. M. Rams and B. Damski, Physical Review Letters 106 , 055701 (2011).
  31. [99]C. E. Granade, C. Ferrie, N. Wiebe, and D. G. Cory, New Journal of Physics 14 , 103013 (2012).
  32. [100]N. Wiebe, C. Granade, C. Ferrie, and D. Cory, Physical review letters 112 , 190501 (2014).
  33. [101]C. Helstrom, Physics letters A 25 , 101 (1967).
  34. [102]A. Monras and F. Illuminati, Physical Review A 81 , 062326 (2010).

Cited by

Sorted by citations

Related

Authors
De Domenico, M., & Biamonte, J.
Affiliations
University of Waterloo (CA)
ORCID
Biamonte, Jacob
Venue
Physical Review X
Publisher
American Physical Society (APS)
Published
2016-12-21
Volume
6
Issue
4
ISSN
2160-3308 (ISSN-L)
DOI
10.1103/physrevx.6.041062
OpenAlex
W2513813309
Cited by
160
References
119
Citations by year
2026: 9 · 2025: 19 · 2024: 22 · 2023: 18 · 2022: 16 · 2021: 22 · 2020: 25 · 2019: 9 · 2018: 13 · 2017: 7
FWCI
5.48
Type
journal article
Language
en
Open access
Licence
Locations
  • Physical Review X (publishedVersion, cc-by)
  • arXiv (Cornell University) (submittedVersion)
  • DOAJ (DOAJ: Directory of Open Access Journals) (submittedVersion, cc-by-sa)
  • Padua Research Archive (University of Padova) (submittedVersion)
  • arXiv (Cornell University)
Funders
  • Foundational Questions Institute
  • Juan de la Cierva (IJCI-2014-20225)
  • IARPA
Topics
  • Physical Sciences › Physics and Astronomy › Statistical and Nonlinear Physics › Complex Network Analysis Techniques
  • Physical Sciences › Physics and Astronomy › Statistical and Nonlinear Physics › Statistical Mechanics and Entropy
  • Physical Sciences › Mathematics › Geometry and Topology › Graph theory and applications
Keywords
network entropy, complex networks, Kullback-Leibler divergence, Jensen-Shannon divergence, network comparison, maximum likelihood estimation, model selection, information criteria, human microbiome, community structure, network information theory

About these checks

Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.

Statistics and arithmetic are recomputed, not judged.

Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.

What counts as a claim ›How we measure confidence ›How we check this ›

Are you an author, or do you see a problem with this page? Request a review