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-studied technique that offers several advantages. Besides, studying interactions that occur over time is useful in various contexts, which can be modeled by the link stream formalism. The Dynamic Clique Percolation Method (DCPM) has been proposed for extending CPM to temporal networks. However, existing implementations are unable to handle massive datasets. We present a novel algorithm that adapts CPM to link streams, which has the advantage that it allows us to speed up the computation time with respect to the existing DCPM method. We evaluate it experimentally on real datasets and show that it scales to massive link streams. For example, it allows to obtain a complete set of communities in under twenty-five minutes for a dataset with thirty million links, what the state of the art fails to achieve even after a week of computation. We further show that our method provides communities similar to DCPM, but slightly more aggregated. We exhibit the relevance of the obtained communities in real world cases, and show that they provide information on the importance of vertices in the link streams.
Code (1)
Tasks
Community DetectionMethods 이 논문이 사용한 방법론
Similar Papers 제목 키워드 기반
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…
ArticlesCommunity DetectionDetecting Communities in Heterogeneous Multi-Relational Networks:A Message Passing based Approach
Community is a common characteristic of networks including social networks, biological networks, computer and information networks, to name a few. Community detection is a basic step for exploring and analysing these net…
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…
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 DetectionNonparametric Link Prediction in Dynamic Networks
We propose a non-parametric link prediction algorithm for a sequence of graph snapshots over time. The model predicts links based on the features of its endpoints, as well as those of the local neighborhood around the en…
Link PredictionPrediction