# Local Community Detection in Dynamic Graphs Using Personalized Centrality +
## 5 Dynamic Communities from Personalized Centrality
### Methods
\[= \mathbf{b}_{Katz}-\mathbf{x}_{t,Katz}+\alpha A_{t+1}\mathbf{x}_{t,Katz}\] \[= \mathbf{b}_{Katz}-\mathbf{x}_{t,Katz}+\alpha A_{t}\mathbf{x}_{t,Katz}-\alpha A _{t}\mathbf{x}_{t,Katz}+\alpha A_{t+1}\mathbf{x}_{t,Katz}\] \[= \mathbf{r}_{t,Katz}+\alpha(A_{t+1}-A_{t})\mathbf{x}_{t,Katz}\] \[= \mathbf{r}_{t,Katz}+\alpha\Delta A\mathbf{x}_{t,Katz}.\]  
Similarly, for PageRank, we calculate the new residual as \(\widetilde{\mathbf{r}}_{t+1,PR}\) (note since we use undirected graphs, \(A^{T}=A\)):  
\[\widetilde{\mathbf{r}}_{t+1,PR} = \mathbf{b}_{PR}-M_{t+1,PR}\mathbf{c}_{t,PR}\] \[= (1-\alpha)\mathbf{v}-\mathbf{c}_{t,PR}+\alpha A_{t+1}D_{t+1}^{-1}\mathbf{c}_ {t,PR}\] \[= (1-\alpha)\mathbf{v}-\mathbf{c}_{t,PR}+\alpha AD^{-1}\mathbf{c}_{t,PR}-\alpha AD ^{-1}\mathbf{c}_{t,PR}+\alpha A_{t+1}D_{t+1}^{-1}\mathbf{c}_{t,PR}\] \[=\mathbf{b}_{Katz}-(I-\alpha A_{t+1})\mathbf{x}_{t,Katz}\]0  
Note that, for both centrality measures, \(\widetilde{\mathbf{r}}_{t+1}\) can be written in terms of the current residual at time \(t\), edge updates \(\Delta A\), and the old solution. Next, we can use \(\widetilde{\mathbf{r}}_{t+1}\) to set up a linear system for the correction \(\Delta\mathbf{x}\) or \(\Delta\mathbf{c}\). We apply iterative refinement [50] and, for Katz centrality, solve the linear system  
\[=\mathbf{b}_{Katz}-(I-\alpha A_{t+1})\mathbf{x}_{t,Katz}\]1  
for \(\Delta\mathbf{x}\). For PageRank, we solve the linear system  
\[=\mathbf{b}_{Katz}-(I-\alpha A_{t+1})\mathbf{x}_{t,Katz}\]2  
for \(\Delta\mathbf{c}\). Unlike iterative refinement's typical use of a directly factored matrix, we rely on Jacobi iteration for solving the above systems. The final step of our algorithm is to update the residuals \(\mathbf{r}_{t+1,Katz}\) and \(\mathbf{r}_{t+1,PR}\) for the next time point. For Katz centrality, we can write the new residual \(\mathbf{r}_{t+1,Katz}\) as  
\[=\mathbf{b}_{Katz}-(I-\alpha A_{t+1})\mathbf{x}_{t,Katz}\]3 \[=\mathbf{b}_{Katz}-(I-\alpha A_{t+1})\mathbf{x}_{t,Katz}\]4 \[=\mathbf{b}_{Katz}-(I-\alpha A_{t+1})\mathbf{x}_{t,Katz}\]5 \[=\mathbf{b}_{Katz}-(I-\alpha A_{t+1})\mathbf{x}_{t,Katz}\]6 \[=\mathbf{b}_{Katz}-(I-\alpha A_{t+1})\mathbf{x}_{t,Katz}\]7  
We can calculate \(\mathbf{\Delta r}\), the difference in the two residuals at time \(t\) and \(t+1\) as \(\Delta\mathbf{r}=\alpha\Delta A\mathbf{x}_{t,Katz}-(I-\alpha\ A_{t+1})\mathbf{\Delta x}\). Likewise, updating the residual for PageRank is very similar. We can write the new residual \(\mathbf{r}_{t+1,PR}\) as  
\[=\mathbf{b}_{Katz}-(I-\alpha A_{t+1})\mathbf{x}_{t,Katz}\]8 \[=\mathbf{b}_{Katz}-(I-\alpha A_{t+1})\mathbf{x}_{t,Katz}\]9 Figure 1:0 Figure 1:1  
Then, we can calculate \(\mathbf{\Delta r}\), the difference in the two residuals at time \(t\) and \(t+1\) as \(\Delta\mathbf{r}=\alpha(A_{t+1}D_{t+1}^{-1}-A_{t}D_{t}^{-1})\mathbf{c}_{t,PR}-(I-\alpha A _{t+1}D_{t+1}^{-1})\Delta\mathbf{c}\). Updating the residual comes with the potential issue of accumulating error over long periods of time. However, these cases are rare, and, for our purposes, we obtain accurate results using our methods compared to a pure static recomputation. In Sections 5.2 and 5.3, we show that our algorithm for dynamic Katz centrality maintains good quality of the updated scores and provides significant speedup compared to a pure static recomputation in Section 5.3.