Top

The Journal of Supercomputing

Published in:

02-08-2022

Graph entropies-graph energies indices for quantifying network structural irregularity

Authors: M. M. Emadi Kouchak, F. Safaei, M. Reshadi

Published in: The Journal of Supercomputing | Issue 2/2023

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

Abstract

Quantifying similarities/dissimilarities among different graph models and studying the irregularity (heterogeneity) of graphs in graphs and complex networks are one of the fundamental issues as well as a challenge of scientific and practical importance in many fields of science and engineering. This paper has been motivated by the necessity to establish novel and efficient entropy-based methods to quantify the structural irregularity properties of graphs, measure structural complexity, classify, and compare complex graphs and networks. In particular, we explore how criteria such as Shannon entropy, Von Newman, and generalized graph entropies, already defined for graphs, can be used to evaluate and measure irregularities in complex graphs and networks. To do so, we use some results obtained from graph spectral theory related to the construction of matrices obtained from graphs. We show how to use these irregularity indices based on graph entropies and demonstrate the usefulness and efficiency of each of these complexity measures on both synthetic networks and real-world data sets.

previous article Decision-making for the anomalies in IIoTs based on 1D convolutional neural networks and Dempster–Shafer theory (DS-1DCNN)

next article uLog: a software-based approximate logarithmic number system for computations on SIMD processors

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Barabási A-L. (2022) Network science book, Boston, MA: Center for Complex Network, Northeastern University, Available online at: http://barabasi.com/networksciencebook

Estrada E, Knight PA (2015) A first course in network theory. Oxford University Press, USAMATH

Watts DJ, Strogatz SH (1998) Collective dynamics of small-world networks. Nature 393(6684):440–442MATH

Barabási A-L, Albert R (1999) Emergence of scaling in random networks. Science 286(5439):509–512MathSciNetMATH

Harary F. (2018) Graph theory, Taylor & Francis

Bondy JA, Murty USR (1976) Graph theory with applications, vol 290. Macmillan, LondonMATH

Calderone A et al (2016) Comparing Alzheimers and Parkinsons diseases networks using graph communities structure. BMC Syst Biol 10:1–10

Carpi L et al (2012) Structural evolution of the Tropical Pacific climate network. Euro Phys J B 85:1434–6028

Dehmer M, Mowshowitz A (2011) A history of graph entropy measures. Inf Sci 181(1):57–78MathSciNetMATH

10.

Li X, Qin Z, Wei M, Gutman I, Dehmer M (2015) Novel inequalities for generalized graph entropies–Graph energies and topological indices. Appl Math Comput 259:470–479MathSciNetMATH

11.

Gutman I (2018) Topological indices and irregularity measures. J Bull 8:469–475MathSciNetMATH

12.

Erdos P, Rényi A (1960) On the evolution of random Graphs. Publ Math Inst Hung Acad Sci 5(1):17–60MathSciNetMATH

13.

Feldman D, Crutchfield J (1998) Measures of statistical complexity: Why? Phys Lett A 238:244–252MathSciNetMATH

14.

Balaban AT (1982) Highly discriminating distance-based topological index. Chem Phys Lett 89:399–404MathSciNet

15.

Estrada E (2010) Quantifying network heterogeneity. Phys Rev E 82(6):066102

16.

Li X, Shi Y (2008) A survey on the Randić index, MATCH: Comm. Math Comput Chem 59:127–156MathSciNetMATH

17.

Maier M, Luxburg U, Hein M. (2010) Influence of graph construction on graph-based clustering measures. NIPS, pp. 1–9

18.

Han L, Escolano F, Hancock ER, Wilson RC (2012) Graph characterizations from von Neumann entropy. Pattern Recogn Lett 33(15):1958–1967

19.

Estrada E, Vargas-Estrada E (2012) Distance-sum Heterogeneity in Graphs and Complex Networks. Appl Math Comput 218:10393–10405MathSciNetMATH

20.

Olfati-Saber R, Fax JA, Murray RM (2007) Consensus and cooperation in networked multi-agent systems. Proc IEEE 95(1):215–233. https://doi.org/10.1109/JPROC.2006.887293CrossRefMATH

21.

Han L (2012) Graph Generative Models from Information Theory. University of York, UK

22.

Collatz L, Sinogowitz U (1957) Spektren endlicher Grafen. Abh Math Sem Univ Hamburg 21:63–77MathSciNetMATH

23.

Cvetković D, Rowlinson P (1988) On connected graphs with maximal index. Publ Inst Math (Beograd) 44:29–34MathSciNetMATH

24.

Bell FK (1992) A note on the irregularity of a graph. Linear Algebra Appl 161:45–54MathSciNetMATH

25.

Snijders TAB (1981) The degree variance: an index of graph heterogeneity. Social Networks 3(3):163–174MathSciNet

26.

Albertson MO (1997) The irregularity of a graph. Ars Comb 46:219–225MATH

