{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,30]],"date-time":"2026-03-30T17:50:21Z","timestamp":1774893021609,"version":"3.50.1"},"reference-count":46,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2023,9,25]],"date-time":"2023-09-25T00:00:00Z","timestamp":1695600000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2023,9,25]],"date-time":"2023-09-25T00:00:00Z","timestamp":1695600000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100001691","name":"Japan Society for the Promotion of Science","doi-asserted-by":"publisher","award":["JP 21H04595"],"award-info":[{"award-number":["JP 21H04595"]}],"id":[{"id":"10.13039\/501100001691","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Appl Netw Sci"],"abstract":"<jats:title>Abstract<\/jats:title><jats:p>Influence maximization (IM) is the task of finding the most important nodes in order to maximize the spread of influence or information on a network. This task is typically studied on static or temporal networks where the complete topology of the graph is known. In practice, however, the seed nodes must be selected before observing the future evolution of the network. In this work, we consider this realistic <jats:italic>ex ante<\/jats:italic> setting where <jats:italic>p<\/jats:italic> time steps of the network have been observed before selecting the seed nodes. Then the influence is calculated after the network continues to evolve for a total of <jats:inline-formula><jats:alternatives><jats:tex-math>$$T&gt;p$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mi>T<\/mml:mi>\n                    <mml:mo>&gt;<\/mml:mo>\n                    <mml:mi>p<\/mml:mi>\n                  <\/mml:mrow>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula> time steps. We address this problem by using statistical, non-negative matrix factorization and graph neural networks link prediction algorithms to predict the future evolution of the network, and then apply existing influence maximization algorithms on the predicted networks. Additionally, the output of the link prediction methods can be used to construct novel IM algorithms. We apply the proposed methods to eight real-world and synthetic networks to compare their performance using the susceptible-infected (SI) diffusion model. We demonstrate that it is possible to construct quality seed sets in the <jats:italic>ex ante<\/jats:italic> setting as we achieve influence spread within 87% of the optimal spread on seven of eight network. In many settings, choosing seed nodes based only historical edges provides results comparable to the results treating the future graph snapshots as known. The proposed heuristics based on the link prediction model are also some of the best-performing methods. These findings indicate that, for these eight networks under the SI model, the latent process which determines the most influential nodes may not have large temporal variation. Thus, knowing the future status of the network is not necessary to obtain good results for <jats:italic>ex ante<\/jats:italic> IM.<\/jats:p>","DOI":"10.1007\/s41109-023-00594-z","type":"journal-article","created":{"date-parts":[[2023,9,25]],"date-time":"2023-09-25T16:02:04Z","timestamp":1695657724000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":10,"title":["Link prediction for ex ante influence maximization on temporal networks"],"prefix":"10.1007","volume":"8","author":[{"given":"Eric","family":"Yanchenko","sequence":"first","affiliation":[]},{"given":"Tsuyoshi","family":"Murata","sequence":"additional","affiliation":[]},{"given":"Petter","family":"Holme","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2023,9,25]]},"reference":[{"issue":"1","key":"594_CR1","doi-asserted-by":"publisher","first-page":"19","DOI":"10.26599\/BDMA.2017.9020002","volume":"1","author":"NM Ahmed","year":"2018","unstructured":"Ahmed NM, Chen L, Wang Y, Li B, Li Y, Liu W (2018) DeepEye: link prediction in dynamic networks based on non-negative matrix factorization. Big Data Min Anal 1(1):19\u201333","journal-title":"Big Data Min Anal"},{"issue":"1","key":"594_CR2","doi-asserted-by":"publisher","first-page":"83","DOI":"10.1016\/0025-5564(94)90025-6","volume":"124","author":"LJ Allen","year":"1994","unstructured":"Allen LJ (1994) Some discrete-time SI, SIR, and SIS epidemic models. Math Biosci 124(1):83\u2013105","journal-title":"Math Biosci"},{"key":"594_CR3","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\u20131038","DOI":"10.1145\/1835804.1835934"},{"key":"594_CR4","doi-asserted-by":"crossref","unstructured":"Chen W, Wang Y, Yang S (2009) Efficient influence maximization in social networks. In: Proceedings of the 15th ACM SIGKDD international conference on knowledge discovery and data mining, pp 199\u2013208","DOI":"10.1145\/1557019.1557047"},{"key":"594_CR5","doi-asserted-by":"crossref","unstructured":"Chen W, Yuan Y, Zhang L(2010) Scalable influence maximization in social networks under the linear threshold model. In: 2010 IEEE international conference on data mining, pp 88\u201397. IEEE","DOI":"10.1109\/ICDM.2010.118"},{"key":"594_CR6","doi-asserted-by":"publisher","first-page":"213","DOI":"10.1007\/s00354-019-00065-z","volume":"38","author":"A Divakaran","year":"2020","unstructured":"Divakaran A, Mohan A (2020) Temporal link prediction: a survey. New Gener Comput 38:213\u2013258","journal-title":"New Gener Comput"},{"key":"594_CR7","doi-asserted-by":"publisher","first-page":"255","DOI":"10.1007\/s00779-005-0046-3","volume":"10","author":"N Eagle","year":"2006","unstructured":"Eagle N, Pentland A (2006) Reality mining: sensing complex social systems. Pers Ubiquitous Comput 10:255\u2013268","journal-title":"Pers Ubiquitous Comput"},{"key":"594_CR8","unstructured":"Erd\u00f6s P, Renyi A (1959) On random graphs. Publicationes Mathematicae Debrecen, pp 260\u2013297"},{"issue":"4","key":"594_CR9","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevE.102.042307","volume":"102","author":"\u015e Erkol","year":"2020","unstructured":"Erkol \u015e, Mazzilli D, Radicchi F (2020) Influence maximization on temporal networks. Phys Rev E 102(4):042307","journal-title":"Phys Rev E"},{"key":"594_CR10","doi-asserted-by":"crossref","unstructured":"Gayraud NT, Pitoura E, Tsaparas P (2015) Diffusion maximization in evolving social networks. In: Proceedings of the 2015 ACM conference on online social networks, pp 125\u2013135","DOI":"10.1145\/2817946.2817965"},{"issue":"3","key":"594_CR11","doi-asserted-by":"publisher","first-page":"326","DOI":"10.1017\/nws.2015.10","volume":"3","author":"M G\u00e9nois","year":"2015","unstructured":"G\u00e9nois M, Vestergaard CL, Fournet J, Panisson A, Bonmarin I, Barrat A (2015) Data on face-to-face contacts in an office building suggest a low-cost vaccination strategy based on community linkers. Netw Sci 3(3):326\u2013347","journal-title":"Netw Sci"},{"key":"594_CR12","doi-asserted-by":"crossref","unstructured":"Goyal A, Lu W, Lakshmanan LV (2011) Celf++ optimizing the greedy algorithm for influence maximization in social networks. In: Proceedings of the 20th international conference companion on world wide web, pp 47\u201348","DOI":"10.1145\/1963192.1963217"},{"key":"594_CR13","doi-asserted-by":"crossref","unstructured":"Goyal A, Lu W, Lakshmanan LV (2011) Simpath: an efficient algorithm for influence maximization under the linear threshold model. In: 2011 IEEE 11th international conference on data mining, pp 211\u2013220. IEEE","DOI":"10.1109\/ICDM.2011.132"},{"key":"594_CR14","doi-asserted-by":"crossref","unstructured":"Grover A, Leskovec J (2016) node2vec: scalable feature learning for networks. In: Proceedings of the 22nd ACM SIGKDD international conference on knowledge discovery and data mining, pp 855\u2013864","DOI":"10.1145\/2939672.2939754"},{"issue":"4","key":"594_CR15","doi-asserted-by":"publisher","DOI":"10.1002\/ett.3054","volume":"28","author":"M Han","year":"2017","unstructured":"Han M, Yan M, Cai Z, Li Y, Cai X, Yu J (2017) Influence maximization by probing partial communities in dynamic online social networks. Trans Emerg Telecommun Technol 28(4):e3054","journal-title":"Trans Emerg Telecommun Technol"},{"issue":"3","key":"594_CR16","doi-asserted-by":"publisher","first-page":"97","DOI":"10.1016\/j.physrep.2012.03.001","volume":"519","author":"P Holme","year":"2012","unstructured":"Holme P, Saram\u00e4ki J (2012) Temporal networks. Phys Rep 519(3):97\u2013125","journal-title":"Phys Rep"},{"key":"594_CR17","doi-asserted-by":"crossref","unstructured":"Kempe D, Kleinberg J, Tardos \u00c9 (2003) Maximizing the spread of influence through a social network. In: Proceedings of the 9th ACM SIGKDD international conference on knowledge discovery and data mining, pp 137\u2013146","DOI":"10.1145\/956750.956769"},{"key":"594_CR18","doi-asserted-by":"publisher","DOI":"10.1016\/j.physa.2020.124289","volume":"553","author":"A Kumar","year":"2020","unstructured":"Kumar A, Singh SS, Singh K, Biswas B (2020) Link prediction techniques, applications, and performance: a survey. Physica A 553:124289","journal-title":"Physica A"},{"issue":"5","key":"594_CR19","doi-asserted-by":"publisher","first-page":"0036439","DOI":"10.1371\/journal.pone.0036439","volume":"7","author":"S Lee","year":"2012","unstructured":"Lee S, Rocha LEC, Liljeros F, Holme P (2012) Exploiting temporal network structures of human interaction to effectively immunize populations. PLoS ONE 7(5):0036439","journal-title":"PLoS ONE"},{"key":"594_CR20","doi-asserted-by":"crossref","unstructured":"Leskovec J, Krause A, Guestrin C, Faloutsos C, VanBriesen J, Glance N (2007) Cost-effective outbreak detection in networks. In: Proceedings of the 13th ACM SIGKDD international conference on knowledge discovery and data mining, pp 420\u2013429","DOI":"10.1145\/1281192.1281239"},{"key":"594_CR21","doi-asserted-by":"crossref","unstructured":"Li X, Du N, Li H, Li K, Gao J, Zhang A (2014) A deep learning approach to link prediction in dynamic networks. In: Proceedings of the 2014 SIAM international conference on data mining, pp 289\u2013297. SIAM","DOI":"10.1137\/1.9781611973440.33"},{"issue":"10","key":"594_CR22","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 K-L (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":"594_CR23","doi-asserted-by":"crossref","unstructured":"Liben-Nowell D, Kleinberg J (2003) The link prediction problem for social networks. In: Proceedings of the 12th international conference on information and knowledge management, pp 556\u2013559","DOI":"10.1145\/956863.956972"},{"key":"594_CR24","doi-asserted-by":"publisher","first-page":"42052","DOI":"10.1109\/ACCESS.2019.2894155","volume":"7","author":"Q Liqing","year":"2019","unstructured":"Liqing Q, Jinfeng Y, Xin F, Wei J, Wenwen G (2019) Analysis of influence maximization in temporal social networks. IEEE Access 7:42052\u201342062","journal-title":"IEEE Access"},{"key":"594_CR25","doi-asserted-by":"crossref","unstructured":"Liu Q, Xiang B, Chen E, Xiong H, Tang F Yu J\u00a0X (2014) Influence maximization over large-scale social networks: a bounded linear approach. In: Proceedings of the 23rd ACM international conference on information and knowledge management, pp 171\u2013180","DOI":"10.1145\/2661829.2662009"},{"issue":"6","key":"594_CR26","doi-asserted-by":"publisher","first-page":"1150","DOI":"10.1016\/j.physa.2010.11.027","volume":"390","author":"L L\u00fc","year":"2011","unstructured":"L\u00fc L, Zhou T (2011) Link prediction in complex networks: a survey. Physica A 390(6):1150\u20131170","journal-title":"Physica A"},{"issue":"9","key":"594_CR27","doi-asserted-by":"publisher","DOI":"10.1371\/journal.pone.0136497","volume":"10","author":"R Mastrandrea","year":"2015","unstructured":"Mastrandrea R, Fournet J, Barrat A (2015) Contact patterns in a high school: a comparison between data collected using wearable sensors, contact diaries and friendship surveys. PLoS ONE 10(9):e0136497","journal-title":"PLoS ONE"},{"issue":"3","key":"594_CR28","doi-asserted-by":"publisher","first-page":"213","DOI":"10.1007\/s00354-014-0402-9","volume":"32","author":"R Michalski","year":"2014","unstructured":"Michalski R, Kajdanowicz T, Br\u00f3dka P, Kazienko P (2014) Seed selection for spread of influence in social networks: temporal vs. static approach. New Gener Comput 32(3):213\u2013235","journal-title":"New Gener Comput"},{"key":"594_CR29","doi-asserted-by":"crossref","unstructured":"Michalski R, Palus S, Kazienko P (2011) Matching organizational structure and social network extracted from email communication. In: Business information systems: 14th international conference, BIS 2011, Pozna\u0144, Poland, June 15\u201317. Proceedings 14, pp 197\u2013206. Springer","DOI":"10.1007\/978-3-642-21863-7_17"},{"issue":"1","key":"594_CR30","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1186\/s40649-018-0056-8","volume":"5","author":"T Murata","year":"2018","unstructured":"Murata T, Koga H (2018) Extended methods for influence maximization in dynamic networks. Comput Soc Netw 5(1):1\u201321","journal-title":"Comput Soc Netw"},{"key":"594_CR31","doi-asserted-by":"publisher","first-page":"265","DOI":"10.1007\/BF01588971","volume":"14","author":"GL Nemhauser","year":"1978","unstructured":"Nemhauser GL, Wolsey LA, Fisher ML (1978) An analysis of approximations for maximizing submodular set functions\u2014i. Math Program 14:265\u2013294","journal-title":"Math Program"},{"key":"594_CR32","doi-asserted-by":"publisher","first-page":"91","DOI":"10.1007\/978-3-319-16112-9_9","volume-title":"Complex networks VI","author":"S Osawa","year":"2015","unstructured":"Osawa S, Murata T (2015) Selecting seed nodes for influence maximization in dynamic networks. In: Mangioni G, Simini F, Uzzo SM, Wang D (eds) Complex networks VI. Springer, Berlin, pp 91\u201398"},{"issue":"5","key":"594_CR33","doi-asserted-by":"publisher","first-page":"911","DOI":"10.1002\/asi.21015","volume":"60","author":"P Panzarasa","year":"2009","unstructured":"Panzarasa P, Opsahl T, Carley KM (2009) Patterns and dynamics of users\u2019 behavior and interaction: network analysis of an online community. J Am Soc Inform Sci Technol 60(5):911\u2013932","journal-title":"J Am Soc Inform Sci Technol"},{"key":"594_CR34","first-page":"5363","volume":"34","author":"A Pareja","year":"2020","unstructured":"Pareja A, Domeniconi G, Chen J, Ma T, Suzumura T, Kanezashi H, Kaler T, Schardl T, Leiserson C (2020) Evolvegcn: evolving graph convolutional networks for dynamic graphs. Proc AAAI Conf Artif Intell 34:5363\u20135370","journal-title":"Proc AAAI Conf Artif Intell"},{"key":"594_CR35","unstructured":"Robinson J, Chuang C-Y, Sra S, Jegelka S (2020) Contrastive learning with hard negative samples. arXiv:2010.04592"},{"issue":"1","key":"594_CR36","doi-asserted-by":"publisher","first-page":"315","DOI":"10.1038\/s41597-019-0325-x","volume":"6","author":"P Sapiezynski","year":"2019","unstructured":"Sapiezynski P, Stopczynski A, Lassen DD, Lehmann S (2019) Interaction data from the copenhagen networks study. Sci Data 6(1):315","journal-title":"Sci Data"},{"key":"594_CR37","doi-asserted-by":"publisher","first-page":"151","DOI":"10.1016\/j.neucom.2021.04.084","volume":"453","author":"AK Singh","year":"2021","unstructured":"Singh AK, Kailasam L (2021) Link prediction-based influence maximization in online social networks. Neurocomputing 453:151\u2013163","journal-title":"Neurocomputing"},{"key":"594_CR38","doi-asserted-by":"crossref","unstructured":"Tang Y, Xiao X, Shi Y (2014) Influence maximization: near-optimal time complexity meets practical efficiency. In: Proceedings of the 2014 ACM SIGMOD international conference on management of data, pp 75\u201386","DOI":"10.1145\/2588555.2593670"},{"issue":"9","key":"594_CR39","doi-asserted-by":"publisher","DOI":"10.1371\/journal.pone.0073970","volume":"8","author":"P Vanhems","year":"2013","unstructured":"Vanhems P, Barrat A, Cattuto C, Pinton J-F, Khanafer N, R\u00e9gis C, Kim B-A, Comte B, Voirin N (2013) Estimating potential infection transmission routes in hospital wards using wearable proximity sensors. PLoS ONE 8(9):e73970","journal-title":"PLoS ONE"},{"key":"594_CR40","doi-asserted-by":"publisher","first-page":"545","DOI":"10.1007\/s10618-012-0262-1","volume":"25","author":"C Wang","year":"2012","unstructured":"Wang C, Chen W, Wang Y (2012) Scalable influence maximization for independent cascade model in large-scale social networks. Data Min Knowl Disc 25:545\u2013576","journal-title":"Data Min Knowl Disc"},{"key":"594_CR41","doi-asserted-by":"crossref","unstructured":"Wang Y, Cong G, Song G, Xie K (2010) Community-based greedy algorithm for mining top-k influential nodes in mobile social networks. In: Proceedings of the 16th ACM SIGKDD international conference on knowledge discovery and data mining, pp 1039\u20131048","DOI":"10.1145\/1835804.1835935"},{"key":"594_CR42","unstructured":"Wen Z, Kveton B, Valko M, Vaswani S (2017) Online influence maximization under independent cascade model with semi-bandit feedback. Adv Neural Inf Process Syst 30"},{"key":"594_CR43","doi-asserted-by":"crossref","unstructured":"Yu Y, Berger-Wolf TY, Saia J (2010) Finding spread blockers in dynamic networks. In: Advances in social network mining and analysis: second international workshop, SNAKDD 2008, Las Vegas, NV, USA, August 24\u201327, 2008, pp 55\u201376. Springer","DOI":"10.1007\/978-3-642-14929-0_4"},{"issue":"11","key":"594_CR44","doi-asserted-by":"publisher","first-page":"103217","DOI":"10.1016\/j.isci.2021.103217","volume":"24","author":"T Zhou","year":"2021","unstructured":"Zhou T (2021) Progresses and challenges in link prediction. Iscience 24(11):103217","journal-title":"Iscience"},{"key":"594_CR45","doi-asserted-by":"crossref","unstructured":"Zhuang H, Sun Y, Tang J, Zhang J, Sun X (2013) Influence maximization in dynamic social networks. In: 2013 IEEE 13th international conference on data mining, pp 1313\u20131318. IEEE","DOI":"10.1109\/ICDM.2013.145"},{"issue":"3","key":"594_CR46","doi-asserted-by":"publisher","first-page":"1215","DOI":"10.1109\/TNSE.2021.3138643","volume":"9","author":"L Zou","year":"2021","unstructured":"Zou L, Zhan X-X, Sun J, Hanjalic A, Wang H (2021) Temporal network prediction and interpretation. IEEE Trans Netw Sci Eng 9(3):1215\u20131224","journal-title":"IEEE Trans Netw Sci Eng"}],"container-title":["Applied Network Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s41109-023-00594-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s41109-023-00594-z\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s41109-023-00594-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,11,18]],"date-time":"2023-11-18T22:02:43Z","timestamp":1700344963000},"score":1,"resource":{"primary":{"URL":"https:\/\/appliednetsci.springeropen.com\/articles\/10.1007\/s41109-023-00594-z"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,9,25]]},"references-count":46,"journal-issue":{"issue":"1","published-online":{"date-parts":[[2023,12]]}},"alternative-id":["594"],"URL":"https:\/\/doi.org\/10.1007\/s41109-023-00594-z","relation":{},"ISSN":["2364-8228"],"issn-type":[{"value":"2364-8228","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,9,25]]},"assertion":[{"value":"17 May 2023","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"13 September 2023","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"25 September 2023","order":3,"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 competing interests.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Competing interest"}}],"article-number":"70"}}