IDEAS home Printed from https://ideas.repec.org/a/plo/pone00/0038159.html
   My bibliography  Save this article

Towards Information Inequalities for Generalized Graph Entropies

Author

Listed:
  • Lavanya Sivakumar
  • Matthias Dehmer

Abstract

In this article, we discuss the problem of establishing relations between information measures for network structures. Two types of entropy based measures namely, the Shannon entropy and its generalization, the Rényi entropy have been considered for this study. Our main results involve establishing formal relationships, by means of inequalities, between these two kinds of measures. Further, we also state and prove inequalities connecting the classical partition-based graph entropies and partition-independent entropy measures. In addition, several explicit inequalities are derived for special classes of graphs.

Suggested Citation

  • 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.
    • Handle: RePEc:plo:pone00:0038159
    DOI: 10.1371/journal.pone.0038159
    as

    Download full text from publisher

    File URL: https://journals.plos.org/plosone/article?id=10.1371/journal.pone.0038159
    Download Restriction: no
    File URL: https://journals.plos.org/plosone/article/file?id=10.1371/journal.pone.0038159&type=printable
    Download Restriction: no
    File URL: https://libkey.io/10.1371/journal.pone.0038159?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
    ---><---

    References listed on IDEAS

    as
    1. Matthias Dehmer & Abbe Mowshowitz & Frank Emmert-Streib, 2011. "Connections between Classical and Parametric Network Entropies," PLOS ONE, Public Library of Science, vol. 6(1), pages 1-8, January.
    2. Kim, Jongkwang & Wilhelm, Thomas, 2008. "What is a complex graph?," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 387(11), pages 2637-2652.
    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. Matthias Dehmer & Lavanya Sivakumar, 2012. "Recent Developments in Quantitative Graph Theory: Information Inequalities for Networks," PLOS ONE, Public Library of Science, vol. 7(2), pages 1-13, February.
    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. Wan, Pengfei & Tu, Jianhua & Dehmer, Matthias & Zhang, Shenggui & Emmert-Streib, Frank, 2019. "Graph entropy based on the number of spanning forests of c-cyclic graphs," Applied Mathematics and Computation, Elsevier, vol. 363(C), pages 1-1.
    2. Carlos F Alvarez & Luis E Palafox & Leocundo Aguilar & Mauricio A Sanchez & Luis G Martinez, 2016. "Using Link Disconnection Entropy Disorder to Detect Fast Moving Nodes in MANETs," PLOS ONE, Public Library of Science, vol. 11(5), pages 1-15, May.

    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. 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.
    2. 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.
    3. 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.
    4. 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.
    5. 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.
    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. da Cunha, Éverton Fernandes & da Fontoura Costa, Luciano, 2022. "On hypercomplex networks," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 591(C).
    8. Roanes-Lozano, Eugenio & Laita, Luis M. & Roanes-Macías, Eugenio & Wester, Michael J. & Ruiz-Lozano, José Luis & Roncero, Carlos, 2009. "Evolution of railway network flexibility: The Spanish broad gauge case," Mathematics and Computers in Simulation (MATCOM), Elsevier, vol. 79(8), pages 2317-2332.
    9. Ghorbani, Modjtaba & Dehmer, Matthias & Rajabi-Parsa, Mina & Emmert-Streib, Frank & Mowshowitz, Abbe, 2019. "Hosoya entropy of fullerene graphs," Applied Mathematics and Computation, Elsevier, vol. 352(C), pages 88-98.
    10. 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).
    11. 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.
    12. Kim, Jongkwang & Wilhelm, Thomas, 2008. "What is a complex graph?," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 387(11), pages 2637-2652.
    13. 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.
    14. 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.
    15. Wang, Jiqiang, 2019. "Disturbance attenuation of complex dynamical systems through interaction topology design," Applied Mathematics and Computation, Elsevier, vol. 355(C), pages 576-584.
    16. Modjtaba Ghorbani & Matthias Dehmer & Frank Emmert-Streib, 2020. "Properties of Entropy-Based Topological Measures of Fullerenes," Mathematics, MDPI, vol. 8(5), pages 1-23, May.
    17. Carlos F Alvarez & Luis E Palafox & Leocundo Aguilar & Mauricio A Sanchez & Luis G Martinez, 2016. "Using Link Disconnection Entropy Disorder to Detect Fast Moving Nodes in MANETs," PLOS ONE, Public Library of Science, vol. 11(5), pages 1-15, May.
    18. 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.
    19. 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).
    20. Ghorbani, Modjtaba & Dehmer, Matthias & Zangi, Samaneh, 2018. "Graph operations based on using distance-based graph entropies," Applied Mathematics and Computation, Elsevier, vol. 333(C), pages 547-555.

    More about this item

    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:plo:pone00:0038159. 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: plosone (email available below). General contact details of provider: https://journals.plos.org/plosone/ .

    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.