Clique percolation method: memory efficient almost exact communities
Automatic detection of relevant groups of nodes in large real-world graphs, i.e. community detection, has applications in many fields and has received a lot of attention in the last twenty years. The most popular method designed to find overlapping communities (where a node can belong to several communities) is perhaps the clique percolation method (CPM). This method formalizes the notion of community as a maximal union of $k$-cliques that can be reached from each other through a series of adjacent $k$-cliques, where two cliques are adjacent if and only if they overlap on $k-1$ nodes. Despite much effort CPM has not been scalable to large graphs for medium values of $k$. Recent work has shown that it is possible to efficiently list all $k$-cliques in very large real-world graphs for medium values of $k$. We build on top of this work and scale up CPM. In cases where this first algorithm faces memory limitations, we propose another algorithm, CPMZ, that provides a solution close to the exact one, using more time but less memory.
Code (1)
Tasks
Community DetectionSimilar Papers 제목 키워드 기반
LSCPM: communities in massive real-world Link Streams by Clique Percolation Method
Community detection is a popular approach to understand the organization of interactions in static networks. For that purpose, the Clique Percolation Method (CPM), which involves the percolation of k-cliques, is a well-s…
Community DetectionA Note on Community Trees in Networks
We introduce the concept of community trees that summarizes topological structures within a network. A community tree is a tree structure representing clique communities from the clique percolation method (CPM). The comm…
PercoMCV: A hybrid approach of community detection in social networks
Knowledge extraction in social networks is a needful tool as it touches every aspect of our lives such as politic, socio-economic, scientific, etc. Community detection is one of the objectives of this specific tool used …
Community DetectionAlmost Exact Recovery in Gossip Opinion Dynamics over Stochastic Block Models
We study community detection based on state observations from gossip opinion dynamics over stochastic block models (SBM). It is assumed that a network is generated from a two-community SBM where each agent has a communit…
ClusteringCommunity DetectionChordal-GCN: Exploiting sparsity in training large-scale graph convolutional networks
Despite the impressive success of graph convolutional networks (GCNs) on numerous applications, training on large-scale sparse networks remains challenging. Current algorithms require large memory space for storing GCN o…
Node Classification