Map Equation Centrality: Community-aware Centrality based on the Map Equation

Abstract

To measure node importance, network scientists employ centrality scores that typically take a microscopic or macroscopic perspective, relying on node features or global network structure. However, traditional centrality measures such as degree centrality, betweenness centrality, or PageRank neglect the community structure found in real-world networks. To study node importance based on network flows from a mesoscopic perspective, we analytically derive a community-aware information-theoretic centrality score based on network flow and the coding principles behind the map equation: map equation centrality. Map equation centrality measures how much further we can compress the network's modular description by not coding for random walker transitions to the respective node, using an adapted coding scheme and determining node importance from a network flow-based point of view. The information-theoretic centrality measure can be determined from a node's local network context alone because changes to the coding scheme only affect other nodes in the same module. Map equation centrality is agnostic to the chosen network flow model and allows researchers to select the model that best reflects the dynamics of the process under study. Applied to synthetic networks, we highlight how our approach enables a more fine-grained differentiation between nodes than node-local or network-global measures. Predicting influential nodes for two different dynamical processes on real-world networks with traditional and other community-aware centrality measures, we find that activating nodes based on map equation centrality scores tends to create the largest cascades in a linear threshold model.

References in corpus (21)

• Fast unfolding of communities in large networks
• Finding and evaluating community structure in networks
• Community detection in graphs
• Maps of random walks on complex networks reveal community structure
• Identification of influential spreaders in complex networks
• Benchmark graphs for testing community detection algorithms
• Identifying modular flows on multilayer networks reveals highly overlapping organization in social systems
• On community structure in complex networks: challenges and opportunities
• Directed network modules
• Global efficiency of local immunization on complex networks
• Mapping higher-order network flows in memory and multilayer networks with Infomap
• Ranking and clustering of nodes in networks with smart teleportation
• Immunization of networks with community structure
• Centrality in Modular Networks
• Measuring Node Contribution to Community Structure with Modularity Vitality
• Cover time for random walks on arbitrary complex networks
• Trust transitivity in social networks
• Predicting the epidemic threshold of the susceptible-infected-recovered model
• Comparing Community-aware Centrality Measures in Online Social Networks
• Identifying Influential Nodes Using Overlapping Modularity Vitality
• Analyzing Community-aware Centrality Measures Using The Linear Threshold Model

Cited by in corpus (2)

• Community Detection with the Map Equation and Infomap: Theory and Applications
• Influence Prediction in Collaboration Networks: An Empirical Study on arXiv