# Local Community Detection in Dynamic Graphs Using Personalized Centrality +
## 5 Dynamic Communities from Personalized Centrality
### Real Graphs  
We test our dynamic algorithm on five real graphs given in Table 4 from the KONECT database [52]. These graphs are chosen because they have timestamps associated with the edges in the graph. Since we have no ground truth of communities in real graphs, we use the results of the \begin{table}
\begin{tabular}{l c c c c c c c c c c} \hline \hline  & & & \multicolumn{3}{c}{**Block Size = 100**} & \multicolumn{3}{c}{**Block Size = 1000**} \\ \cline{3-11}
**Parameters** & **Batch Size** & \(t=\) & **100** & **200** & **300** & **400** & **1000** & **2000** & **3000** & **4000** \\ \hline \(p_{in}=0.2\), & 10 & 0.86 & 0.94 & 0.93 & 0.85 & 0.93 & 0.97 & 0.98 & 9.98 \\ \(p_{out}=0.01\) & 100 & 0.76 & 0.89 & 0.89 & 0.75 & 0.97 & 0.99 & 0.99 & 0.97 \\ \(1000\) & 1000 & 0.76 & 0.84 & 0.84 & 0.66 & 0.93 & 0.97 & 0.97 & 0.93 \\ \hline \(p_{in}=0.5\), & 10 & 0.92 & 0.96 & 0.97 & 0.92 & 0.96 & 0.98 & 0.99 & 0.99 \\ \(P_{out}=0.01\) & 100 & 0.79 & 0.89 & 0.90 & 0.78 & 0.95 & 0.98 & 0.98 & 0.95 \\ \(1000\) & 0.88 & 0.91 & 0.91 & 0.82 & 0.96 & 0.99 & 0.99 & 0.96 \\ \hline \hline \end{tabular}
\end{table} 
Table 3: Average recalls at each point in time for synthetic merging and splitting of communities over time. Figure 2: Synthetic dynamic graph showing merging and splitting of communities. (**a**) \(t=1\), (**b**) \(t=2\), (**c**) \(t=3\), (**d**) \(t=4\). static algorithm as a pseudo-ground truth. Thus, every time we update the centrality scores using our dynamic algorithm, we recompute the centrality vector statically from scratch to have a baseline for comparison. We create an initial graph \(G_{0}\) using the first half of edges, which provides a starting point for both the dynamic and static algorithms. To simulate a stream of edges in a dynamic graph, we insert the remaining edges in timestamped order in batches of size \(b\) and apply both algorithms and use batches of size \(b=10\), \(100\), and \(1000\). We use communities of size \(R\in\{100,1000\}\). The code was implemented in Python and run on an 18 core Intel Xeon CPU (Atlanta, GA, USA) at 2.10 GHz. We evaluate our dynamic algorithm with respect to performance and quality. For performance, we calculate the speedup with respect to time and iterations. Denote the time taken by static recomputation and our dynamic algorithm as \(T_{S}\) and \(T_{D}\), respectively. Similarly, denote the number of iterations taken by static recomputation and our dynamic algorithm as \(I_{S}\) and \(I_{D}\), respectively. We then calculate speedups in time and iterations as:  
\[speedup_{time}=\frac{T_{S}}{T_{D}},speedup_{iter}=\frac{I_{S}}{I_{D}}.\]  
Higher values of the speedups indicate that our dynamic algorithm provides more benefits compared to a pure static recomputation. We evaluate the quality of the results produced by our algorithms using three metrics: (1) recall, (2) ratio of conductance, and (3) ratio of normalized edge cut. We denote the conductance (\(\phi\)) of the community obtained from static recomputation as \(\phi_{S}\) and the conductance of the community obtained from our dynamic algorithm as \(\phi_{D}\), so we calculate the ratio of conductance scores as \(\frac{\phi_{S}}{\phi_{D}}\). Since lower values of conductance indicate higher quality communities, a ratio of conductance scores greater than 1 indicates our dynamic algorithm produces higher quality communities than static recomputation. We denote the normalized edge cut for the community (\(f\)) obtained by the static recomputation as \(f_{S}\) and \(f_{D}\) for the community obtained from our dynamic algorithm. We calculate the ratio of cuts as \(\frac{f_{S}}{f_{D}}\), where values of the ratio in scores less than 1 indicate that our dynamic algorithm produces higher quality communities than static recomputation. We first show averages over time for all batch sizes for all graphs tested for all the performance and quality metrics in Table 5. Results shown are averaged over both community sizes tested.