27.

Fath-Tabar GH, Gutman I, Nasiri R, (2013) Extremely irregular trees, Bulletin (Académie serbe des sciences et des arts. Classe des sciences mathématiques et naturelles. Sciences mathématiques), pp.1–8

28.

Hansen P, Mélot H. (2005) Graphs and Discovery. In S. Fajtlowicz (Eds.), DIMACS Series in Discrete Mathematics and Theoretical Computer Science, Providence, American Mathematical Society, Vol. 69, pp. 253–264

29.

Abdo H, Dimitrov D, Gutman I (2018) Graphs with maximal s irregularity. Discrete Appl Math 250:57–64MathSciNetMATH

30.

Gutman I, Togan M, Yurttas A, Cevik AS, Cangul IN (2018) Inverse problem for sigma index. MATCH Commun Math Comput Chem 79:491–508MathSciNetMATH

31.

Abdo H, Brandt S, Dimitrov D (2014) The total irregularity of a graph. Discrete Math Theory Comput Sci 16:201–206MathSciNetMATH

32.

Nikiforov V (2006) Eigenvalues and degree deviation in graphs. Linear Algebra Appl. 414:347–360MathSciNetMATH

33.

Shi L (2009) Bounds on Randic indices. Discr Appl Math 309:5238–5241MathSciNetMATH

34.

Gutman I, Furtula B, Elphick C (2014) The new/old vertex-degree-based topological indices. MATCH Commun Math Comput Chem 72:617–632MathSciNetMATH

35.

Goldberg F. (2014) Spectral radius minus average degree: a better bound, arXiv: 1407.4285v1 [math.co] 16 July

36.

Réti T, Tóth-Laufer E (2017) On the construction and comparison of graph irregularity indices. Kragujevac J Sci 39:53–75

37.

Hamzeh A, Réti T (2014) An analogue of Zagreb index inequality obtained from graph irregularity measures. MATCH Commun Math Comput Chem 72(3):669–683MathSciNetMATH

38.

Elphick C, Wocjan P (2014) New measures of graph irregularity. Electron J Graph Theory Appli 2(1):52–65MathSciNetMATH

39.

Izumino S, Mori H, Seo Y (1998) On Ozeki’s inequality. J Inequalities Appli 2:235–253MathSciNetMATH

40.

