[en] A NEW BRANCH-AND-CUT ALGORITHM FOR THE GENERALIZED LEAST COST INFLUENCE PROBLEM IN NETWORKS
Ano de defesa: | 2020 |
---|---|
Autor(a) principal: | |
Orientador(a): | |
Banca de defesa: | |
Tipo de documento: | Tese |
Tipo de acesso: | Acesso aberto |
Idioma: | por |
Instituição de defesa: |
MAXWELL
|
Programa de Pós-Graduação: |
Não Informado pela instituição
|
Departamento: |
Não Informado pela instituição
|
País: |
Não Informado pela instituição
|
Palavras-chave em Português: | |
Link de acesso: | https://www.maxwell.vrac.puc-rio.br/colecao.php?strSecao=resultado&nrSeq=50960&idi=1 https://www.maxwell.vrac.puc-rio.br/colecao.php?strSecao=resultado&nrSeq=50960&idi=2 http://doi.org/10.17771/PUCRio.acad.50960 |
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. |