Predição de Relacionamentos
Paulo Soares
Roteiro
• Introdução
• Métricas
• Abordagens
– Não temporal
– Temporal
• Aplicações
• Caso prático
• Conclusão
Introdução
• Crescimento das redes sociais nos últimos
anos
• Disponibilidade das redes para estudo
• Redes sociais são muito dinâmicas
• Possuem ligações esparsas
Introdução
• Tipos de redes sociais
–
–
–
–
Coautoria. Ex.: DBLP, arXiv
Relacionamentos. Ex. Facebook, Orkut
Citação. Ex. CiteSeer
Atores. Ex. IMDb
• Problema
1. Predizer, com certa precisão, que ligações irão ocorrer na
rede em um determinado intervalo de tempo futuro.
2. Inferir relacionamentos “perdidos” em uma rede
observada.
Representação
Alan
Alice
Bob
?
V = {Alan, Alice, Bob}
E = {(Alan, Alice),(Alan, Bob))}
G = <V,E>
Métricas
• Similaridade entre dois nós de uma rede
• Características relacionais
– Áreas de pesquisa, gostos, comunidades...
• Características topológicas
– Baseadas na vizinhança
• Preferential attachment, common neighbors...
– Baseadas em distância
• Katz, hitting time
Métricas
• Preferential Attachment
𝑠𝑐𝑜𝑟𝑒 𝑥, 𝑦 = |Γ 𝑥 |. |Γ 𝑦 |
e
d
a
Γ 𝑎
=2
Γ 𝑏
=2
𝑠𝑐𝑜𝑟𝑒 𝑎, 𝑏 = 4
b
c
Prós: baseado no efeito “rich-get-richer”
Contras: ainda que bem conectados, nós distantes na rede provavelmente nunca formarão
links no futuro
Métricas
• Common Neighbors
𝑠𝑐𝑜𝑟𝑒 𝑥, 𝑦 = |Γ 𝑥 ∩ Γ 𝑦 |
Γ 𝑥 ∩ Γ 𝑦 = {𝑐, 𝑑}
e
𝑠𝑐𝑜𝑟𝑒 𝑎, 𝑏 = 2
d
a
b
c
Prós: amizades tendem a se formar intermediadas por nós em comum
Contras: os nós em comum podem ser hubs
Métricas
• Adamic/Adar
𝑠𝑐𝑜𝑟𝑒 𝑥, 𝑦 =
𝑧 ∈ Γ 𝑥 ∩Γ 𝑦
Γ 𝑥 ∩ Γ 𝑦 = {𝑐, 𝑑}
e
𝑠𝑐𝑜𝑟𝑒 𝑎, 𝑏 =
d
a
1
log(Γ 𝑧 )
1
1
+
log(2)
log(3)
b
c
Prós: minimiza efeitos dos hubs como vizinhos em comum
Contras: análise da rede localmente
= 5.42
Métricas
• Katz
∞
β𝑙 . |𝑝𝑎𝑡ℎ𝑠 <𝑙> (𝑥, 𝑦)|
𝑠𝑐𝑜𝑟𝑒 𝑥, 𝑦 =
𝑙=1
β = 0.05;
e
𝑙 = 1; |𝑝𝑎𝑡ℎ𝑠 <1> 𝑎, 𝑏 | = 0
𝑙 = 2; |𝑝𝑎𝑡ℎ𝑠 <2> 𝑎, 𝑏 | = 2
d
a
b
𝑠𝑐𝑜𝑟𝑒 𝑎, 𝑏 = 0.05 ∗ 0 + 0.0025 ∗ 2 = 0.005
c
Prós: minimiza efeitos da análise local
Contras: alto custo computacional
Métricas
• Hitting Time
𝑠𝑐𝑜𝑟𝑒 𝑥, 𝑦 = −(𝐻𝑥,𝑦 . 𝜋𝑦 + 𝐻𝑦,𝑥 . 𝜋𝑥 )
𝐻𝑥,𝑦 = nº de passos até atingir “y” a partir de “x” com random walking.
𝜋𝑥 = probabilidade estacionária de “x”.
Prós: métrica probabilista
Contras: apresenta resultados inferiores a outros algoritmos baseados no mesmo princípio
Abordagens
• Não temporal
– Usam um snapshot da rede no tempo t, para
predizer novos relacionamentos no período entre
t e um tempo futuro t’
1. Ranqueamento
2. Aprendizagem de máquina
Ranqueamento
• Algoritmo
1. Computar scores para cada par de vértices que não
formam links no conjunto de treinamento
2. Ranquear os scores em ordem decrescente
3. Determinar um limiar de corte
4. Classificar os pares acima desse limiar como
positivos (formam ligações) e os abaixo como
negativos (não formam ligações).
• Não considera remoção de arestas (geralmente)
Ranqueamento
• Ex. Common Neighbors
e
d
a
b
𝑠𝑐𝑜𝑟𝑒
𝑠𝑐𝑜𝑟𝑒
𝑠𝑐𝑜𝑟𝑒
𝑠𝑐𝑜𝑟𝑒
𝑠𝑐𝑜𝑟𝑒
𝑎, 𝑏
𝑎, 𝑒
𝑏, 𝑒
𝑐, 𝑑
𝑐, 𝑒
=2
=1
=1
=2
=0
𝑠𝑐𝑜𝑟𝑒
𝑠𝑐𝑜𝑟𝑒
𝑠𝑐𝑜𝑟𝑒
𝑠𝑐𝑜𝑟𝑒
𝑠𝑐𝑜𝑟𝑒
𝑎, 𝑏
𝑐, 𝑑
𝑎, 𝑒
𝑏, 𝑒
𝑐, 𝑒
=2
=2
=1
=1
=0
e
c
Rede no tempo t
d
a
b
c
Possível rede no tempo t’
Aprendizagem de Máquina
• Algoritmo
1. Gerar feature vector para cada par de vértices que
não formam links no conjunto de treinamento
2. Utilizar algum classificador (ex. SVM) para construir
o modelo de predição
• Classes
– 0. Não possui ligação
– 1. Possui ligação
• Não considera remoção de arestas (geralmente)
Aprendizagem de Máquina
• Ex. Feature vector: (pa,cn,aa,classe)
e
d
a
b
𝑓𝑣
𝑓𝑣
𝑓𝑣
𝑓𝑣
𝑓𝑣
𝑎, 𝑏
𝑎, 𝑒
𝑏, 𝑒
𝑐, 𝑑
𝑐, 𝑒
= (4,2,5.42,1)
= (2,1,2.09,0)
= (2,1,2.09,0)
= (4,2,6.64,1)
= (2,0,0,0)
c
e
d
a
b
c
Rede no tempo t
Rede no tempo t’
SVM
Modelo
Abordagens
• Temporal
– Usam a evolução da rede até um tempo t para
prever relacionamentos em um tempo entre t e
um tempo futuro t’
1. Graph evolution rules
2. Séries temporais
Graph Evolution Rules
• Objetivo: minerar o grafo para obter regras de
evolução que melhor descrevam a dinamicidade
da rede ao longo do tempo
• Algoritmo [Berlingerio, M. et al., 2009]
1. Gerar regras de evolução a partir da mineração do
grafo
2. Calcular scores, a partir das regras obtidas
3. Usar abordagem de ranqueamento para
classificação
Graph Evolution Rules
GER 1
5
d
5
1
Head
1
Body
b
6
2
0
0
𝑠𝑐𝑜𝑟𝑒1
𝑠𝑐𝑜𝑟𝑒2
𝑠𝑐𝑜𝑟𝑒3
𝑠𝑐𝑜𝑟𝑒4
GERM
GER 2
a
6
c
Rede no tempo t
0
Body
= 𝑐𝑜𝑛𝑓 𝑅
= sup 𝑅 ∗ 𝑐𝑜𝑛𝑓 𝑅
= 𝑐𝑜𝑛𝑓 𝑅 ∗ 𝑐𝑜𝑢𝑛𝑡 𝑝𝑐 , 𝑅
= sup 𝑅 ∗ 𝑐𝑜𝑛𝑓 𝑅 ∗ 𝑐𝑜𝑢𝑛𝑡 𝑝𝑐 , 𝑅
1
0
0
𝑝𝑐 , 𝑅
𝑝𝑐 , 𝑅
𝑝𝑐 , 𝑅
𝑝𝑐 , 𝑅
0
Head
5
d
b
7
5
7
7
a
6
6
6
Acumular scores,
ranquear e
predizer
6
c
Possível rede no tempo t’
Séries Temporais
• Objetivo: construir séries temporais para os
relacionamentos, modelar e predizer comportamento
futuro
• Algoritmo [HUANG, Z.; LIN, D., 2009]
1. Para cada par de nós do grafo, gerar série temporal de
ocorrência de ligações
2. Estimar modelo ARIMA* para cada série
3. Efetuar predições (probabilidades)
4. Para cada par de nós, combinar scores tradicionais (St)
com predições da série (Ss)
𝑠𝑐𝑜𝑟𝑒 𝑥, 𝑦 = (𝑆𝑠 𝑥, 𝑦 +
𝑚𝑠
* Autoregressive integrated moving average
𝑎) ∗ (𝑆𝑡 𝑥, 𝑦 +
𝑚𝑡
𝑎)
Aplicações
• Redes de Relacionamentos
Aplicações
• Redes de Coautoria
Rede de colaboração científica entre Duncan Wattz e Albert-László Barabási [NEWMAN, M. E. J., 2000]
Aplicações
• Redes de Atores
Rede de atores do romance Les Misérables de Victor Hugo [NEWMAN, M. E. J.; GIRVAN, M., 2004]
Aplicações
• Emails
Caso Prático
Caso Prático
• Detectar automaticamente grupos de
contatos
• Abordagens anteriores
1. Clustering
2. Análise de conteúdo (palavras chaves)
• Interações entre usuários implicitamente
agrupam contatos
Caso Prático
• Grafo Social Implícito
Bob
– Formado pela interação dos usuários
Alice e seus
Mom
contatos
Me e com peso
– Hipergrafo direcionado
– Egocêntrico
• Para cada usuário, analisa apenas o subgrafo que
contém suas interaçõesCarol
diretas
Bob
Caso Prático
• Interactions Rank (IR)
𝐼𝑔 = {𝐼𝑜𝑢𝑡𝑔𝑜𝑖𝑛𝑔 , 𝐼𝑖𝑛𝑐𝑜𝑚𝑖𝑛𝑔 }
𝐼𝑅(𝑔) = 𝜔𝑜𝑢𝑡
𝑖 ∈ 𝐼𝑜𝑢𝑡
1
2
𝑡𝑛𝑜𝑤 −𝑡(𝑖)
λ
+
𝑖 ∈ 𝐼𝑖𝑛
1
2
𝑡𝑛𝑜𝑤 −𝑡(𝑖)
λ
𝑡 𝑖 : Timestamp da interação i
λ: Halflife. Velocidade de decaimento da importância da interação
ωout: Importância da interação de saída com relação a interação de entrada
Caso Prático
• Se λ = 2 semanas e ωout = 4
IR(Alice,Bob) = ωout(1 + 0.5) + 1 = 7
Caso Prático
• Algoritmo ExpandSeed
– Entrada: usuário u e seed group S
– Saída: sugestões de contatos relacionados aos que estão
em S
• G(u): conjunto de todos os grupos na rede egocêntrica de u e seus
respectivos IRs

