An empirical study on classical and community-aware centrality measures in complex networks

Stephany Rajeh (1) , Marinette Savonnet (2) , Eric Leclercq (3) , Hocine Cherifi (3)

1 UB - Université de Bourgogne
2 Le2i - Laboratoire Electronique, Informatique et Image [UMR6306]
3 LIB - Laboratoire d'Informatique de Bourgogne [Dijon]

Community structure is a ubiquitous feature in natural and artificial systems. Identifying key nodes is a fundamental task to speed up or mitigate any diffusive processes in these systems. Centrality measures aim to do so by selecting a small set of critical nodes. Classical centrality measures are agnostic to community structure, while community-aware centrality measures exploit this property. Several works study the relationship between classical centrality measures, but the relationship between classical and community-aware centrality measures is almost unexplored. In this work [1], we answer two questions: (1) How do classical and community-aware centrality measures relate? (2) What is the influence of the network topology on their relationship? We perform an analysis involving a set of popular classical and community-aware centrality measures on synthetic and real-world networks. Communityaware centrality measures can be classified into two groups. The local ones are relying mainly on the intra-community links. The global ones exploit the connections bridging the communities. First, we calculate the Kendall's Tau correlation between all pair of classical and community-aware centrality measures on a set of synthetic LFR networks with controllable parameters (community structure strength (), degree distribution exponent (), and community size distribution exponent ()). Results show that the main feature driving the correlation variation between classical and community-aware centrality measures is the community structure strength. Furthermore, local community-aware centrality measures correlate with classical ones in networks with a strong community structure, while correlation is weak for global community-aware centrality measures. One observes the opposite behavior in networks with a weak community structure. Second, we calculate the Kendall's Tau correlation using a set of 50 real-world networks from various domains. We perform a linear regression analysis to assess the relationship between the networks' macroscopic and mesoscopic features and the mean correlation value. Results show that the community structure strength and transitivity are the most significant features driving the correlation between classical and community-aware centrality measures. These findings open a new perspective on designing community-aware centrality measures tailored to the network topology.

Domaines: Informatique [cs]; Réseaux sociaux et d'information [cs.SI]; Apprentissage [cs.LG]

Stephany Rajeh, Marinette Savonnet, Eric Leclercq, Hocine Cherifi. An empirical study on classical and community-aware centrality measures in complex networks. Conference on Complex Systems, Oct 2021, Lyon, France. ⟨hal-03512667⟩