Análise de uma métrica alternativa para predição de laços sociais em grafos lei de potência

Abstract

Resumo: As redes sociais são uma maneira de descrever as interações sociais em um grupo ou comunidade. Podem ser modeladas por meio de grafos, em que um vértice corresponde a uma pessoa, e uma aresta representa alguma forma de associação entre duas pessoas [Hasan e Zaki, 2011]. As redes sociais são objetos altamente dinâmicos, elas crescem e mudam rapidamente ao longo do tempo devido à adição e exclusão de vértices e arestas. Compreender os mecanismos pelos quais estas estruturas sociais evoluem é uma questão fundamental, ainda não bem compreendida, e que constitui a motivação para este projeto. Mais especificamente, a pesquisa se dedica ao problema da predição de laços sociais: dado um snapshot de uma rede social em tempo t0, busca-se prever com precisão as arestas que serão adicionados à rede em um determinado momento t futuro, tal que t > t0 [Liben-Nowell, 2005]. As soluções estudadas se dividem em dois grupos principais: predição de laço supervisionada e a predição de laço não supervisionada. A predição de laço supervisionada envolve técnicas de aprendizado de máquina como a extração de características e algoritmos de classificação [Zhang e Yu, 2011]. A predição não supervisionada busca de calcular métricas baseadas nas características topológicas do grafo [Hasan e Zaki, 2011]. Com base no segundo paradigma, e a partir do estudo de modelos de geração de grafos, é proposta como contribuição uma métrica para calcular a probabilidade de formação de arestas entre dois vértices específica para grafos com distribuição de grau Lei de Potência.

Abstract: Social networks are a popular way to model the interactions among people in a group or community. They can be visualized as graphs, where a vertex corresponds to a person in some group and an edge represents some form of association between the corresponding persons [Hasan e Zaki, 2011]. Social networks are very dynamic, since new edges and vertices are added to the graph over time. Understanding the dynamics that drive the evolution of social networks is a complex problem, yet to be fully understood, and which comprises the motivation of this project. A basic computational problem underlying social-network evolution is the linkprediction problem: given a snapshot of a social network at time t, we seek to accurately predict the edges that will be added to the network during the interval from time t to a given future time t0, considering t > t0 [Liben-Nowell, 2005]. Most works in this field branch into two main groups: supervised and unsupervised link prediction. Supervised link prediction models have two important components: feature extraction and classification [Zhang e Yu, 2011]. Unsupervised link prediction calculates metrics based on features which are extracted from the graph topology, some works develop a graph evolution model [Hasan e Zaki, 2011]. Based on unsupervised link prediction concepts, mainly on graph generation models, we propose a link prediction metric, which is specific to power-law graphs.