# Local Community Detection in Dynamic Graphs Using Personalized Centrality +
## 5 Dynamic Communities from Personalized Centrality
### Real Graphs
Unless otherwise specified, we use a single seed vertex and average over five different seeds for the personalized centrality metric. For a majority of the graphs, most notably the three larger graphs, the speedup in both time and number of iterations does not decrease with increasing batch size. This shows that our algorithm is able to maintain significant speedups even with large batch insertions of up to 1000 edges. We note that our dynamic algorithm also produces high quality communities compared to static recomputation. In terms of the recall, our dynamic algorithm always has recall values greater than 0.85, meaning we correctly identify a majority of the vertices in the local community compared to static recomputation, regardless of the batch size. Next, we examine the ratio of conductance scores of the community obtain via static recomputation compared to the community obtained from our dynamic algorithm. Ratios close to 1 indicate that the communities produced from our dynamic algorithm are similar to the ones produced from static recomputation w.r.t. their conductance scores, and values greater than 1 indicate our dynamic algorithm produces higher quality communities than \begin{table}
\begin{tabular}{c c c} \hline \hline
**Graph** & \(|V|\) & \(|E|\) \\ \hline slashdot-threads & 51,083 & 140,778 \\ enron & 87,221 & 1,148,072 \\ digg & 279,630 & 1,731,653 \\ wiki-talk & 541,355 & 2,424,962 \\ youtube-u-growth & 3,223,589 & 9,375,374 \\ \hline \hline \end{tabular}
\end{table} 
Table 4: Real graphs used in experiments. Columns are graph name, number of vertices, and number of edges. static recomputation. In a majority of the graphs and batch sizes tested, we obtain ratios very close to 1, and in some cases ratios greater than 1. Since we treat static recomputation as ground truth, this means that the dynamic communities are of similar quality to the static communities, and, in some cases, higher quality than the statically computed ones. Finally, we compare values of the normalized edge cut for both communities. Recall that ratios of the normalized edge cut lower than 1 indicate that our dynamic algorithm produces higher quality communities w.r.t. the normalized edge cut. In a majority of cases, we obtain communities close in quality to that of static recomputation, similar to the results we see from comparing the conductances of the communities obtained from static recomputation and our dynamic algorithm. In summary, the most prominent trends from this table are twofold: (1) we see significant speedups w.r.t. both time and iteration counts by using our dynamic algorithm compared to static recomputation to compute local communities using personalized centrality metrics, and (2) the communities produced by our dynamic algorithm are of similar quality to that of static recomputation, and in some cases, of higher quality. Next, we examine the performance and quality of our algorithm over time. Figure 3 plots the speedup in iterations over time (Figure 3a) and the ratio of conductance scores over time (Figure 3b). Since our dynamic algorithm only targets places in the centrality vector that are directly affected by edge updates to the graph, the performance of our dynamic algorithm is unaffected by the size of the underlying graph. This is unlike static recomputation, which is directly affected by the size of the underlying graph. Therefore, the speedup in iterations increases over time. Finally, we observe that the quality of our dynamic algorithm (in terms of conductance) matches the quality of the static algorithm with little to no decrease over time. There is only one graph for which the quality slightly decreases over time (DIGG); however, even for this graph, the ratio of conductances scores is still consistently above 0.95. In contrast, for the enron graph, the conductance of the dynamic community is better than the conductance of the static community (ratios greater than 1).