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_26: We discover communities from social network data, and analyze the community evolution. These communities are inherent characteristics of human interaction in online social networks, as well as paper citation networks. Also, communities may evolve over time, due to changes to individuals' roles and social status in the network as well as changes to individuals' research interests. We present an innovative algorithm that deviates from the traditional two-step approach to analyze community evolutions. In the traditional approach, communities are first detected for each time slice, and then compared to determine correspondences. We argue that this approach is inappropriate in applications with noisy data. In this paper, we propose FacetNet for analyzing communities and their evolutions through a robust unified process. In this novel framework, communities not only generate evolutions, they also are regularized by the temporal smoothness of evolutions. As a result, this framework will discover communities that jointly maximize the fit to the observed data and the temporal evolution. Our approach relies on formulating the problem in terms of non-negative matrix factorization, where communities and their evolutions are factorized in a unified way. Then we develop an iterative algorithm, with proven low time complexity, which is guaranteed to converge to an optimal solution. We perform extensive experimental studies, on both synthetic datasets and real datasets, to demonstrate that our method discovers meaningful communities and provides additional insights not directly obtainable from traditional methods.
@cite_28: Community is an important attribute of Pocket Switched Networks (PSN), because mobile devices are carried by people who tend to belong to communities. We analysed community structure from mobility traces and used for forwarding algorithms [12], which shows significant impact of community. Here, we propose and evaluate three novel distributed community detection approaches with great potential to detect both static and temporal communities. We find that with suitable configuration of the threshold values, the distributed community detection can approximate their corresponding centralised methods up to 90 accuracy.
@cite_19: The recent boom of large-scale online social networks (OSNs) both enables and necessitates the use of parallelizable and scalable computational techniques for their analysis. We examine the problem of real-time community detection and a recently proposed linear time--- @math on a network with @math edges---label propagation, or epidemic'' community detection algorithm. We identify characteristics and drawbacks of the algorithm and extend it by incorporating different heuristics to facilitate reliable and multifunctional real-time community detection. With limited computational resources, we employ the algorithm on OSN data with @math nodes and about @math directed edges. Experiments and benchmarks reveal that the extended algorithm is not only faster but its community detection accuracy compares favorably over popular modularity-gain optimization algorithms known to suffer from their resolution limits.
@cite_13: Inspired by the increasing interest in self-organizing social opportunistic networks, we investigate the problem of distributed detection of unknown communities in dynamic random graphs. As a formal framework, we consider the dynamic version of the well-studied Planted Bisection Model dyn- G ( n , p , q ) where the node set n ] of the network is partitioned into two unknown communities and, at every time step, each possible edge ( u , v ) is active with probability p if both nodes belong to the same community, while it is active with probability q (with q ? p ) otherwise. We also consider a time-Markovian generalization of this model.We propose a distributed protocol based on the popular Label-Propagation approach and prove that, when the ratio p q is larger than n b (for an arbitrarily small constant b 0 ), the protocol finds the right "planted" partition in O ( log ? n ) time even when the snapshots of the dynamic graph are sparse and disconnected (i.e., when p = ? ( 1 n ) ).
@cite_25: Cluster detection has been widely applied to the problem of efficient data delivery in highly dynamic mobile ad hoc networks. By grouping participants who meet most often into clusters, hierarchical structures in the network are formed which can be used to efficiently transfer data between the participants. However, data delivery algorithms which rely on clusters can be inefficient in some situations. In the case of dynamic networks formed by encounters between humans, sometimes called Pocket Switched Networks (PSNs), cluster based data delivery methods may see a drop in efficiency if obsolete cluster membership persists despite changes to behavioural patterns. Our work aims to improve the relevance of clusters to particular time frames, and thus improve the performance of cluster based data delivery algorithms in PSNs. Furthermore, we will show that by detecting spatio-temporal clusters in PSNs, we can now improve on the data delivery success rates and efficiency of data delivery algorithms which do not use clustering; something which has been difficult to demonstrate in the past.
But even more than in the static case, taking into account the nature of the considered networks and the dynamics they are subject to is essential to design efficient methods @cite_26 . In this context, decentralised methods adaptation to process the dynamic case have been found to offer good performance, in terms of partition quality as well as computational efficiency, also offering the advantage to be easily implemented in parallel frameworks, as it is the case for label propagation @cite_19 @cite_13 . It is also very popular for applications in specific environments such as small decentralised mobile networks such as Pocket Switched Networks (PSN), for which community detection helps to improve network discovery and information routing @cite_28 @cite_25 .