Efficient discovery of overlapping communities in massive networks
Detecting overlapping communities is essential to analyzing and exploring natural networks such as social networks, biological networks, and citation networks. However, most existing approaches do not scale to the size of networks that we regularly observe in the real world. In this paper, we develop a scalable approach to community detection that discovers overlapping communities in massive realworld networks. Our approach is based on a Bayesian model of networks that allows nodes to participate in multiple communities, and a corresponding algorithm that naturally interleaves subsampling from the network and updating an estimate of its communities. We demonstrate how we can discover the hidden community structure of several real-world networks, including 3.7 million US patents, 575,000 physics articles from the arXiv preprint server, and 875,000 connected Web pages from the Internet. Furthermore, we demonstrate on large simulated networks that our algorithm accurately discovers the true community structure. This paper opens the door to using sophisticated statistical models to analyze massive networks.
Code (1)
Tasks
ArticlesCommunity DetectionSimilar Papers 제목 키워드 기반
Overlapping Community Detection at Scale: A Nonnegative Matrix Factorization Approach
Network communities represent basic structures for understanding the organization of real-world networks. A community (also referred to as a module or a cluster) is typically thought of as a group of nodes with more conn…
Community DetectionLine Graph for Weighted Networks toward Overlapping Community Discovery
We propose generalized line graph for weighted networks toward over- lapping community discovery from the networks. Community discovery from a net- work has often been conducted by assigning each node in a network only…
Scalable Modeling of Conversational-role based Self-presentation Characteristics in Large Online Forums
Online discussion forums are complex webs of overlapping subcommunities (macrolevel structure, across threads) in which users enact different roles depending on which subcommunity they are participating in within a parti…
Topic ModelsVariational InferenceDeep Generative Models for Relational Data with Side Information
We present a probabilistic framework for overlapping community discovery and link prediction for relational data, given as a graph. The proposed framework has: (1) a deep architecture which enables us to infer multiple l…
Data AugmentationLink PredictionA testing based extraction algorithm for identifying significant communities in networks
A common and important problem arising in the study of networks is how to divide the vertices of a given network into one or more groups, called communities, in such a way that vertices of the same community are more int…
Community Detection