Large-scale multi-objective influence maximisation with network downscaling

Elia Cunegatti, Giovanni Iacca*, Doina Bucur

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

1 Citation (Scopus)
31 Downloads (Pure)


Finding the most influential nodes in a network is a computationally hard problem with several possible applications in various kinds of network-based problems. While several methods have been proposed for tackling the influence maximisation (IM) problem, their runtime typically scales poorly when the network size increases. Here, we propose an original method, based on network downscaling, that allows a multi-objective evolutionary algorithm (MOEA) to solve the IM problem on a reduced scale network, while preserving the relevant properties of the original network. The downscaled solution is then upscaled to the original network, using a mechanism based on centrality metrics such as PageRank. Our results on eight large networks (including two with ∼ 50k nodes) demonstrate the effectiveness of the proposed method with a more than 10-fold runtime gain compared to the time needed on the original network, and an up to 82 % time reduction compared to CELF.

Original languageEnglish
Title of host publicationParallel Problem Solving from Nature – PPSN XVII
Subtitle of host publication17th International Conference, PPSN 2022, Dortmund, Germany, September 10–14, 2022, Proceedings, Part II
EditorsGünter Rudolph, Anna V. Kononova, Hernán Aguirre, Pascal Kerschke, Gabriela Ochoa, Tea Tušar
Number of pages14
ISBN (Electronic)978-3-031-14721-0
Publication statusPublished - 15 Aug 2022
Event17th International Conference on Parallel Problem Solving from Nature, PPSN 2022 - TU Dortmund University, Dortmund, Germany
Duration: 10 Sept 202214 Sept 2022
Conference number: 17

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume13399 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Conference17th International Conference on Parallel Problem Solving from Nature, PPSN 2022
Abbreviated titlePPSN 2022


  • cs.SI
  • cs.AI
  • cs.LG
  • cs.NE
  • 22/3 OA procedure


Dive into the research topics of 'Large-scale multi-objective influence maximisation with network downscaling'. Together they form a unique fingerprint.

Cite this