# Local Community Detection in Dynamic Graphs Using Personalized Centrality +
## 6 Guaranteed Ranking
### Results  
Since our stopping criterion is theoretically guaranteed to return the top \(R\) vertices with any user-desired precision \(\phi^{*}\), we evaluate our method by comparing quality versus performance. Specifically, for different user-desired precisions, we calculate both (1) the raw number of iterations the solver takes to guarantee the set of top \(R\) as well as (2) the speedup obtained compared to iterating to machine precision for both PageRank and Katz. We vary the precision \(\phi^{*}\in\{0.5,0.6,0.7,0.8,0.9,1.0\}\) and test values of \(R=100\) and \(1000\), or equivalently calculate communities of sizes \(100\) and \(1000\). For each graph and community size, we use five randomly chosen seeds to calculate the personalized centrality vector and results shown are averages over the five seeds. We use the same five datasets from Table 4.  
Figure 4 plots the raw number of iterations taken for different values of the desired precision \(\phi^{*}\) for each graph for \(R=100\) (Figure 4a) and \(R=1000\) (Figure 4b) using personalized Katz centrality. We see that the number of iterations slowly increases up until a precision of \(\phi^{*}=0.9\) and then sharply increases for a perfect precision of \(\phi^{*}=1.0\). The fact that the iteration count increases minimally for precisions of 0.5-0.9 shows our method can deliver fairly precise sets of top \(R\) vertices with minimal extra computation. Specifically, we can obtain fairly precise (\(\phi^{*}=0.9\)) sets of top \(R\) vertices (or in our case, local communities of size \(R\)) without much more work than, for example, a precision of \(\phi^{*}=0.5\). It is only when we seek a precision of \(\phi^{*}=1.0\) that the iteration count sharply increases for all graphs, almost doubling in some cases. In many cases, the difference in iteration counts going from a precision of 0.9 to 1.0 is the same as the difference going from a precision of 0.5 to 0.9. Additionally, the overall number of iterations is much less for \(R=100\) compared to \(R=1000\) over all graphs and for both centrality metrics. This is because, regardless of the centrality metric, the gap \(\epsilon_{k}\) that we are looking for is fixed, while values in the centrality vector decrease exponentially. Thus, when we are looking for the gap \(\epsilon_{k}\) for larger values of \(R\), we will need to traverse further down the ranking vector to obtain the necessary gap, and most probably require a more accurate numerical solution compared to the solution needed for smaller values of \(R\). The previous results have shown raw iteration counts for both centrality metrics for different values of \(R\). Figure 5 therefore plots the speedup in iterations using our new stopping criterion  
Figure 4: Katz precision vs. iteration count. (**a**) \(R=100\), (**b**) \(R=1000\). compared to running the solver to machine precision. Denote the number of iterations taken by our method to obtain the top \(R\) vertices as \(I_{A}\) and the number of iterations taken to run to machine precision as \(I_{M}\). We calculate speedup as \(\frac{I_{M}}{I_{A}}\). We plot speedup versus the user-desired precision for both \(R=100\) and \(R=1000\). Results are averaged over all the graphs tested. Similar to the results seen earlier, we see less speedup for \(R=1000\) compared to \(R=100\). Additionally, we obtain less speedup for more precise local communities returned. Intuitively, this again makes sense since we require a more accurate numerical solution for the more precise communities. We have presented a method for discerning when the rank of vertex \(i\) above \(j\) is correct based on if there is a substantial gap between the centrality values of vertices \(i\) and \(j\), respectively. However, it is quite possible to have vertex \(i\) with a score of 100 and vertex \(j\) with a score of 100.1, where ranking \(j\) higher than \(i\) would probably not change the result substantially.