# Local Community Detection in Dynamic Graphs Using Personalized Centrality +
## 1 Introduction  
A variety of applications from many different fields of research, such as society, network security, finance, and biology, represent their data in graphs. Broadly speaking, a graph is a collection of vertices and edges, where an edge between vertices represents a relationship between the two vertices. For example, in a social network, the vertices represent people and an edge between two people signifies a friendship or interaction between them. In a financial network, the vertices may also be people but an edge between two people may indicate that these two people participated in a mutual transaction. Much of real data today changes constantly, so we turn to dynamic graphs. Dynamic graph data represents the changing relationships between different entities over time.  
Two fundamental topics in the analysis of large, dynamic graphs are (1) identifying closely related subgraphs or communities, and (2) measuring vertex \"importance\" or centrality. Community detection identifies groups of vertices more closely related to each other than to the rest of the graph. In a social network, a community may represent a group of friends or people who share a similar interest. In a financial network, a community may be a group of people who regularly participate in transactions with each other. Global community detection methods partition the entire graph into different communities. Typically, most methods partition the graph into disjoint communities, but overlapping community detection is also a growing field of research. In contrast to global community detection methods that seek to optimize a global partition on the graph, local community detection methods aim to identify a single community in the graph relevant to a few seed vertices of interest. This problem is alternatively called seed set expansion. Since many real graphs have millions or billions of vertices oredges, visualization is extremely difficult. Furthermore, many computationally intensive algorithms cannot be run on such large graphs. Seed set expansion can be used to extract a smaller, relevant subgraph for further analysis.  
In addition to community detection, identifying the most important vertices in a graph is another well-studied problem in network analysis. In a social network, these might be the people who are the most influential on a social networking site. In a network modeling disease spread, these might be the sites of disease origin. To identify vertex importance, we use centrality measures, which assign a numerical score to each vertex in the graph. These numerical scores can then in turn be translated into rankings on the vertices of the graph, where highly ranked vertices are the most \"important\" vertices in the graph. We can again think of centrality in terms of _global_ values or _local_ values. Intuitively, global centrality values indicate how important each vertex is with respect to all other vertices. In contrast, local centrality values (or personalized centrality) indicate how important vertices are with respect to specific seed vertices of interest. In this work, we bridge the two research questions of community detection and centrality by using personalized centrality metrics to identify local communities in dynamic graphs.