{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,24]],"date-time":"2025-03-24T08:08:08Z","timestamp":1742803688794,"version":"3.37.3"},"reference-count":56,"publisher":"MDPI AG","issue":"12","license":[{"start":{"date-parts":[[2018,11,30]],"date-time":"2018-11-30T00:00:00Z","timestamp":1543536000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/501100004281","name":"Narodowe Centrum Nauki","doi-asserted-by":"publisher","award":["DEC-2016\/23\/B\/ST6\/03962"],"id":[{"id":"10.13039\/501100004281","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Entropy"],"abstract":"Graph energy is the energy of the matrix representation of the graph, where the energy of a matrix is the sum of singular values of the matrix. Depending on the definition of a matrix, one can contemplate graph energy, Randi\u0107 energy, Laplacian energy, distance energy, and many others. Although theoretical properties of various graph energies have been investigated in the past in the areas of mathematics, chemistry, physics, or graph theory, these explorations have been limited to relatively small graphs representing chemical compounds or theoretical graph classes with strictly defined properties. In this paper we investigate the usefulness of the concept of graph energy in the context of large, complex networks. We show that when graph energies are applied to local egocentric networks, the values of these energies correlate strongly with vertex centrality measures. In particular, for some generative network models graph energies tend to correlate strongly with the betweenness and the eigencentrality of vertices. As the exact computation of these centrality measures is expensive and requires global processing of a network, our research opens the possibility of devising efficient algorithms for the estimation of these centrality measures based only on local information.<\/jats:p>","DOI":"10.3390\/e20120916","type":"journal-article","created":{"date-parts":[[2018,11,30]],"date-time":"2018-11-30T17:13:17Z","timestamp":1543597997000},"page":"916","source":"Crossref","is-referenced-by-count":9,"title":["Graph Energies of Egocentric Networks and Their Correlation with Vertex Centrality Measures"],"prefix":"10.3390","volume":"20","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-2905-9538","authenticated-orcid":false,"given":"Miko\u0142aj","family":"Morzy","sequence":"first","affiliation":[{"name":"Institute of Computer Science, Pozna\u0144 University of Technology, 60-965 Pozna\u0144, Poland"},{"name":"Center for Artificial Intelligence and Machine Learning CAMIL, Poznan University of Technology, 60-965 Pozna\u0144, Poland"}]},{"given":"Tomasz","family":"Kajdanowicz","sequence":"additional","affiliation":[{"name":"Department of Computational Intelligence, Wroc\u0142aw University of Science and Technology, 50-370 Wroc\u0142aw, Poland"}]}],"member":"1968","published-online":{"date-parts":[[2018,11,30]]},"reference":[{"unstructured":"Biggs, N., Biggs, N.L., and Biggs, E.N. (1993). Algebraic Graph Theory, Cambridge University Press.","key":"ref_1"},{"unstructured":"Cvetkovi\u0107, D.M., Doob, M., and Sachs, H. (1980). Spectra of Graphs: Theory and Application, Academic Press.","key":"ref_2"},{"unstructured":"Kier, L. (2012). Molecular Connectivity in Chemistry and Drug Research, Elsevier.","key":"ref_3"},{"key":"ref_4","doi-asserted-by":"crossref","first-page":"509","DOI":"10.1126\/science.286.5439.509","article-title":"Emergence of scaling in random networks","volume":"286","author":"Albert","year":"1999","journal-title":"Science"},{"doi-asserted-by":"crossref","unstructured":"Li, X., Shi, Y., and Gutman, I. (2012). Graph Energy, Springer.","key":"ref_5","DOI":"10.1007\/978-1-4614-4220-2"},{"unstructured":"Bernstein, D.S. (2005). Matrix Mathematics: Theory, Facts, and Formulas with Application to Linear Systems Theory, Princeton University Press.","key":"ref_6"},{"doi-asserted-by":"crossref","unstructured":"Van Mieghem, P. (2010). Graph Spectra for Complex Networks, Cambridge University Press.","key":"ref_7","DOI":"10.1017\/CBO9780511921681"},{"doi-asserted-by":"crossref","unstructured":"Cvetkovic, D., Simic, S., and Rowlinson, P. (2009). An Introduction to the Theory of Graph Spectra, Cambridge University Press.","key":"ref_8","DOI":"10.1017\/CBO9780511801518"},{"doi-asserted-by":"crossref","unstructured":"Godsil, C., and Royle, G. (2001). Algebraic Graph Theory, Springer.","key":"ref_9","DOI":"10.1007\/978-1-4613-0163-9"},{"doi-asserted-by":"crossref","unstructured":"Gutman, I. (2001). The energy of a graph: Old and new results. Algebraic Combinatorics and Applications, Springer.","key":"ref_10","DOI":"10.1007\/978-3-642-59448-9_13"},{"key":"ref_11","doi-asserted-by":"crossref","first-page":"1472","DOI":"10.1016\/j.jmaa.2006.03.072","article-title":"The energy of graphs and matrices","volume":"326","author":"Nikiforov","year":"2007","journal-title":"J. Math. Anal. Appl."},{"key":"ref_12","first-page":"3","article-title":"New Spectral Indices for Molecule Description","volume":"60","author":"Consonni","year":"2008","journal-title":"MATCH Commun. Math. Comput. Chem."},{"key":"ref_13","doi-asserted-by":"crossref","first-page":"82","DOI":"10.1016\/j.laa.2016.05.011","article-title":"Beyond graph energy: Norms of graphs and matrices","volume":"506","author":"Nikiforov","year":"2016","journal-title":"Linear Algebra Its Appl."},{"key":"ref_14","doi-asserted-by":"crossref","first-page":"6609","DOI":"10.1021\/ja00856a001","article-title":"On Characterization of Molecular Branching","volume":"97","year":"1975","journal-title":"J. Am. Chem. Soc."},{"key":"ref_15","doi-asserted-by":"crossref","first-page":"29","DOI":"10.1016\/j.laa.2005.09.008","article-title":"Laplacian energy of a graph","volume":"414","author":"Gutman","year":"2006","journal-title":"Linear Algebra Its Appl."},{"key":"ref_16","doi-asserted-by":"crossref","first-page":"19","DOI":"10.1080\/03081089508818377","article-title":"A Survey of Graph Laplacians","volume":"39","author":"Merris","year":"1995","journal-title":"Linear Multilinear Algebra"},{"key":"ref_17","doi-asserted-by":"crossref","first-page":"1223","DOI":"10.1016\/j.laa.2009.04.019","article-title":"On incidence energy of a graph","volume":"431","author":"Gutman","year":"2009","journal-title":"Linear Algebra Its Appl."},{"key":"ref_18","doi-asserted-by":"crossref","first-page":"815","DOI":"10.1021\/ci00027a004","article-title":"Heats of Formation of Polyhex Polycyclic Aromatic Hydrocarbons from Their Adjacency Matrixes","volume":"35","author":"Cash","year":"1995","journal-title":"J. Chem. Inf. Comput. Sci."},{"key":"ref_19","first-page":"461","article-title":"On Distance Energy of Graphs","volume":"60","author":"Indulal","year":"2008","journal-title":"MATCH Commun. Math. Comput. Chem."},{"key":"ref_20","doi-asserted-by":"crossref","first-page":"175","DOI":"10.1007\/BF02018473","article-title":"On the eigenvalues of trees","volume":"3","year":"1973","journal-title":"Periodica Math. Hung."},{"key":"ref_21","doi-asserted-by":"crossref","first-page":"517","DOI":"10.1021\/ci00004a014","article-title":"Topological indices and real number vertex invariants based on graph eigenvalues or eigenvectors","volume":"31","author":"Balaban","year":"1991","journal-title":"J. Chem. Inf. Comput. Sci."},{"key":"ref_22","doi-asserted-by":"crossref","first-page":"153","DOI":"10.1021\/ci00011a023","article-title":"A novel definition of the Wiener index for trees","volume":"33","author":"Mohar","year":"1993","journal-title":"J. Chem. Inf. Comput. Sci."},{"key":"ref_23","doi-asserted-by":"crossref","first-page":"056103","DOI":"10.1103\/PhysRevE.71.056103","article-title":"Subgraph centrality in complex networks","volume":"71","author":"Estrada","year":"2005","journal-title":"Phys. Rev. E"},{"key":"ref_24","doi-asserted-by":"crossref","first-page":"247","DOI":"10.1016\/j.cplett.2007.03.098","article-title":"Statistical-mechanical approach to subgraph centrality in complex networks","volume":"439","author":"Estrada","year":"2007","journal-title":"Chem. Phys. Lett."},{"unstructured":"Chung, F.R., and Graham, F.C. (1997). Spectral Graph Theory, American Mathematical Society.","key":"ref_25"},{"doi-asserted-by":"crossref","unstructured":"Spielman, D.A. (2007, January 21\u201323). Spectral graph theory and its applications. Proceedings of the 48th Annual IEEE Symposium on Foundations of Computer Science (FOCS\u201907), Providence, RI, USA.","key":"ref_26","DOI":"10.1109\/FOCS.2007.56"},{"key":"ref_27","doi-asserted-by":"crossref","first-page":"2053","DOI":"10.1109\/TIT.2010.2044061","article-title":"The power of convex relaxation: Near-optimal matrix completion","volume":"56","author":"Tao","year":"2010","journal-title":"IEEE Trans. Inf. Theory"},{"key":"ref_28","doi-asserted-by":"crossref","first-page":"717","DOI":"10.1007\/s10208-009-9045-5","article-title":"Exact matrix completion via convex optimization","volume":"9","author":"Recht","year":"2009","journal-title":"Found. Comput. Math."},{"key":"ref_29","doi-asserted-by":"crossref","first-page":"219","DOI":"10.1287\/mnsc.17.3.219","article-title":"An r-dimensional quadratic placement algorithm","volume":"17","author":"Hall","year":"1970","journal-title":"Manag. Sci."},{"key":"ref_30","doi-asserted-by":"crossref","first-page":"298","DOI":"10.21136\/CMJ.1973.101168","article-title":"Algebraic connectivity of graphs","volume":"23","author":"Fiedler","year":"1973","journal-title":"Czechoslov. Math. J."},{"unstructured":"Donath, W., and Hoffman, A. (1972). Algorithms for Partitioning of Graphs and Computer Logic Based on Eigenvectors of Connections Matrices, IBM Technical Disclosure Bulletin.","key":"ref_31"},{"key":"ref_32","first-page":"1","article-title":"Random walks on graphs: A survey","volume":"2","year":"1993","journal-title":"Comb. Paul Erdos Is Eighty"},{"key":"ref_33","doi-asserted-by":"crossref","first-page":"330","DOI":"10.1112\/jlms\/s1-42.1.330","article-title":"The eigenvalues of a graph and its chromatic number","volume":"1","author":"Wilf","year":"1967","journal-title":"J. Lond. Math. Soc."},{"key":"ref_34","doi-asserted-by":"crossref","first-page":"1769","DOI":"10.1137\/090773714","article-title":"Max cut and the smallest eigenvalue","volume":"41","author":"Trevisan","year":"2012","journal-title":"SIAM J. Comput."},{"unstructured":"Sinha, K. (2014). Structural Complexity and Its Implications for Design of Cyber-Physical Systems. [Ph.D. Thesis, Massachusetts Institute of Technology].","key":"ref_35"},{"key":"ref_36","first-page":"127","article-title":"A survey on the Randic index","volume":"59","author":"Li","year":"2008","journal-title":"MATCH Commun. Math. Comput. Chem."},{"key":"ref_37","doi-asserted-by":"crossref","first-page":"301","DOI":"10.1007\/s10910-005-9020-6","article-title":"On the Randi\u0107 index","volume":"44","author":"Liu","year":"2008","journal-title":"J. Math. Chem."},{"key":"ref_38","doi-asserted-by":"crossref","first-page":"50","DOI":"10.1016\/j.laa.2013.06.010","article-title":"On Randi\u0107 energy","volume":"442","author":"Gutman","year":"2014","journal-title":"Linear Algebra Its Appl."},{"key":"ref_39","first-page":"88","article-title":"Randi\u0107 energy and Randi\u0107 Estrada index of a graph","volume":"5","author":"Bozkurt","year":"2012","journal-title":"Eur. J. Pure Appl. Math."},{"key":"ref_40","first-page":"223","article-title":"On the general Randic index for certain families of trees","volume":"54","author":"Clark","year":"2000","journal-title":"Ars Comb."},{"key":"ref_41","doi-asserted-by":"crossref","first-page":"2239","DOI":"10.1016\/j.laa.2008.06.023","article-title":"On sum of powers of the Laplacian eigenvalues of graphs","volume":"429","author":"Zhou","year":"2008","journal-title":"Linear Algebra Its Appl."},{"key":"ref_42","first-page":"395","article-title":"More on the relation between energy and Laplacian energy of graphs","volume":"61","author":"Stevanovic","year":"2009","journal-title":"MATCH Commun. Math. Comput. Chem."},{"key":"ref_43","first-page":"435","article-title":"Upper bounds for Laplacian energy of graphs","volume":"60","author":"Aleksic","year":"2008","journal-title":"MATCH Commun. Math. Comput. Chem."},{"key":"ref_44","first-page":"219","article-title":"Some lower bounds for Laplacian energy of graphs","volume":"4","author":"Li","year":"2009","journal-title":"Int. J. Contemp. Math. Sci."},{"doi-asserted-by":"crossref","unstructured":"Newman, M. (2018). Networks, Oxford University Press.","key":"ref_45","DOI":"10.1093\/oso\/9780198805090.001.0001"},{"doi-asserted-by":"crossref","unstructured":"Wasserman, S., and Faust, K. (1994). Social Network Analysis: Methods and Applications, Cambridge University Press.","key":"ref_46","DOI":"10.1017\/CBO9780511815478"},{"key":"ref_47","doi-asserted-by":"crossref","first-page":"39","DOI":"10.1007\/BF02289026","article-title":"A new status index derived from sociometric analysis","volume":"18","author":"Katz","year":"1953","journal-title":"Psychometrika"},{"key":"ref_48","doi-asserted-by":"crossref","first-page":"1170","DOI":"10.1086\/228631","article-title":"Power and centrality: A family of measures","volume":"92","author":"Bonacich","year":"1987","journal-title":"Am. J. Sociol."},{"key":"ref_49","doi-asserted-by":"crossref","first-page":"57","DOI":"10.1016\/0378-8733(94)00248-9","article-title":"Eccentricity and centrality in networks","volume":"17","author":"Hage","year":"1995","journal-title":"Soc. Netw."},{"key":"ref_50","doi-asserted-by":"crossref","first-page":"661","DOI":"10.1137\/070710111","article-title":"Power-law distributions in empirical data","volume":"51","author":"Clauset","year":"2009","journal-title":"SIAM Rev."},{"key":"ref_51","doi-asserted-by":"crossref","first-page":"026107","DOI":"10.1103\/PhysRevE.76.026107","article-title":"Clustering in complex directed networks","volume":"76","author":"Fagiolo","year":"2007","journal-title":"Phys. Rev. E"},{"key":"ref_52","first-page":"17","article-title":"On the evolution of random graphs","volume":"5","year":"1960","journal-title":"Publ. Math. Inst. Hung. Acad. Sci."},{"key":"ref_53","doi-asserted-by":"crossref","first-page":"440","DOI":"10.1038\/30918","article-title":"Collective dynamics of \u2018small-world\u2019 networks","volume":"393","author":"Watts","year":"1998","journal-title":"Nature"},{"key":"ref_54","first-page":"292","article-title":"A general theory of bibliometric and other cumulative advantage processes","volume":"27","author":"Price","year":"1976","journal-title":"J. Assoc. Inf. Sci. Technol."},{"key":"ref_55","doi-asserted-by":"crossref","first-page":"026107","DOI":"10.1103\/PhysRevE.65.026107","article-title":"Growing scale-free networks with tunable clustering","volume":"65","author":"Holme","year":"2002","journal-title":"Phys. Rev. E"},{"key":"ref_56","doi-asserted-by":"crossref","first-page":"1617","DOI":"10.1109\/49.12889","article-title":"Routing of multipoint connections","volume":"6","author":"Waxman","year":"1988","journal-title":"IEEE J. Sel. Areas Commun."}],"container-title":["Entropy"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1099-4300\/20\/12\/916\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,6,14]],"date-time":"2024-06-14T02:17:09Z","timestamp":1718331429000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1099-4300\/20\/12\/916"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,11,30]]},"references-count":56,"journal-issue":{"issue":"12","published-online":{"date-parts":[[2018,12]]}},"alternative-id":["e20120916"],"URL":"https:\/\/doi.org\/10.3390\/e20120916","relation":{},"ISSN":["1099-4300"],"issn-type":[{"type":"electronic","value":"1099-4300"}],"subject":[],"published":{"date-parts":[[2018,11,30]]}}}