Improving Multi-objective Evolutionary Influence Maximization in Social Networks

Doina Bucur; Giovanni Iacca; Andrea Marcelli; Giovanni Squillero; Alberto Tonda

doi:10.1007/978-3-319-77538-8_9

Improving Multi-objective Evolutionary Influence Maximization in Social Networks

Doina Bucur, Giovanni Iacca, Andrea Marcelli, Giovanni Squillero, Alberto Tonda^*

^*Corresponding author for this work

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

21 Citations (Scopus)

230 Downloads (Pure)

Abstract

In the context of social networks, maximizing influence means contacting the largest possible number of nodes starting from a set of seed nodes, and assuming a model for influence propagation. The real-world applications of influence maximization are of uttermost importance, and range from social studies to marketing campaigns. Building on a previous work on multi-objective evolutionary influence maximization, we propose improvements that not only speed up the optimization process considerably, but also deliver higher-quality results. State-of-the-art heuristics are run for different sizes of the seed sets, and the results are then used to initialize the population of a multi-objective evolutionary algorithm. The proposed approach is tested on three publicly available real-world networks, where we show that the evolutionary algorithm is able to improve upon the solutions found by the heuristics, while also converging faster than an evolutionary algorithm started from scratch.

Original language	English
Title of host publication	Applications of Evolutionary Computation
Subtitle of host publication	21st International Conference, EvoApplications 2018, Proceedings
Editors	Kevin Sim, Paul Kaufmann
Publisher	Springer
Pages	117-124
Number of pages	8
ISBN (Electronic)	978-3-319-77538-8
ISBN (Print)	978-3-319-77537-1
DOIs	https://doi.org/10.1007/978-3-319-77538-8_9
Publication status	Published - 1 Jan 2018
Event	21st International Conference on the Applications of Evolutionary Computation, EvoApplications 2018 - Parma, Italy Duration: 4 Apr 2018 → 6 Apr 2018 Conference number: 21 http://www.evostar.org/2018/cfp_evoapps.php

Publication series

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

Conference

Conference	21st International Conference on the Applications of Evolutionary Computation, EvoApplications 2018
Abbreviated title	EvoApplications 2018
Country/Territory	Italy
City	Parma
Period	4/04/18 → 6/04/18
Internet address	http://www.evostar.org/2018/cfp_evoapps.php

Keywords

Influence maximization
Multi-objective evolutionary algorithms
Seeding
Social network

Access to Document

10.1007/978-3-319-77538-8_9

Evo18-BucurAccepted author version, 284 KB

Cite this

Bucur, D., Iacca, G., Marcelli, A., Squillero, G., & Tonda, A. (2018). Improving Multi-objective Evolutionary Influence Maximization in Social Networks. In K. Sim, & P. Kaufmann (Eds.), Applications of Evolutionary Computation: 21st International Conference, EvoApplications 2018, Proceedings (pp. 117-124). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 10784 LNCS). Springer. https://doi.org/10.1007/978-3-319-77538-8_9

Bucur, Doina ; Iacca, Giovanni ; Marcelli, Andrea et al. / Improving Multi-objective Evolutionary Influence Maximization in Social Networks. Applications of Evolutionary Computation: 21st International Conference, EvoApplications 2018, Proceedings. editor / Kevin Sim ; Paul Kaufmann. Springer, 2018. pp. 117-124 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{64dfd26ff2a444bd89fadb67cd7821f7,

title = "Improving Multi-objective Evolutionary Influence Maximization in Social Networks",

abstract = "In the context of social networks, maximizing influence means contacting the largest possible number of nodes starting from a set of seed nodes, and assuming a model for influence propagation. The real-world applications of influence maximization are of uttermost importance, and range from social studies to marketing campaigns. Building on a previous work on multi-objective evolutionary influence maximization, we propose improvements that not only speed up the optimization process considerably, but also deliver higher-quality results. State-of-the-art heuristics are run for different sizes of the seed sets, and the results are then used to initialize the population of a multi-objective evolutionary algorithm. The proposed approach is tested on three publicly available real-world networks, where we show that the evolutionary algorithm is able to improve upon the solutions found by the heuristics, while also converging faster than an evolutionary algorithm started from scratch.",

keywords = "Influence maximization, Multi-objective evolutionary algorithms, Seeding, Social network",

author = "Doina Bucur and Giovanni Iacca and Andrea Marcelli and Giovanni Squillero and Alberto Tonda",

year = "2018",

month = jan,

day = "1",

doi = "10.1007/978-3-319-77538-8_9",

language = "English",

isbn = "978-3-319-77537-1",

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

publisher = "Springer",

pages = "117--124",

editor = "Kevin Sim and Paul Kaufmann",

booktitle = "Applications of Evolutionary Computation",

address = "Germany",

note = "21st International Conference on the Applications of Evolutionary Computation, EvoApplications 2018, EvoApplications 2018 ; Conference date: 04-04-2018 Through 06-04-2018",

url = "http://www.evostar.org/2018/cfp_evoapps.php",

}

