Uncovering the Small Community Structure in Large Networks: A Local Spectral Approach

Abstract

Large graphs arise in a number of contexts and understanding their structure and extracting information from them is an important research area. Early algorithms on mining communities have focused on the global structure, and often run in time functional to the size of the entire graph. Nowadays, as we often explore networks with billions of vertices and find communities of size hundreds, it is crucial to shift our attention from macroscopic structure to microscopic structure when dealing with large networks. A growing body of work has been adopting local expansion methods in order to identify the community from a few exemplary seed members. In this paper, we propose a novel approach for finding overlapping communities called LEMON (Local Expansion via Minimum One Norm). Different from PageRank-like diffusion methods, LEMON finds the community by seeking a sparse vector in the span of the local spectra such that the seeds are in its support. We show that LEMON can achieve the highest detection accuracy among state-of-the-art proposals. The running time depends on the size of the community rather than that of the entire graph. The algorithm is easy to implement, and is highly parallelizable. Moreover, given that networks are not all similar in nature, a comprehensive analysis on how the local expansion approach is suited for uncovering communities in different networks is still lacking. We thoroughly evaluate our approach using both synthetic and real-world datasets across different domains, and analyze the empirical variations when applying our method to inherently different networks in practice. In addition, the heuristics on how the quality and quantity of the seed set would affect the performance are provided.

10pages, published in WWW2015 proceedings

References in corpus (6)

• Near linear time algorithm to detect community structures in large-scale networks
• Benchmark graphs for testing community detection algorithms
• Multilevel compression of random walks on networks reveals hierarchical organization in large integrated systems
• Markov random walk under constraint for discovering overlapping communities in complex networks
• Heat kernel based community detection
• Semi-supervised Eigenvectors for Large-scale Locally-biased Learning

Cited by in corpus (9)

• IEDC: An Integrated Approach for Overlapping and Non-overlapping Community Detection
• In a World That Counts: Clustering and Detecting Fake Social Engagement at Scale
• Overlapping Community Detection with Graph Neural Networks
• Overlapping Community Detection via Local Spectral Clustering
• Flow-based Algorithms for Improving Clusters: A Unifying Framework, Software, and Performance
• Improving PageRank for Local Community Detection
• Scalable and Robust Local Community Detection via Adaptive Subgraph Extraction and Diffusions
• Real-Time Community Detection in Large Social Networks on a Laptop
• The Lifecycle and Cascade of WeChat Social Messaging Groups