CoChat
Sign Up
Cited by 43Complex Network Analysis TechniquesGraph theory and applicationsQuantum Mechanics and Applications

Community Detection in Quantum Complex Networks

Open access
Faccin, Mauro, Migdał, Piotr, Johnson, Tomi H., Bergholm, Ville, Biamonte, Jacob D.·2014·Physical Review X
DOI 10.1103/physrevx.4.041012
Open this paper in CoChat — free accountOpen PDF

Abstract

Determining community structure is a central topic in the study of complex networks, be it technological, social, biological or chemical, static or in interacting systems.In this paper, we extend the concept of community detection from classical to quantum systems-a crucial missing component of a theory of complex networks based on quantum mechanics.We demonstrate that certain quantum mechanical effects cannot be captured using current classical complex network tools and provide new methods that overcome these problems.Our approaches are based on defining closeness measures between nodes, and then maximizing modularity with hierarchical clustering.Our closeness functions are based on quantum transport probability and state fidelity, two important quantities in quantum information theory.To illustrate the effectiveness of our approach in detecting community structure in quantum systems, we provide several examples, including a naturally occurring light-harvesting complex, LHCII.The prediction of our simplest algorithm, semiclassical in nature, mostly agrees with a proposed partitioning for the LHCII found in quantum chemistry literature, whereas our fully quantum treatment of the problem uncovers a new, consistent, and appropriately quantum community structure.

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.4.041012

Cites

5 of 5 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?

  • A second closeness measure is related to the average fidelity of the evolving process compared with the initial state, with the localization of eigenstates determining the closeness of two nodes.

    “A second quantity, also proposed as a closeness measure, is related to the average fi delity of the evolving process compared with the initial state. In this case, the localization of eigenstates is the characteristic determining the closeness of two nodes.”

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

    Section III.B (Intracommunity fidelity; page unavailable) defines a closeness measure from the fidelity between the evolving state and the initial state, and then takes its time average. Its long-time expression uses projectors onto Hamiltonian eigenspaces, but the paper does not state that eigenstate localization is the characteristic determining closeness between two nodes; the measure also depends on the chosen initial state. (LLM, conf=0.82)

    Experimental — accuracy not yet measured

  • If the average in-between transport is computed over a short time period compared with evolution time scales, the closeness values are proportional to the Hamiltonian terms |Hij|, providing a classical approach to community detection.

    “If this average is computed over a short time period (compared with evolution time scales), then the closeness values are proportional to the Hamiltonian terms | Hij |, providing a classical approach to community detection (see Fig. 3).”

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

    The Intercommunity transport section says that short-time averaging yields a semiclassical approach to community detection. But it states that the averaged transfer matrix is proportional to |Hij|², not |Hij|; the claimed proportionality is unsupported. (LLM, conf=0.90)

    Experimental — accuracy not yet measured

  • Classical network descriptors have been ported to the quantum realm to gain better insights about the structure and the dynamics of networked quantum systems.

    “classical network descriptors have been ported to the quantum realm to gain better insights about the structure and the dynamics of networked quantum systems 13 .”

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

  • Even the classical network describing a quantum system can exhibit complex features.

    “even the classical network describing a quantum system can exhibit complex features”

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

  • In that framework, two nodes are considered to be close if, on average, their in-between transport is high.

    “In this framework, two nodes are considered to be close if, on average, their in-between transport is high.”

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

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