Bucur, D, Iacca, G, Marcelli, A, Squillero, G & Tonda, A 2018, Improving Multi-objective Evolutionary Influence Maximization in Social Networks. in K Sim & P Kaufmann (eds), Applications of Evolutionary Computation: 21st International Conference, EvoApplications 2018, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 10784 LNCS, Springer, pp. 117-124, 21st International Conference on the Applications of Evolutionary Computation, EvoApplications 2018, Parma, Italy, 4/04/18. https://doi.org/10.1007/978-3-319-77538-8_9

Improving Multi-objective Evolutionary Influence Maximization in Social Networks. / Bucur, Doina; Iacca, Giovanni; Marcelli, Andrea et al.
Applications of Evolutionary Computation: 21st International Conference, EvoApplications 2018, Proceedings. ed. / Kevin Sim; Paul Kaufmann. Springer, 2018. p. 117-124 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 10784 LNCS).

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

TY - GEN

T1 - Improving Multi-objective Evolutionary Influence Maximization in Social Networks

AU - Bucur, Doina

AU - Iacca, Giovanni

AU - Marcelli, Andrea

AU - Squillero, Giovanni

AU - Tonda, Alberto

N1 - Conference code: 21

PY - 2018/1/1

Y1 - 2018/1/1

N2 - In the context of social networks, maximizing influence means contacting the largest possible number of nodes starting from a set of seed nodes, and assuming a model for influence propagation. The real-world applications of influence maximization are of uttermost importance, and range from social studies to marketing campaigns. Building on a previous work on multi-objective evolutionary influence maximization, we propose improvements that not only speed up the optimization process considerably, but also deliver higher-quality results. State-of-the-art heuristics are run for different sizes of the seed sets, and the results are then used to initialize the population of a multi-objective evolutionary algorithm. The proposed approach is tested on three publicly available real-world networks, where we show that the evolutionary algorithm is able to improve upon the solutions found by the heuristics, while also converging faster than an evolutionary algorithm started from scratch.

AB - In the context of social networks, maximizing influence means contacting the largest possible number of nodes starting from a set of seed nodes, and assuming a model for influence propagation. The real-world applications of influence maximization are of uttermost importance, and range from social studies to marketing campaigns. Building on a previous work on multi-objective evolutionary influence maximization, we propose improvements that not only speed up the optimization process considerably, but also deliver higher-quality results. State-of-the-art heuristics are run for different sizes of the seed sets, and the results are then used to initialize the population of a multi-objective evolutionary algorithm. The proposed approach is tested on three publicly available real-world networks, where we show that the evolutionary algorithm is able to improve upon the solutions found by the heuristics, while also converging faster than an evolutionary algorithm started from scratch.

KW - Influence maximization

KW - Multi-objective evolutionary algorithms

KW - Seeding

KW - Social network

UR - http://www.scopus.com/inward/record.url?scp=85044073274&partnerID=8YFLogxK

U2 - 10.1007/978-3-319-77538-8_9

DO - 10.1007/978-3-319-77538-8_9

M3 - Conference contribution

AN - SCOPUS:85044073274

SN - 978-3-319-77537-1

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

SP - 117

EP - 124

BT - Applications of Evolutionary Computation

A2 - Sim, Kevin

A2 - Kaufmann, Paul

PB - Springer

T2 - 21st International Conference on the Applications of Evolutionary Computation, EvoApplications 2018

Y2 - 4 April 2018 through 6 April 2018

ER -

Bucur D, Iacca G, Marcelli A, Squillero G, Tonda A. Improving Multi-objective Evolutionary Influence Maximization in Social Networks. In Sim K, Kaufmann P, editors, Applications of Evolutionary Computation: 21st International Conference, EvoApplications 2018, Proceedings. Springer. 2018. p. 117-124. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-319-77538-8_9

Improving Multi-objective Evolutionary Influence Maximization in Social Networks

Abstract

Publication series

Conference

Keywords

Access to Document

Other files and links

Fingerprint

Cite this