Multi-objective Evolutionary Algorithms for Influence Maximization in Social Networks

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

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

6 Citations (Scopus)

Abstract

As the pervasiveness of social networks increases, new NP-hard related problems become interesting for the optimization community. The objective of influence maximization is to contact the largest possible number of nodes in a network, starting from a small set of seed nodes, and assuming a model for information propagation. This problem is of utmost practical importance for applications ranging from social studies to marketing. The influence maximization problem is typically formulated assuming that the number of the seed nodes is a parameter. Differently, in this paper, we choose to formulate it in a multi-objective fashion, considering the minimization of the number of seed nodes among the goals, and we tackle it with an evolutionary approach. As a result, we are able to identify sets of seed nodes of different size that spread influence the best, providing factual data to trade-off costs with quality of the result. The methodology is tested on two real-world case studies, using two different influence propagation models, and compared against state-of-the-art heuristic algorithms. The results show that the proposed approach is almost always able to outperform the heuristics.
Original languageEnglish
Title of host publicationApplications of Evolutionary Computation
Subtitle of host publication20th European Conference, EvoApplications 2017, Amsterdam, The Netherlands, April 19-21, 2017, Proceedings, Part I
EditorsGiovanni Squillero, Kevin Sim
Place of PublicationCham
PublisherSpringer
Pages221-233
Number of pages13
ISBN (Electronic)978-3-319-55849-3
ISBN (Print)978-3-319-55848-6
DOIs
Publication statusPublished - Apr 2017

Publication series

NameLecture Notes in Computer Science
PublisherSpringer
Volume10199
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Fingerprint

Evolutionary algorithms
Seed
Heuristic algorithms
Marketing
Costs

Cite this

Bucur, D., Iacca, G., Marcelli, A., Squillero, G., & Tonda, A. (2017). Multi-objective Evolutionary Algorithms for Influence Maximization in Social Networks. In G. Squillero, & K. Sim (Eds.), Applications of Evolutionary Computation: 20th European Conference, EvoApplications 2017, Amsterdam, The Netherlands, April 19-21, 2017, Proceedings, Part I (pp. 221-233). (Lecture Notes in Computer Science; Vol. 10199). Cham: Springer. https://doi.org/10.1007/978-3-319-55849-3_15
Bucur, Doina ; Iacca, Giovanni ; Marcelli, Andrea ; Squillero, Giovanni ; Tonda, Alberto. / Multi-objective Evolutionary Algorithms for Influence Maximization in Social Networks. Applications of Evolutionary Computation: 20th European Conference, EvoApplications 2017, Amsterdam, The Netherlands, April 19-21, 2017, Proceedings, Part I. editor / Giovanni Squillero ; Kevin Sim. Cham : Springer, 2017. pp. 221-233 (Lecture Notes in Computer Science).
@inproceedings{d305d10696ed41b6980759979b22c5d3,
title = "Multi-objective Evolutionary Algorithms for Influence Maximization in Social Networks",
abstract = "As the pervasiveness of social networks increases, new NP-hard related problems become interesting for the optimization community. The objective of influence maximization is to contact the largest possible number of nodes in a network, starting from a small set of seed nodes, and assuming a model for information propagation. This problem is of utmost practical importance for applications ranging from social studies to marketing. The influence maximization problem is typically formulated assuming that the number of the seed nodes is a parameter. Differently, in this paper, we choose to formulate it in a multi-objective fashion, considering the minimization of the number of seed nodes among the goals, and we tackle it with an evolutionary approach. As a result, we are able to identify sets of seed nodes of different size that spread influence the best, providing factual data to trade-off costs with quality of the result. The methodology is tested on two real-world case studies, using two different influence propagation models, and compared against state-of-the-art heuristic algorithms. The results show that the proposed approach is almost always able to outperform the heuristics.",
author = "Doina Bucur and Giovanni Iacca and Andrea Marcelli and Giovanni Squillero and Alberto Tonda",
year = "2017",
month = "4",
doi = "10.1007/978-3-319-55849-3_15",
language = "English",
isbn = "978-3-319-55848-6",
series = "Lecture Notes in Computer Science",
publisher = "Springer",
pages = "221--233",
editor = "Giovanni Squillero and Kevin Sim",
booktitle = "Applications of Evolutionary Computation",

}

