Link Prediction Problem for Social Networks
Diego Spíndola
Roteiro

Definição do problema

Motivação e aplicações

Contribuições

Metodologia

Técnicas

Resultados

A melhorar

Referência

Rede social: conjunto
de entidades (nós)
que se relacionam
(por arestas) = grafo
O problema...

Problema da predição de links: “dado um
retrato de uma rede social, podemos inferir as
interações que provavelmente ocorrerão entre
seus membros num futuro próximo?”
Em outras palavras...

Dado um retrato da rede social no tempo t,
tentamos prever as arestas que surgirão no
tempo t'.
motivação

Muitas questões externas à rede podem
determinar novos relacionamentos


ex.: colaboração entre cientistas – mudança de
residência
Mas a topologia da rede também pode dar
dicas para novas colaborações

ex.: cientistas perto na rede terão colegas em
comum, estarão em círculos similares – isso sugere
que eles mesmos podem colaborar num futuro
próximo
aplicação


Organização grande pode se beneficiar das
interações na rede social informal entre os
empregados; as quais suplementam a
hierarquia oficial imposta pela companhia.
Monitoramento de redes terroristas – indivíduos
particulares estão trabalhando juntos, mesmo
que sua interação não seja diretamente
observada.
Contribuições

Predição de links por medidas da proximidade
dos nós na rede


quais medidas de proximidade melhor predizem os
próximos relacionamentos
Resultados sugerem que previsões podem ser
feitas a partir de estudos da topologia da rede

técnicas de teoria dos grafos.
metodologia




Base de artigos científicos (nós: autores;
arestas: colaboração no mesmo trabalho)
Coleção de artigos divididos em dois períodos
Período de treinamento → aplicação de
técnicas → definição de lista decrescente de
“scores(x,y)”
Comparação das melhores arestas (de maior
“score”) com as novas ligações reais
técnicas

Vizinhança

Caminhos

Caminhada aleatória
Técnicas - vizinhança

Vizinhos comuns

Coeficiente de Jaccard

Adamic/Adar

Conexões preferenciais

Ranking de similaridade
Vizinhos comuns

Interseção dos
vizinhos de x com os
de y
Coeficiente de Jaccard

Vizinhos comuns
divididos pela união
dos vizinhos
Adamic/Adar

Atribuir peso maior
aos vizinhos comuns
com poucos
relacionamentos
Conexões preferenciais (preferential
attachment)

Produto das
quantidades
respectivas de
vizinhos
Ranking de similaridade


x e y são similares, se
tiverem vizinhos
similares
Definição recursiva
Técnicas - caminhos

Menor caminho

Katz
Menor caminho

Menor caminho entre x e y
Katz



Caminhos de
tamanho “l” entre x e
y
ß<1
Quanto maior o
caminho, menor a
sua importância
Técnicas – caminhada aleatória

“hitting time”

“commute time”
Hitting time

Numa caminhada
aleatória, em quantos
passos eu vou de x
para y
Commute time
resultados

O grafo
realmente
contém
informações
úteis em sua
topologia
Campeões da predição


Adamic/
Adar
Katz
Problema dos mundos pequenos



De fato um problema para a
técnica de “menor caminho”:
caminhos curtos entre nós
muito distintos, que
dificilmente se relacionarão.
ex.: cientistas de campos
muito distintos têm um
caminho relativamente curto
entre si
No ex., outras técnicas
mostram robustez com
relação à fraca colaboração
Pode melhorar...



O melhor: 16% de acerto
Tirar mais vantagem das informações da
topologia
Tratar colaborações mais recentes como mais
importantes
Referência

Liben-Nowell, David.; Kleinberg, Jon. The Link
Prediction Problem for Social Networks. CIKM
'03 Proceedings of the twelfth international
conference on Information and knowledge
management, 2003.
Obrigado!
Link Prediction Problem for Social Networks
Diego Spíndola