# Local Community Detection in Dynamic Graphs Using Personalized Centrality +
## 3 Related Work
### Community Detection
Our work falls into this second category of dynamic community detection, except that we deal with local communities, which are described next. Local community detection is the task of finding the best community for a set of vertices of interest, often called seed vertices. This is also called seed set expansion. When dealing with massive graphs, running computationally intensive analytics, visualization, and manual inspection by human analysts is likely to be infeasible, and this difficulty only increases for dynamic data. In such cases, local community detection can be used to extract a smaller, relevant subgraph in order to perform such tasks. [PERSON] presented a greedy algorithm that starts with all seed vertices in the community and repeatedly checks all neighboring vertices for inclusion [PERSON] (1986). At each iteration, the neighboring vertex that most increases the chosen fitness score is added to the community. This method is shown in Algorithm 2, where \(C\) represents the community and \(Nb(C)\) is the set of vertices neighboring \(C\), or those with an edge to a vertex in \(C\). In order to grow a community of \(k\) vertices, not including any seeds, it is necessary to perform \(k\) iterations and in each iteration check each neighboring vertex. Therefore, the complexity depends on the number of vertices bordering the community. This number may be approximated by \(kd\), where \(d\) is the average degree of the graph and \(k\) the community size. In this case, the time complexity is given by \(\mathcal{O}(k^{2}d)\). However, this is an overestimate when community members share many common neighbors, such as in graphs with a high clustering coefficient. In Section 4, we use synthetic, static graphs to compare the results of our method to this greedy seed set expansion algorithm. We show that our centrality based approach produces high quality communities compared to a common greedy approach and we explain when our approach is faster and preferable. Finally, there has been some work in relating centrality measures and community detection, though much of the previous work has focused on the global or static case. Betweenness centrality as a measure of vertex importance was originally introduced by [PERSON] in [PERSON] (1970) to measure influence of a vertex over the flow of information between other nodes by counting shortest paths in a network. The works by [PERSON] and [PERSON] [PERSON] and [PERSON] (2004); [PERSON] and [PERSON] (2003) extend the definition of vertex betweenness centrality to define edge betweenness as the number of shortest paths between pairs of vertices that run along it. Assuming communities in graphs are connected by only a few inter-community edges, these edges will have high edge betweenness. Therefore, by iteratively removing edges with the highest edge betweenness, community structure can be uncovered. A greedy local community algorithm using centrality metrics is the L-shell method [PERSON] and [PERSON] (2004), in which vertices are added to the community from successive shells, or sets of vertices at a fixed distance from the seed vertex. PageRank-Nibble is a spectral method of finding local communities in which personalized PageRank scores are computed and the community is formed by adding vertices with the highest values [PERSON] (2004). Our work differs from these previous works because we incrementally update scores to perform dynamic local community detection. Section 5.3 compares our results with static expansion using Katz centrality in the place of PageRank. ```
1:procedureGreedySeedset(graph \(G\), seed set \(seed\))
2:\(C=seed\)
3:\(progress=True\)
4:whileprogressdo
5:\(maxscore=-1\)
6:\(maxrtx=null\)
7:for\(v\in Nb(C)\)do
8:\(s(v)=fit(C\cup v)-fit(C)\)
9:if\(s(v)>maxscore\)then
10:\(maxscore=s(v)\)
11:\(maxvtx=v\)
12:endif
13:endfor
14:if\(maxscore>0\)then
15:\(C=C\cup maxrtx\)
16:else
17:\(progress=false\)
18:endif
19:endwhile
20:return\(C\)
21:endprocedure
```  
**Algorithm 2** Static, Greedy Seed Set Expansion