In this paper, we propose ( DyPerm ), the first dynamic community detection method which optimizes a novel community scoring metric, called permanence. ( DyPerm ) incrementally modifies the community structure by updating those communities where the editing of nodes and edges has been performed, keeping the rest of the network unchanged. We present strong theoretical guarantees to show how why mere updates on the existing community structure lead to permanence maximization in dynamic networks, which in turn decreases the computational complexity drastically. Experiments on both synthetic and six real-world networks with given ground-truth community structure show that ( DyPerm ) achieves (on average) 35 gain in accuracy (based on NMI) compared to the best method among four baseline methods. ( DyPerm ) also turns out to be 15 times faster than its static counterpart.
Our proposed method is an incremental clustering method. It differs from the earlier methods in terms of at least two aspects: (i) is the first dynamic community detection method which optimizes permanence'' @cite_8 , a novel metric that has been shown to be very effective compared to other state-of-the-art optimization functions (such as modularity, conductance etc.) for static communities @cite_8 @cite_18 ; (ii) permanence, being a local vertex-centric metric (as opposed to the global metrics such as modularity), enables to inspect only a small portion of the network (which has recently been changed), thus leading to obtain accurate communities with minimum changes @cite_1 .
@cite_18 @cite_1 @cite_8
2963455014 1968656203
Detecting and analyzing dense groups or communities from social and information networks has attracted immense attention over the last decade due to its enormous applicability in different domains. Community detection is an ill-defined problem, as the nature of the communities is not known in advance. The problem has turned even more complicated due to the fact that communities emerge in the network in various forms such as disjoint, overlapping, and hierarchical. Various heuristics have been proposed to address these challenges, depending on the application in hand. All these heuristics have been materialized in the form of new metrics, which in most cases are used as optimization functions for detecting the community structure, or provide an indication of the goodness of detected communities during evaluation. Over the last decade, a large number of such metrics have been proposed. Thus, there arises a need for an organized and detailed survey of the metrics proposed for community detection and evaluation. Here, we present a survey of the start-of-the-art metrics used for the detection and the evaluation of community structure. We also conduct experiments on synthetic and real networks to present a comparative analysis of these metrics in measuring the goodness of the underlying community structure. Despite the prevalence of community detection algorithms, relatively less work has been done on understanding whether a network is indeed modular and how resilient the community structure is under perturbations. To address this issue, we propose a new vertex-based metric called "permanence", that can quantitatively give an estimate of the community- like structure of the network. The central idea of permanence is based on the observation that the strength of membership of a vertex to a community depends upon the following two factors: (i) the distribution of external connectivity of the vertex to individual communities and not the total external connectivity, and (ii) the strength of its internal connectivity and not just the total internal edges. In this paper, we demonstrate that compared to other metrics, permanence provides (i) a more accurate estimate of a derived community structure to the ground-truth community and (ii) is more sensitive to perturbations in the network. As a by-product of this study, we have also developed a community detection algorithm based on maximizing permanence. For a modular network structure, the results of our algorithm match well with ground-truth communities.