# Local Community Detection in Dynamic Graphs Using Personalized Centrality +
## 5 Dynamic Communities from Personalized Centrality
### Real Graphs
#### 5.3.1 Different Seeding Methods  
Finally, we examine different methods of choosing seed vertices. The purpose of this section is to test our dynamic algorithm with multiple seeds used in the right-hand side vector. All the previous results have been w.r.t. a single seed vertex (or averages of results for single seeds) chosen randomly from a pool of the top 10% highest degree vertices. We now use the following three methods to choose multiple seeds: (1) RW-1, (2) RW-2, and (3) RW-3, similar to [53]. Using just one seed vertex \(i\), the right-hand side \(\mathbf{b}=\mathbf{e}_{i}\). In the case of using multiple seeds \(S=\{v_{1},v_{2},\cdots,v_{|S|}\}\), the right hand side is \(\mathbf{b}=\mathbf{e}_{v_{1}}+\mathbf{e}_{v_{1}}+\cdots+\mathbf{e}_{v_{|S|}}\). The method RW-\(k\) chooses \(|S|\) seeds as follows: we first choose a vertex \(v\) at random from the existing vertices in the initial graph. We perform a random walk of length \(k\) from \(v\) and take the terminal vertex as a seed. We repeat this procedure to generate \(|S|\) unique seeds. Table 6 gives the results for different seeds methods for all the evaluation metrics. With respect to the speedup in both time and iterations, there is no significant difference in using a larger number of seed vertices or a different seeding methods. This intuitively makes sense since varying the number of seeds merely changes the right-hand side vector \(\mathbf{b}\) of the linear system, which has no effect on how many iterations the iterative solver takes to converge to a solution. With regards to the recall, we see a slight increase in recall values for a larger number of seeds. This can be attributed to the fact that a larger number of seeds indicates that the right-hand side vector has a larger number of nonzero values, meaning that the centrality values produced (\(\mathbf{c}\)) are with respect to all the seeds instead a single one.  
Furthermore, the method RW-1 produces higher values of recall than RW-2, which produces higher values of recall than RW-3 across multiple number of seed vertices. We offer a possible explanation for this behavior. The seeds produced by RW-1 are all neighbors of a single vertex and are more likely to belong to the same community. Since the seeds produced by RW-3 are three steps away from the initial randomly chosen vertex, it is less likely that these seeds belong to the same community, so the highly ranked vertices in the personalized centrality metric with respect to these seeds may not be as tightly knit of a community. However, the ratios of the conductance and normalized edge cut see no significant differences in varying the number of seeds or different seeding methods. All three seeding methods produce similar quality communities from our dynamic algorithm compared to static recomputation. In summary, we see that the performance doesn't change with respect to the number of seeds used, but the quality in terms of the recall shows a slight increase with more seeds used.  
Figure 3: Performance and quality behavior of dynamic algorithm compared to static recomputation over time. (**a**) speedup in iterations over time for \(b=10\), (**b**) ratio of conductance scores over time for \(b=100\).