Projects per year
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.
Original language  English 

Article number  cnae036 
Pages (fromto)  114 
Number of pages  14 
Journal  Journal of Complex Networks 
Volume  12 
Issue number  5 
DOIs  
Publication status  Published  1 Oct 2024 
MoE publication type  A1 Journal articlerefereed 
Keywords
 complement graph
 dense network
 eigenvector centrality
 Katz centrality
 negative parameter
Fingerprint
Dive into the research topics of 'Efficient computation of Katz centrality for very dense networks via negative parameter Katz'. Together they form a unique fingerprint.Projects
 1 Finished

Noferini_Vanni_AoF_Project: Noferini Vanni Academy Project
Noferini, V. (Principal investigator), Quintana Ponce, M. (Project Member), Barbarino, G. (Project Member), Wood, R. (Project Member) & Nyman, L. (Project Member)
01/09/2020 → 31/08/2024
Project: Academy of Finland: Other research funding