# Local Community Detection in Dynamic Graphs Using Personalized Centrality +
## 3 Related Work
### Dynamic Algorithms for Centrality Measures  
While much of the literature tends to focus on optimizing algorithms for centrality measures on static graphs, a growing body of work addresses dynamic algorithms for updating centrality measures given updates to the underlying graph. As PageRank is one of the most commonly studied problems in the literature, we outline several dynamic algorithms for updating the centrality metric given edge updates to the graph. There are two general areas of techniques used to approximate dynamic updates to the PageRank vector: (1) linear algebraic methods that mainly use techniques from linear and matrix algebra and perhaps using some structural properties of the network [39; 40], and (2) Monte Carlo methods that use a small number of simulated random walks per vertex to approximate PageRank [41; 42]. Many linear algebraic techniques use \"aggregation\" methods, which operate under the assumption that changes to the underlying network affect only a localized portion of the PageRank vector [43; 44]. Aggregation methods partition the set of vertices into two disjoint sets \(S\) and \(V\backslash S\), where \(S\) is the set of all vertices close to the incremental change and \(V\backslash S\) is the set of all other vertices. All the vertices in \(V\backslash S\) are aggregated into a single hyper-vertex and a smaller graph is created. The PageRank values of all the vertices are updated using this smaller graph and the result is pushed back to the original graph. However, most aggregation techniques do not translate well for real-time applications due to both performance and quality reasons. Since the performance of these methods depends on the partitioning of the network, a poor partitioning can cause these methods to be extremely slow [45]. In terms of quality, since the aggregation is ultimately an approximation of the updated PageRank vector given incremental changes to the graph, the approximation error could potentially accumulate over time leading to a very poor quality PageRank vector. Monte Carlo methods for the incremental computation of approximate PageRank, personalized PageRank and similar random walk methods is examined in detail in [46]. These methods are typically very efficient and can achieve good quality personalized scores, but most literature on these approaches has thus far only been applied to static networks. These methods maintain a small number of short random walk segments starting at each vertex in the graph. For the case of identifying the top \(k\) vertices, these methods are able to provide highly accurate estimates of the centrality values for the top vertices,but smaller values in the personalized case are nearly identical and therefore impossible to tell apart. In [3], we present an algorithm for updating PageRank values in dynamic graphs by only using sparse updates to the residual is presented. A similar algorithm for updating Katz centrality scores is given in [2]. These two methods are the base for this work. We believe a similar method will apply to non-backtracking variants of Katz centrality [47] as well, but that remains as future work. Personalized PageRank vectors and conductance scores have also been used to identify communities in graphs [48]. This method is based off of the fact that the personalized PageRank vector is the stationary distribution of a random walk that follows an edge of the graph with probability \(\alpha\) and \"teleports\" back to the seed vertex with probability \(1-\alpha\). The PageRank scores are calculated by an algorithm that pushes scores to neighboring vertices at each stage using the algorithm described in [38]. Once the PageRank vector is calculated, the algorithm performs a sweep cut to identify the optimal community. This procedure sweeps over all cuts induced by the ordering of the personalized PageRank vector and chooses the best cut determined by conductance scores of the induced cuts.