Full text
| |
| Author(s): |
Felipe de Carvalho Pereira
Total Authors: 1
|
| Document type: | Master's Dissertation |
| Press: | Campinas, SP. |
| Institution: | Universidade Estadual de Campinas (UNICAMP). Instituto de Computação |
| Defense date: | 2021-03-22 |
| Examining board members: |
Pedro Jussieu de Rezende;
Claudio Nogueira de Meneses;
Fábio Luiz Usberti
|
| Advisor: | Pedro Jussieu de Rezende; Cid Carvalho de Souza |
| Abstract | |
The Perfect Awareness Problem (PAP) is a combinatorial optimization problem within the area of viral marketing and related to the spread of information in social networks. The problem can be described as follows. The input consists of a pair (G,t) where G = (V,E) is an undirected graph and t : V -> N* is a "threshold function". The set of vertices V corresponds to the collection of individuals in a social network and the edges in E indicate pairs of individuals between whom communication is possible. It is assumed that, initially, all individuals in the network are ignorant of a certain information, except for an initial set of "spreaders", called "seed set". If an ignorant vertex v is informed by a neighboring spreader, then v becomes "aware". Moreover, as soon as v is informed by a number of neighboring spreaders greater than or equal to t(v), v also becomes a spreader. The objective of the problem is to find a seed set of minimum size, from which the propagation of the information makes all members of the network aware. The PAP is NP-hard and, so far, only one heuristic has been reported in the literature for this problem. In this work, we present four novel heuristics for the PAP, based on the metaheuristic GRASP. In addition to these algorithms, we developed the first two Integer Programming formulations for the problem, in order to obtain optimal solutions for PAP instances, so as to compare them with the solutions produced by our heuristics. The contributions of this research also include three preprocessing approaches for reducing the size of input instances and a new benchmark of 840 instances of the PAP that simulate social networks. An extensive set of comparative experiments was conducted, followed by statistical analyses, showing the effectiveness and efficiency of the proposed heuristics. Furthermore, we applied the best one of our heuristics to 17 instances from the literature that represent real social networks and found that our algorithm surpasses the only previously reported heuristic for the PAP (AU) | |
| FAPESP's process: | 19/22297-1 - Exact algorithms and heuristics for the Perfect Awareness problem |
| Grantee: | Felipe de Carvalho Pereira |
| Support Opportunities: | Scholarships in Brazil - Master |