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.

Large-Scale Multi-objective Influence Maximisation with Network Downscaling / Cunegatti, Elia; Iacca, Giovanni; Bucur, Doina. - 13399:(2022), pp. 207-220. (Intervento presentato al convegno PPSN 2022 tenutosi a Dortmund nel 10th September-14th September 2022) [10.1007/978-3-031-14721-0_15].

Large-Scale Multi-objective Influence Maximisation with Network Downscaling

Cunegatti, Elia;Iacca, Giovanni;
2022-01-01

Abstract

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.
2022
Parallel Problem Solving from Nature – PPSN XVII
Cham
Springer
978-3-031-14720-3
978-3-031-14721-0
Cunegatti, Elia; Iacca, Giovanni; Bucur, Doina
Large-Scale Multi-objective Influence Maximisation with Network Downscaling / Cunegatti, Elia; Iacca, Giovanni; Bucur, Doina. - 13399:(2022), pp. 207-220. (Intervento presentato al convegno PPSN 2022 tenutosi a Dortmund nel 10th September-14th September 2022) [10.1007/978-3-031-14721-0_15].
File in questo prodotto:
File Dimensione Formato  
paper_003.pdf

Open Access dal 17/08/2023

Tipologia: Post-print referato (Refereed author’s manuscript)
Licenza: Tutti i diritti riservati (All rights reserved)
Dimensione 1.92 MB
Formato Adobe PDF
1.92 MB Adobe PDF Visualizza/Apri

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11572/352160
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 1
  • ???jsp.display-item.citation.isi??? 1
social impact