Detecting Important Nodes to Community Structure Using the Spectrum of the Graph

Abstract

Many complex systems can be represented as networks, and how a network breaks up into subnetworks or communities is of wide interest. However, the development of a method to detect nodes important to communities that is both fast and accurate is a very challenging and open problem. In this manuscript, we introduce a new approach to characterize the node importance to communities. First, a centrality metric is proposed to measure the importance of network nodes to community structure using the spectrum of the adjacency matrix. We define the node importance to communities as the relative change in the eigenvalues of the network adjacency matrix upon their removal. Second, we also propose an index to distinguish two kinds of important nodes in communities, i.e., "community core" and "bridge". Our indices are only relied on the spectrum of the graph matrix. They are applied in many artificial networks as well as many real-world networks. This new methodology gives us a basic approach to solve this challenging problem and provides a realistic result.

10 pages,7 gigures

References in corpus (10)

• Modularity and community structure in networks
• Community detection in graphs
• Finding community structure in networks using the eigenvectors of matrices
• Cooperative Game Theory Approaches for Network Partitioning
• Benchmark graphs for testing community detection algorithms
• Robustness of community structure in networks
• Community landscapes: an integrative approach to determine overlapping network module hierarchy, identify key nodes and predict network dynamics
• Characterizing the community structure of complex networks
• Statistical significance of communities in networks
• How to Measure Significance of Community Structure in Complex Networks

Cited by in corpus (9)

• Structure and dynamics of core-periphery networks
• Centrality Measures for Networks with Community Structure
• Growing networks of overlapping communities with internal structure
• Multiple structural transitions in interacting networks
• Generating Post-hoc Explanations for Skip-gram-based Node Embeddings by Identifying Important Nodes with Bridgeness
• Structural importance and evolution: an application to financial transaction networks
• Exact and Approximate Algorithms for Computing Betweenness Centrality in Directed Graphs
• Novel Adaptive Algorithms for Estimating Betweenness, Coverage and k-path Centralities
• Metropolis-Hastings Algorithms for Estimating Betweenness Centrality in Large Networks