Comprehensive spectral approach for community structure analysis on complex networks

Abstract

A simple but efficient spectral approach for analyzing the community structure of complex networks is introduced. It works the same way for all types of networks, by spectrally splitting the adjacency matrix into a "unipartite" and a "multipartite" component. These two matrices reveal the structure of the network from different perspectives and can be analyzed at different levels of detail. Their entries, or the entries of their lower-rank approximations, provide measures of the affinity or antagonism between the nodes that highlight the communities and the "gateway" links that connect them together. An algorithm is then proposed to achieve the automatic assignment of the nodes to communities based on the information provided by either matrix. This algorithm naturally generates overlapping communities but can also be tuned to eliminate the overlaps.

11 pages, 10 figures, final version

References in corpus (14)

• Modularity and community structure in networks
• Finding community structure in networks using the eigenvectors of matrices
• Cooperative Game Theory Approaches for Network Partitioning
• Near linear time algorithm to detect community structures in large-scale networks
• Benchmark graphs for testing community detection algorithms
• Resolution limit in community detection
• Community structure in directed networks
• Community Structure in Jazz
• Modularity and community detection in bipartite networks
• Analysis of the structure of complex networks at different resolution levels
• Phase transition in the detection of modules in sparse networks
• Graph spectra and the detectability of community structure in networks
• Fast and accurate determination of modularity and its effect size
• A paradox in community detection