Favaron O, Mahéo M, Saclé JF (1993) Some eigenvalue properties in Graphs (conjectures of Graffiti-II. Discrete Math 111:197–220MathSciNetMATH

41.

Newman MEJ (xxxx) Random graphs as models of networks, Sante Fe Institute, Working Paper 2002–02–005.

42.

Ilić A, Stevanović D (2009) On comparing Zagreb indices. MATCH Commun Math Comput Chem 62:681–687MathSciNetMATH

43.

Ilić A, Zhou B (2012) On reformulated Zagreb indices. Discr Appl Math 160:204–209MathSciNetMATH

44.

Hao J (2011) Theorems about Zagreb indices and modified Zagreb indices. MATCH Commun Math Comput Chem 65:659–670MathSciNetMATH

45.

Zimmermann MG, Eguiluz VM, San Miguel M (2004) Coevolution of dynamical states and interactions in dynamic networks. Phys Rev E 69:065102

46.

Smith KM, Escudero J (2020) Normalised degree variance. Appl Netw Science 5(1):1–22

47.

Safaei F, Tabrizchi S, Rasanan AH, Zare M (2019) An energy-based heterogeneity measure for quantifying structural irregularity in complex networks. J Comput Sci 36:101011MathSciNet

48.

Gutman I (1978) The energy of a graph. Ber Math-Statist Sekt Forschungsz Graz 103:1–22MATH

49.

Estrada E, Benzi M (2017) What is the meaning of the graph energy after all? Discret Appl Math 230:71–77MathSciNetMATH

50.

Safaei F, Kashkooei Jahromi F, Fathi S (2019) A method for computing local contributions to graph energy based on Estrada-Benzi approach. Discrete Appl Math 260:214–226MathSciNetMATH

51.

Safaei F, Kashkooei Jahromi F, Fathi S (2021) Graphlets importance ranking in complex networks based on the spectral energy contribution. Int J Comput Math: Comput Syst Theory 6(1):21–36MathSciNet

52.

Gutman I, Zhou B (2006) Laplacian energy of a graph. Linear Algebra Appl 414(1):29–37MathSciNetMATH

53.

Gutman I et al (2008) Relation between Energy and Laplacian Energy. MATCH Commun Math Comput Chem 59:343–354MathSciNetMATH

54.

McClelland BJ (1971) Properties of the latent roots of a matrix: The estimation of π-electron energies. J Chem Phys 54:640–643

55.

Dehmer M, Li X, Shi Y (2015) Connections between generalized graph entropies and graph energy. Complexity 21(1):35–41MathSciNet

56.

Dehmer M (2008) Information processing in complex networks: graph entropy and information functionals. Appl Math Comput 201:82–94MathSciNetMATH

57.

Shannon CE, Weaver W (1949) The Mathematical Theory of Communication. University of Illinois Press, UrbanaMATH

58.

Dehmer M, Mowshowitz A (2011) Generalized graph entropies. Complexity 17:45–50MathSciNetMATH

59.

Rényi P. (1961) On measures of information and entropy. In: Proceedings of the 4th Berkeley symposium on mathematics, statistics and probability, Vol. 1, University of California Press: Berkeley, CA, pp 547–561

60.

Daròczy Z, Jarai A (1979) On the measurable solutions of functional equation arising in information theory. Acta Math Acad SciHungar 34:105–116MathSciNetMATH

61.

Faloutsos M, Faloutsos P, Faloutsos C (1999) On power-law relationships of the internet topology. Comp Comm Rev 29:251–262MATH

62.

Dorogovtsev SN, Mendes JFF, Samukhin AN (2003) Metric structure of random networks. Nucl Phys B 653:307–338MathSciNetMATH

63.

Malarz K, Karpinska J, Kardas A, Kulalowski K (xxxx) Node-node distance distribution for growing networks, arXiv:cond-mat/0309255v2.

64.

Blondell VD, Guillaume J-L, Hendrickx JM, Jungers RM (2007) Distance distribution in random graphs and application to network exploration. Phys Rev E 76:066101MathSciNet

65.

Wiener H (1947) Structural determination of paraffin boiling points. J Amer Chem Soc 69:17–20

66.

Freeman LC (1979) Centrality in networks: I Conceptual clarification. Social Networks 1:215–239

67.

Dangalchev C (2006) Residual closeness in networks. Physica A 365(2):556–564

68.

Alikhani S, Ghanbari N. (2014) On the Randic characteristic polynomial of specific graphs, In: The First Conference on Computational Group Theory, Computational Number Theory and Applications, University of Kashan, pp. 26–28, Dec. 17–19, 2014, pp. 11–15

69.

Passerini F, Severini S. (2008) The von Neumann entropy of networks. arXiv preprint arXiv:0812.2597

70.

Anand K, Bianconi G, Severini S (2011) Shannon and von Neumann entropy of random networks with heterogeneous expected degree. Phys Rev E 83(3):036109MathSciNet

71.

Safaei F, Yeganloo H, Akbar R (2020) Robustness on topology reconfiguration of complex networks: an entropic approach. Math Comput Simul 170:379–409MathSciNetMATH

72.

Ellens W, Spieksma FM, Van Mieghem P, Jamakovic A, Kooij RE (2011) Effective graph resistance. Linear Algebra Appl 435(10):2491–2506MathSciNetMATH

73.

http://www-personal.umich.edu/~mejn/netdata/ , Available online at 19 December 2021

74.

Zare M, Rezvani Z, Benasich AA (2016) Automatic classification of 6-month-old infants at familial risk for language-based learning disorder using a support vector machine. Clin Neurophysiol 127:2695–2703

75.

http://cosinproject.eu/extra/data/foodwebs/WEB.html , Available online at 19 December 2021

76.

Estrada E (2019) Degree heterogeneity of graphs and networks. I. Interpretation and the “heterogeneity paradox.” J Interdiscip Math 22(4):503–529

77.

Estrada E (2019) Degree heterogeneity of graphs and networks. II. Comparison with other indices. J Interdiscip Math 22(5):711–735

78.

Safaei F, Babaei A, Moudi M (2020) Optimally connected hybrid complex networks with Windmill Graphs Backbone. J Syst Sci Complexity 33:903–929MATH

79.

Abdo H, Dimitrov D, Gutman I (2019) Graph irregularity and its measures. Appl Math Comput 357:317–324MathSciNetMATH

Title: Graph entropies-graph energies indices for quantifying network structural irregularity
Authors: M. M. Emadi Kouchak
F. Safaei
M. Reshadi
Publication date: 02-08-2022
Publisher: Springer US
Published in: The Journal of Supercomputing / Issue 2/2023
Print ISSN: 0920-8542
Electronic ISSN: 1573-0484
DOI: https://doi.org/10.1007/s11227-022-04724-9

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft"

Springer Professional "Technik"

Springer Professional "Wirtschaft+Technik"

Other articles of this Issue 2/2023

Design of novel area-efficient coplanar reversible arithmetic and logic unit with an energy estimation in quantum-dot cellular automata

VANET authentication protocols: security analysis and a proposal

A cost and makespan aware scheduling algorithm for dynamic multi-workflow in cloud environment

Traffic-aware dynamic controller placement in SDN using NFV

uLog: a software-based approximate logarithmic number system for computations on SIMD processors

Stable parallel training of Wasserstein conditional generative adversarial neural networks

Premium Partner