Influence Maximization in Social Networks with Genetic Algorithms

Doina Bucur, Giovanni Iacca

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

20 Citations (Scopus)

Abstract

We live in a world of social networks. Our everyday choices are often influenced by social interactions. Word of mouth, meme diffusion on the Internet, and viral marketing are all examples of how social networks can affect our behaviour. In many practical applications, it is of great interest to determine which nodes have the highest influence over the network, i.e., which set of nodes will, indirectly, reach the largest audience when propagating information. These nodes might be, for instance, the target for early adopters of a product, the most influential endorsers in political elections, or the most important investors in financial operations, just to name a few examples. Here, we tackle the NP-hard problem of influence maximization on social networks by means of a Genetic Algorithm. We show that, by using simple genetic operators, it is possible to find in feasible runtime solutions of high-influence that are comparable, and occasionally better, than the solutions found by a number of known heuristics (one of which was previously proven to have the best possible approximation guarantee, in polynomial time, of the optimal solution). The advantages of Genetic Algorithms show, however, in them not requiring any assumptions about the graph underlying the network, and in them obtaining more diverse sets of feasible solutions than current heuristics.
Original languageEnglish
Title of host publicationApplications of Evolutionary Computation
Subtitle of host publication19th European Conference, EvoApplications 2016, Porto, Portugal, March 30-April 1, 2016, Proceedings, Part I
EditorsGiovanni Squillero, Paolo Burelli
Place of PublicationCham
PublisherSpringer
Pages379-392
Number of pages14
ISBN (Electronic)978-3-319-31204-0
ISBN (Print)978-3-319-31203-3
DOIs
Publication statusPublished - Apr 2016

Publication series

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

    Fingerprint

Cite this

Bucur, D., & Iacca, G. (2016). Influence Maximization in Social Networks with Genetic Algorithms. In G. Squillero, & P. Burelli (Eds.), Applications of Evolutionary Computation: 19th European Conference, EvoApplications 2016, Porto, Portugal, March 30-April 1, 2016, Proceedings, Part I (pp. 379-392). (Lecture Notes in Computer Science; Vol. 9597). Cham: Springer. https://doi.org/10.1007/978-3-319-31204-0_25