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

8 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 Dive into the research topics of 'Multi-objective Evolutionary Algorithms for Influence Maximization in Social Networks'. Together they form a unique fingerprint.

Cite this