Efficient computation of Katz centrality for very dense networks via negative parameter Katz

Loading...
Thumbnail Image
Access rights
openAccess
Journal Title
Journal ISSN
Volume Title
A1 Alkuperäisartikkeli tieteellisessä aikakauslehdessä
Date
2024-10-01
Major/Subject
Mcode
Degree programme
Language
en
Pages
14
Series
Journal of Complex Networks, Volume 12, issue 5, pp. 1-14
Abstract
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, i.e. 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 'Katz centrality with negative parameter' 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.
Description
Publisher Copyright: © The authors 2024.
Keywords
complement graph, dense network, eigenvector centrality, Katz centrality, negative parameter
Other note
Citation
Noferini, V & Wood, R 2024, ' Efficient computation of Katz centrality for very dense networks via negative parameter Katz ', Journal of Complex Networks, vol. 12, no. 5, cnae036, pp. 1-14 . https://doi.org/10.1093/comnet/cnae036