[pt] A propagação de influências tem sido objeto de extensos estudos devido
a seu importante impacto em redes sociais, epidemiologia e muitas
outras áreas. A compreensão do mecanismo de propagação é crítica, por
exemplo, para controlar a disseminação de notícias falsas ou controlar uma
epidemia. Neste trabalho, seguimos uma perspectiva de otimização e identificamos o menor grupo de usuários que precisam ser convertidos para
atingir um certo nível de influência em toda a rede. Portanto, estudamos
formalmente o problema de influência de menor custo generalizado, propondo
algoritmos de programação matemática para resolver este problema.
Introduzimos novos algoritmos de planos de corte e separação, e os incorporamos em um algoritmo de branch-and-cut. Nossos resultados experimentais em instâncias da literatura demonstram a capacidade do método de resolver pequenas e médias instâncias, bem como diminuir o gap da melhor
solução conhecida e inclusive encontrando também soluções ótimas para
alguns problemas em aberto. / [en] Influence propagation has been the subject of extensive study due to
its important role in social networks, epidemiology, and many other areas.
Understanding the propagation mechanism is critical, e.g., to control the
spread of fake news or to control an epidemic. In this work, we follow
an optimization perspective, and attempt to identify the smallest group
of users that needs to be converted to achieve an certain influence level
over the entire network. We therefore formally study the generalized least
cost influence problem, proposing mathematical programming algorithms
to solve the challenging problem. We introduce new cutting plane and
separation algorithms and embed them into a branch-and-cut algorithm.
Our experimental results on classical benchmark instances demonstrates
the method ability to solve small-to medium-scale benchmark instances,
also finding optimal solutions for some open problems.
| Identifer | oai:union.ndltd.org:puc-rio.br/oai:MAXWELL.puc-rio.br:50960 |
| Date | 21 December 2020 |
| Creators | VINICIUS FERREIRA DE SOUZA |
| Contributors | THIBAUT VICTOR GASTON VIDAL |
| Publisher | MAXWELL |
| Source Sets | PUC Rio |
| Language | Portuguese |
| Detected Language | Portuguese |
| Type | TEXTO |
Page generated in 0.0024 seconds