IDEAS home Printed from https://ideas.repec.org/a/eee/phsmap/v387y2008i11p2637-2652.html
   My bibliography  Save this article

What is a complex graph?

Author

Listed:
  • Kim, Jongkwang
  • Wilhelm, Thomas

Abstract

Many papers published in recent years show that real-world graphs G(n,m) (n nodes, m edges) are more or less “complex” in the sense that different topological features deviate from random graphs. Here we narrow the definition of graph complexity and argue that a complex graph contains many different subgraphs. We present different measures that quantify this complexity, for instance C1e, the relative number of non-isomorphic one-edge-deleted subgraphs (i.e. DECK size). However, because these different subgraph measures are computationally demanding, we also study simpler complexity measures focussing on slightly different aspects of graph complexity. We consider heuristically defined “product measures”, the products of two quantities which are zero in the extreme cases of a path and clique, and “entropy measures” quantifying the diversity of different topological features. The previously defined network/graph complexity measures Medium Articulation and Offdiagonal complexity (OdC) belong to these two classes. We study OdC measures in some detail and compare it with our new measures. For all measures, the most complex graph GCmax has a medium number of edges, between the edge numbers of the minimum and the maximum connected graph n−1

Suggested Citation

  • Kim, Jongkwang & Wilhelm, Thomas, 2008. "What is a complex graph?," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 387(11), pages 2637-2652.
    • Handle: RePEc:eee:phsmap:v:387:y:2008:i:11:p:2637-2652
    DOI: 10.1016/j.physa.2008.01.015
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0378437108000319
    Download Restriction: Full text for ScienceDirect subscribers only. Journal offers the option of making the article available online on Science direct for a fee of $3,000
    File URL: https://libkey.io/10.1016/j.physa.2008.01.015?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    As the access to this document is restricted, you may want to search for a different version of it.

    References listed on IDEAS

    as
    1. H. Jeong & S. P. Mason & A.-L. Barabási & Z. N. Oltvai, 2001. "Lethality and centrality in protein networks," Nature, Nature, vol. 411(6833), pages 41-42, May.
    2. Pablo M. Gleiser & Leon Danon, 2003. "Community Structure In Jazz," Advances in Complex Systems (ACS), World Scientific Publishing Co. Pte. Ltd., vol. 6(04), pages 565-573.
    3. Claussen, Jens Christian, 2007. "Offdiagonal complexity: A computationally quick complexity measure for graphs and networks," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 375(1), pages 365-373.
    4. Sinha, Sitabhra, 2005. "Complexity vs. stability in small-world networks," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 346(1), pages 147-153.
    5. Wilhelm, Thomas & Hollunder, Jens, 2007. "Information theoretic description of networks," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 385(1), pages 385-396.
    Full references (including those not matched with items on IDEAS)

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. Wang, Jiqiang, 2019. "Disturbance attenuation of complex dynamical systems through interaction topology design," Applied Mathematics and Computation, Elsevier, vol. 355(C), pages 576-584.
    2. Frank Emmert-Streib, 2013. "Structural Properties and Complexity of a New Network Class: Collatz Step Graphs," PLOS ONE, Public Library of Science, vol. 8(2), pages 1-14, February.
    3. Mehmet N. Aydin & N. Ziya Perdahci, 0. "Dynamic network analysis of online interactive platform," Information Systems Frontiers, Springer, vol. 0, pages 1-12.
    4. Mikołaj Morzy & Tomasz Kajdanowicz & Przemysław Kazienko, 2017. "On Measuring the Complexity of Networks: Kolmogorov Complexity versus Entropy," Complexity, Hindawi, vol. 2017, pages 1-12, November.
    5. da Cunha, Éverton Fernandes & da Fontoura Costa, Luciano, 2022. "On hypercomplex networks," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 591(C).
    6. Mahmoud Saleh & Yusef Esa & Ahmed Mohamed, 2018. "Applications of Complex Network Analysis in Electric Power Systems," Energies, MDPI, vol. 11(6), pages 1-16, May.
    7. Glover, Fred & Lewis, Mark & Kochenberger, Gary, 2018. "Logical and inequality implications for reducing the size and difficulty of quadratic unconstrained binary optimization problems," European Journal of Operational Research, Elsevier, vol. 265(3), pages 829-842.
    8. Lin, Yun Hui & Wang, Yuan & Lee, Loo Hay & Chew, Ek Peng, 2021. "Consistency matters: Revisiting the structural complexity for supply chain networks," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 572(C).
    9. Zenil, Hector & Soler-Toscano, Fernando & Dingle, Kamaludin & Louis, Ard A., 2014. "Correlation of automorphism group size and topological properties with program-size complexity evaluations of graphs and complex networks," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 404(C), pages 341-358.
    10. Tuğal, İhsan & Karcı, Ali, 2019. "Comparisons of Karcı and Shannon entropies and their effects on centrality of social networks," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 523(C), pages 352-363.
    11. Lavanya Sivakumar & Matthias Dehmer, 2012. "Towards Information Inequalities for Generalized Graph Entropies," PLOS ONE, Public Library of Science, vol. 7(6), pages 1-14, June.
    12. Wang, Jiang & Yang, Chen & Wang, Ruofan & Yu, Haitao & Cao, Yibin & Liu, Jing, 2016. "Functional brain networks in Alzheimer’s disease: EEG analysis based on limited penetrable visibility graph and phase space method," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 460(C), pages 174-187.
    13. Raducha, Tomasz & Gubiec, Tomasz, 2017. "Coevolving complex networks in the model of social interactions," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 471(C), pages 427-435.
    14. Mehmet N. Aydin & N. Ziya Perdahci, 2019. "Dynamic network analysis of online interactive platform," Information Systems Frontiers, Springer, vol. 21(2), pages 229-240, April.
    15. Nasrolahzadeh, Mahda & Mohammadpoory, Zeynab & Haddadnia, Javad, 2023. "Indices from visibility graph complexity of spontaneous speech signal: An efficient nonlinear tool for Alzheimer's disease diagnosis," Chaos, Solitons & Fractals, Elsevier, vol. 174(C).

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Giorgio Jansen & Tanda Qi & Vito Latora & Grigoris D. Amoutzias & Daniela Delneri & Stephen G. Oliver & Giuseppe Nicosia, 2024. "Minimisation of metabolic networks defines a new functional class of genes," Nature Communications, Nature, vol. 15(1), pages 1-11, December.
    2. Piaopiao Chen & Agnès H. Michel & Jianzhi Zhang, 2022. "Transposon insertional mutagenesis of diverse yeast strains suggests coordinated gene essentiality polymorphisms," Nature Communications, Nature, vol. 13(1), pages 1-15, December.
    3. Zhang, Wen-Yao & Wei, Zong-Wen & Wang, Bing-Hong & Han, Xiao-Pu, 2016. "Measuring mixing patterns in complex networks by Spearman rank correlation coefficient," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 451(C), pages 440-450.
    4. Zhang, Yun & Liu, Yongguo & Li, Jieting & Zhu, Jiajing & Yang, Changhong & Yang, Wen & Wen, Chuanbiao, 2020. "WOCDA: A whale optimization based community detection algorithm," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 539(C).
    5. Rezvanian, Alireza & Meybodi, Mohammad Reza, 2015. "Sampling social networks using shortest paths," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 424(C), pages 254-268.
    6. Kong, Hanzhang & Kang, Qinma & Li, Wenquan & Liu, Chao & Kang, Yunfan & He, Hong, 2019. "A hybrid iterated carousel greedy algorithm for community detection in complex networks," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 536(C).
    7. Yuan, Quan & Liu, Binghui, 2021. "Community detection via an efficient nonconvex optimization approach based on modularity," Computational Statistics & Data Analysis, Elsevier, vol. 157(C).
    8. Yubo Peng & Bofeng Zhang & Furong Chang, 2021. "Overlapping Community Detection of Bipartite Networks Based on a Novel Community Density," Future Internet, MDPI, vol. 13(4), pages 1-21, March.
    9. Fathin Faizah Said, 2017. "Global Banking on the Financial Network Modelling: Sectorial Analysis," Computational Economics, Springer;Society for Computational Economics, vol. 49(2), pages 227-253, February.
    10. Xinyu Huang & Dongming Chen & Dongqi Wang & Tao Ren, 2020. "MINE: Identifying Top- k Vital Nodes in Complex Networks via Maximum Influential Neighbors Expansion," Mathematics, MDPI, vol. 8(9), pages 1-25, August.
    11. Fatemi, Samira & Salehi, Mostafa & Veisi, Hadi & Jalili, Mahdi, 2018. "A fuzzy logic based estimator for respondent driven sampling of complex networks," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 510(C), pages 42-51.
    12. Zhao, Shuying & Sun, Shaowei, 2023. "Identification of node centrality based on Laplacian energy of networks," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 609(C).
    13. Ms. Sheri M. Markose, 2012. "Systemic Risk from Global Financial Derivatives: A Network Analysis of Contagion and Its Mitigation with Super-Spreader Tax," IMF Working Papers 2012/282, International Monetary Fund.
    14. Zhe Li & Xinyu Huang, 2023. "Identifying Influential Spreaders Using Local Information," Mathematics, MDPI, vol. 11(6), pages 1-14, March.
    15. Jones, Dominic & Jensen, Henrik Jeldtoft & Sibani, Paolo, 2010. "Mutual information in the Tangled Nature model," Ecological Modelling, Elsevier, vol. 221(3), pages 400-404.
    16. Hisi, Andreia N.S. & Guimarães, Paulo R. & de Aguiar, Marcus A.M., 2010. "The role of predator overlap in the robustness and extinction of a four species predator–prey network," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 389(21), pages 4725-4733.
    17. Vahan Mkrtchyan & Hovhannes Sargsyan, 2018. "A tight lower bound for the hardness of clutters," Journal of Combinatorial Optimization, Springer, vol. 35(1), pages 21-25, January.
    18. Fiedor, Paweł, 2014. "Sector strength and efficiency on developed and emerging financial markets," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 413(C), pages 180-188.
    19. Wilhelm, Thomas & Hollunder, Jens, 2007. "Information theoretic description of networks," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 385(1), pages 385-396.
    20. Mahyar, Hamidreza & Hasheminezhad, Rouzbeh & Ghalebi K., Elahe & Nazemian, Ali & Grosu, Radu & Movaghar, Ali & Rabiee, Hamid R., 2018. "Compressive sensing of high betweenness centrality nodes in networks," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 497(C), pages 166-184.

    More about this item

    Keywords

    Network; Graph; Complexity;
    All these keywords.

    Statistics

    Access and download statistics

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:eee:phsmap:v:387:y:2008:i:11:p:2637-2652. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Catherine Liu (email available below). General contact details of provider: http://www.journals.elsevier.com/physica-a-statistical-mechpplications/ .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.