Abstract Community structure is one of the most prominent features of complex networks. Community structure detection is of great importance to provide insights into the network structure and functionalities. Most proposals focus on static networks. However, finding communities in a dynamic network is even more challenging, especially when communities overlap with each other. In this article, we present an online algorithm, called OLCPM, based on clique percolation and label propagation methods. OLCPM can detect overlapping communities and works on temporal networks with a fine granularity. By locally updating the community structure, OLCPM delivers significant improvement in running time compared with previous clique percolation techniques. The experimental results on both synthetic and real-world networks illustrate the effectiveness of the method.
The work of @cite_30 falls into the category of community matching approaches, i.e., methods with a static community detection step and a matching step. Most of the earliest algorithms proposed for dynamic community detection were following a similar approach, with variations in the method used for detection in each snapshot (MOSES in @cite_7 ), Louvain in @cite_14 , etc.) and for community matching (Jaccard Coefficient in @cite_7 , Core nodes in @cite_9 , etc).
@cite_30 @cite_9 @cite_14 @cite_7
2092124750 1542535189 2131681506 2145977038
The rich set of interactions between individuals in society results in complex community structure, capturing highly connected circles of friends, families or professional cliques in a social network. Thanks to frequent changes in the activity and communication patterns of individuals, the associated social and communication network is subject to constant evolution. Our knowledge of the mechanisms governing the underlying community dynamics is limited, but is essential for a deeper understanding of the development and self-optimization of society as a whole. We have developed an algorithm based on clique percolation that allows us to investigate the time dependence of overlapping communities on a large scale, and thus uncover basic relationships characterizing community evolution. Our focus is on networks capturing the collaboration between scientists and the calls between mobile phone users. We find that large groups persist for longer if they are capable of dynamically altering their membership, suggesting that an ability to change the group composition results in better adaptability. The behaviour of small groups displays the opposite tendency-the condition for stability is that their composition remains unchanged. We also show that knowledge of the time commitment of members to a given community can be used for estimating the community's lifetime. These findings offer insight into the fundamental differences between the dynamics of small groups and large institutions. Social network analysis has been a hot topic in the field of graph mining. After people have achieved the goal of detecting communities from various networks, now they are interested in how these explored communities change as time passes by. In other words, people focus on the problem of community evolution and further discover those dynamic characteristics of kinds of networks. Here, we propose CommTracker, a novel and parameter-free algorithm of tracking community evolution, which utilizes the representative quality of core nodes in a community to establish the evolving relationship between two communities in consecutive time snapshots. With such a distinct strategy, it is suitable for analyzing large scale datasets. Depending on relationships established from CommTracker, it is feasible to identify communitysplitand mergence. In addition, one relationship amongst evolution traces, evolutiontracesintersection, is also studied. At last, we demonstrate the correctness and effectiveness of our algorithm on 4 real datasets. We propose a simple method to extract the community structure of large networks. Our method is a heuristic method that is based on modularity optimization. It is shown to outperform all other known community detection methods in terms of computation time. Moreover, the quality of the communities detected is very good, as measured by the so-called modularity. This is shown first by identifying language communities in a Belgian mobile phone network of 2 million customers and by analysing a web graph of 118 million nodes and more than one billion links. The accuracy of our algorithm is also verified on ad hoc modular networks. Real-world social networks from a variety of domains can naturally be modelled as dynamic graphs. However, approaches to detecting communities have largely focused on identifying communities in static graphs. Recently, researchers have begun to consider the problem of tracking the evolution of groups of users in dynamic scenarios. Here we describe a model for tracking the progress of communities over time in a dynamic network, where each community is characterised by a series of significant evolutionary events. This model is used to motivate a community-matching strategy for efficiently identifying and tracking dynamic communities. Evaluations on synthetic graphs containing embedded events demonstrate that this strategy can successfully track communities over time in volatile networks. In addition, we describe experiments exploring the dynamic communities detected in a real mobile operator network containing millions of users.