{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T17:51:53Z","timestamp":1740160313846,"version":"3.37.3"},"reference-count":56,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2021,10,3]],"date-time":"2021-10-03T00:00:00Z","timestamp":1633219200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2021,10,3]],"date-time":"2021-10-03T00:00:00Z","timestamp":1633219200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100000780","name":"European Commission","doi-asserted-by":"publisher","award":["739574"],"award-info":[{"award-number":["739574"]}],"id":[{"id":"10.13039\/501100000780","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100004329","name":"Javna Agencija za Raziskovalno Dejavnost RS","doi-asserted-by":"publisher","award":["N1-0093","J2-2504"],"award-info":[{"award-number":["N1-0093","J2-2504"]}],"id":[{"id":"10.13039\/501100004329","id-type":"DOI","asserted-by":"publisher"}]},{"name":"Lulea University of Technology"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Soc. Netw. Anal. Min."],"published-print":{"date-parts":[[2021,12]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>Both community detection and influence maximization are well-researched fields of network science. Here, we investigate how several popular community detection algorithms can be used as part of a heuristic approach to influence maximization. The heuristic is based on the community value, a node-based metric defined on the outputs of overlapping community detection algorithms. This metric is used to select nodes as high influence candidates for expanding the set of influential nodes. Our aim in this paper is twofold. First, we evaluate the performance of eight frequently used overlapping community detection algorithms on this specific task to show how much improvement can be gained compared to the originally proposed method of Kempe et al. Second, selecting the community detection algorithm(s) with the best performance, we propose a variant of the influence maximization heuristic with significantly reduced runtime, at the cost of slightly reduced quality of the output. We use both artificial benchmarks and real-life networks to evaluate the performance of our approach.<\/jats:p>","DOI":"10.1007\/s13278-021-00804-5","type":"journal-article","created":{"date-parts":[[2021,10,4]],"date-time":"2021-10-04T22:10:33Z","timestamp":1633385433000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["Evaluating the role of community detection in improving influence maximization heuristics"],"prefix":"10.1007","volume":"11","author":[{"given":"L\u00e1szl\u00f3","family":"Hajdu","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Mikl\u00f3s","family":"Kr\u00e9sz","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-0322-8698","authenticated-orcid":false,"given":"Andr\u00e1s","family":"B\u00f3ta","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2021,10,3]]},"reference":[{"issue":"14","key":"804_CR1","doi-asserted-by":"publisher","first-page":"1760","DOI":"10.1093\/bioinformatics\/btm257","volume":"23","author":"G Bagler","year":"2007","unstructured":"Bagler G, Sinha S (2007) Assortative mixing in protein contact networks and protein folding kinetics. Bioinformatics 23(14):1760\u20131767","journal-title":"Bioinformatics"},{"issue":"6","key":"804_CR2","doi-asserted-by":"publisher","first-page":"e501","DOI":"10.1371\/journal.pone.0000501","volume":"2","author":"D Balcan","year":"2007","unstructured":"Balcan D et al (2007) The information coded in the yeast response elements accounts for most of the topological properties of its transcriptional regulation network. PLoS One 2(6):e501","journal-title":"PLoS One"},{"issue":"5916","key":"804_CR3","doi-asserted-by":"publisher","first-page":"892","DOI":"10.1126\/science.1165821","volume":"323","author":"SP Borgatti","year":"2009","unstructured":"Borgatti SP, Mehra A, Brass DJ, Labianca G (2009) Network analysis in the social sciences. Science 323(5916):892\u2013895","journal-title":"Science"},{"key":"804_CR4","doi-asserted-by":"crossref","unstructured":"Bridgwater A, B\u00f3ta A (2021) Identifying regions most likely to contribute to an epidemic outbreak in a human mobility network. In: Proceedings of the 2021 Swedish artificial intelligence society workshop (SAIS), pp. 1-4, IEEE","DOI":"10.1109\/SAIS53221.2021.9483971"},{"issue":"1\u20137","key":"804_CR5","doi-asserted-by":"publisher","first-page":"107","DOI":"10.1016\/S0169-7552(98)00110-X","volume":"30","author":"S Brin","year":"1998","unstructured":"Brin S, Page L (1998) The anatomy of a large-scale hypertextual Web search engine (PDF). Comput Netw ISDN Syst 30(1\u20137):107\u2013117","journal-title":"Comput Netw ISDN Syst"},{"issue":"2","key":"804_CR6","doi-asserted-by":"publisher","first-page":"345","DOI":"10.1007\/s10100-014-0375-2","volume":"23","author":"A B\u00f3ta","year":"2015","unstructured":"B\u00f3ta A, Csernenszky A, Gy\u0151rffy L, Kov\u00e1cs G, Kr\u00e9sz M, Pluh\u00e1r A (2015) Applications of the inverse infection problem on bank transaction networks. Cent Eur J Oper Res 23(2):345\u2013356","journal-title":"Cent Eur J Oper Res"},{"key":"804_CR7","doi-asserted-by":"crossref","unstructured":"B\u00f3ta A, Kov\u00e1cs L (2014) The community structure of word association graphs. In: Proceedings of the 9th international conference on applied informatics (Vol. 1, pp. pp-113). Eger, Hungary","DOI":"10.14794\/ICAI.9.2014.1.113"},{"key":"804_CR8","unstructured":"CFinder, http:\/\/www.cfinder.org\/"},{"key":"804_CR9","unstructured":"COPRA, https:\/\/gregory.org\/research\/networks\/software\/copra.html"},{"key":"804_CR10","doi-asserted-by":"crossref","unstructured":"Chen W, Wang C, Wang Y (2010) Scalable influence maximization for prevalent viral marketing in large-scale social networks. In: Proceedings of the 16th ACM SIGKDD international conference on Knowledge discovery and data mining (pp 1029-1038)","DOI":"10.1145\/1835804.1835934"},{"issue":"7","key":"804_CR11","doi-asserted-by":"publisher","first-page":"2015","DOI":"10.1073\/pnas.0510525103","volume":"103","author":"V Colizza","year":"2006","unstructured":"Colizza V, Barrat A, Barth\u00e9lemy M, Vespignani A (2006) The role of the airline transportation network in the prediction and predictability of global epidemics. Proc Natl Acad Sci 103(7):2015\u20132020","journal-title":"Proc Natl Acad Sci"},{"issue":"3","key":"804_CR12","doi-asserted-by":"publisher","first-page":"329","DOI":"10.1080\/00018732.2011.572452","volume":"60","author":"LDF Costa","year":"2011","unstructured":"Costa LDF et al (2011) Analyzing and modeling real-world phenomena with complex networks: a survey of applications. Adv Phys 60(3):329\u2013412","journal-title":"Adv Phys"},{"issue":"20","key":"804_CR13","doi-asserted-by":"publisher","first-page":"3846","DOI":"10.1093\/bioinformatics\/bti625","volume":"21","author":"L Diambra","year":"2005","unstructured":"Diambra L, Costa LDF (2005) Complex networks approach to gene expression driven phenotype imaging. Bioinformatics 21(20):3846\u20133851","journal-title":"Bioinformatics"},{"key":"804_CR14","volume-title":"Generalized blockmodeling","author":"P Doreian","year":"2005","unstructured":"Doreian P, Batagelj V, Ferligoj A (2005) Generalized blockmodeling, vol 25. Cambridge University Press, Cambridge"},{"issue":"2","key":"804_CR15","first-page":"021025","volume":"1","author":"AV Esquivel","year":"2011","unstructured":"Esquivel AV, Rosvall M (2011) Compression of flow can reveal overlapping-module organization in networks. Phys Rev X 1(2):021025","journal-title":"Phys Rev X"},{"issue":"3","key":"804_CR16","doi-asserted-by":"publisher","first-page":"75","DOI":"10.1016\/j.physrep.2009.11.002","volume":"486","author":"S Fortunato","year":"2010","unstructured":"Fortunato S (2010) Community detection in graphs. Phys Rep 486(3):75\u2013174","journal-title":"Phys Rep"},{"issue":"1","key":"804_CR17","doi-asserted-by":"publisher","first-page":"35","DOI":"10.2307\/3033543","volume":"40","author":"Linton Freeman","year":"1977","unstructured":"Freeman Linton (1977) A set of measures of centrality based upon betweenness. Sociometry 40(1):35\u201341","journal-title":"Sociometry"},{"issue":"3","key":"804_CR18","doi-asserted-by":"publisher","first-page":"215","DOI":"10.1016\/0378-8733(78)90021-7","volume":"1","author":"Linton C Freeman","year":"1979","unstructured":"Freeman Linton C (1979) Centrality in social networks conceptual clarification. Soc Netw 1(3):215\u2013239","journal-title":"Soc Netw"},{"key":"804_CR19","unstructured":"GCE, https:\/\/sites.google.com\/site\/greedycliqueexpansion\/"},{"issue":"1","key":"804_CR20","doi-asserted-by":"publisher","first-page":"e0006194","DOI":"10.1371\/journal.pntd.0006194","volume":"12","author":"LM Gardner","year":"2018","unstructured":"Gardner LM, B\u00f3ta A, Gangavarapu K, Kraemer MU, Grubaugh ND (2018) Inferring the risk factors behind the geographical spread and transmission of Zika in the Americas. PLoS Negl Trop Dis 12(1):e0006194","journal-title":"PLoS Negl Trop Dis"},{"issue":"6","key":"804_CR21","doi-asserted-by":"publisher","first-page":"1420","DOI":"10.1086\/226707","volume":"83","author":"M Granovetter","year":"1978","unstructured":"Granovetter M (1978) Threshold models of collective behavior. Am J Sociol 83(6):1420\u20131443","journal-title":"Am J Sociol"},{"key":"804_CR22","unstructured":"Graph-tool https:\/\/graph-tool.skewed.de\/"},{"issue":"03n04","key":"804_CR23","doi-asserted-by":"publisher","first-page":"1250054","DOI":"10.1142\/S0219525912500543","volume":"15","author":"P Gravino","year":"2012","unstructured":"Gravino P, Servedio VD, Barrat A, Loreto V (2012) Complex structures and semantics in free word association. Adv Complex Syst 15(03n04):1250054","journal-title":"Adv Complex Syst"},{"issue":"10","key":"804_CR24","doi-asserted-by":"publisher","first-page":"103018","DOI":"10.1088\/1367-2630\/12\/10\/103018","volume":"12","author":"S Gregory","year":"2010","unstructured":"Gregory S (2010) Finding overlapping communities in networks by label propagation. New J Phys 12(10):103018","journal-title":"New J Phys"},{"key":"804_CR25","doi-asserted-by":"crossref","unstructured":"Hajdu L, Kr\u00e9sz M, B\u00f3ta A (2018) Community based influence maximization in the Independent Cascade Model. In: 2018 Federated Conference on Computer Science and Information Systems (FedCSIS) (pp. 237-243) IEEE","DOI":"10.15439\/2018F201"},{"key":"804_CR26","unstructured":"InfoMap http:\/\/www.mapequation.org"},{"key":"804_CR27","doi-asserted-by":"crossref","unstructured":"Jung K, Heo W, Chen W (2012) Irie: Scalable and robust influence maximization in social networks. In: 2012 IEEE 12th international conference on data mining (pp 918-923)","DOI":"10.1109\/ICDM.2012.79"},{"key":"804_CR28","doi-asserted-by":"crossref","unstructured":"Kempe D, Kleinberg J, Tardos E (2003) Maximizing the spread of influence though a social network. Proceedings of the 9th ACM SIGKDD international conference on knowledge discovery and data mining, ACM (2003) 137\u2013146","DOI":"10.1145\/956750.956769"},{"key":"804_CR29","doi-asserted-by":"crossref","unstructured":"Kempe D, Kleinberg J, Tardos \u00c9 (2005) Influential nodes in a diffusion model for social networks. In: international colloquium on automata, languages, and programming (pp 1127-1138). Springer, Berlin, Heidelberg","DOI":"10.1007\/11523468_91"},{"issue":"1","key":"804_CR30","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/s13278-020-00680-5","volume":"10","author":"H Kingi","year":"2020","unstructured":"Kingi H, Wang LAD, Shafer T, Huynh M, Trinh M, Heuser A et al (2020) A numerical evaluation of the accuracy of influence maximization algorithms. Soc Netw Anal Min 10(1):1\u201310","journal-title":"Soc Netw Anal Min"},{"key":"804_CR31","volume-title":"Encyclopedia of social network analysis and mining","author":"M Kr\u00e9sz","year":"2017","unstructured":"Kr\u00e9sz M, Pluh\u00e1r A (2017) Economic network analysis based on infection models. In: Alhajj R, Rokne J (eds) Encyclopedia of social network analysis and mining. Springer, New York"},{"issue":"1","key":"804_CR32","doi-asserted-by":"publisher","first-page":"016118","DOI":"10.1103\/PhysRevE.80.016118","volume":"80","author":"A Lancichinetti","year":"2009","unstructured":"Lancichinetti A, Fortunato S (2009) Benchmarks for testing community detection algorithms on directed and weighted graphs with overlapping communities. Phys Rev E 80(1):016118","journal-title":"Phys Rev E"},{"issue":"5","key":"804_CR33","doi-asserted-by":"publisher","first-page":"056117","DOI":"10.1103\/PhysRevE.80.056117","volume":"80","author":"A Lancichinetti","year":"2009","unstructured":"Lancichinetti A, Fortunato S (2009) Community detection algorithms: a comparative analysis. Phys Rev E 80(5):056117","journal-title":"Phys Rev E"},{"issue":"4","key":"804_CR34","doi-asserted-by":"publisher","first-page":"e18961","DOI":"10.1371\/journal.pone.0018961","volume":"6","author":"A Lancichinetti","year":"2011","unstructured":"Lancichinetti A, Radicchi F, Ramasco JJ, Fortunato S (2011) Finding statistically significant communities in networks. PloS One 6(4):e18961","journal-title":"PloS One"},{"key":"804_CR35","unstructured":"Lee C, Reid F, McDaid A, Hurley N (2010) Detecting highly overlapping community structure by greedy clique expansion. arXiv preprint arXiv:1002.1827"},{"key":"804_CR36","doi-asserted-by":"crossref","unstructured":"Leskovec J, Kleinberg J, Faloutsos C (2007) Graph Evolution: densification and Shrinking Diameters. ACM transactions on knowledge discovery from data (ACM TKDD) 1(1)","DOI":"10.1145\/1217299.1217301"},{"key":"804_CR37","unstructured":"Leskovec J, Krevl A (2014) SNAP Datasets: stanford large network dataset collection, http:\/\/snap.stanford.edu\/data"},{"issue":"10","key":"804_CR38","doi-asserted-by":"publisher","first-page":"1852","DOI":"10.1109\/TKDE.2018.2807843","volume":"30","author":"Y Li","year":"2018","unstructured":"Li Y, Fan J, Wang Y, Tan KL (2018) Influence maximization on social graphs: a survey. IEEE Trans Knowl Data Eng 30(10):1852\u20131872","journal-title":"IEEE Trans Knowl Data Eng"},{"key":"804_CR39","doi-asserted-by":"crossref","unstructured":"Liu Q, Xiang B, Chen E, Xiong H, Tang F, et al (2014) Influence maximization over large-scale social networks: a bounded linear approach. In: Proceedings of the 23rd ACM international conference on conference on information and knowledge management, pp 171-180","DOI":"10.1145\/2661829.2662009"},{"key":"804_CR40","unstructured":"MOSES https:\/\/sites.google.com\/site\/aaronmcdaid\/downloads"},{"issue":"1","key":"804_CR41","doi-asserted-by":"publisher","first-page":"193","DOI":"10.1007\/s100510050929","volume":"11","author":"RN Mantegna","year":"1999","unstructured":"Mantegna RN (1999) Hierarchical structure in financial markets. Eur Phys J B-Condens Matter Complex Syst 11(1):193\u2013197","journal-title":"Eur Phys J B-Condens Matter Complex Syst"},{"key":"804_CR42","doi-asserted-by":"crossref","unstructured":"McDaid A, Hurley N (2010) Detecting highly overlapping communities with model-based overlapping seed expansion. In: 2010 international conference on advances in social networks analysis and mining (pp 112-119) IEEE","DOI":"10.1109\/ASONAM.2010.77"},{"issue":"2","key":"804_CR43","doi-asserted-by":"publisher","first-page":"167","DOI":"10.1137\/S003614450342480","volume":"45","author":"ME Newman","year":"2003","unstructured":"Newman ME (2003) The structure and function of complex networks. SIAM Rev 45(2):167\u2013256","journal-title":"SIAM Rev"},{"key":"804_CR44","unstructured":"OSLOM, http:\/\/www.oslom.org\/"},{"issue":"7043","key":"804_CR45","doi-asserted-by":"publisher","first-page":"814","DOI":"10.1038\/nature03607","volume":"435","author":"G Palla","year":"2005","unstructured":"Palla G, Der\u00e9nyi I, Farkas I, Vicsek T (2005) Uncovering the overlapping community structure of complex networks in nature and society. Nature 435(7043):814\u2013818","journal-title":"Nature"},{"issue":"3","key":"804_CR46","doi-asserted-by":"publisher","first-page":"925","DOI":"10.1103\/RevModPhys.87.925","volume":"87","author":"R Pastor-Satorras","year":"2015","unstructured":"Pastor-Satorras R, Castellano C, Van Mieghem P, Vespignani A (2015) Epidemic processes in complex networks. Rev Mod Phys 87(3):925","journal-title":"Rev Mod Phys"},{"issue":"1","key":"804_CR47","first-page":"011033","volume":"5","author":"TP Peixoto","year":"2015","unstructured":"Peixoto TP (2015) Model selection and hypothesis testing for large-scale network models with overlapping groups. Phys Rev X 5(1):011033","journal-title":"Phys Rev X"},{"issue":"3","key":"804_CR48","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"},{"issue":"4","key":"804_CR49","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"},{"key":"804_CR50","unstructured":"SLPA, https:\/\/github.com\/sebastianliu\/SLPA-community-detection"},{"key":"804_CR51","doi-asserted-by":"crossref","unstructured":"Serrat O (2017) Social network analysis. In Knowledge solutions (pp 39-43). Springer, Singapore","DOI":"10.1007\/978-981-10-0983-9_9"},{"issue":"1","key":"804_CR52","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/s13278-015-0305-x","volume":"5","author":"A Srivastava","year":"2015","unstructured":"Srivastava A, Chelmis C, Prasanna VK (2015) The unified model of social influence and its application in influence maximization. Soc Netw Anal Min 5(1):1\u201315","journal-title":"Soc Netw Anal Min"},{"issue":"1","key":"804_CR53","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/s13278-018-0489-y","volume":"8","author":"J Tang","year":"2018","unstructured":"Tang J, Tang X, Yuan J (2018) An efficient and effective hop-based approach for influence maximization in social networks. Soc Netw Anal Min 8(1):1\u201319","journal-title":"Soc Netw Anal Min"},{"issue":"2","key":"804_CR54","doi-asserted-by":"publisher","first-page":"176","DOI":"10.1038\/ng1242","volume":"35","author":"S Wuchty","year":"2003","unstructured":"Wuchty S, Oltvai ZN, Barab\u00e1si AL (2003) Evolutionary conservation of motif constituents in the yeast protein interaction network. Nat Genet 35(2):176\u2013179","journal-title":"Nat Genet"},{"key":"804_CR55","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 (pp. 344-349), IEEE","DOI":"10.1109\/ICDMW.2011.154"},{"key":"804_CR56","doi-asserted-by":"crossref","unstructured":"Yang J, Leskovec, J (2012) Defining and evaluating network communities based on ground-truth. ICDM","DOI":"10.1145\/2350190.2350193"}],"container-title":["Social Network Analysis and Mining"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s13278-021-00804-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s13278-021-00804-5\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s13278-021-00804-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,11,20]],"date-time":"2021-11-20T14:33:56Z","timestamp":1637418836000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s13278-021-00804-5"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,10,3]]},"references-count":56,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2021,12]]}},"alternative-id":["804"],"URL":"https:\/\/doi.org\/10.1007\/s13278-021-00804-5","relation":{},"ISSN":["1869-5450","1869-5469"],"issn-type":[{"type":"print","value":"1869-5450"},{"type":"electronic","value":"1869-5469"}],"subject":[],"published":{"date-parts":[[2021,10,3]]},"assertion":[{"value":"4 February 2021","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"22 August 2021","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"15 September 2021","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"3 October 2021","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors declare that they have no conflict of interest.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}}],"article-number":"91"}}