# Local Community Detection in Dynamic Graphs Using Personalized Centrality +
## 3 Related Work  
### Community Detection  
Most of the literature in the field of community detection focuses on finding global communities in a static, unchanging graph. Popular methods include greedy agglomerative algorithms such as the Clauset-Newman-Moore (CNM) algorithm [PERSON] (1973) and the Louvain method [PERSON] (1974). These two methods find a global partition of the graph in which each vertex belongs to exactly one community. Another widely used method of finding global, non-overlapping communities is spectral partitioning, which uses the eigenvectors of the Laplacian of the graph adjacency matrix to partition the graph in two [PERSON] and [PERSON] (2000); [PERSON] (1973). This process may be repeated recursively to find smaller communities. While much of previous work has focused on partitioning methods that find non-overlapping communities, there are many methods that identify overlapping clusters. These include clique percolation [PERSON] and [PERSON] (2000), label propagation [PERSON] and [PERSON] (2000); [PERSON] (1973), edge partitioning [PERSON] and [PERSON] (2000), Order Statistics Local Optimization Method (OSLOM) [PERSON] and [PERSON] (2000), multiple local expansions [PERSON] and [PERSON] (2000); [PERSON] (2000); [PERSON] (2000), and ensemble combinations [PERSON] (2000). Community detection has also been studied in the context of dynamic graph data and this work can be broadly divided into two categories. Algorithms in the first category focus only on quality, while those in the second aim to both detect high quality communities and minimize computation. Typically, methods in the former category seek to find the best sequence of communities given the dynamic data by maximizing both the quality of communities found at each point in time and the smoothness of community change over time. This can be done by collecting all temporal data before inferring communities, as in [PERSON] and [PERSON] (2000); [PERSON] (2000); [PERSON] and [PERSON] (2000). Using all temporal data may produce better choices of communities over time, but may be computationally expensive and can only be performed after all data is collected. Therefore, this approach is not suitable for applications in which updated communities must be found quickly. Alternatively, each community may be found using only past data, as in evolutionary clustering [PERSON] and [PERSON] (2000) and FaceNet [PERSON] and [PERSON] (2000). In the other category of dynamic community detection work, the goal is to both maintain good communities on a changing graph while minimizing computation. Typically, this is done as follows. A graph is formed from an initial set of data and communities are identified. When the graph changes due to new data, new communities are found by starting with the previous community solution and incrementally updating it. Many algorithms of this type update the results of greedy, agglomerative algorithms. For example, [PERSON] et al. [PERSON] et al. (2017) presents an incremental version of the Louvain algorithm. Whenever the graph changes, the previous clusters are used as a starting point. Changes are made by checking if the modularity would increase by moving any vertex to a different community. The work in [PERSON] et al. (2017) is another incremental version of Louvain clustering that starts with the previous cluster assignment modified based on the graph changes that occurred. The Modules Identification in Evolving Networks algorithm (MIEN) [PERSON] et al. (2017) is an incremental version of greedy agglomerative methods such as CNM. In the work by [PERSON] and [PERSON], whenever edges are inserted or deleted, the endpoint vertices of such edges are moved from their communities into singleton communities before restarting their agglomerative algorithm [PERSON] et al. (2017). In the work in [PERSON] et al. (2017) by [PERSON] et al., the authors present algorithms to maintain a clustering of a dynamic graph where edges appear as a stream by optimizing modularity while guaranteeing smoother clustering dynamics.