# Local Community Detection in Dynamic Graphs Using Personalized Centrality +
## 5 Dynamic Communities from Personalized Centrality  
### Methods  
We have detailed how to obtain a local community from a personalized centrality vector in Section 4.1. In this section, we describe how to obtain communities in dynamic graphs using personalized centrality metrics. The identification of local communities in dynamic graphs can be split into two components: (1) updating the personalized centrality vector every time the graph changes, and (2) obtaining the new local community from the updated centrality vector. For both centrality metrics, if \(\mathbf{c}_{t}\) denotes the solution at time \(t\), we solve for a correction \(\Delta\mathbf{c}\) so that we can obtain the new solution at time \(t+1\) as \(\mathbf{c}_{t+1}=\mathbf{c}_{t}+\Delta\mathbf{c}\). Essentially, we use the old solution as a starting point for the new solution instead of recomputing from scratch each time the graph is changed. Personalized Katz centrality scores w.r.t. vertex \(i\) are given as \(\mathbf{c}_{Katz}=A\mathbf{x}_{Katz}\) where \(\mathbf{x}_{Katz}\) is the solution to the linear system \((I-\alpha A)\mathbf{x}_{Katz}=\mathbf{b}_{Katz}\) for \(\mathbf{b}_{Katz}=\mathbf{e}_{i}\) and personalized PageRank scores are given as \(\mathbf{c}_{PR}=(I-\alpha A^{T}D^{-1})^{-1}\mathbf{b}_{PR}\), where \(\mathbf{c}_{PR}\) is the solution to the linear system \((I-\alpha A^{T}D^{-1})\,\mathbf{c}_{PR}\ =\ \mathbf{b}_{PR}\) for \(\mathbf{c}_{PR}\). After a batch of edge insertions to the graph, the static algorithm to obtain the updated Katz scores first recomputes \(\mathbf{x}_{t+1,Katz}\) using an iterative solver and obtains \(\mathbf{c}_{t+1,Katz}\) as \(A_{t+1}\mathbf{x}_{t+1,Katz}\) (for Katz centrality) or recomputes \(\mathbf{c}_{t+1,PR}\) (for personalized PageRank). For Katz centrality, since calculating \(\mathbf{c}_{t}\) given \(\mathbf{x}_{t}\) at any time point \(t\) is one matrix-vector multiplication and can be done in \(\mathcal{O}(m)\), this is not the bottleneck of static recomputation. Instead, the bottleneck is repeatedly updating \(\mathbf{x}_{t,Katz}\) given more edges being inserted into the graph, and hence we focus our dynamic algorithm on limiting the number of iterations taken to obtain the updated vector \(\mathbf{x}_{t,Katz}\), and, similarly, for PageRank, the focus of our dynamic algorithm on limiting the number of iterations taken to obtain the updated vector \(\mathbf{c}_{t,PR}\). Therefore, for Katz, we solve for the correction \(\Delta\mathbf{x}\) so that we can obtain the new solution at time \(t+1\) as \(\mathbf{x}_{t+1}=\mathbf{x}_{t}+\Delta\mathbf{x}\). For PageRank, we solve for the correction \(\Delta\mathbf{c}\) so that we can obtain the new solution at time \(t+1\) as \(\mathbf{c}_{t+1}=\mathbf{c}_{t}+\Delta\mathbf{c}\). The algorithm for updating Katz centrality is published in our previous work in [2] and the algorithm for updating PageRank is published in our previous work in [3]. The first step in updating the centrality vector is to measure how close the old solution \(\mathbf{x}_{t,Katz}\) or \(\mathbf{c}_{t,PR}\) is to solving the system for the updated graph \(A_{t+1}\). We calculate the new residual for Katz centrality as \(\widetilde{\mathbf{r}}_{t+1,Katz}\)  
\[\widetilde{\mathbf{r}}_{t+1,Katz} =\mathbf{b}_{Katz}-M_{t+1,Katz}\mathbf{x}_{t,Katz}\] \[=\mathbf{b}_{Katz}-(I-\alpha A_{t+1})\mathbf{x}_{t,Katz}\]  
Figure 1: The speedup of the personalized Katz centrality method compared to greedy expansion is shown for SBM graphs with different parameters. (**a**) The number of vertices \(n\) in the graph varies, with \(d=20\) and \(k=2\). (**b**) The number of communities \(k\) in the graph varies, with \(n=47104\) and \(d=20\). (**c**) The average vertex degree \(d\) varies, with \(n=1000\) and \(k=2\).