Relatórios Técnicos do DCC/UFJF, 2018

Tamanho da fonte:  Menor  Médio  Maior

Otimização da difusão de informação em redes complexas

Warley Almeida Silva, Lorenza Leão Oliveira Moreno, Victor Ströele de Andrade Menezes

Resumo


 

Redes complexas têm sido muito pesquisadas recentemente graças a suas aplicações em diversas áreas. Uma rede complexa pode ser modelada naturalmente como um grafo, onde cada nó representa um indivíduo e cada arco representa uma relação entre indivíduos. Dada a natureza complexa das relações humanas, torna-se necessário ponderar essas relações conforme a aplicação desejada.

Uma área interessante de estudo dentro de Redes Complexas visa escolher um subgrupo de indivíduos que consigam efetivamente distribuir uma informação dentro da rede com base na sua relação com os demais. Saber como a informação é difundida numa rede tem aplicações em áreas como marketing, dispersão de doenças, dentre outras.

Uma empresa que quer difundir um novo produto, por exemplo, está disposta a oferecer alguns protótipos para usuários especiais. Entretanto, é importante que esses usuários sejam capazes de difundir para o máximo de pessoas dentro da rede o que acharam desse produto, de forma que outras pessoas também comprem o produto. Nesse caso, escolher um grupo efetivo de pessoas traz economia e melhor difusão da existência do novo produto.

                Da mesma forma, ao tratar cada nó da rede como um local, saber como os locais se relacionam com relação às formas de transmissão de uma determinada doença permite simular a difusão da doença nessa rede. O resultado dessa simulação pode gerar um grupo de locais de risco que devem ser tratados previamente a fim de evitar uma epidemia.

                A otimização da difusão de informação também tem aplicação em redes de colaboração científica, onde pesquisadores se relacionam com base no número de artigos publicados em conjunto. Autores defendem que essas redes apresentam múltiplas características relevantes quando aspectos estruturais de redes são investigados [3]. Nesse caso específico, saber como os pesquisadores se relacionam permite uma melhor divulgação de conferências, chamadas para publicação e distribuição de protótipos, dentre outros exemplos.

                Baseado nessa característica de redes de colaboração científica, escolheu-se trabalhar com a base de dados extraído da Digital Bibliography & Library Project (DBLP)[1], com distribuição regulada pela licença Open Data Commons Attribution License (ODC-BY 1.0). Após pré-processamento da base relacional, gerou-se um grafo com 1306563 nós e 9488594 arcos. Inicialmente, o peso do arco (u,v) entre pesquisadores u e v representava o número de artigos que u publicou com v. Após normalização dos pesos, o peso do arco (u,v) representa a porcentagem de artigos de u publicados com v.

                O problema de seleção de um subgrupo para difusão ótima de informação em uma rede pode ser definido formalmente da seguinte maneira: Dado um grafo G = (N, A) e uma função σ: 2N → 2N que determina quais nós são ativados por um subconjunto, encontre um subconjunto Z ∈ N com tamanho limitado por uma constante de forma que o tamanho do conjunto ativado pelo subconjunto Z, ou seja, |σ(Z)| seja máximo.

                Uma abordagem heurística muito utilizada para seleção desse subgrupo baseia-se em métricas de centralidade, como aquelas descritas em [1]. Algumas métricas são definidas com base em características invariantes da rede - como grau do nó, excentricidade, diâmetro, dentre outras –, enquanto outras são definidas através de cálculos mais rebuscados – como betweeness. Em grandes redes sociais, métricas que se baseiam em invariantes tendem a não ter uma noção da rede como um todo, enquanto métricas mais rebuscadas são computacionalmente difíceis de se calcular.

                Além da seleção com base em métricas de centralidade, modelos matemáticos que descrevem a otimização de informação já foram propostos na literatura. Dentre eles, destacam-se o Linear Threshold Model e o Independent Cascade Model. Como provado em [2], ambos são classificados como NP-difícil e soluções aproximadas encontradas por algoritmos gulosos alcançam pelo menos 63% da solução ótima.

                Com o intuito de alcançar melhores resultados e obter maior escalabilidade levando em consideração o grande tamanho das redes sociais atuais, propõe-se o desenvolvimento de um modelo de programação inteira mista que resolva o problema da difusão de informação em redes complexas. Dado a grande complexidade das relações a serem modeladas, o modelo atual está em fase de refinamento. Espera-se num futuro breve avaliar o modelo com outras abordagens de escolha, como os modelos previamente mencionados e escolhas baseadas em medidas de centralidade.

               

Referências bibliográficas

[1] Freitas, L. Q. Medidas de centralidade em grafos. 2010. Dissertação (Mestrado em Engenharia de Produção) – COPPE, UFRJ, Rio de Janeiro, 2010.

[2] Kempe, D., Kleinberg, J. & Tardos, E. (2015). Maximizing the spread of influence through a social network. Theory of Computing, 11(4):105–147.

[3] Newmann, M. E. J. (2001). The structure of scientific collaboration networks. Proceedings of the National Academy of Sciences, 98(2):404–409.


[1] http://dblp.uni-trier.de/

 


Texto Completo: PDF