Predição de links por interesse em redes sociais

1 Introdução
Redes sociais são estruturas cujos nós representam pessoas ou outras entidades imersas em um contexto social e cujas arestas representam a interação, a colaboração, ou a influência entre estas entidades [Liben-Nowell e Kleinberg, 2003]. As redes sociais online são altamente dinâmicas, pois crescem e mudam rapidamente ao longo do tempo através da adição de novas arestas, o que significa o aparecimento de novas interações na estrutura social.
Nos últimos anos temos testemunhado o surgimento de muitas redes sociais online.
Muitas dessas estão concentradas nas interações entre os usuários, que podem marcar outros usuários como seus amigos, além de poderem especificar a sua localização e declarar os seus interesses. Como exemplo, temos redes sociais como LinkedIn, Classmates. com, e MyFamily.com que especializaram-se em determinados tipos de ligações, tais como entre colegas de trabalho, entre colegas de escola ou entre parentes.
Uma das características desejáveis de uma rede social online é ser capaz de sugerir amigos em potencial para seus usuários. Esta tarefa pode ser escalada como um problema de predição link. Predição de link é o problema de prever a probabilidade de formação de um link entre nós ainda não interligados em um grafo, com base na estrutura atual do grafo [Liben-Nowell e Kleinberg, 2003]. Mais precisamente, a tarefa é prever a existência de uma ligação de amizade entre dois usuários baseada na topologia da rede ou nos atributos informados pelos usuários [Caragea et al., 2009].
Uma empresa pode se beneficiar das interações dentro da rede social informal entre seus membros, esses laços servem para complementar a hierarquia oficial imposta pela própria organização. Métodos eficazes para a predição de link poderiam ser usados para analisar essa rede social e sugerir interações promissoras ou colaborações que ainda não foram identificadas dentro da organização [Liben-Nowell e Kleinberg, 2003].
Como exemplo, considere