# Local Community Detection in Dynamic Graphs Using Personalized Centrality +
## 2 Background
### Centrality Measures  
As mentioned earlier, identification of the most \"important\" vertices in graphs is a fundamental problem in network analysis, which is done using centrality measures. In this work, we focus on two popular linear algebra based metrics, Katz centrality and PageRank, that can be written as functions of the adjacency matrix \(A\). Katz centrality scores (\(\epsilon_{Katz}\)) count the number of weighted walks in a graph starting at vertex \(i\), penalizing longer walks with a user-chosen parameter \(\alpha\), where \(\alpha\in(0,1/\|A\|_{2})\)[8]. A walk in a graph traverses edges between a series of vertices \(v_{1},v_{2},\cdots,v_{k}\), where vertices and edges are allowed to repeat. To count weighted walks of different lengths in the graph, we sum powers of the adjacency matrix [9] using the infinite series  
\[\sum_{k=1}^{\infty}\alpha^{k-1}A^{k}=A+\alpha A^{2}+\alpha^{2}A^{3}+\alpha^{3} A^{4}+\cdots+\alpha^{k-1}A^{k}+\cdots,\]  
where \(A^{k}(i,j)\) is the number of walks of length \(k\) from vertex \(i\) to vertex \(j\). Provided \(\alpha\) is chosen to be within the appropriate range, this infinite series converges to the matrix resolvent \(A(I-\alpha A)^{-1}\), where \(I\) is the \(n\times n\) identity matrix. When Katz centrality was first introduced, [PERSON] used the column sums to calculate vertex importance to obtain centrality scores as \(A(I-\alpha A)^{-1}\mathbf{1}\), where \(\mathbf{1}\) is the \(n\times 1\) vector of all \(1\)s. These are referred to as _global Katz scores_ and count the total sum of the number of weighted walks of different length starting at each vertex. We can extrapolate from this definition _personalized Katz scores_, where the \(i\)th column of the matrix \(A(I-\alpha A)^{-1}\) represents the personalized scores with respect to vertex \(i\), or the weighted counts of the number of walks from vertex \(i\) to all other vertices in the graph. Mathematically, we can write the personalized Katz scores with respect to vertex \(i\) as \(A(I-\alpha A)^{-1}e_{i}\), where \(e_{i}\) is the \(i\)th canonical basis vector, the vector of all \(0\)s except a \(1\) in the \(i\)th position. If we desire personalized scores with respect to a seed set of vertices \(S=\{v_{1},v_{2}\cdots,v_{|S|}\}\), we define the vector \(e_{S}=e_{v_{1}}+e_{v_{2}}+\cdots+e_{v_{|S|}}\) and calculate the scores as \(A(I-\alpha A)^{-1}e_{S}\). In this work, we deal only with personalized centrality scores. To summarize, we denote the centrality scores obtained through Katz centrality as the \(n\times 1\) vector \(\boldsymbol{c}_{Katz}=A(I-\alpha A)^{-1}\boldsymbol{e}_{i}\). If we let \(M_{Katz}=I-\alpha A\), then we can first solve the linear system \(M_{Katz}\boldsymbol{x}_{Katz}=\boldsymbol{b}_{Katz}\) for \(\boldsymbol{x}_{Katz}\) and then obtain the personalized centrality scores as \(\boldsymbol{c}_{Katz}=A\boldsymbol{x}_{Katz}\). PageRank is another walk-based centrality metric that assigns high scores to vertices that are visited by a large number of random walks in the network [10]. We can also write PageRank scores (\(\boldsymbol{c}_{PR}\)) as a function of the adjacency matrix \(A\), as \(\boldsymbol{c}_{PR}=(I-\alpha A^{T}D^{-1})^{-1}\boldsymbol{b}_{PR}\), where here \(\alpha\) is known as the \"teleportation\" constant and \(\boldsymbol{v}\) is a personalization vector with \(\|\boldsymbol{v}\|_{1}=1\). Similar to Katz centrality, we can define _global_ and _personalized_ scores. If \(\boldsymbol{v}\) has entries \(1/|V|\) denoting a uniformly random start, we obtain _global_ scores, otherwise for personalized scores w.r.t. vertex \(i\) we can set \(\boldsymbol{v}=\boldsymbol{e}_{i}\). Again if we desire personalized scores with respect to a seed set of vertices \(S=\{v_{1},v_{2}\cdots,v_{|S|}\}\), we define the normalized vector \(\boldsymbol{e}_{S}=(e_{v_{1}}+e_{v_{2}}+\cdots+e_{v_{|S|}})/|S|\) and calculate the scores as \(A(I-\alpha A)^{-1}\boldsymbol{e}_{S}\).