# The complete title of one (or more) paper(s) published in the open literature describing the work that the author claims describes a human-competitive result;

Multi-Objective Evolutionary Algorithms for Influence Maximization in Social Networks


# The name, complete physical mailing address, e-mail address, and phone number of EACH author of EACH paper(s);

Doina Bucur, EWI, University of Twente, Drienerloolaan 5, 7522 NB Enschede, The Netherlands; d.bucur@utwente.nl;

Giovanni Iacca, ISS, RWTH Aachen University, Kopernikusstrae 16, Aachen, Germany; iacca@ice.rwth-aachen.de;

Andrea Marcelli, DAUIN, Politecnico di Torino, Corso Duca degli Abruzzi 24, Torino, Italy; andrea.marcelli@polito.it;

Giovanni Squillero, DAUIN, Politecnico di Torino, Corso Duca degli Abruzzi 24, Torino, Italy; giovanni.squillero@polito.it; Tel: +39-011090.7186

Alberto Tonda, Université Paris-Saclay, INRA, 1 av. Brétignières, 78850, Thiverval-Grignon, France; alberto.tonda@inra.fr; Tel: +33 1 30 81 45 96


# The name of the corresponding author (i.e., the author to whom notices will be sent concerning the competition);

Giovanni Squillero <giovanni.squillero@polito.it>


# The abstract of the paper(s);

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.


# A list containing one or more of the eight letters (A, B, C, D, E, F, G, or H) that correspond to the criteria (see above) that the author claims that the work satisfies;

(E) The result is equal to or better than the most recent human-created solution to a long-standing problem for which there has been a succession of increasingly better human-created solutions.

(G) The result solves a problem of indisputable difficulty in its field.


# A statement stating why the result satisfies the criteria that the contestant claims (see examples of statements of human-competitiveness as a guide to aid in constructing this part of the submission);

(E) There is a long history of human-devised heuristics for influence maximization, from greedy methods such High Degree and Simple Discount, to more refined heuristics such as Cost-Effective Lazy Forward selection. We proved that human-designed heuristics for influence maximization perform comparatively poorly against EAs. In particular, Multi-Objective EAs can find good compromises between the size of the number of seed nodes and the influence obtained, helping users locate their desired combination of values.

(G) Influence maximization in social networks is a challenging problem, with current applications ranging from advertisement to political engagement, to creating and spreading new items of digital culture, such as new style trends, and new vocabulary (#covfefe). Modern social network graphs are so large that they fall into the category of "big data", and their structure is complex beyond their sheer size (variable-sized clustering with many inter-cluster weak bridges). 


# A full citation of the paper (that is, author names; publication date; name of journal, conference, technical report, thesis, book, or book chapter; name of editors, if applicable, of the journal or edited book; publisher name; publisher city; page numbers, if applicable);

@Inbook{Bucur2017,
    author="Bucur, Doina and Iacca, Giovanni and Marcelli, Andrea and Squillero, Giovanni and Tonda, Alberto",
    editor="Squillero, Giovanni and Sim, Kevin",
    title="Multi-objective Evolutionary Algorithms for Influence Maximization in Social Networks",
    bookTitle="Applications of Evolutionary Computation: 20th European Conference, EvoApplications 2017, Amsterdam, The Netherlands, April 19-21, 2017, Proceedings, Part I",
    year="2017",
    publisher="Springer International Publishing",
    address="Cham",
    pages="221--233",
    isbn="978-3-319-55849-3",
    doi="10.1007/978-3-319-55849-3_15",
    url="http://dx.doi.org/10.1007/978-3-319-55849-3_15"
}


# A statement either that "any prize money, if any, is to be divided equally among the co-authors" OR a specific percentage breakdown as to how the prize money, if any, is to be divided among the co-authors;

Any prize money, if any, is to be divided equally among the co-authors.


# A statement stating why the authors expect that their entry would be the "best"

As more and more businesses and institutions rely upon the digital world for advertisement and diffusion of information, the problem of optimizing influence in social networks, to reach a vast and potentially interested audience, becomes more and more pressing. Despite a considerable amount of research on the subject, human-devised methods are still suboptimal, and we proved that EAs can not only provide a considerable contribution to the field, but that MOEAs are currently the state of the art. 


# An indication of the general type of genetic or evolutionary computation used, such as GA (genetic algorithms), GP (genetic programming), ES (evolution strategies), EP (evolutionary programming), LCS (learning classifier systems), GE (grammatical evolution), GEP (gene expression programming), DE (differential evolution), etc.

In this work, we used a multi-objective evolutionary algorithm (based on NSGA-II), with a variable genome length composed of integers. Each individual represents a set of seed nodes inside the target network.