Large-scale multi-objective influence maximisation with network downscaling

Elia Cunegatti; Giovanni Iacca; Doina Bucur

doi:10.1007/978-3-031-14721-0_15

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 proceeding › Conference contribution › Academic › peer-review

6 Citations (Scopus)

171 Downloads (Pure)

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.

Original language	English
Title of host publication	Parallel Problem Solving from Nature – PPSN XVII
Subtitle of host publication	17th International Conference, PPSN 2022, Dortmund, Germany, September 10–14, 2022, Proceedings, Part II
Editors	Günter Rudolph, Anna V. Kononova, Hernán Aguirre, Pascal Kerschke, Gabriela Ochoa, Tea Tušar
Pages	207-220
Number of pages	14
ISBN (Electronic)	978-3-031-14721-0
DOIs	https://doi.org/10.1007/978-3-031-14721-0_15
Publication status	Published - 15 Aug 2022
Event	17th International Conference on Parallel Problem Solving from Nature, PPSN 2022 - TU Dortmund University, Dortmund, Germany Duration: 10 Sept 2022 → 14 Sept 2022 Conference number: 17

Publication series

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

Conference

Conference	17th International Conference on Parallel Problem Solving from Nature, PPSN 2022
Abbreviated title	PPSN 2022
Country/Territory	Germany
City	Dortmund
Period	10/09/22 → 14/09/22

Keywords

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

Access to Document

10.1007/978-3-031-14721-0_15

10.1007_978-3-031-14721-0_15Final published version, 1.42 MBLicence: Taverne

Cite this

Cunegatti, E., Iacca, G., & Bucur, D. (2022). Large-scale multi-objective influence maximisation with network downscaling. In G. Rudolph, A. V. Kononova, H. Aguirre, P. Kerschke, G. Ochoa, & T. Tušar (Eds.), Parallel Problem Solving from Nature – PPSN XVII: 17th International Conference, PPSN 2022, Dortmund, Germany, September 10–14, 2022, Proceedings, Part II (pp. 207-220). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 13399 LNCS). https://doi.org/10.1007/978-3-031-14721-0_15

Cunegatti, Elia ; Iacca, Giovanni ; Bucur, Doina. / Large-scale multi-objective influence maximisation with network downscaling. Parallel Problem Solving from Nature – PPSN XVII: 17th International Conference, PPSN 2022, Dortmund, Germany, September 10–14, 2022, Proceedings, Part II. editor / Günter Rudolph ; Anna V. Kononova ; Hernán Aguirre ; Pascal Kerschke ; Gabriela Ochoa ; Tea Tušar. 2022. pp. 207-220 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{8d4c0d0043d449528e9c7fc0c45b7c10,

title = "Large-scale multi-objective influence maximisation with network downscaling",

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.",

keywords = "cs.SI, cs.AI, cs.LG, cs.NE, 22/3 OA procedure",

author = "Elia Cunegatti and Giovanni Iacca and Doina Bucur",

note = "Publisher Copyright: {\textcopyright} 2022, The Author(s), under exclusive license to Springer Nature Switzerland AG.; 17th International Conference on Parallel Problem Solving from Nature, PPSN 2022, PPSN 2022 ; Conference date: 10-09-2022 Through 14-09-2022",

year = "2022",

month = aug,

day = "15",

doi = "10.1007/978-3-031-14721-0\_15",

language = "English",

isbn = "978-3-031-14720-3",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

pages = "207--220",

editor = "G{\"u}nter Rudolph and Kononova, \{Anna V.\} and Hern{\'a}n Aguirre and Pascal Kerschke and Gabriela Ochoa and Tea Tu{\v s}ar",

booktitle = "Parallel Problem Solving from Nature – PPSN XVII",

}

Cunegatti, E, Iacca, G & Bucur, D 2022, Large-scale multi-objective influence maximisation with network downscaling. in G Rudolph, AV Kononova, H Aguirre, P Kerschke, G Ochoa & T Tušar (eds), Parallel Problem Solving from Nature – PPSN XVII: 17th International Conference, PPSN 2022, Dortmund, Germany, September 10–14, 2022, Proceedings, Part II. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 13399 LNCS, pp. 207-220, 17th International Conference on Parallel Problem Solving from Nature, PPSN 2022, Dortmund, Germany, 10/09/22. https://doi.org/10.1007/978-3-031-14721-0_15

Large-scale multi-objective influence maximisation with network downscaling. / Cunegatti, Elia; Iacca, Giovanni; Bucur, Doina.
Parallel Problem Solving from Nature – PPSN XVII: 17th International Conference, PPSN 2022, Dortmund, Germany, September 10–14, 2022, Proceedings, Part II. ed. / Günter Rudolph; Anna V. Kononova; Hernán Aguirre; Pascal Kerschke; Gabriela Ochoa; Tea Tušar. 2022. p. 207-220 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 13399 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

TY - GEN

T1 - Large-scale multi-objective influence maximisation with network downscaling

AU - Cunegatti, Elia

AU - Iacca, Giovanni

AU - Bucur, Doina

N1 - Conference code: 17

PY - 2022/8/15

Y1 - 2022/8/15

N2 - 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.

AB - 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.

KW - cs.SI

KW - cs.AI

KW - cs.LG

KW - cs.NE

KW - 22/3 OA procedure

UR - https://arxiv.org/pdf/2204.06250

U2 - 10.1007/978-3-031-14721-0_15

DO - 10.1007/978-3-031-14721-0_15

M3 - Conference contribution

SN - 978-3-031-14720-3

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 207

EP - 220

BT - Parallel Problem Solving from Nature – PPSN XVII

A2 - Rudolph, Günter

A2 - Kononova, Anna V.

A2 - Aguirre, Hernán

A2 - Kerschke, Pascal

A2 - Ochoa, Gabriela

A2 - Tušar, Tea

T2 - 17th International Conference on Parallel Problem Solving from Nature, PPSN 2022

Y2 - 10 September 2022 through 14 September 2022

ER -

Cunegatti E, Iacca G, Bucur D. Large-scale multi-objective influence maximisation with network downscaling. In Rudolph G, Kononova AV, Aguirre H, Kerschke P, Ochoa G, Tušar T, editors, Parallel Problem Solving from Nature – PPSN XVII: 17th International Conference, PPSN 2022, Dortmund, Germany, September 10–14, 2022, Proceedings, Part II. 2022. p. 207-220. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-031-14721-0_15

Large-scale multi-objective influence maximisation with network downscaling

Abstract

Publication series

Conference

Keywords

Access to Document

Other files and links

Fingerprint

Cite this