Para cada grupo g em G:
1. Iterar sobre cada contato c do grupo g
2. Não analisar contatos que já estão em S
3. Computar suggestion score para o contato c, dado a similaridade
entre g e S e os IRs do grupo g.
• F(c): soma dos scores de c em todos os grupos implícitos a que c
pertence
• Retornar contatos com maiores scores em F
Caso Prático
• Suggestion score
1. Top Contact

Não considera similaridade entre grupos
2. Intersecting Group Count

Não considera Interactions Rank
Caso Prático
• Suggestion score
3. Intersecting Group Score

Considera similaridade e IRs
4. Weighted Intersecting Group Score
Caso Prático
Caso Prático
• Don’t forget Bob!
Caso Prático
• Got the wrong Bob?
Caso Prático
• Algoritmo WrongBob
–
–
–
–
Entrada: usuário u e lista de destinatários L
Saída: par de contatos (ci,cj)
Ci: Contanto em L que provavelmente está errado
Cj: Contato sugerido em substituição a ci
• Para cada contato ci em L:
1.
2.
3.
4.
Criar um seed group s removendo ci de L
Gerar contatos sugeridos executando ExpandSeed(u,s)
Se ci está no conjunto de contatos sugeridos, é improvável que
tenha ocorrido um erro
Senão, comparar ci aos contatos sugeridos:

