Predição de Relacionamentos

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

• Problema1. 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𝑠𝑐𝑜𝑟𝑒 (𝑥 , 𝑦 )=¿ Γ (𝑥 )∨ .∨Γ (𝑦 )∨¿

a

d

c

b

e |Γ (𝑎)|=2|Γ (𝑏)|=2𝑠𝑐𝑜𝑟𝑒 (𝑎 ,𝑏)=4

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𝑠𝑐𝑜𝑟𝑒 (𝑥 , 𝑦 )=¿ Γ (𝑥 )∩Γ (𝑦 )∨¿

a

d

c

b

e Γ (𝑥 )∩Γ (𝑦 )={𝑐 ,𝑑}𝑠𝑐𝑜𝑟𝑒 (𝑎 ,𝑏)=2

Prós: amizades tendem a se formar intermediadas por nós em comumContras: os nós em comum podem ser hubs

Métricas

• Adamic/Adar𝑠𝑐𝑜𝑟𝑒 (𝑥 , 𝑦 )= ∑

𝑧∈ Γ (𝑥 )∩Γ (𝑦 )

1log (Γ (𝑧 ))

a

d

c

b

e Γ (𝑥 )∩Γ (𝑦 )={𝑐 ,𝑑} = 5.42

Prós: minimiza efeitos dos hubs como vizinhos em comumContras: análise da rede localmente

Métricas

• Katz𝑠𝑐𝑜𝑟𝑒 (𝑥 , 𝑦 )=∑

𝑙=1

∞

β 𝑙 .∨ h𝑝𝑎𝑡 𝑠❑¿ 𝑙>¿(𝑥 ,𝑦 )∨¿ ¿¿

a

d

c

b

e

𝑙=1 ;¿ h𝑝𝑎𝑡 𝑠❑¿1>¿ (𝑎 ,𝑏 )∨¿ 0¿

𝑠𝑐𝑜𝑟𝑒 (𝑎 ,𝑏)=0.05∗0+0.0025∗2=0.005

Prós: minimiza efeitos da análise localContras: alto custo computacional

β=0.05 ;

𝑙=2 ;∨ h𝑝𝑎𝑡 𝑠❑¿2>¿ (𝑎 ,𝑏)∨¿2¿

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 probabilistaContras: 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. Ranqueamento2. Aprendizagem de máquina

Ranqueamento

• Algoritmo1. Computar scores para cada par de vértices que não

formam links no conjunto de treinamento2. Ranquear os scores em ordem decrescente3. Determinar um limiar de corte4. 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

a

d

c

b

e

• Ex. Common Neighbors

Rede no tempo t

a

d

c

b

e

Possível rede no tempo t’

Aprendizagem de Máquina

• Algoritmo1. Gerar feature vector para cada par de vértices que não

formam links no conjunto de treinamento2. 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)

(4,2,5.42,1) (2,1,2.09,0) (2,1,2.09,0) (4,2,6.64,1) (2,0,0,0)

a

d

c

b

e

Rede no tempo t

a

d

c

b

e

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 rules2. 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 obtidas3. Usar abordagem de ranqueamento para classificação

Graph Evolution Rules

Rede no tempo t

a

d

c

b5

6

5 6 GERM

0

1

0

1

2

Body Head

GER 1

0

0

0

0

1

Body Head

GER 2

Acumular scores, ranquear e predizer

a

d

c

b5

6

5 6

6

6

7

7

7

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ções2. Estimar modelo ARIMA* para cada série3. 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. Clustering2. Análise de conteúdo (palavras chaves)

• Interações entre usuários implicitamente agrupam contatos

Caso Prático

• Grafo Social Implícito– Formado pela interação dos usuários e seus

contatos– Hipergrafo direcionado e com peso– Egocêntrico• Para cada usuário, analisa apenas o subgrafo que

contém suas interações diretas

Me

Bob

Alice

Bob

Mom

Carol

Caso Prático

• Interactions Rank (IR)𝐼𝑔={𝐼𝑜𝑢𝑡𝑔𝑜𝑖𝑛𝑔 , 𝐼𝑖𝑛𝑐𝑜𝑚𝑖𝑛𝑔 }

𝐼 𝑅 (𝑔)=𝜔𝑜𝑢𝑡 ∑𝑖∈ 𝐼𝑜𝑢𝑡

( 12 )𝑡 𝑛𝑜𝑤− 𝑡 (𝑖)

λ +∑𝑖∈ 𝐼𝑖𝑛

( 12 )𝑡 𝑛𝑜𝑤−𝑡 (𝑖)

λ

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 g2. Não analisar contatos que já estão em S3. 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 score1. Top Contact

Não considera similaridade entre grupos

2. Intersecting Group Count Não considera Interactions Rank

Caso Prático

• Suggestion score3. 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. Criar um seed group s removendo ci de L

2. Gerar contatos sugeridos executando ExpandSeed(u,s)3. Se ci está no conjunto de contatos sugeridos, é improvável que tenha ocorrido um

erro4. 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.3-12.

• BERLINGERIO, M. et al. (2009). Mining graph evolution rules, ECML PKDD, LCNS 5781, Springer, pp, 115-130.

• 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