# Local Community Detection in Dynamic Graphs Using Personalized Centrality +
## 7 Conclusions  
The problems of community detection and centrality have been well-studied in recent years. In this work, we have bridged these two fields by presenting a new method of identifying local communities using personalized centrality metrics. We extended our previous work in [1; 2; 3] by using dynamic algorithms for calculating centrality scores in order to find local communities in evolving networks. Our method uses the top \(R\) highly ranked vertices from a personalized centrality metric as the local community with respect to seed vertices of interest. Experiments on synthetic networks show that our method is able to identify blocks in artificially generated stochastic block models. We have shown that we obtain a high recall of the vertices using our method compared to the ground truth and that our method is faster than conventional local community detection methods such as greedy seed set expansion. Next, we extended our method to detect evolving communities in dynamic graphs. Using a synthetic example of a stochastic block model graph overlaid on an R-MAT background, we showed that our method successfully detects merging and splitting of communities over time. We applied our methods to real graphs and showed that our algorithm yields similar quality communities to static recomputation and is faster in both time and the number of iterations taken. Finally, we presented theory for guaranteeing the correct ordering of vertices from an approximation of a centrality vector to the exact solution. Since we are able to guarantee the highly ranked vertices as correct in an approximation, we know that the vertices returned in the local community are indeed the exact highly ranked vertices from the exact solution. The main drawback of our method is that it requires previous knowledge of the community size. Future work will investigate methods to identify the local community using personalized centrality without previous knowledge of community size. For example, we can use a sweep cut method similar to [38]. After the personalized centrality metric is calculated using our dynamic algorithm, we can sweep over all cuts induced by the ordering of the personalized centrality vector and choose the best cut determined by conductance scores of the induced cuts. This method would therefore identify the best local community given the centrality scores without any size requirement. We also could combine the termination criteria with the gap between centrality values to maintain only a limited portion of the centrality vector. Future work will also extend the theory to dynamic graphs so we are able to ensure correctness of vertices returned in evolving networks over time instead of recomputing the theoretical guarantee each time the underlying graph changes. Since local communities with respect to a seed vertex can be computed independently of other local communities with respect to different seeds, the computation of separate communities can be easily parallelized. By computing multiple local communities across an entire graph, we can partition the global graph into different communities. This can also be addressed in future work. The work depicted in this paper was partially sponsored by the Defense Advanced Research Projects Agency (DARPA) under agreement #HR0011-13-2-0001. The content, views and conclusions presented in this document do not necessarily reflect the position or the policy of DARPA or the U.S. Government, and no official endorsement should be inferred. Distribution Statement A: \"Approved for public release; distribution is unlimited.\" This work was also partially sponsored by NSF Grant ACI-1339745 (XScala). We thank Oracle for the hardware platform and reviewers for their careful attention to detail, relevant references, and useful suggestions. [PERSON] and [PERSON] constructed the experiments and wrote the majority of the paper. [PERSON] wrote pieces of the paper and edited heavily. [PERSON] provided guidance and editing. The authors declare no conflict of interest.