Se há um contato cj que é similar a ci e tem alto suggestion
score, mantenha o par {ci, cj} como candidato
• Retornar o par {ci, cj} com maior suggestion score
Conclusão
• Análise de Redes Sociais é uma área
emergente de pesquisa
• Link Prediction vem ganhando destaque na
área
• Técnicas de predição de relacionamentos
podem ser aplicadas em diversos domínios
• Abordagem temporal ainda é pouco
explorada, mas tem ganho adeptos
Referências
•
•
•
•
•
•
•
•
LIBEN-NOWELL, D.; KLEINBERG, J. (2003). The link prediction problem for social networks, Proceedings of
the twelfth international conference on information and knowledge management, New Orleans, LA, USA.
GETOOR, L.; Diehl, C. P. (2005). Link mining: a survey, ACM SIGKDD Explorations Newsletter, v.7 n.2, p.312.
BERLINGERIO, M. et al. (2009). Mining graph evolution rules, ECML PKDD, LCNS 5781, Springer, pp, 115130.
BRINGMANN, B. et al. (2010). Learning and Predicting the Evolution of Social Networks. IEEE Intelligent
Systems, 25(4), 26-35.
HUANG, Z.; LIN, D. K. J. (2009). The Time-Series Link Prediction Problem with Applications in
Communication Surveillance. INFORMS J. on Computing 21, 2, 286-303.
NEWMAN, M. E. J. (2000). Who is the best connected scientist?: a study of scientific coauthorship
networks. Santa Fé: The Santa Fé Institute. Paper 00-12-064.
NEWMAN, M. E. J.; GIRVAN, M. (2004). Finding and evaluating community structure in networks. Physical
Review E, 69(2), 26113.
ROTH, M. (2010). Suggesting friends using the implicit social graph. In Proceedings of the 16th ACM
SIGKDD international conference on Knowledge discovery and data mining (KDD '10). ACM, New York, NY,
USA, 233-242