# Local Community Detection in Dynamic Graphs Using Personalized Centrality +
## 6 Guaranteed Ranking
### Methods  
For our purposes, the eventual goal of calculating the personalized centrality vector is to return the highly ranked vertices as the local community with respect to seed vertices of interest. Thus, we focus on _ranking accuracy_ and not _numerical accuracy_. More specifically, the error in the numerical problem of solving the linear system will most probably be different than the error in the data mining problem of identification of highly ranked vertices: the relative ranking of vertices can be correct even without a fully correct centrality vector. Therefore, we theoretically guarantee the accuracy of the solution to numerical problem needed to successfully answer the data mining question of ranking. Recall that, to solve for Katz centrality, we solve for the vector \(\epsilon_{Katz}=A(I-\alpha A)^{-1}\mathbf{b}_{Katz}\), or equivalently solve the linear system \((I-\alpha A)\mathbf{x}_{Katz}=M_{Katz}\mathbf{x}_{Katz}=\mathbf{b}_{Katz}\) and then obtain \(\epsilon_{Katz}\) as \(A\mathbf{x}_{Katz}\), where the right-hand side \(\mathbf{b}\) is set accordingly as described in Section 2.3. When the solution \(\mathbf{c}=M^{-1}\mathbf{b}\) to the linear system is approximated, there will be differences between the approximate solution and the exact solution. We prove that these differences along with the ranking values can indicate how far down the ranking we can go before the approximation error makes it unreliable. \begin{table}
\begin{tabular}{l l c c c c c c c c c c} \hline \hline \multirow{2}{*}{**Graph**} & \multirow{2}{*}{**Method**} & \multicolumn{10}{c}{**Number of Seeds**} \\ \cline{3-11}  & & **1** & **2** & **3** & **4** & **5** & **6** & **7** & **8** & **9** & **10** \\ \hline \multirow{4}{*}{\(T_{S}/T_{D}\)} & RW-1 & 46.9\(\times\) & 54.4\(\times\) & 49.3\(\times\) & 41.7\(\times\) & 39.4\(\times\) & 30.3\(\times\) & 32.4\(\times\) & 47.3\(\times\) & 41.5\(\times\) & 29.3\(\times\) \\  & RW-2 & 33.7\(\times\) & 66.1\(\times\) & 42.8\(\times\) & 51.5\(\times\) & 57.0\(\times\) & 52.1\(\times\) & 50.6\(\times\) & 46.1\(\times\) & 53.2\(\times\) & 39.0\(\times\) \\  & RW-3 & 44.5\(\times\) & 53.4\(\times\) & 54.0\(\times\) & 44.3\(\times\) & 53.6\(\times\) & 44.5\(\times\) & 53.0\(\times\) & 63.2\(\times\) & 68.5\(\times\) & 47.8\(\times\) \\  & RW-1 & 29.4\(\times\) & 30.9\(\times\) & 29.8\(\times\) & 24.6\(\times\) & 24.5\(\times\) & 24.4\(\times\) & 21.0\(\times\) & 29.2\(\times\) & 25.3\(\times\) & 22.3\(\times\) \\  & RW-2 & 20.4\(\times\) & 37.3\(\times\) & 24.4\(\times\) & 30.9\(\times\) & 31.8\(\times\) & 29.2\(\times\) & 29.0\(\times\) & 28.4\(\times\) & 30.1\(\times\) & 24.1\(\times\) \\  & RW-3 & 26.0\(\times\) & 29.8\(\times\) & 31.9\(\times\) & 27.9\(\times\) & 33.4\(\times\) & 27.4\(\times\) & 30.9\(\times\) & 38.2\(\times\) & 37.0\(\times\) & 29.9\(\times\) \\  & RW-1 & 0.99 & 0.98 & 1.00 & 0.98 & 1.00 & 1.00 & 0.99 & 0.98 & 1.00 & 1.00 \\ Recall & RW-2 & 0.96 & 0.98 & 0.95 & 0.99 & 0.96 & 0.99 & 1.00 & 0.99 & 0.99 & 0.99 & 0.99 \\  & RW-3 & 0.93 & 0.97 & 0.95 & 0.99 & 0.98 & 0.99 & 0.99 & 0.98 & 0.99 & 0.99 \\  & RW-1 & 1.00 & 1.00 & 1.00 & 1.00 & 1.00 & 1.00 & 1.00 & 1.00 & 1.00 & 1.00 \\ \(\phi_{S}/\phi_{D}\) & RW-2 & 1.00 & 1.00 & 1.00 & 1.00 & 1.00 & 1.00 & 1.00 & 1.00 & 1.00 & 1.00 \\  & RW-3 & 1.00 & 1.00 & 1.00 & 1.00 & 1.00 & 1.00 & 1 For iteration \(k\) of the iterative solver, define \(\mathbf{d}^{(k)}=\pi^{(k)}\epsilon^{(k)}\), where \(\mathbf{\pi}^{(k)}\) is the permutation such that \(\mathbf{d}^{(k)}\) is the vector \(\mathbf{\epsilon}^{(k)}\) ordered in decreasing order so that \(d_{i}^{(k)}\geq d_{i+1}^{(k)}\). Define \(\lambda_{min}(M)\) to be the smallest eigenvalue of the matrix \(M_{Katz}\). The matrix 2-norm \(\|A\|_{2}\) is the largest eigenvalue (since we use undirected graphs) \(\lambda_{max}(A)\). The residual norm is given as \(r_{k}=\|\mathbf{b}-M\mathbf{x}^{(k)}\|_{2}\). Theorem 1 below provides guarantees as to when the rank of vertex \(i\) above \(j\) is correct.