Measuring Node Contribution to Community Structure with Modularity Vitality

Abstract

Community-aware centrality is an emerging research area in network science concerned with the importance of nodes in relation to community structure. Measures are a function of a network's structure and a given partition. Previous approaches extend classical centrality measures to account for community structure with little connection to community detection theory. In contrast, we propose cluster-quality vitality measures, i.e., modularity vitality, a community-aware measure which is well-grounded in both centrality and community detection theory. Modularity vitality quantifies positive and negative contributions to community structure, which indicate a node's role as a community bridge or hub. We derive a computationally efficient method of calculating modularity vitality for all nodes in O(M + NC) time, where C is the number of communities. We systematically fragment networks by removing central nodes, and find that modularity vitality consistently outperforms existing community-aware centrality measures. Modularity vitality is over 8 times more effective than the next-best method on a million-node infrastructure network. This result does not generalize to social media communication networks, which exhibit extreme robustness to all community-aware centrality attacks. This robustness suggests that user-based interventions to mitigate misinformation diffusion will be ineffective. Finally, we demonstrate that modularity vitality provides a new approach to community-deception.

arXiv commentAccepted to IEEE Transactions on Network Science and Engineering

References in corpus (18)

• Fast unfolding of communities in large networks
• Community structure in social and biological networks
• Modularity and community structure in networks
• Finding community structure in very large networks
• From Louvain to Leiden: guaranteeing well-connected communities
• Uncovering the overlapping community structure of complex networks in nature and society
• Finding community structure in networks using the eigenvectors of matrices
• The science of fake news
• Network robustness and fragility: Percolation on random graphs
• Attack vulnerability of complex networks
• The ground truth about metadata and community detection in networks
• Hiding Individuals and Communities in a Social Network
• On community structure in complex networks: challenges and opportunities
• Centrality Measures for Networks with Community Structure
• Immunization of networks with community structure
• Centrality in Modular Networks
• Complex networks vulnerability to module-based attacks
• Weighted percolation on directed networks

Cited by in corpus (7)

• Comparative evaluation of community-aware centrality measures
• Map Equation Centrality: Community-aware Centrality based on the Map Equation
• Comparing Community-aware Centrality Measures in Online Social Networks
• Analyzing Community-aware Centrality Measures Using The Linear Threshold Model
• Identifying Influential Nodes Using Overlapping Modularity Vitality
• Mining Influential Spreaders in Complex Networks by an Effective Combination of the Degree and K-Shell
• How Correlated are Community-aware and Classical Centrality Measures in Complex Networks?