22 Mar 2021
14:00 Master's Defense Fully distance
Theme
A Computational Study of the Problem of Perfect Gnosticism
Student
Felipe de Carvalho Pereira
Advisor / Teacher
Pedro Jussieu de Rezende (Advisor) / Cid Carvalho de Souza (Co-supervisor)
Brief summary
"The Perfect Gnosticism Problem (PAP of the Perfect Awareness Problem) is a combinatorial optimization problem inserted in the topic of viral marketing that involves the spread of information on social networks. The problem can be described as follows. The entry consists of a pair (G, t), where G = (V, E) is an undirected graph and t: V → Z + is a threshold function.The set of vertices V corresponds to the collection of individuals in a social network and the set of edges E represents the possible communications between such individuals. It is assumed that, initially, all individuals in the network are unaware of a certain information, except for an initial set of disseminators, called seed set. If an unknown vertex v is informed by a disseminating neighbor , then v becomes knowledgeable. Furthermore, as soon as v is informed by a number of disseminating neighbors greater than or equal to t (v), v becomes also a disseminator. conclude a seed set of minimum size, from which a spread of information makes all members of the network aware of it. PAP is an NP-difficult problem and so far only one heuristic method has been reported in the literature to deal with it. In this paper, we present four new heuristics for PAP based on the GRASP meta-heuristic. In addition to these algorithms, we developed the first two Integral Linear Programming (PLI) formulations for the problem, in order to obtain optimal solutions for PAP instances and to be able to compare with them the solutions produced by our heuristics. The research contributions also include three instances preprocessing approaches for reducing the size of entries and a new benchmark of 840 PAP instances that simulate social networks. An extensive set of comparative experiments was also carried out, followed by statistical analysis, showing the effectiveness and efficiency of the proposed heuristics. In addition, we applied the best of our heuristics to 17 instances of the literature that represent real social networks and found that our algorithm surpasses the only heuristic previously existing for PAP. "
Examination Board
Headlines:
| Pedro Jussieu de Rezende | IC / UNICAMP |
| Claudio Nogueira de Meneses | CMCC / UFABC |
| Fábio Luiz Usberti | IC / UNICAMP |
Substitutes:
| Lehilton Lelis Chaves Pedrosa | IC / UNICAMP |
| Maycon Sambinelli | CMCC / UFABC |