# Local Community Detection in Dynamic Graphs Using Personalized Centrality +
## 5 Dynamic Communities from Personalized Centrality
### Synthetic Dynamic Graphs  
In this section, we evaluate our dynamic algorithm on a synthetic network to show our ability to track merging and splitting of communities. We use a synthetic stochastic block model network with a recursive matrix (R-MAT) background with parameters \(a=0.55,b=0.15,c=0.15,d=0.25\). An R-MAT generator [51] creates scale-free networks designed to emulate real-world networks. Consider an adjacency matrix: the matrix is subdivided into four quadrants, where each quadrant has a different probability of being selected. Once a quadrant is selected, this quadrant is recursively subdivided into four subquadrants and using the previous probabilities, we select one of the subquadrants. This process is repeated until we arrive at a single cell in the adjacency matrix. An edge is assigned between the two vertices making up that cell.  
Figure 2 shows the community evolution in the stochastic block model part of the synthetic network that we are able to track with our dynamic algorithm. In Figure 2a, we start with three separate communities: \(C_{1}\) (the top left community), \(C_{2}\) (the middle community), and \(C_{3}\) (the bottom right community). In Figure 2b, communities \(C_{1}\) and \(C_{2}\) merge together, and, in Figure 2c, \(C_{1}\) splits off but communities \(C_{2}\) and \(C_{3}\) are merged together. Finally, in Figure 2d, communities \(C_{2}\) and \(C_{3}\) split and we obtain the original graph of three disjoint communities.  
We pick five seeds at random from community \(C_{2}\) to track both merging and splitting of communities and evaluate the recall of the community produced by our dynamic algorithm compared to the ground truth community at each of the four time points and results are averaged over the different seeds. We test our algorithm on communities of size 100 and 1000. The entire graph (including the R-MAT background) is 1,048,576 vertices and 10,485,760 edges (edge factor of 10).  
To generate dynamic stochastic block models, we use parameters \(p_{in}\in\{0.2,0.5\}\) and \(p_{out}=0.01\), where \(p_{in}\) and \(p_{out}\) are the probabilities of an edge existing between a pair of vertices that are in the same and different communities, respectively. These parameters ease describing communities that change size compared to parameters used in Section 4.2. For example, when a community grows, the average vertex degree would have to change in order to reflect the same \(p_{in}\) and \(p_{out}\) parameters.  
At each time point, we compare the community obtained from static recomputation versus the community obtained from our dynamic algorithm. We track the changing centrality vector and select top \(R\) vertices as the community, where \(R\) is the expected size of the community given the synthetic example in Figure 2. For a community of size \(R\), let \(C_{S}\) be the community obtained from the statically computed centrality vector (i.e., the top \(R\) highly ranked vertices from \(\mathbf{c}_{S}\)). Similarly, let \(C_{D}\) be the community obtained from the dynamically computed vector \(\mathbf{c}_{D}\). We calculate the recall of the vertices in the community produced by the dynamic algorithm as  
\[recall=\frac{|C_{S}\cap C_{D}|}{R}.\]  
Table 3 gives the recall values at each time point for the different graphs tested with the averages for each time point at the bottom. In a majority of the time steps, we obtain a recall above 0.80 and the communities with 1000 vertices have a higher recall than the communities with 100 vertices. Therefore, we are able to track evolving communities over time in dynamic synthetic graphs.