{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,11]],"date-time":"2024-09-11T00:26:35Z","timestamp":1726014395052},"reference-count":22,"publisher":"Oxford University Press (OUP)","issue":"5","license":[{"start":{"date-parts":[[2024,9,10]],"date-time":"2024-09-10T00:00:00Z","timestamp":1725926400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by-nc\/4.0\/"}],"funder":[{"name":"Suomen Akatemian p\u00e4\u00e4t\u00f6s","award":["331240"]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2024,9,10]]},"abstract":"Abstract<\/jats:title>\n Katz centrality (and its limiting case, eigenvector centrality) is a frequently used tool to measure the importance of a node in a network, and to rank the nodes accordingly. One reason for its popularity is that Katz centrality can be computed very efficiently when the network is sparse, ie having only O(n) edges between its n nodes. While sparsity is common in practice, in some applications one faces the opposite situation of a very dense network, where only O(n) potential edges are missing with respect to a complete graph. We explain why and how, even for very dense networks, it is possible to efficiently compute the ranking stemming from Katz centrality for unweighted graphs, possibly directed and possibly with loops, by working on the complement graph. Our approach also provides an interpretation, regardless of sparsity, of \u2018Katz centrality with negative parameter\u2019 as usual Katz centrality on the complement graph. For weighted graphs, we provide instead an approximation method that is based on removing sufficiently many edges from the network (or from its complement), and we give sufficient conditions for this approximation to provide the correct ranking. We include numerical experiments to illustrate the advantages of the proposed approach.<\/jats:p>","DOI":"10.1093\/comnet\/cnae036","type":"journal-article","created":{"date-parts":[[2024,9,10]],"date-time":"2024-09-10T12:38:24Z","timestamp":1725971904000},"source":"Crossref","is-referenced-by-count":0,"title":["Efficient computation of Katz centrality for very dense networks via negative parameter Katz"],"prefix":"10.1093","volume":"12","author":[{"ORCID":"http:\/\/orcid.org\/0000-0002-1775-041X","authenticated-orcid":false,"given":"Vanni","family":"Noferini","sequence":"first","affiliation":[{"name":"Department of Mathematics and Systems Analysis, Aalto University , P.O. Box 11100, FI-00076 Aalto, Finland"}]},{"given":"Ryan","family":"Wood","sequence":"additional","affiliation":[{"name":"Department of Mathematics and Systems Analysis, Aalto University , P.O. Box 11100, FI-00076 Aalto, Finland"}]}],"member":"286","published-online":{"date-parts":[[2024,9,10]]},"reference":[{"key":"2024091010510901200_cnae036-B1","doi-asserted-by":"crossref","first-page":"696","DOI":"10.1137\/090761070","article-title":"Network properties revealed through matrix functions","volume":"52","author":"Estrada","year":"2010","journal-title":"SIAM Rev"},{"key":"2024091010510901200_cnae036-B2","doi-asserted-by":"crossref","first-page":"124","DOI":"10.1093\/comnet\/cnt007","article-title":"Total communicability as a centrality measure","volume":"1","author":"Benzi","year":"2013","journal-title":"J. Complex Netw"},{"key":"2024091010510901200_cnae036-B3","doi-asserted-by":"crossref","DOI":"10.1093\/acprof:oso\/9780199591756.001.0001","volume-title":"The Structure of Complex Networks","author":"Estrada","year":"2011"},{"key":"2024091010510901200_cnae036-B4","doi-asserted-by":"crossref","first-page":"39","DOI":"10.1007\/BF02289026","article-title":"A new status index derived from sociometric data analysis","volume":"18","author":"Katz","year":"1953","journal-title":"Psychometrika"},{"key":"2024091010510901200_cnae036-B5","doi-asserted-by":"crossref","DOI":"10.1093\/acprof:oso\/9780199206650.001.0001","volume-title":"Networks. An Introduction","author":"Newman","year":"2010"},{"key":"2024091010510901200_cnae036-B6","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":"2024091010510901200_cnae036-B7","doi-asserted-by":"crossref","DOI":"10.1137\/1.9780898719604","volume-title":"LAPACK Users\u2019 Guide","author":"Anderson","year":"1999"},{"key":"2024091010510901200_cnae036-B8","author":"Arslan","year":"2024"},{"key":"2024091010510901200_cnae036-B9","doi-asserted-by":"crossref","first-page":"1419","DOI":"10.1126\/science.1175509","article-title":"GABAergic hub neurons orchestrate synchrony in developing hippocampal networks","volume":"326","author":"Bonifazi","year":"2009","journal-title":"Science"},{"key":"2024091010510901200_cnae036-B10","doi-asserted-by":"crossref","first-page":"12917","DOI":"10.1073\/pnas.192407699","article-title":"Food-web structure and network theory: the role of connectance and size","volume":"99","author":"Dunne","year":"2002","journal-title":"Proc. Natl. Acad. Sci. USA"},{"key":"2024091010510901200_cnae036-B11","doi-asserted-by":"crossref","first-page":"1665","DOI":"10.1038\/srep01665","article-title":"Spread of risk across financial markets: better to invest in the peripheries","volume":"3","author":"Pozzi","year":"2013","journal-title":"Sci. Rep"},{"key":"2024091010510901200_cnae036-B12","doi-asserted-by":"crossref","first-page":"1059","DOI":"10.1016\/j.neuroimage.2009.10.003","article-title":"Complex network measures of brain connectivity: uses and interpretations","volume":"52","author":"Rubinov","year":"2010","journal-title":"Neuroimage"},{"key":"2024091010510901200_cnae036-B13","doi-asserted-by":"crossref","first-page":"e20648","DOI":"10.1371\/journal.pone.0020648","article-title":"Emergence of scale-free leadership structure in social recommender systems","volume":"6","author":"Zhou","year":"2011","journal-title":"PLos One"},{"key":"2024091010510901200_cnae036-B14","doi-asserted-by":"crossref","DOI":"10.1142\/9567","volume-title":"Matrices: Algebra, Analysis and Applications","author":"Friedland","year":"2015"},{"key":"2024091010510901200_cnae036-B15","doi-asserted-by":"crossref","first-page":"199","DOI":"10.1007\/s00211-007-0061-6","article-title":"Fast matrix multiplication is stable","volume":"106","author":"Demmel","year":"2007","journal-title":"Numer. Math"},{"key":"2024091010510901200_cnae036-B16","doi-asserted-by":"crossref","first-page":"686","DOI":"10.1137\/130950550","article-title":"On the limiting behavior of parameter-dependent network centrality measures","volume":"36","author":"Benzi","year":"2015","journal-title":"SIAM J. Matrix Anal. Appl"},{"key":"2024091010510901200_cnae036-B17","doi-asserted-by":"crossref","first-page":"107","DOI":"10.1016\/S0169-7552(98)00110-X","article-title":"The anatomy of a large-scale hypertextual Web search engine","volume":"30","author":"Brin","year":"1998","journal-title":"Comput. Netw. ISDN Syst"},{"key":"2024091010510901200_cnae036-B18","doi-asserted-by":"crossref","first-page":"124","DOI":"10.1214\/aoms\/1177729893","article-title":"Adjustment of an inverse matrix corresponding to a change in one element of a given matrix","volume":"21","author":"Sherman","year":"1950","journal-title":"Ann. Math. Statist"},{"key":"2024091010510901200_cnae036-B19","doi-asserted-by":"crossref","first-page":"111","DOI":"10.1016\/j.socnet.2014.03.005","article-title":"Networks containing negative ties","volume":"38","author":"Everett","year":"2014","journal-title":"Soc. Netw"},{"key":"2024091010510901200_cnae036-B20","doi-asserted-by":"crossref","first-page":"137","DOI":"10.1007\/BF01386217","article-title":"Norms and exclusion theorems","volume":"2","author":"Bauer","year":"1960","journal-title":"Numer. Math"},{"key":"2024091010510901200_cnae036-B21","doi-asserted-by":"crossref","first-page":"397","DOI":"10.1137\/23M155219X","article-title":"Weighted enumeration of nonbacktracking walks on weighted graphs","volume":"45","author":"Arrigo","year":"2024","journal-title":"SIAM J. Matrix Anal. Appl"},{"key":"2024091010510901200_cnae036-B22","doi-asserted-by":"crossref","first-page":"81","DOI":"10.1093\/biomet\/30.1-2.81","article-title":"A new measure of rank correlation","volume":"30","author":"Kendall","year":"1938","journal-title":"Biometrika"}],"container-title":["Journal of Complex Networks"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/academic.oup.com\/comnet\/article-pdf\/12\/5\/cnae036\/59073581\/cnae036.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/academic.oup.com\/comnet\/article-pdf\/12\/5\/cnae036\/59073581\/cnae036.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,9,10]],"date-time":"2024-09-10T12:38:40Z","timestamp":1725971920000},"score":1,"resource":{"primary":{"URL":"https:\/\/academic.oup.com\/comnet\/article\/doi\/10.1093\/comnet\/cnae036\/7754427"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,9,10]]},"references-count":22,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2024,9,10]]}},"URL":"https:\/\/doi.org\/10.1093\/comnet\/cnae036","relation":{},"ISSN":["2051-1329"],"issn-type":[{"value":"2051-1329","type":"electronic"}],"subject":[],"published-other":{"date-parts":[[2024,10]]},"published":{"date-parts":[[2024,9,10]]}}}