Research works printed but not linked: 66

  1. M. Girvan and M. E. J. Newman, Community Structure in Social and Biological Networks, Proc. Natl. Acad. Sci. · DOI · Paper page
  2. U.S.A. 99, 7821 (2002). · DOI · Paper page
  3. M. A. Porter, J.-P. Onnela, and P. J. Mucha, Communities in Networks, Not. Am. Math. Soc. 56, 1082 (2009).
  4. S. Fortunato, Community Detection in Graphs, Phys. Rep. 486, 75 (2010). · DOI · Paper page
  5. S. A. Rice, The Identification of Blocs in Small Political Bodies, Am. Pol. Sci. Rev. 21, 619 (1927). · DOI
  6. W. W. Zachary, An Information Flow Model for Conflict and Fission in Small Groups, Journal of anthropological research 33, 452 (1977).
  7. D. Lusseau and M. E. J. Newman, Identifying the Role That Animals Play in Their Social Networks, Proc. R. Soc. B 271, S477 (2004). · DOI
  8. P. F. Jonsson, T. Cavanna, D. Zicha, and P. A. Bates, Cluster Analysis of Networks Generated through Homology: Au- tomatic Identification of Important Protein Communities Involved in Cancer Metastasis, BMC Bioinf. 7, 2 (2006). · DOI
  9. S. L. Pimm, The Structure of Food Webs, Theor. Popul. Biol. 16, 144 (1979). · DOI
  10. A. E. Krause, K. A. Frank, D. M. Mason, R. E. Ulanowicz, and W. W. Taylor, Compartments Revealed in Food-Web Structure, Nature (London) 426, 282 (2003). · DOI · Paper page
  11. P. Holme, M. Huss, and H. Jeong, Subnetwork Hierarchies of Biochemical Pathways, Bioinformatics 19, 532 (2003). · DOI
  12. G. William Flake, S. Lawrence, C. Lee Giles, and F. M. Coetzee, Self-Organization and Identification of Web Com- munities, Computer 35, 66 (2002). · DOI
  13. L. Gauvin, A. Panisson, and C. Cattuto, Detecting the Community Structure and Activity Patterns of Temporal Networks: A Non-negative Tensor Factorization Approach, PLoS One 9, e86028 (2014). · DOI
  14. M. Allegra and P. Giorda, Topology and Energy Transport in Networks of Interacting Photosynthetic Complexes, Phys. Rev. E 85, 051917 (2012). · DOI
  15. M. B. Plenio and S. F. Huelga, Dephasing-Assisted Trans- port: Quantum Networks and Biomolecules, New J. Phys. 10, 113019 (2008). · DOI · Paper page
  16. J. Adolphs and T. Renger, How Proteins Trigger Excitation Energy Transfer in the FMO Complex of Green Sulfur Bacteria, Biophys. J. 91, 2778 (2006). · DOI
  17. J. C. Baez and J. Biamonte, A Course on Quantum Tech- niques for Stochastic Mechanics, arXiv:1209.3632. · arXiv
  18. M. Faccin, T. Johnson, J. Biamonte, S. Kais, and P. Migdał, Degree Distribution in Quantum Walks on Complex Net- works, Phys. Rev. X 3, 041007 (2013). · DOI
  19. T. H. Johnson, S. R. Clark, and D. Jaksch, What is a Quantum Simulator?, EPJ Quantum Technol. 1, 10 (2014). · DOI
  20. A. K. Ringsmuth, G. J. Milburn, and T. M. Stace, Multiscale Photosynthetic and Biomimetic Excitation Energy Transfer, Nat. Phys. 8, 562 (2012). · DOI
  21. M. Sarovar, A. Ishizaki, G. R. Fleming, and K. Birgitta Whaley, Quantum Entanglement in Photosynthetic Light- Harvesting Complexes, Nat. Phys. 6, 462 (2010). · DOI · Paper page
  22. A. Ishizaki and G. R. Fleming, Quantum Coherence in Photosynthetic Light Harvesting, Annu. Rev. Condens. Matter Phys. 3, 333 (2012). · DOI
  23. Y.-C. Cheng and G. R. Fleming, Dynamics of Light Harvest- ing in Photosynthesis, Annu. Rev. Phys. Chem. 60, 241 (2009). · DOI
  24. F. Caruso, A. W. Chin, A. Datta, S. F. Huelga, and M. B. Plenio, Highly Efficient Energy Excitation Transfer in Light-Harvesting Complexes: The Fundamental Role of Noise-Assisted Transport, J. Chem. Phys. 131, 105106 (2009). · DOI · Paper page
  25. M. Mohseni, P. Rebentrost, S. Lloyd, and A. Aspuru-Guzik, Environment-Assisted Quantum Walks in Photosynthetic Energy Transfer, J. Chem. Phys. 129, 174106 (2008). · DOI · Paper page
  26. L. Banchi, G. Costagliola, A. Ishizaki, and P. Giorda, An Analytical Continuation Approach for Evaluating Emission Lineshapes of Molecular Aggregates and the Adequacy of Multichromophoric Förster Theory, J. Chem. Phys. 138 184107 (2013). · DOI
  27. D. S. Rokhsar and B. G. Kotliar, Gutzwiller Projection for Bosons, Phys. Rev. B 44, 10 328 (1991). · DOI
  28. W. Krauth, M. Caffarel, and J.-P. Bouchaud, Gutzwiller Wave Function for a Model of Strongly Interacting Bosons, Phys. Rev. B 45, 3137 (1992). · DOI
  29. K Sheshadri, H. R. Krishnamurthy, R. Pandit, and T. V. Ramakrishnan, Superfluid and Insulating Phases in an Interacting-Boson Model: Mean-Field Theory and the RPA, Europhys. Lett. 22, 257 (1993). · DOI
  30. D. S. Lühmann, Cluster Gutzwiller Method for Bosonic Lattice Systems, Phys. Rev. A 87, 043619 (2013). · DOI
  31. F. Verstraete, V. Murg, and J. Ignacio Cirac, Matrix Product States, Projected Entangled Pair States, and Variational Renormalization Group Methods for Quantum Spin Sys- tems, Adv. Phys. 57, 143 (2008). · DOI
  32. J. Ignacio Cirac and F. Verstraete, Renormalization and Tensor Product States in Spin Chains and Lattices, J. Phys. A 42, 504004 (2009). · DOI
  33. H. Wang, I. Pshenichnyuk, R. Härtle, and M. Thoss, Numerically Exact, Time-Dependent Treatment of Vibra- tionally Coupled Electron Transport in Single-Molecule Junctions, J. Chem. Phys. 135, 244506 (2011). · DOI
  34. L. Cao, S. Krönke, O. Vendrell, and P. Schmelcher, The Multi-Layer Multi-Configuration Time-Dependent Hartree Method for Bosons: Theory, Implementation, and Applica- tions, J. Chem. Phys. 139, 134103 (2013). · DOI
  35. X. Pan, Z. Liu, M. Li, and W. Chang, Architecture and Function of Plant Light-Harvesting Complexes II, Curr. Opin. Struct. Biol. 23, 515 (2013). · DOI
  36. V. I. Novoderezhkin, M. A. Palacios, H. van Amerongen, and R. van Grondelle, Excitation Dynamics in the LHCII Complex of Higher Plants: Modeling Based on the 2.72 Å Crystal Structure, J. Phys. Chem. B 109, 10 493 (2005). · DOI
  37. G. Carlsson and F. Mémoli, Characterization, Stability and Convergence of Hierarchical Clustering Methods, J. Mach. Learn. Res. 99, 1425 (2010).
  38. R. Guimerà, M. Sales-Pardo, and L. A. Nunes Amaral, Modularity from Fluctuations in Random Graphs and Complex Networks, Phys. Rev. E 70, 025101 (2004). · DOI · Paper page
  39. A. Lancichinetti, F. Radicchi, J. J. Ramasco, and S. Fortunato, Finding Statistically Significant Communities in Networks, PLoS One 6, e18961 (2011). · DOI
  40. E. Estrada, Community detection based on network com- municability, Chaos 21, 016103 (2011). · DOI
  41. E. Estrada and N. Hatano, Communicability Graph and Community Structures in Complex Networks, Appl. Math. Comput. 214, 500 (2009). · DOI
  42. M. Meila and J. Shi, in Proceedings of the Eighth International Workshop on Artificial Intelligence and Statistics (2001); http://www.gatsby.ucl.ac.uk/aistats/ aistats2001/index.html.
  43. J.-C. Delvenne, S. N. Yaliraki, and M. Barahona, Stability of Graph Communities across Time Scales, Proc. Natl. Acad. Sci. U.S.A. 107, 12755 (2010). · DOI
  44. M. Rosvall and C. T. Bergstrom, Multilevel Compression of Random Walks on Networks reveals Hierarchical Organi- zation in Large Integrated Systems, PLoS One 6, e18209 (2011). · DOI
  45. P. Pons and M. Latapy, Computing Communities in Large Networks Using Random Walks (Springer, New York, 2005), pp. 284-293.
  46. T. Hastie, R. Tibshirani, and J. Friedman, The Elements of Statistical Learning Theory (Springer, New York, 2001).
  47. M. E. J. Newman and M. Girvan, Finding and Evaluating Community Structure in Networks, Phys. Rev. E 69, 026113 (2004). · DOI · Paper page
  48. M. E. J. Newman, Fast Algorithm for Detecting Community Structure in Networks, Phys. Rev. E 69, 066133 (2004). · DOI
  49. A. Clauset, M. E. J. Newman, and C. Moore, Finding Community Structure in Very Large Networks, Phys. Rev. E 70, 066111 (2004). · DOI · Paper page
  50. R. R. Nadakuditi and M. E. J. Newman, Graph Spectra and the Detectability of Community Structure in Networks, Phys. Rev. Lett. 108, 188701 (2012). · DOI
  51. F. Radicchi, Detectability of Communities in Heterogeneous Networks, Phys. Rev. E 88, 010801 (2013). · DOI
  52. F. Radicchi, A Paradox in Community Detection, Europhys. Lett. 106, 38001 (2014). · DOI
  53. L. N. F. Ana and A. K. Jain, in Proceedings of Robust data clustering (IEEE, New York, 2003), Vol. 2, pp. II-128-II- 133.
  54. A. Strehl and J. Ghosh, Cluster Ensembles-A Knowledge Reuse Framework for Combining Multiple Partitions, J. Mach. Learn. Res. 3, 583 (2003).
  55. L. Danon, A. Díaz-Guilera, J. Duch, and A. Arenas, Comparing Community Structure Identification, J. Stat. Mech. (2005) P09008. · DOI
  56. See Supplemental Material at http://link.aps.org/ supplemental/10.1103/PhysRevX.4.041012 for a detailed derivation of the closeness measures.
  57. D. Lu, J. D. Biamonte, J. Li, H. Li, T. H. Johnson, V. Bergholm, M. Faccin, Z. Zimborás, R. Laflamme, J. Baugh, and S. Lloyd, Chiral Quantum Walks, arXiv:1405.6209. · arXiv
  58. K. Astrup Eriksen, I. Simonsen, S. Maslov, and K. Sneppen, Modularity and Extreme Edges of the Internet, Phys. Rev. Lett. 90, 148701 (2003). · DOI
  59. E. Weinan, T. Li, and E. Vanden-Eijnden, Optimal Partition and Effective Dynamics of Complex Networks, Proc. Natl. Acad. Sci. U.S.A. 105, 7907 (2008). · DOI
  60. C. Godsil, Average Mixing of Continuous Quantum Walks, arXiv:1103.2578. · arXiv
  61. V. A. Traag and J. Bruggeman, Community Detection in Networks with Positive and Negative Links, Phys. Rev. E 80, 036115 (2009). · DOI
  62. A. Lancichinetti, S. Fortunato, and F. Radicchi, Benchmark Graphs for Testing Community Detection Algorithms, Phys. Rev. E 78, 046110 (2008). · DOI
  63. E. Harel and G. S. Engel, Quantum Coherence Spectros- copy Reveals Complex Dynamics in Bacterial Light- Harvesting Complex 2 (LH2), Proc. Natl. Acad. Sci. · DOI
  64. U.S.A. 109, 706 (2012). · DOI
  65. M. Newman, Networks: An Introduction (Oxford University Press, Oxford, UK, 2009).
  66. E. Sánchez-Burillo, J. Duch, J. Gómez-Gardeñes, and D. Zueco, Quantum Navigation and Ranking in Complex Networks, Sci. Rep. 2, 605 (2012). · DOI · Paper page

