Exact algorithms for influence propagation in complex networks
Resumo
Resumo: Uma rede complexa é um tipo de grafo com características topológicas que normalmente aparecem em grafos que modelam dados do mundo real. Um fato importante sobre tais redes é que existem indicações práticas da tratabilidade de alguns problemas de otimização combinatória em grafos cuja distribuição de graus segue uma lei de potência. Um problema combinatório decorrente da investigação sobre propagação de influência em redes sociais é o problema de Maximização de Influência, que surge no contexto de adoção em cadeia de novos comportamentos pelos indivíduos de uma rede social. Embora o problema Maximização de Influência tenha sido estudado intensivamente, a literatura a partir da perspectiva de métodos exatos é limitada e nenhum estudo explora a distribuição de graus desta perspectiva. Os resultados recentes em programação matemática para este problema são relevantes, mas ainda existe espaço para melhorias. Portanto, para resolver o problema de Maximização de Influência usando algoritmos exatos, propomos tirar proveito de algumas propriedades dos grafos lei de potência. As contribuições desta tese são três. Duas destas são técnicas de pré-processamento para variantes do problema de maximização de influência. Ambos os algoritmos são especializados na distribuição de grau de redes complexas. A terceira contribuição é um algoritmo combinatório específico do problema para calcular um limitante dual "apertado" para o problema de Influência de Custo Mínimo. Além disso, apresentamos análises teóricas para nossas descobertas e fornecemos experimentos empíricos para avaliar nossas propostas em grafos sintéticos e dados do mundo real. Palavras-chave: Propagação de influência. Otimização combinatória. Redes complexas. Abstract: A complex network is a type of graph with topological characteristics that usually appear in graphs that model data observed in real-word. An important fact about these networks is that there are practical indications of the tractability of some combinatorial optimization problems in graphs with power-law degree distribution. A combinatorial problem arising from the investigation on the spread of influence in social networks is the Influence Maximization, which appears in the context of a chain adoption of new behaviors by the individuals of a social network. Although the Influence Maximization problem has been studied intensively, only limited literature is from the exact methods perspective, and none of them exploits the degree distribution. Recent results in mathematical programming for this problem and its variants are relevant. However, there is room for improvements in the exact solutions of literature. Therefore, to address the Influence Maximization problem using exact algorithms, we propose to take advantage of some properties of complex networks. The contributions of this thesis are threefold. Two of them are presolving techniques for variants of the influence maximization problem. Both algorithms are specialized in the power-law degree distribution of complex networks. The third contribution is a problem-specific combinatorial algorithm to compute a tight dual bound for the Least Cost Influence Problem. Moreover, we present theoretical analysis for our findings and provide empirical experiments to evaluate our proposals in synthetic graphs and real-world data. Keywords: Influence propagation. Combinatorial optimization. Complex networks.
Collections
- Teses [140]