Local Community Detection in Dynamic Graphs Using Personalized Centrality

Local Community Detection in Dynamic Graphs Using Personalized Centrality. Nathan, E., Zakrzewska, A., Riedy, J., & Bader, D. A. Algorithms, August, 2017.
doi abstract bibtex

Analyzing massive graphs poses challenges due to the vast amount of data available. Extracting smaller relevant subgraphs allows for further visualization and analysis that would otherwise be too computationally intensive. Furthermore, many real data sets are constantly changing, and require algorithms to update as the graph evolves. This work addresses the topic of local community detection, or seed set expansion, using personalized centrality measures, specifically PageRank and Katz centrality. We present a method to efficiently update local communities in dynamic graphs. By updating the personalized ranking vectors, we can incrementally update the corresponding local community. Applying our methods on real-world graphs, we are able to obtain speedups of up to 60$\times$ compared to static recomputation while maintaining an average recall of 0.94 of the highly ranked vertices returned. Next, we investigate how approximations of a centrality vector affect the resulting local community. Specifically, our method that guarantees that the vertices returned in the community are the highly ranked vertices from a personalized centrality metric.

@article{localcomm-2017,
  author = {Eisha Nathan and Anita Zakrzewska and Jason Riedy and David A. Bader},
  title = {Local Community Detection in Dynamic Graphs Using Personalized Centrality},
  journal = {Algorithms},
  year = 2017,
  month = {August},
  abstract = {Analyzing massive graphs poses challenges due to the vast amount of data available.  Extracting smaller relevant subgraphs allows for further visualization and analysis that would otherwise be too computationally intensive.  Furthermore, many real data sets are constantly changing, and require algorithms to update as the graph evolves.  This work addresses the topic of local community detection, or seed set expansion, using personalized centrality measures, specifically PageRank and Katz centrality.  We present a method to efficiently update local communities in dynamic graphs. By updating the personalized ranking vectors, we can incrementally update the corresponding local community.  Applying our methods on real-world graphs, we are able to obtain speedups of up to 60$\times$ compared to static recomputation while maintaining an average recall of 0.94 of the highly ranked vertices returned.  Next, we investigate how approximations of a centrality vector affect the resulting local community. Specifically, our method that guarantees that the vertices returned in the community are the highly ranked vertices from a personalized centrality metric.},
  issn = {1999-4893},
  doi = {10.3390/a10030102},
  volume = 10,
  number = 3,
  article_number = 102,
  projtag = {grateful, hpda},
  ejr-proj = {high-performance-data-analysis, graph-analysis},
  ejr-grant = {hpda, grateful, xscala}
}

Downloads: 0

{"_id":"Z5LnxYk6Sy5t228yJ","bibbaseid":"nathan-zakrzewska-riedy-bader-localcommunitydetectionindynamicgraphsusingpersonalizedcentrality-2017","downloads":0,"creationDate":"2018-08-21T18:11:53.697Z","title":"Local Community Detection in Dynamic Graphs Using Personalized Centrality","author_short":["Nathan, E.","Zakrzewska, A.","Riedy, J.","Bader, D. A."],"year":2017,"bibtype":"article","biburl":"http://lovesgoodfood.com/jason/CV/ejr.bib","bibdata":{"bibtype":"article","type":"article","author":[{"firstnames":["Eisha"],"propositions":[],"lastnames":["Nathan"],"suffixes":[]},{"firstnames":["Anita"],"propositions":[],"lastnames":["Zakrzewska"],"suffixes":[]},{"firstnames":["Jason"],"propositions":[],"lastnames":["Riedy"],"suffixes":[]},{"firstnames":["David","A."],"propositions":[],"lastnames":["Bader"],"suffixes":[]}],"title":"Local Community Detection in Dynamic Graphs Using Personalized Centrality","journal":"Algorithms","year":"2017","month":"August","abstract":"Analyzing massive graphs poses challenges due to the vast amount of data available. Extracting smaller relevant subgraphs allows for further visualization and analysis that would otherwise be too computationally intensive. Furthermore, many real data sets are constantly changing, and require algorithms to update as the graph evolves. This work addresses the topic of local community detection, or seed set expansion, using personalized centrality measures, specifically PageRank and Katz centrality. We present a method to efficiently update local communities in dynamic graphs. By updating the personalized ranking vectors, we can incrementally update the corresponding local community. Applying our methods on real-world graphs, we are able to obtain speedups of up to 60$\\times$ compared to static recomputation while maintaining an average recall of 0.94 of the highly ranked vertices returned. Next, we investigate how approximations of a centrality vector affect the resulting local community. Specifically, our method that guarantees that the vertices returned in the community are the highly ranked vertices from a personalized centrality metric.","issn":"1999-4893","doi":"10.3390/a10030102","volume":"10","number":"3","article_number":"102","projtag":"grateful, hpda","ejr-proj":"high-performance-data-analysis, graph-analysis","ejr-grant":"hpda, grateful, xscala","bibtex":"@article{localcomm-2017,\n author = {Eisha Nathan and Anita Zakrzewska and Jason Riedy and David A. Bader},\n title = {Local Community Detection in Dynamic Graphs Using Personalized Centrality},\n journal = {Algorithms},\n year = 2017,\n month = {August},\n abstract = {Analyzing massive graphs poses challenges due to the vast amount of data available. Extracting smaller relevant subgraphs allows for further visualization and analysis that would otherwise be too computationally intensive. Furthermore, many real data sets are constantly changing, and require algorithms to update as the graph evolves. This work addresses the topic of local community detection, or seed set expansion, using personalized centrality measures, specifically PageRank and Katz centrality. We present a method to efficiently update local communities in dynamic graphs. By updating the personalized ranking vectors, we can incrementally update the corresponding local community. Applying our methods on real-world graphs, we are able to obtain speedups of up to 60$\\times$ compared to static recomputation while maintaining an average recall of 0.94 of the highly ranked vertices returned. Next, we investigate how approximations of a centrality vector affect the resulting local community. Specifically, our method that guarantees that the vertices returned in the community are the highly ranked vertices from a personalized centrality metric.},\n issn = {1999-4893},\n doi = {10.3390/a10030102},\n volume = 10,\n number = 3,\n article_number = 102,\n projtag = {grateful, hpda},\n ejr-proj = {high-performance-data-analysis, graph-analysis},\n ejr-grant = {hpda, grateful, xscala}\n}\n\n","author_short":["Nathan, E.","Zakrzewska, A.","Riedy, J.","Bader, D. A."],"key":"localcomm-2017","id":"localcomm-2017","bibbaseid":"nathan-zakrzewska-riedy-bader-localcommunitydetectionindynamicgraphsusingpersonalizedcentrality-2017","role":"author","urls":{},"metadata":{"authorlinks":{}}},"search_terms":["local","community","detection","dynamic","graphs","using","personalized","centrality","nathan","zakrzewska","riedy","bader"],"keywords":[],"authorIDs":[],"dataSources":["yxjEg4KYBKLdX7BAz","iovMFeXD2oi65krsd"]}