{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,12]],"date-time":"2026-04-12T03:00:30Z","timestamp":1775962830845,"version":"3.50.1"},"reference-count":59,"publisher":"Oxford University Press (OUP)","issue":"1","license":[{"start":{"date-parts":[[2020,2,1]],"date-time":"2020-02-01T00:00:00Z","timestamp":1580515200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/academic.oup.com\/journals\/pages\/open_access\/funder_policies\/chorus\/standard_publication_model"}],"funder":[{"name":"The Scientific and Technological Research Council of Turkey"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2020,2,1]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>Influence Maximization (IM) aims at finding the most influential users in a social network, that is, users who maximize the spread of an opinion within a certain propagation model. Previous work investigated the correlation between influence spread and nodal centrality measures to bypass more expensive IM simulations. The results were promising but incomplete, since these studies investigated the performance (i.e. the ability to identify influential users) of centrality measures only in restricted settings, for example, in undirected\/unweighted networks and\/or within a propagation model less common for IM. In this article, we first show that good results within the Susceptible-Infected-Removed propagation model for unweighted and undirected networks do not necessarily transfer to directed or weighted networks under the popular Independent Cascade (IC) propagation model. Then, we identify a set of centrality measures with good performance for weighted and directed networks within the IC model. Our main contribution is a new way to combine the centrality measures in a closed formula to yield even better results. Additionally, we also extend gravitational centrality (GC) with the proposed combined centrality measures. Our experiments on 50 real-world data sets show that our proposed centrality measures outperform well-known centrality measures and the state-of-the art GC measure significantly.<\/jats:p>","DOI":"10.1093\/comnet\/cnz048","type":"journal-article","created":{"date-parts":[[2019,12,31]],"date-time":"2019-12-31T20:10:07Z","timestamp":1577823007000},"source":"Crossref","is-referenced-by-count":15,"title":["Combined centrality measures for an improved characterization of influence spread in social networks"],"prefix":"10.1093","volume":"8","author":[{"given":"Mehmet","family":"\u015eim\u015fek","sequence":"first","affiliation":[{"name":"Faculty of Engineering, Department of Computer Engineering, D\u00fczce University, Konuralp Campus, 81620, D\u00fczce, Turkey"}]},{"given":"Henning","family":"Meyerhenke","sequence":"additional","affiliation":[{"name":"Department of Computer Science, Humboldt-Universit\u00e4t zu Berlin, Rudower Chaussee 25, Johann von Neumann-Haus, 12489, Berlin, Germany"}]}],"member":"286","published-online":{"date-parts":[[2020,2,20]]},"reference":[{"key":"2020022006093355200_B1","doi-asserted-by":"crossref","first-page":"474","DOI":"10.1046\/j.0266-4909.2003.00051.x","article-title":"Understanding and analysing activity and learning in virtual communities","volume":"19","author":"Henri,","journal-title":"J. Comput. Assist. Learn."},{"key":"2020022006093355200_B2","doi-asserted-by":"crossref","first-page":"200","DOI":"10.1016\/j.eswa.2017.10.018","article-title":"A hierarchical approach for influential node ranking in complex social networks","volume":"93","author":"Zareie,","year":"2018","journal-title":"Expert Syst. Appl."},{"key":"2020022006093355200_B3","doi-asserted-by":"crossref","first-page":"70","DOI":"10.1007\/s10618-009-0150-5","article-title":"Extracting influential nodes on a social network for information diffusion","volume":"20","author":"Kimura,","year":"2010","journal-title":"Data Mining Knowl. Discov."},{"key":"2020022006093355200_B4","doi-asserted-by":"crossref","first-page":"517","DOI":"10.1016\/j.physa.2017.05.098","article-title":"Identification of influential users by neighbors in online social networks","volume":"486","author":"Sheikhahmadi,","year":"2017","journal-title":"Physica A"},{"key":"2020022006093355200_B5","doi-asserted-by":"crossref","first-page":"345","DOI":"10.1509\/jmkr.43.3.345","article-title":"The effect of word of mouth on sales: online book reviews","volume":"43","author":"Chevalier,","year":"2006","journal-title":"J. Market. Res."},{"key":"2020022006093355200_B6","doi-asserted-by":"crossref","first-page":"179","DOI":"10.1007\/s12599-013-0263-7","article-title":"Who will lead and who will follow: identifying influential users in online social networks","volume":"5","author":"Probst,","year":"2013","journal-title":"Bus. Inf. Syst. Eng."},{"key":"2020022006093355200_B7","doi-asserted-by":"crossref","first-page":"269","DOI":"10.1140\/epjb\/e2004-00119-8","article-title":"Immunization and epidemic dynamics in complex networks","volume":"38","author":"Madar,","year":"2004","journal-title":"Eur Phys J. B"},{"key":"2020022006093355200_B8","doi-asserted-by":"crossref","first-page":"3200","DOI":"10.1103\/PhysRevLett.86.3200","article-title":"Epidemic spreading in scale-free networks","volume":"86","author":"Pastor-Satorras,","year":"2001","journal-title":"Phys. Rev. Lett."},{"key":"2020022006093355200_B9","doi-asserted-by":"crossref","first-page":"1852","DOI":"10.1109\/TKDE.2018.2807843","article-title":"Influence maximization on social graphs: a survey","volume":"30","author":"Li,","year":"2018","journal-title":"IEEE Trans. Knowl. Data Eng."},{"key":"2020022006093355200_B10","doi-asserted-by":"crossref","first-page":"137","DOI":"10.1145\/956750.956769","article-title":"Maximizing the spread of influence through a social network","volume-title":"Proceedings of the Ninth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining - KDD \u201903","author":"Kempe,","year":"2003"},{"key":"2020022006093355200_B11","doi-asserted-by":"crossref","first-page":"55","DOI":"10.1016\/j.socnet.2004.11.008","article-title":"Centrality and network flow","volume":"27","author":"Borgatti,","year":"2005","journal-title":"Soc. Netw."},{"key":"2020022006093355200_B12","doi-asserted-by":"crossref","first-page":"466","DOI":"10.1016\/j.socnet.2005.11.005","article-title":"A graph-theoretic perspective on centrality","volume":"28","author":"Borgatti,","year":"2006","journal-title":"Soc. Netw."},{"key":"2020022006093355200_B13","doi-asserted-by":"crossref","first-page":"21","DOI":"10.1007\/s10588-006-7084-x","article-title":"Identifying sets of key players in a social network","volume":"12","author":"Borgatti,","year":"2006","journal-title":"Comput. Math. Organ. Theory"},{"key":"2020022006093355200_B14","doi-asserted-by":"crossref","first-page":"892","DOI":"10.1126\/science.1165821","article-title":"Network analysis in the social sciences","volume":"323","author":"Borgatti,","year":"2009","journal-title":"Science"},{"key":"2020022006093355200_B15","doi-asserted-by":"crossref","first-page":"41","DOI":"10.1016\/j.chaos.2018.03.014","article-title":"A new centrality measure based on the negative and positive effects of clustering coefficient for identifying influential spreaders in complex networks","volume":"110","author":"Berahmand,","year":"2018","journal-title":"Chaos, Solitons Fractals"},{"key":"2020022006093355200_B16","first-page":"1","article-title":"Locating influential nodes via dynamics-sensitive centrality","volume":"6","author":"Liu,","year":"2016","journal-title":"Nature"},{"key":"2020022006093355200_B17","doi-asserted-by":"crossref","first-page":"205","DOI":"10.1016\/j.physa.2015.12.162","article-title":"Identifying influential spreaders in complex networks based on gravity formula","volume":"451","author":"Ma,","year":"2016","journal-title":"Physica A"},{"key":"2020022006093355200_B18","doi-asserted-by":"crossref","first-page":"310","DOI":"10.1016\/j.physa.2018.02.016","article-title":"Identifying influential spreaders in complex networks based on kshell hybrid method","volume":"499","author":"Namtirtha,","year":"2018","journal-title":"Physica A"},{"key":"2020022006093355200_B19","doi-asserted-by":"crossref","first-page":"635","DOI":"10.1016\/j.physa.2017.12.087","article-title":"BridgeRank: a novel fast centrality measure based on local structure of the network","volume":"496","author":"Salavati,","year":"2018","journal-title":"Physica A"},{"key":"2020022006093355200_B20","doi-asserted-by":"crossref","first-page":"388","DOI":"10.1016\/j.amc.2018.04.028","article-title":"Improved centrality indicators to characterize the nodal spreading capability in complex networks","volume":"334","author":"Wang,","year":"2018","journal-title":"Appl. Math. Comput."},{"key":"2020022006093355200_B21","doi-asserted-by":"crossref","DOI":"10.1093\/oso\/9780198805090.001.0001","volume-title":"Networks","author":"Newman,","year":"2018","edition":"2nd edn"},{"key":"2020022006093355200_B22","doi-asserted-by":"crossref","first-page":"141","DOI":"10.1016\/j.neucom.2015.11.123","article-title":"Identifying social influence in complex networks: a novel conductance eigenvector centrality model","volume":"210","author":"Li,","year":"2016","journal-title":"Neurocomputing"},{"key":"2020022006093355200_B23","doi-asserted-by":"crossref","first-page":"22","DOI":"10.1109\/MCI.2016.2572538","article-title":"An efficient memetic algorithm for influence maximization in social networks","volume":"11","author":"Gong,","year":"2016","journal-title":"IEEE Comput. Intell. Mag."},{"key":"2020022006093355200_B24","doi-asserted-by":"crossref","first-page":"600","DOI":"10.1016\/j.ins.2016.07.012","article-title":"Influence maximization in social networks based on discrete particle swarm optimization","volume":"367\u2013368","author":"Gong,","year":"2016","journal-title":"Inf. Sci."},{"key":"2020022006093355200_B25","doi-asserted-by":"crossref","first-page":"69","DOI":"10.1016\/j.neucom.2017.03.003","article-title":"Positive influence maximization in signed social networks based on simulated annealing","volume":"260","author":"Li,","year":"2017","journal-title":"Neurocomputing"},{"key":"2020022006093355200_B26","doi-asserted-by":"crossref","first-page":"e102199","DOI":"10.1371\/journal.pone.0102199","article-title":"Polarity related influence maximization in signed social networks","volume":"9","author":"Li,","year":"2014","journal-title":"PLoS One"},{"key":"2020022006093355200_B27","doi-asserted-by":"crossref","first-page":"224","DOI":"10.1016\/j.eswa.2018.07.038","article-title":"Using swarm intelligence algorithms to detect influential individuals for influence maximization in social networks","volume":"114","author":"Simsek,","year":"2018","journal-title":"Expert Syst. Appl."},{"key":"2020022006093355200_B28","doi-asserted-by":"crossref","first-page":"2320","DOI":"10.1109\/ACCESS.2017.2782814","article-title":"Influence maximization-cost minimization in social networks based on a multiobjective discrete particle swarm optimization algorithm","volume":"6","author":"Yang,","year":"2018","journal-title":"IEEE Access"},{"key":"2020022006093355200_B29","doi-asserted-by":"crossref","first-page":"199","DOI":"10.1145\/1557019.1557047","volume-title":"Proceedings of the 15th ACM SIGKDD international conference on Knowledge discovery and data mining - KDD \u201909","author":"Chen,","year":"2009"},{"key":"2020022006093355200_B30","doi-asserted-by":"crossref","first-page":"1379","DOI":"10.1109\/TPDS.2014.2320515","article-title":"Influence maximization on large-scale mobile social network: a divide-and-conquer method","volume":"26","author":"Song,","year":"2015","journal-title":"IEEE Trans. Parallel Distrib. Syst."},{"key":"2020022006093355200_B31","doi-asserted-by":"crossref","first-page":"10","DOI":"10.1016\/j.physa.2018.05.057","article-title":"Sequential seeding for spreading in complex networks: influence of the network topology","volume":"508","author":"Liu,","year":"2018","journal-title":"Physica A"},{"key":"2020022006093355200_B32","doi-asserted-by":"crossref","first-page":"996","DOI":"10.1093\/jigpal\/jzw048","article-title":"A new heuristic for influence maximization in social networks","volume":"24","author":"Nu\u00f1ez-Gonzalez,","year":"2016","journal-title":"Logic J. IGPL"},{"key":"2020022006093355200_B33","doi-asserted-by":"crossref","first-page":"112","DOI":"10.1109\/TNET.2016.2563397","article-title":"Adaptive influence maximization in dynamic social networks","volume":"25","author":"Tong,","year":"2017","journal-title":"IEEE\/ACM Trans. Netw."},{"key":"2020022006093355200_B34","doi-asserted-by":"crossref","first-page":"146","DOI":"10.1016\/j.ins.2016.08.023","article-title":"Social influence modeling using information theory in mobile social networks","volume":"379","author":"Peng,","year":"2017","journal-title":"Inf. Sci."},{"key":"2020022006093355200_B35","doi-asserted-by":"crossref","first-page":"151","DOI":"10.1109\/TCSS.2016.2627811","article-title":"Effector detection in social networks","volume":"3","author":"Tong,","year":"2016","journal-title":"IEEE Trans. Comput. Soc. Syst."},{"key":"2020022006093355200_B36","doi-asserted-by":"crossref","first-page":"e1003352","DOI":"10.1371\/journal.pcbi.1003352","article-title":"Epidemic spread on weighted networks","volume":"9","author":"Kamp,","year":"2013","journal-title":"PLoS Comput. Biol."},{"key":"2020022006093355200_B37","doi-asserted-by":"crossref","first-page":"635","DOI":"10.1016\/j.physleta.2014.01.004","article-title":"Epidemic spreading on weighted complex networks","volume":"378","author":"Sun,","year":"2014","journal-title":"Phys. Lett. A"},{"key":"2020022006093355200_B38","doi-asserted-by":"crossref","first-page":"6562","DOI":"10.1038\/s41598-018-24648-w","article-title":"Simulating SIR processes on networks using weighted shortest paths","volume":"8","author":"Toli\u0107,","year":"2018","journal-title":"Sci. Rep."},{"key":"2020022006093355200_B39","doi-asserted-by":"crossref","first-page":"289","DOI":"10.1016\/j.physa.2016.02.028","article-title":"Identify influential spreaders in complex networks, the role of neighborhood","volume":"452","author":"Liu,","year":"2016","journal-title":"Physica A"},{"key":"2020022006093355200_B40","doi-asserted-by":"crossref","first-page":"1777","DOI":"10.1016\/j.physa.2011.09.017","article-title":"Identifying influential nodes in complex networks","volume":"391","author":"Chen,","year":"2012","journal-title":"Physica A"},{"key":"2020022006093355200_B41","doi-asserted-by":"crossref","first-page":"083030","DOI":"10.1088\/1367-2630\/14\/8\/083030","article-title":"A k -shell decomposition method for weighted networks","volume":"14","author":"Garas,","year":"2012","journal-title":"N. J. Phys."},{"key":"2020022006093355200_B42","unstructured":"Leskovec, J. & Krevl,A. (2014) SNAP Datasets: Stanford Large Network Dataset Collection. http:\/\/snap. stanford.edu\/data."},{"key":"2020022006093355200_B43","doi-asserted-by":"crossref","first-page":"1343","DOI":"10.1145\/2487788.2488173","article-title":"KONECT","volume-title":"Proceedings of the 22nd International Conference on World Wide Web - WWW \u201913 Companion","author":"Kunegis,","year":"2013"},{"key":"2020022006093355200_B44","first-page":"4292","article-title":"The network data repository with interactive graph analytics and visualization","volume-title":"Proceedings of the Twenty-Ninth AAAI Conference on Artificial Intelligence","author":"Rossi,","year":"2015"},{"key":"2020022006093355200_B45","doi-asserted-by":"crossref","first-page":"508","DOI":"10.1017\/nws.2016.20","article-title":"NetworKit: a tool suite for large-scale complex network analysis","volume":"4","author":"Staudt,","year":"2016","journal-title":"Netw. Sci."},{"key":"2020022006093355200_B46","doi-asserted-by":"crossref","first-page":"1.2:1","DOI":"10.1145\/3284359","article-title":"KADABRA is an ADaptive Algorithm for Betweenness via Random Approximation","volume":"24","author":"Borassi,","year":"2019","journal-title":"J. Exp. Algorithmics"},{"key":"2020022006093355200_B47","doi-asserted-by":"crossref","first-page":"438","DOI":"10.1007\/s10618-015-0423-0","article-title":"Fast approximation of betweenness centrality through sampling","volume":"30","author":"Riondato,","year":"2016","journal-title":"Data Min. Knowl. Discov."},{"key":"2020022006093355200_B48","doi-asserted-by":"crossref","first-page":"440","DOI":"10.1038\/30918","article-title":"Collective dynamics of \u2018small-world\u2019 networks","volume":"393","author":"Watts,","year":"1998","journal-title":"Nature"},{"key":"2020022006093355200_B49","doi-asserted-by":"crossref","first-page":"167","DOI":"10.1023\/A:1009683123448","article-title":"Friendship networks through time: an actor-oriented dynamic statistical network model","volume":"5","author":"Van De Bunt,","year":"1999","journal-title":"Comput. Math. Organ. Theory"},{"key":"2020022006093355200_B50","volume-title":"Introduction to Mathematical Sociology","author":"Coleman,","year":"1964"},{"key":"2020022006093355200_B51","doi-asserted-by":"crossref","first-page":"109","DOI":"10.1016\/S0378-8733(97)00016-6","article-title":"Exploring social structure using dynamic three-dimensional color images","volume":"20","author":"Freeman,","year":"1998","journal-title":"Soc. Netw."},{"key":"2020022006093355200_B52","doi-asserted-by":"crossref","first-page":"253","DOI":"10.2307\/2785979","article-title":"The diffusion of an innovation among physicians","volume":"20","author":"Coleman,","year":"1957","journal-title":"Sociometry"},{"key":"2020022006093355200_B53","doi-asserted-by":"crossref","first-page":"261","DOI":"10.1016\/S0378-8733(01)00042-9","article-title":"Peer influence groups: identifying dense clusters in large networks","volume":"23","author":"Moody,","year":"2001","journal-title":"Soc. Netw."},{"key":"2020022006093355200_B54","article-title":"GEMSEC: graph embedding with self clustering","author":"Rozemberczki,","year":"2018","journal-title":"arXiv:1802.03997v"},{"key":"2020022006093355200_B55","first-page":"539","article-title":"Learning to discover social circles in ego networks","author":"McAuley,","year":"2012","journal-title":"NIPS\u201912 Proceedings of the 25th International Conference on Neural Information Processing Systems"},{"key":"2020022006093355200_B56","doi-asserted-by":"crossref","first-page":"658","DOI":"10.1109\/DASC.2009.130","article-title":"Bowling alone and trust decline in social network sites","author":"Massa,","year":"2009","journal-title":"2009 Eighth IEEE International Conference on Dependable, Autonomic and Secure Computing"},{"key":"2020022006093355200_B57","doi-asserted-by":"crossref","first-page":"641","DOI":"10.1145\/1772690.1772756","article-title":"Predicting positive and negative links in online social networks","volume-title":"Proceedings of the 19th International Conference on World Wide Web - WWW \u201910","author":"Leskovec,","year":"2010"},{"key":"2020022006093355200_B58","first-page":"1361","article-title":"Signed networks in social media","author":"Leskovec,","year":"2010","journal-title":"Proceedings of the 28th International Conference on Human Factors in Computing Systems - CHI \u201910"},{"key":"2020022006093355200_B59","doi-asserted-by":"crossref","first-page":"239","DOI":"10.1093\/biomet\/33.3.239","article-title":"The treatment of ties in ranking problems","volume":"33","author":"Kendall,","year":"1945","journal-title":"Biometrika"}],"container-title":["Journal of Complex Networks"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/academic.oup.com\/comnet\/article-pdf\/8\/1\/cnz048\/32527921\/cnz048.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"http:\/\/academic.oup.com\/comnet\/article-pdf\/8\/1\/cnz048\/32527921\/cnz048.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,2,14]],"date-time":"2021-02-14T17:29:31Z","timestamp":1613323771000},"score":1,"resource":{"primary":{"URL":"https:\/\/academic.oup.com\/comnet\/article\/doi\/10.1093\/comnet\/cnz048\/5741153"}},"subtitle":[],"editor":[{"given":"Jose","family":"Mateos","sequence":"additional","affiliation":[]}],"short-title":[],"issued":{"date-parts":[[2020,2,1]]},"references-count":59,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2020,2,1]]}},"URL":"https:\/\/doi.org\/10.1093\/comnet\/cnz048","relation":{},"ISSN":["2051-1329"],"issn-type":[{"value":"2051-1329","type":"electronic"}],"subject":[],"published-other":{"date-parts":[[2020,2]]},"published":{"date-parts":[[2020,2,1]]},"article-number":"cnz048"}}