Bucur, D, Iacca, G, Marcelli, A, Squillero, G & Tonda, A 2017, Multi-objective Evolutionary Algorithms for Influence Maximization in Social Networks. in G Squillero & K Sim (eds), Applications of Evolutionary Computation: 20th European Conference, EvoApplications 2017, Amsterdam, The Netherlands, April 19-21, 2017, Proceedings, Part I. Lecture Notes in Computer Science, vol. 10199, Springer, Cham, pp. 221-233. https://doi.org/10.1007/978-3-319-55849-3_15

Multi-objective Evolutionary Algorithms for Influence Maximization in Social Networks. / Bucur, Doina; Iacca, Giovanni; Marcelli, Andrea; Squillero, Giovanni; Tonda, Alberto.

Applications of Evolutionary Computation: 20th European Conference, EvoApplications 2017, Amsterdam, The Netherlands, April 19-21, 2017, Proceedings, Part I. ed. / Giovanni Squillero; Kevin Sim. Cham : Springer, 2017. p. 221-233 (Lecture Notes in Computer Science; Vol. 10199).

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

TY - GEN

T1 - Multi-objective Evolutionary Algorithms for Influence Maximization in Social Networks

AU - Bucur, Doina

AU - Iacca, Giovanni

AU - Marcelli, Andrea

AU - Squillero, Giovanni

AU - Tonda, Alberto

PY - 2017/4

Y1 - 2017/4

N2 - As the pervasiveness of social networks increases, new NP-hard related problems become interesting for the optimization community. The objective of influence maximization is to contact the largest possible number of nodes in a network, starting from a small set of seed nodes, and assuming a model for information propagation. This problem is of utmost practical importance for applications ranging from social studies to marketing. The influence maximization problem is typically formulated assuming that the number of the seed nodes is a parameter. Differently, in this paper, we choose to formulate it in a multi-objective fashion, considering the minimization of the number of seed nodes among the goals, and we tackle it with an evolutionary approach. As a result, we are able to identify sets of seed nodes of different size that spread influence the best, providing factual data to trade-off costs with quality of the result. The methodology is tested on two real-world case studies, using two different influence propagation models, and compared against state-of-the-art heuristic algorithms. The results show that the proposed approach is almost always able to outperform the heuristics.

AB - As the pervasiveness of social networks increases, new NP-hard related problems become interesting for the optimization community. The objective of influence maximization is to contact the largest possible number of nodes in a network, starting from a small set of seed nodes, and assuming a model for information propagation. This problem is of utmost practical importance for applications ranging from social studies to marketing. The influence maximization problem is typically formulated assuming that the number of the seed nodes is a parameter. Differently, in this paper, we choose to formulate it in a multi-objective fashion, considering the minimization of the number of seed nodes among the goals, and we tackle it with an evolutionary approach. As a result, we are able to identify sets of seed nodes of different size that spread influence the best, providing factual data to trade-off costs with quality of the result. The methodology is tested on two real-world case studies, using two different influence propagation models, and compared against state-of-the-art heuristic algorithms. The results show that the proposed approach is almost always able to outperform the heuristics.

U2 - 10.1007/978-3-319-55849-3_15

DO - 10.1007/978-3-319-55849-3_15

M3 - Conference contribution

SN - 978-3-319-55848-6

T3 - Lecture Notes in Computer Science

SP - 221

EP - 233

BT - Applications of Evolutionary Computation

A2 - Squillero, Giovanni

A2 - Sim, Kevin

PB - Springer

CY - Cham

ER -

Bucur D, Iacca G, Marcelli A, Squillero G, Tonda A. Multi-objective Evolutionary Algorithms for Influence Maximization in Social Networks. In Squillero G, Sim K, editors, Applications of Evolutionary Computation: 20th European Conference, EvoApplications 2017, Amsterdam, The Netherlands, April 19-21, 2017, Proceedings, Part I. Cham: Springer. 2017. p. 221-233. (Lecture Notes in Computer Science). https://doi.org/10.1007/978-3-319-55849-3_15