Título
[en] A NEW BRANCH-AND-CUT ALGORITHM FOR THE GENERALIZED LEAST COST INFLUENCE PROBLEM IN NETWORKS
Título
[pt] UM NOVO ALGORITMO BRANCH-AND-CUT PARA O PROBLEMA DE INFLUÊNCIA DE MENOR CUSTO GENERALIZADO EM REDES
Autor
[pt] VINICIUS FERREIRA DE SOUZA
Vocabulário
[pt] PROGRAMACAO INTEIRA MISTA
Vocabulário
[pt] BRANCH-AND-CUT
Vocabulário
[pt] PROPAGACAO DE INFLUENCIA
Vocabulário
[en] MIXED INTEGER PROGRAMMING
Vocabulário
[en] BRANCH-AND-CUT
Vocabulário
[en] INFLUENCE PROPAGATION
Resumo
[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.
Resumo
[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.
Orientador(es)
THIBAUT VICTOR GASTON VIDAL
Coorientador(es)
ARTUR ALVES PESSOA
Banca
MARCUS VINICIUS SOLEDADE POGGI DE ARAGAO
Banca
ARTUR ALVES PESSOA
Banca
RAFAEL MARTINELLI PINTO
Banca
THIBAUT VICTOR GASTON VIDAL
Catalogação
2020-12-21
Apresentação
2020-09-24
Tipo
[pt] TEXTO
Formato
application/pdf
Idioma(s)
PORTUGUÊS
Referência [pt]
https://www.maxwell.vrac.puc-rio.br/colecao.php?strSecao=resultado&nrSeq=50960@1
Referência [en]
https://www.maxwell.vrac.puc-rio.br/colecao.php?strSecao=resultado&nrSeq=50960@2
Referência DOI
https://doi.org/10.17771/PUCRio.acad.50960
Arquivos do conteúdo
NA ÍNTEGRA PDF