{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,12]],"date-time":"2025-10-12T04:14:40Z","timestamp":1760242480659,"version":"build-2065373602"},"reference-count":53,"publisher":"MDPI AG","issue":"3","license":[{"start":{"date-parts":[[2017,8,29]],"date-time":"2017-08-29T00:00:00Z","timestamp":1503964800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithms"],"abstract":"<jats:p>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 to real-world graphs, we are able to obtain speedups of up to 60\u00d7 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 guarantees that the vertices returned in the community are the highly ranked vertices from a personalized centrality metric.<\/jats:p>","DOI":"10.3390\/a10030102","type":"journal-article","created":{"date-parts":[[2017,8,29]],"date-time":"2017-08-29T10:39:15Z","timestamp":1504003155000},"page":"102","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":10,"title":["Local Community Detection in Dynamic Graphs Using Personalized Centrality"],"prefix":"10.3390","volume":"10","author":[{"given":"Eisha","family":"Nathan","sequence":"first","affiliation":[{"name":"School of Computational Science and Engineering, Georgia Tech, Atlanta, GA 30332, USA"}]},{"given":"Anita","family":"Zakrzewska","sequence":"additional","affiliation":[{"name":"School of Computational Science and Engineering, Georgia Tech, Atlanta, GA 30332, USA"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-4345-4200","authenticated-orcid":false,"given":"Jason","family":"Riedy","sequence":"additional","affiliation":[{"name":"School of Computational Science and Engineering, Georgia Tech, Atlanta, GA 30332, USA"}]},{"given":"David","family":"Bader","sequence":"additional","affiliation":[{"name":"School of Computational Science and Engineering, Georgia Tech, Atlanta, GA 30332, USA"}]}],"member":"1968","published-online":{"date-parts":[[2017,8,29]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","first-page":"68","DOI":"10.1016\/j.procs.2017.05.021","article-title":"Graph Ranking Guarantees for Numerical Approximations to Katz Centrality","volume":"108","author":"Nathan","year":"2017","journal-title":"Procedia Comput. Sci."},{"key":"ref_2","doi-asserted-by":"crossref","unstructured":"Nathan, E., and Bader, D.A. (August, January 31). A Dynamic Algorithm for Updating Katz Centrality in Graphs. Proceedings of the 2017 IEEE\/ACM International Conference on Advances in Social Networks Analysis and Mining, Sydney, Australia.","DOI":"10.1145\/3110025.3110034"},{"key":"ref_3","doi-asserted-by":"crossref","unstructured":"Riedy, J. (2016, January 23\u201327). Updating PageRank for Streaming Graphs. Proceedings of the 2016 IEEE International Parallel and Distributed Processing Symposium Workshops, Chicago, IL, USA.","DOI":"10.1109\/IPDPSW.2016.22"},{"key":"ref_4","doi-asserted-by":"crossref","unstructured":"Chung, F.R. (1997). Spectral Graph Theory, American Mathematical Society.","DOI":"10.1090\/cbms\/092"},{"key":"ref_5","doi-asserted-by":"crossref","unstructured":"Havemann, F., Heinz, M., Struck, A., and Gl\u00e4ser, J. (2011). Identification of overlapping communities and their hierarchy by locally calculating community-changing resolution levels. J. Stat. Mech. Theory Exp.","DOI":"10.1088\/1742-5468\/2011\/01\/P01023"},{"key":"ref_6","doi-asserted-by":"crossref","first-page":"026113","DOI":"10.1103\/PhysRevE.69.026113","article-title":"Finding and evaluating community structure in networks","volume":"69","author":"Newman","year":"2004","journal-title":"Phys. Rev. E"},{"key":"ref_7","doi-asserted-by":"crossref","unstructured":"Bader, D.A., Meyerhenke, H., Sanders, P., and Wagner, D. (2013). Graph partitioning and graph clustering. Contemporary Mathematics, Proceedings of the 10th DIMACS Implementation Challenge Workshop, Atlanta, GA, USA, 13\u201314 February 2012, American Mathematical Society.","DOI":"10.1090\/conm\/588"},{"key":"ref_8","doi-asserted-by":"crossref","first-page":"39","DOI":"10.1007\/BF02289026","article-title":"A new status index derived from sociometric analysis","volume":"18","author":"Katz","year":"1953","journal-title":"Psychometrika"},{"key":"ref_9","unstructured":"Benzi, M., and Klymko, C. (2014). A matrix analysis of different centrality measures. arXiv."},{"key":"ref_10","unstructured":"Page, L., Brin, S., Motwani, R., and Winograd, T. (1999). The PageRank Citation Ranking: Bringing Order to the Web, Stanford InfoLab. Technical Report 1999-66."},{"key":"ref_11","doi-asserted-by":"crossref","first-page":"2303","DOI":"10.1142\/S0218127407018403","article-title":"Centrality estimation in large networks","volume":"17","author":"Brandes","year":"2007","journal-title":"Int. J. Bifurc. Chaos"},{"key":"ref_12","doi-asserted-by":"crossref","unstructured":"Saad, Y. (2003). Iterative Methods for Sparse Linear Systems, SIAM.","DOI":"10.1137\/1.9780898718003"},{"key":"ref_13","doi-asserted-by":"crossref","first-page":"066111","DOI":"10.1103\/PhysRevE.70.066111","article-title":"Finding community structure in very large networks","volume":"70","author":"Clauset","year":"2004","journal-title":"Phys. Rev. E"},{"key":"ref_14","doi-asserted-by":"crossref","unstructured":"Blondel, V.D., Guillaume, J.L., Lambiotte, R., and Lefebvre, E. (2008). Fast unfolding of communities in large networks. J. Stat. Mech. Theory Exp.","DOI":"10.1088\/1742-5468\/2008\/10\/P10008"},{"key":"ref_15","doi-asserted-by":"crossref","first-page":"430","DOI":"10.1137\/0611030","article-title":"Partitioning sparse matrices with eigenvectors of graphs","volume":"11","author":"Pothen","year":"1990","journal-title":"SIAM J. Matrix Anal. Appl."},{"key":"ref_16","doi-asserted-by":"crossref","first-page":"160202","DOI":"10.1103\/PhysRevLett.94.160202","article-title":"Clique percolation in random networks","volume":"94","author":"Palla","year":"2005","journal-title":"Phys. Rev. Lett."},{"key":"ref_17","doi-asserted-by":"crossref","unstructured":"Xie, J., Szymanski, B.K., and Liu, X. (2011, January 11). SLPA: Uncovering overlapping communities in social networks via a speaker-listener interaction dynamic process. Proceedings of the 2011 IEEE 11th International Conference on Data Mining Workshops (ICDMW), Vancouver, BC, Canada.","DOI":"10.1109\/ICDMW.2011.154"},{"key":"ref_18","doi-asserted-by":"crossref","unstructured":"Xie, J., and Szymanski, B.K. (2012). Towards linear time overlapping community detection in social networks. Advances in Knowledge Discovery and Data Mining, Springer.","DOI":"10.1007\/978-3-642-30220-6_3"},{"key":"ref_19","doi-asserted-by":"crossref","first-page":"265","DOI":"10.1140\/epjb\/e2010-00261-8","article-title":"Line graphs of weighted networks for overlapping communities","volume":"77","author":"Evans","year":"2010","journal-title":"Eur. Phys. J. B"},{"key":"ref_20","doi-asserted-by":"crossref","unstructured":"Lancichinetti, A., Radicchi, F., Ramasco, J.J., and Fortunato, S. (2011). Finding statistically significant communities in networks. PLoS ONE, 6.","DOI":"10.1371\/journal.pone.0018961"},{"key":"ref_21","doi-asserted-by":"crossref","first-page":"033015","DOI":"10.1088\/1367-2630\/11\/3\/033015","article-title":"Detecting the overlapping and hierarchical community structure in complex networks","volume":"11","author":"Lancichinetti","year":"2009","journal-title":"New J. Phys."},{"key":"ref_22","unstructured":"Lee, C., Reid, F., McDaid, A., and Hurley, N. (2010, January 25\u201328). Detecting highly overlapping community structure by greedy clique expansion. Proceedings of the 4th SNA-KDD Workshop, Washington, DC, USA."},{"key":"ref_23","doi-asserted-by":"crossref","first-page":"171","DOI":"10.1109\/TPDS.2015.2390633","article-title":"Engineering Parallel Algorithms for Community Detection in Massive Networks","volume":"27","author":"Staudt","year":"2016","journal-title":"IEEE Trans. Parallel Distrib. Syst."},{"key":"ref_24","doi-asserted-by":"crossref","unstructured":"Tantipathananandh, C., Berger-Wolf, T., and Kempe, D. (2007, January 12\u201315). A framework for community identification in dynamic social networks. Proceedings of the 13th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, San Jose, CA, USA.","DOI":"10.1145\/1281192.1281269"},{"key":"ref_25","doi-asserted-by":"crossref","first-page":"876","DOI":"10.1126\/science.1184819","article-title":"Community structure in time-dependent, multiscale, and multiplex networks","volume":"328","author":"Mucha","year":"2010","journal-title":"Science"},{"key":"ref_26","unstructured":"Jdidia, M.B., Robardet, C., and Fleury, E. (2007, January 28\u201331). Communities detection and analysis of their dynamics in collaborative networks. Proceedings of the 2nd International Conference on Digital Information Management, Lyon, France."},{"key":"ref_27","doi-asserted-by":"crossref","unstructured":"Chakrabarti, D., Kumar, R., and Tomkins, A. (2006, January 20\u201323). Evolutionary clustering. Proceedings of the 12th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, Philadelphia, PA, USA.","DOI":"10.1145\/1150402.1150467"},{"key":"ref_28","doi-asserted-by":"crossref","first-page":"8","DOI":"10.1145\/1514888.1514891","article-title":"Analyzing communities and their evolutions in dynamic social networks","volume":"3","author":"Lin","year":"2009","journal-title":"ACM Trans. Knowl. Discov. Data"},{"key":"ref_29","unstructured":"Aynaud, T., and Guillaume, J.L. (June, January 31). Static community detection algorithms for evolving networks. Proceedings of the WiOpt\u201910: Modeling and Optimization in Mobile, Ad Hoc, and Wireless Networks, Avignon, France."},{"key":"ref_30","unstructured":"Shang, J., Liu, L., Xie, F., Chen, Z., Miao, J., Fang, X., and Wu, C. (2014). A real-time detecting algorithm for tracking community structure of dynamic networks. arXiv."},{"key":"ref_31","doi-asserted-by":"crossref","unstructured":"Dinh, T.N., Xuan, Y., and Thai, M.T. (2009, January 14\u201316). Towards social-aware routing in dynamic communication networks. Proceedings of the 2009 IEEE 28th International Performance Computing and Communications Conference (IPCCC), Scottsdale, AZ, USA.","DOI":"10.1109\/PCCC.2009.5403845"},{"key":"ref_32","doi-asserted-by":"crossref","unstructured":"Riedy, J., and Bader, D.A. (2013, January 20\u201324). Multithreaded community monitoring for massive streaming graph data. Proceedings of the 2013 IEEE 27th International Symposium on Parallel and Distributed Processing Workshops and PhD Forum IEEE, Boston, MA, USA.","DOI":"10.1109\/IPDPSW.2013.229"},{"key":"ref_33","first-page":"1","article-title":"Dynamic graph clustering combining modularity and smoothness","volume":"18","author":"Maillard","year":"2013","journal-title":"ACM J. Exp. Algorithmics"},{"key":"ref_34","doi-asserted-by":"crossref","first-page":"026132","DOI":"10.1103\/PhysRevE.72.026132","article-title":"Finding local community structure in networks","volume":"72","author":"Clauset","year":"2005","journal-title":"Phys. Rev. E"},{"key":"ref_35","doi-asserted-by":"crossref","first-page":"35","DOI":"10.2307\/3033543","article-title":"A set of measures of centrality based on betweenness","volume":"40","author":"Freeman","year":"1977","journal-title":"Sociometry"},{"key":"ref_36","doi-asserted-by":"crossref","first-page":"7821","DOI":"10.1073\/pnas.122653799","article-title":"Community structure in social and biological networks","volume":"99","author":"Girvan","year":"2002","journal-title":"Proc. Natl. Acad. Sci. USA"},{"key":"ref_37","doi-asserted-by":"crossref","first-page":"046108","DOI":"10.1103\/PhysRevE.72.046108","article-title":"Local method for detecting communities","volume":"72","author":"Bagrow","year":"2005","journal-title":"Phys. Rev. E"},{"key":"ref_38","doi-asserted-by":"crossref","unstructured":"Andersen, R., Chung, F., and Lang, K. (2006, January 21\u201324). Local graph partitioning using PageRank vectors. Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science, Berkeley, CA, USA.","DOI":"10.1109\/FOCS.2006.44"},{"key":"ref_39","doi-asserted-by":"crossref","unstructured":"Chen, Y.Y., Gan, Q., and Suel, T. (2004, January 8\u201313). Local methods for estimating PageRank values. Proceedings of the thirteenth ACM International Conference on Information and Knowledge Management, Washington, DC, USA.","DOI":"10.1145\/1031171.1031248"},{"key":"ref_40","unstructured":"Chien, S., Dwork, C., Kumar, R., and Sivakumar, D. Towards exploiting link evolution. Proceedings of the Workshop on Algorithms and Models for the Web Graph, Available online: http:\/\/citeseerx.ist.psu.edu\/viewdoc\/summary?doi=10.1.1.16.811."},{"key":"ref_41","doi-asserted-by":"crossref","first-page":"13","DOI":"10.1145\/1970392.1970397","article-title":"Estimating PageRank on graph streams","volume":"58","author":"Sarma","year":"2011","journal-title":"J. ACM"},{"key":"ref_42","unstructured":"Gy\u00f6ngyi, Z., Garcia-Molina, H., and Pedersen, J. (September, January 31). Combating web spam with trustrank. Proceedings of the Thirtieth International Conference on Very Large Data Bases\u2014Volume 30, Toronto, ON, Canada."},{"key":"ref_43","unstructured":"Langville, A.N., and Meyer, C.D. (2002). Updating PageRank Using the Group Inverse and Stochastic Complementation, North Carolina State University. Technical Report CRSC-TR02-32."},{"key":"ref_44","doi-asserted-by":"crossref","first-page":"968","DOI":"10.1137\/040619028","article-title":"Updating the stationary vector of an irreducible Markov chain with an eye on Google\u2019s PageRank","volume":"27","author":"Langville","year":"2004","journal-title":"SIAM. J. Matrix Anal. Appl."},{"key":"ref_45","doi-asserted-by":"crossref","unstructured":"Langville, A.N., and Meyer, C.D. (2004, January 17\u201322). Updating PageRank with iterative aggregation. Proceedings of the 13th International World Wide Web conference on Alternate Track Papers & Posters, New York, NY, USA.","DOI":"10.1145\/1010432.1010556"},{"key":"ref_46","doi-asserted-by":"crossref","first-page":"173","DOI":"10.14778\/1929861.1929864","article-title":"Fast incremental and personalized PageRank","volume":"4","author":"Bahmani","year":"2010","journal-title":"Proc. VLDB Endow."},{"key":"ref_47","unstructured":"Arrigo, F., Grindrod, P., Higham, D.J., and Noferini, V. (2017). Nonbacktracking Walk Centrality for Directed Networks, University of Manchester. Technical Report MIMS Preprint 2017.9."},{"key":"ref_48","doi-asserted-by":"crossref","unstructured":"Leskovec, J., Lang, K.J., Dasgupta, A., and Mahoney, M.W. (2008, January 21\u201325). Statistical properties of community structure in large social and information networks. Proceedings of the 17th International Conference on World Wide Web, Beijing, China.","DOI":"10.1145\/1367497.1367591"},{"key":"ref_49","doi-asserted-by":"crossref","first-page":"33","DOI":"10.1073\/pnas.1611275114","article-title":"Block Models and Personalized PageRank","volume":"114","author":"Kloumann","year":"2016","journal-title":"Proc. Natl. Acad. Sci. USA"},{"key":"ref_50","doi-asserted-by":"crossref","first-page":"316","DOI":"10.1145\/321386.321394","article-title":"Iterative Refinement in Floating Point","volume":"14","author":"Moler","year":"1967","journal-title":"J. ACM"},{"key":"ref_51","doi-asserted-by":"crossref","unstructured":"Chakrabarti, D., Zhan, Y., and Faloutsos, C. (2004, January 22\u201324). R-MAT: A Recursive Model for Graph Mining. Proceedings of the Fourth SIAM International Conference on Data Mining, Lake Buena Vista, FL, USA.","DOI":"10.1137\/1.9781611972740.43"},{"key":"ref_52","doi-asserted-by":"crossref","unstructured":"Kunegis, J. (2013, January 13\u201317). KONECT: the Koblenz network collection. Proceedings of the 22nd International Conference on World Wide Web, Rio de Janeiro, Brazil.","DOI":"10.1145\/2487788.2488173"},{"key":"ref_53","unstructured":"Riedy, J., Bader, D.A., Jiang, K., Pande, P., and Sharma, R. (2011). Detecting Communities from Given Seeds in Social Networks, Georgia Institute of Technology. Technical Report."}],"container-title":["Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1999-4893\/10\/3\/102\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T18:43:37Z","timestamp":1760208217000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1999-4893\/10\/3\/102"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,8,29]]},"references-count":53,"journal-issue":{"issue":"3","published-online":{"date-parts":[[2017,9]]}},"alternative-id":["a10030102"],"URL":"https:\/\/doi.org\/10.3390\/a10030102","relation":{},"ISSN":["1999-4893"],"issn-type":[{"type":"electronic","value":"1999-4893"}],"subject":[],"published":{"date-parts":[[2017,8,29]]}}}