Cited by

Sorted by citations

Authors
Faccin, M., Migdał, P., Johnson, T. H., Bergholm, V., & Biamonte, J. D.
Affiliations
  • Institute for Scientific Interchange (IT)
  • Centre for Quantum Technologies (SG)
ORCID
Biamonte, Jacob D.
Venue
Physical Review X
Publisher
American Physical Society (APS)
Published
2014-10-21
Volume
4
Issue
4
ISSN
2160-3308 (ISSN-L)
DOI
10.1103/physrevx.4.041012
OpenAlex
W2091830728
Cited by
43
References
5
Citations by year
2025: 6 · 2024: 6 · 2023: 2 · 2022: 3 · 2021: 5 · 2020: 8 · 2019: 1 · 2018: 4 · 2017: 3 · 2016: 3 · 2015: 2
FWCI
1.76
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)
  • arXiv (Cornell University) (cc-by)
Funders
  • European Research Council (FP7/2007-2013)
  • Spanish MINCIN/MINECO (FIS2008-00784)
  • EU Integrated Projects: ACUTE, SIQS
  • HISTERA project: DIQUIP
  • ERC (319286)
  • Singapore National Research Foundation
  • Singapore Ministry of Education
  • Foundational Questions Institute (FQXi-RFP3-1322)
  • Fondazione Compagnia di San Paolo project: Q-ARACNE
Topics
  • Physical Sciences › Physics and Astronomy › Statistical and Nonlinear Physics › Complex Network Analysis Techniques
  • Physical Sciences › Mathematics › Geometry and Topology › Graph theory and applications
  • Physical Sciences › Physics and Astronomy › Atomic and Molecular Physics, and Optics › Quantum Mechanics and Applications
Keywords
community detection, quantum transport, state fidelity, modularity optimization, hierarchical clustering, light-harvesting complexes, light-harvesting complex II, quantum chemistry, semiclassical approximation

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