{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,17]],"date-time":"2025-10-17T14:07:15Z","timestamp":1760710035122,"version":"3.37.3"},"reference-count":36,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2019,10,29]],"date-time":"2019-10-29T00:00:00Z","timestamp":1572307200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2019,10,29]],"date-time":"2019-10-29T00:00:00Z","timestamp":1572307200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100001866","name":"Fonds National de la Recherche Luxembourg","doi-asserted-by":"publisher","award":["10929115"],"award-info":[{"award-number":["10929115"]}],"id":[{"id":"10.13039\/501100001866","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Appl Netw Sci"],"published-print":{"date-parts":[[2019,12]]},"abstract":"<jats:title>Abstract<\/jats:title>\n              <jats:p>The objective of a community detection algorithm is to group similar nodes that are more connected to each other than with the rest of the network. Several methods have been proposed but many are of high complexity and require global knowledge of the network, which makes them less suitable for large-scale networks. The Label Propagation Algorithm initially assigns a distinct label to each node that iteratively updates its label with the one of the majority of its neighbors, until consensus is reached among all nodes in the network. Nodes sharing the same label are then grouped into communities. It runs in near linear time and is decentralized, but it gets easily stuck in local optima and often returns a single giant community. To overcome these problems we propose MemLPA, a variation of the classical Label Propagation Algorithm where each node implements a memory mechanism that allows them to \u201cremember\u201d about past states of the network and uses a decision rule that takes this information into account. We demonstrate through extensive experiments, on the Lancichinetti-Fortunato-Radicchi benchmark and a set of real-world networks, that MemLPA outperforms other existing label propagation algorithms that implement memory and some of the well-known community detection algorithms. We also perform a topological analysis to extend the performance study and compare the topological properties of the communities found to the ground-truth community structure.<\/jats:p>","DOI":"10.1007\/s41109-019-0210-8","type":"journal-article","created":{"date-parts":[[2019,10,30]],"date-time":"2019-10-30T22:23:13Z","timestamp":1572474193000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":6,"title":["Local memory boosts label propagation for community detection"],"prefix":"10.1007","volume":"4","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-0287-4388","authenticated-orcid":false,"given":"Antonio Maria","family":"Fiscarelli","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Matthias R.","family":"Brust","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Gr\u00e9goire","family":"Danoy","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Pascal","family":"Bouvry","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2019,10,29]]},"reference":[{"issue":"6749","key":"210_CR1","doi-asserted-by":"publisher","first-page":"130","DOI":"10.1038\/43601","volume":"401","author":"R Albert","year":"1999","unstructured":"Albert, R, Jeong H, Barab\u00e1si A-L (1999) Internet: Diameter of the world-wide web. Nature 401(6749):130\u2013131.","journal-title":"Nature"},{"issue":"2","key":"210_CR2","doi-asserted-by":"publisher","first-page":"026129","DOI":"10.1103\/PhysRevE.80.026129","volume":"80","author":"MJ Barber","year":"2009","unstructured":"Barber, MJ, Clark JW (2009) Detecting network communities by propagating labels under constraints. Phys Rev E 80(2):026129.","journal-title":"Phys Rev E"},{"issue":"10","key":"210_CR3","doi-asserted-by":"publisher","first-page":"P10008","DOI":"10.1088\/1742-5468\/2008\/10\/P10008","volume":"2008","author":"VD Blondel","year":"2008","unstructured":"Blondel, VD, Guillaume J-L, Lambiotte R, Lefebvre E (2008) Fast unfolding of communities in large networks. J Stat Mech Theory Exp 2008(10):P10008.","journal-title":"J Stat Mech Theory Exp"},{"issue":"2","key":"210_CR4","doi-asserted-by":"publisher","first-page":"172","DOI":"10.1109\/TKDE.2007.190689","volume":"20","author":"U Brandes","year":"2008","unstructured":"Brandes, U, Delling D, Gaertler M, Gorke R, Hoefer M, Nikoloski Z, Wagner D (2008) On modularity clustering. IEEE Trans Knowl Data Eng 20(2):172\u2013188.","journal-title":"IEEE Trans Knowl Data Eng"},{"issue":"6","key":"210_CR5","doi-asserted-by":"publisher","first-page":"066111","DOI":"10.1103\/PhysRevE.70.066111","volume":"70","author":"A Clauset","year":"2004","unstructured":"Clauset, A, Newman ME, Moore C (2004) Finding community structure in very large networks. Phys Rev E 70(6):066111.","journal-title":"Phys Rev E"},{"issue":"5","key":"210_CR6","first-page":"1","volume":"1695","author":"G Csardi","year":"2006","unstructured":"Csardi, G, Nepusz T (2006) The igraph software package for complex network research. InterJournal Complex Systems 1695(5):1\u20139.","journal-title":"InterJournal Complex Systems"},{"issue":"09","key":"210_CR7","doi-asserted-by":"publisher","first-page":"P09008","DOI":"10.1088\/1742-5468\/2005\/09\/P09008","volume":"2005","author":"L Danon","year":"2005","unstructured":"Danon, L, Diaz-Guilera A, Duch J, Arenas A (2005) Comparing community structure identification. J Stat Mech Theory Exp 2005(09):P09008.","journal-title":"J Stat Mech Theory Exp"},{"key":"210_CR8","doi-asserted-by":"crossref","unstructured":"Dao, V-L, Bothorel C, Lenca P (2018) Estimating the similarity of community detection methods based on cluster size distribution In: International Conference on Complex Networks and Their Applications, 183\u2013194.. Springer.","DOI":"10.1007\/978-3-030-05411-3_15"},{"key":"210_CR9","unstructured":"Dongen, S (2000) A cluster algorithm for graphs."},{"key":"210_CR10","doi-asserted-by":"crossref","unstructured":"Fiscarelli, AM, Brust MR, Danoy G, Bouvry P (2018) A Memory-Based Label Propagation Algorithm for Community Detection In: International Conference on Complex Networks and their Applications, 171\u2013182.. Springer.","DOI":"10.1007\/978-3-030-05411-3_14"},{"issue":"12","key":"210_CR11","doi-asserted-by":"publisher","first-page":"7821","DOI":"10.1073\/pnas.122653799","volume":"99","author":"M Girvan","year":"2002","unstructured":"Girvan, M, Newman ME (2002) Community structure in social and biological networks. Proc Natl Acad Sci 99(12):7821\u20137826.","journal-title":"Proc Natl Acad Sci"},{"key":"210_CR12","doi-asserted-by":"crossref","unstructured":"Hosseini, R, Azmi R (2015) Memory-based label propagation algorithm for community detection in social networks In: 2015 The International Symposium on Artificial Intelligence and Signal Processing (AISP), 256\u2013260.. IEEE.","DOI":"10.1109\/AISP.2015.7123488"},{"issue":"1","key":"210_CR13","doi-asserted-by":"publisher","first-page":"193","DOI":"10.1007\/BF01908075","volume":"2","author":"L Hubert","year":"1985","unstructured":"Hubert, L, Arabie P (1985) Comparing partitions. J classif 2(1):193\u2013218.","journal-title":"J classif"},{"key":"210_CR14","doi-asserted-by":"publisher","first-page":"651","DOI":"10.1016\/j.physa.2017.10.018","volume":"492","author":"M Jebabli","year":"2018","unstructured":"Jebabli, M, Cherifi H, Cherifi C, Hamouda A (2018) Community detection algorithm evaluation with ground-truth data. Phys A Stat Mech Appl 492:651\u2013706.","journal-title":"Phys A Stat Mech Appl"},{"issue":"6804","key":"210_CR15","doi-asserted-by":"publisher","first-page":"651","DOI":"10.1038\/35036627","volume":"407","author":"H Jeong","year":"2000","unstructured":"Jeong, H, Tombor B, Albert R, Oltvai ZN, Barab\u00e1si A-L (2000) The large-scale organization of metabolic networks. Nature 407(6804):651\u2013654.","journal-title":"Nature"},{"issue":"2","key":"210_CR16","doi-asserted-by":"publisher","first-page":"76","DOI":"10.1109\/TNSE.2015.2391998","volume":"1","author":"R Lambiotte","year":"2014","unstructured":"Lambiotte, R, Delvenne J-C, Barahona M (2014) Random walks, markov processes and the multiscale modular organization of complex networks. IEEE Trans Netw Sci Eng 1(2):76\u201390.","journal-title":"IEEE Trans Netw Sci Eng"},{"issue":"4","key":"210_CR17","doi-asserted-by":"publisher","first-page":"046110","DOI":"10.1103\/PhysRevE.78.046110","volume":"78","author":"A Lancichinetti","year":"2008","unstructured":"Lancichinetti, A, Fortunato S, Radicchi F (2008) Benchmark graphs for testing community detection algorithms. Phys Rev E 78(4):046110.","journal-title":"Phys Rev E"},{"issue":"6","key":"210_CR18","doi-asserted-by":"publisher","first-page":"066107","DOI":"10.1103\/PhysRevE.79.066107","volume":"79","author":"IX Leung","year":"2009","unstructured":"Leung, IX, Hui P, Lio P, Crowcroft J (2009) Towards real-time community detection in large networks. Phys Rev E 79(6):066107.","journal-title":"Phys Rev E"},{"issue":"7","key":"210_CR19","doi-asserted-by":"publisher","first-page":"1493","DOI":"10.1016\/j.physa.2009.12.019","volume":"389","author":"X Liu","year":"2010","unstructured":"Liu, X, Murata T (2010) Advanced modularity-specialized label propagation algorithm for detecting communities in networks. Phys A Stat Mech 389(7):1493\u20131500.","journal-title":"Phys A Stat Mech"},{"key":"210_CR20","doi-asserted-by":"crossref","unstructured":"Newman, ME (2004) Fast algorithm for detecting community structure in networks. Phys Rev E 69(6).","DOI":"10.1103\/PhysRevE.69.066133"},{"issue":"3","key":"210_CR21","doi-asserted-by":"publisher","first-page":"036104","DOI":"10.1103\/PhysRevE.74.036104","volume":"74","author":"ME Newman","year":"2006","unstructured":"Newman, ME (2006) Finding community structure in networks using the eigenvectors of matrices. Phys Rev E 74(3):036104.","journal-title":"Phys Rev E"},{"issue":"2","key":"210_CR22","doi-asserted-by":"publisher","first-page":"026113","DOI":"10.1103\/PhysRevE.69.026113","volume":"69","author":"ME Newman","year":"2004","unstructured":"Newman, ME, Girvan M (2004) Finding and evaluating community structure in networks. Phys Rev E 69(2):026113.","journal-title":"Phys Rev E"},{"issue":"08","key":"210_CR23","doi-asserted-by":"publisher","first-page":"P08001","DOI":"10.1088\/1742-5468\/2012\/08\/P08001","volume":"2012","author":"GK Orman","year":"2012","unstructured":"Orman, GK, Labatut V, Cherifi H (2012) Comparative evaluation of community detection algorithms: a topological approach. J Stat Mech Theory Exp 2012(08):P08001.","journal-title":"J Stat Mech Theory Exp"},{"key":"210_CR24","doi-asserted-by":"crossref","unstructured":"Par\u00e9s, F, Gasulla DG, Vilalta A, Moreno J, Ayguad\u00e9 E, Labarta J, Cort\u00e9s U, Suzumura T (2017) Fluid communities: a competitive, scalable and diverse community detection algorithm In: International Conference on Complex Networks and their Applications, 229\u2013240.. Springer.","DOI":"10.1007\/978-3-319-72150-7_19"},{"key":"210_CR25","unstructured":"Pons, P, Latapy M (2005) Computing communities in large networks using random walks In: ISCIS, vol. 3733, 284\u2013293."},{"issue":"3","key":"210_CR26","doi-asserted-by":"publisher","first-page":"036106","DOI":"10.1103\/PhysRevE.76.036106","volume":"76","author":"UN Raghavan","year":"2007","unstructured":"Raghavan, UN, Albert R, Kumara S (2007) Near linear time algorithm to detect community structures in large-scale networks. Phys Rev E 76(3):036106.","journal-title":"Phys Rev E"},{"key":"210_CR27","unstructured":"Reginaldo Filho, J, Brust MR, Ribeiro CH (2009) Consensus dynamics in a non-deterministic naming game with shared memory. arXiv preprint arXiv:0912.4553."},{"issue":"1","key":"210_CR28","doi-asserted-by":"publisher","first-page":"016110","DOI":"10.1103\/PhysRevE.74.016110","volume":"74","author":"J Reichardt","year":"2006","unstructured":"Reichardt, J, Bornholdt S (2006) Statistical mechanics of community detection. Phys Rev E 74(1):016110.","journal-title":"Phys Rev E"},{"issue":"4","key":"210_CR29","doi-asserted-by":"publisher","first-page":"1118","DOI":"10.1073\/pnas.0706851105","volume":"105","author":"M Rosvall","year":"2008","unstructured":"Rosvall, M, Bergstrom CT (2008) Maps of random walks on complex networks reveal community structure. Proc Natl Acad Sci 105(4):1118\u20131123.","journal-title":"Proc Natl Acad Sci"},{"issue":"1","key":"210_CR30","doi-asserted-by":"publisher","first-page":"109","DOI":"10.1177\/0038038588022001007","volume":"22","author":"J Scott","year":"1988","unstructured":"Scott, J (1988) Social network analysis. Sociology 22(1):109\u2013127.","journal-title":"Sociology"},{"issue":"3","key":"210_CR31","doi-asserted-by":"publisher","first-page":"036103","DOI":"10.1103\/PhysRevE.83.036103","volume":"83","author":"L \u0160ubelj","year":"2011","unstructured":"\u0160ubelj, L, Bajec M (2011) Unfolding communities in large complex networks: Combining defensive and offensive label propagation for core extraction. Phys Rev E 83(3):036103.","journal-title":"Phys Rev E"},{"key":"210_CR32","doi-asserted-by":"crossref","unstructured":"Xie, J, Szymanski BK (2011) Community detection using a neighborhood strength driven label propagation algorithm In: 2011 IEEE Network Science Workshop, 188\u2013195.. IEEE.","DOI":"10.1109\/NSW.2011.6004645"},{"key":"210_CR33","doi-asserted-by":"crossref","unstructured":"Xie, J, Szymanski BK2013. Labelrank: A stabilized label propagation algorithm for community detection in networks. IEEE, New York.","DOI":"10.1109\/NSW.2013.6609210"},{"key":"210_CR34","doi-asserted-by":"crossref","unstructured":"Xie, J, Szymanski BK, Liu X (2011) Slpa: Uncovering overlapping communities in social networks via a speaker-listener interaction dynamic process In: 2011 ieee 11th international conference on data mining workshops, 344\u2013349.. IEEE.","DOI":"10.1109\/ICDMW.2011.154"},{"key":"210_CR35","unstructured":"Uzun, TG, Da Silva-Filho RJ, Brust MR, Ribeiro CH (2011) Influence of Sha red Memory and Network Topology in the Consensus Dynamics of a Naming Game In: XXXVIII Semin\u00e1rio Integrado de Software e Hardware (SEMISH).. Anais do XXXI Congresso da Sociedade Brasileira de Computa\u00e7\u00e3o."},{"key":"210_CR36","doi-asserted-by":"publisher","first-page":"30750","DOI":"10.1038\/srep30750","volume":"6","author":"Z Yang","year":"2016","unstructured":"Yang, Z, Algesheimer R, Tessone CJ (2016) A comparative analysis of community detection algorithms on artificial networks. Sci Rep 6:30750.","journal-title":"Sci Rep"}],"container-title":["Applied Network Science"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s41109-019-0210-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s41109-019-0210-8\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s41109-019-0210-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,10,28]],"date-time":"2020-10-28T00:21:47Z","timestamp":1603844507000},"score":1,"resource":{"primary":{"URL":"https:\/\/appliednetsci.springeropen.com\/articles\/10.1007\/s41109-019-0210-8"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,10,29]]},"references-count":36,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2019,12]]}},"alternative-id":["210"],"URL":"https:\/\/doi.org\/10.1007\/s41109-019-0210-8","relation":{},"ISSN":["2364-8228"],"issn-type":[{"type":"electronic","value":"2364-8228"}],"subject":[],"published":{"date-parts":[[2019,10,29]]},"assertion":[{"value":"3 April 2019","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"10 September 2019","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"29 October 2019","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"The authors declare that they have no competing interests.","order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Competing interests"}}],"article-number":"95"}}