Finding communities in evolving networks is a difficult task and raises issues different from the classic static detection case. We introduce an approach based on the recent vertex-centred paradigm. The proposed algorithm, named DynLOCNeSs, detects communities by scanning and evaluating each vertex neighbourhood, which can be done independently in a parallel way. It is done by means of a preference measure, using these preferences to handle community changes. We also introduce a new vertex neighbourhood preference measure, CWCN, more efficient than current existing ones in the considered context. Experimental results show the relevance of this measure and the ability of the proposed approach to detect classical community evolution patterns such as grow-shrink and merge-split.
@cite_24: A variety of massive datasets, such as social networks and biological data, are represented as graphs that reveal underlying connections, trends, and anomalies. Community detection is the task of discovering dense groups of vertices in a graph. Its one specific form is seed set expansion, which finds the best local community for a given set of seed vertices. Greedy, agglomerative algorithms, which are commonly used in seed set expansion, have been previously designed only for a static, unchanging graph. However, in many applications, new data is constantly produced, and vertices and edges are inserted and removed from a graph. We present an algorithm for dynamic seed set expansion, which incrementally updates the community as the underlying graph changes. We show that our dynamic algorithm outputs high quality communities that are similar to those found when using a standard static algorithm. The dynamic approach also improves performance compared to re-computation, achieving speedups of up to 600x.
@cite_5: Evolutionary community discovery is a hot research topic which clusters the dynamic or temporal network. The communities detected in dynamic network should get reasonable partition for the current data while simultaneously not deviate drastically from the previous ones. In this paper, the evolutionary community discovery algorithm based on leader nodes (EvoLeaders) is proposed to cluster the dynamic network. Compared with the static community discovery algorithm based on leader nodes (the Top Leaders algorithm), experimental results over two real-world datasets demonstrate that the EvoLeaders is more suitable for dynamic scenarios.
@cite_10: Multiplex network is an emergent model that has been lately proposed in order to cope with the complexity of real-world networks. A multiplex network is defined as a multi-layer interconnected graph. Each layer contains the same set of nodes but interconnected by different types of links. This rich representation model requires to redefine most of the existing network analysis algorithms. In this paper we focus on the central problem of community detection. Most of existing approaches consist on transforming the problem, in a way or another, to the classical setting of community detection in a monoplex network. In this work, we propose a new approach that consists on adapting a seed-centric algorithm to the multiplex case. The first experiments on heterogeneous bibliographical networks show the relevance of the approach compared to the existing algorithms.
@cite_11: Complex networks can often be divided in dense sub-networks called communities. Using a partition edit distance, we study how three community detection algorithms transform their outputs if the input network is slightly modified. The instabilities appear to be important and we propose a modification of one algorithm to stabilize it and to allow the tracking of the communities in an evolving network. This modification has one parameter which is a tradeoff between stability and quality. The resulting algorithm appears to be very effective. We finally use it on an evolving network of blogs.
The major drawback with these algorithms is that they loose one of the initial benefits of the leader-based approach, i.e. lightness and flexibility. Built on top of Top-Leaders, Evo-Leaders @cite_5 adds a costly split-merge of community at each time step. mux-LICOD @cite_10 uses degree centrality and shortest path calculation to compare leaders and followers. Shortest path computation can be costly if used for each vertex to each potential leader. It also relies on an aggregation phase repeated until stabilisation, though experiments do not reveal whether the stabilisation is fast or not. Finally, 's method @cite_24 relies on a fitness function and a set of ad-hoc update rules and pruning over updates. It is hard to know however how efficient this policy is, as the experiments proposed by the authors are limited to a comparison with re-computation of the static counterpart. While faster than static re-computation (which is generally expected for specifically dynamic-addressed algorithms), the proposed @math -score comparison with the set of static re-computed instances is not meaningful, as static re-computation has been proved to give unstable results @cite_11 .