# Local Community Detection in Dynamic Graphs Using Personalized Centrality +
## 4 Communities from Personalized Centrality
### Results on Static, Synthetic Graphs  
This section validates using personalized centrality for local community detection. Static, synthetic graphs with known community structure provide test cases for the Katz centrality approach. We also compare our approach to the popular method of greedy expansion [34], which is described in Section 3.1. To test, we generate multiple stochastic block model (SBM) graphs with varying parameters, randomly choose seed vertices, and detect local communities with both personalized Katz centrality and greedy expansion. The greedy expansion method uses conductance as its fitness function. A simple stochastic block model graph can be generated with four parameters: the total number of vertices \(n\), the number of communities \(k\), the average degree of vertices \(d\), and the percentage of inter-community edges \(\rho\). All communities in such a graph are generated with the same parameters and are interchangeable. Note that SBM graphs can also be generated with different parameters than we use. Instead of using an average degree and proportion of inter-community edges, the parameters \(p_{in}\) and \(p_{out}\) can be used. These define the probabilities of placing and edge between a pair of vertices that are in the same community and between a pair in different communities, respectively. Although different parameters are used, these two models are the same when all communities are generated with the same parameters. The parameters are related as follows. For a set community size of \(c=\frac{n}{k}\), \(p_{in}=\frac{d(1-\rho)}{c}\) and \(p_{out}=\frac{d\rho}{c(k-1)}\). The code was implemented in Python and run on an 18 core Intel Xeon CPU at 2.10 GHz. Table 2a-c shows the recall of communities found with each method compared to the known ground truth. The recall is the fraction of the ground truth recovered by each method. For these results, random stochastic block model graphs were created with 1000 vertices and two communities and a random seed was chosen. The minimum, mean, and maximum recall values shown are obtained from 100 runs, each with a random graph and seed vertex. For the results shown in Table 2a, the average degree of vertices was varies from 5 to 490, while the proportion of inter-community edges is fixed at 0.01. All others are intra-community edges. Because the proportion is fixed, as the average degree increases, both the number of intra-community and inter-community edges increases. Overall, recall scores are at or near 1, showing that the Katz method returns good communities for all average degrees considered. This suggests that using personalized centrality is a viable method of local community detection. In fact, on SBM graphs with low degrees, the personalized Katz method performs better than greedy expansion. This occurs because the greedy expansion method stops adding new vertices once a local quality maximum is reached. On very low degree SBM graphs, it stops expanding after adding only a few vertices, which results in very small communities and thus low recall. Therefore, we also show results for a modified version of the greedy algorithm in which expansion is forced to occur until the community reaches the desired size (labeled _Force Expand_ in Tables 2a-c). Normally, the greedy algorithm is not run in this way, but because we know the size of the community ahead of time, we can obtain these results. Note that results for the normal greedy algorithm and the forced expansion version tend to differ only for graphs in which the average degree is low compared to the community size. Table 2b,c shows how the quality of communities detected varies for SBM graphs with an increasing proportion of inter-community edges. For these experiments, the average degree is fixed at 20 (Table 2b) and 100 (Table 2c), and the proportion of edges that are inter-community varies from 0.01 to 0.4 (thus the proportion of intra-community edges varies from 0.99 to 0.6).