38
Predição de Relacionamentos Paulo Soares

Predição de Relacionamentos

  • Upload
    zelig

  • View
    31

  • Download
    0

Embed Size (px)

DESCRIPTION

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 - PowerPoint PPT Presentation

Citation preview

Page 1: Predição de  Relacionamentos

Predição de Relacionamentos

Paulo Soares

Page 2: Predição de  Relacionamentos

Roteiro

• Introdução• Métricas• Abordagens– Não temporal– Temporal

• Aplicações• Caso prático• Conclusão

Page 3: Predição de  Relacionamentos

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

Paulo
Esse crescimento influenciou pesquisas em análise de redes sociais
Page 4: Predição de  Relacionamentos

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.

Page 5: Predição de  Relacionamentos

Representação

Alan

Alice Bob

?

V = {Alan, Alice, Bob}E = {(Alan, Alice),(Alan, Bob))}G = <V,E>

Page 6: Predição de  Relacionamentos

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

Page 7: Predição de  Relacionamentos

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

Page 8: Predição de  Relacionamentos

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

Page 9: Predição de  Relacionamentos

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

Page 10: Predição de  Relacionamentos

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¿

Page 11: Predição de  Relacionamentos

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

Page 12: Predição de  Relacionamentos

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

Page 13: Predição de  Relacionamentos

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)

Page 14: Predição de  Relacionamentos

Ranqueamento

a

d

c

b

e

• Ex. Common Neighbors

Rede no tempo t

a

d

c

b

e

Possível rede no tempo t’

Page 15: Predição de  Relacionamentos

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)

Page 16: Predição de  Relacionamentos

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

Page 17: Predição de  Relacionamentos

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

Page 18: Predição de  Relacionamentos

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

Page 19: Predição de  Relacionamentos

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’

Page 20: Predição de  Relacionamentos

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

𝑠𝑐𝑜𝑟𝑒 (𝑥 , 𝑦 )=(𝑆¿¿ 𝑠 (𝑥 , 𝑦 )+𝑚𝑠

𝑎)∗(𝑆¿¿𝑡 (𝑥 , 𝑦 )+

𝑚𝑡

𝑎)¿ ¿

Page 21: Predição de  Relacionamentos

Aplicações

• Redes de Relacionamentos

Page 22: Predição 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]

Page 23: Predição de  Relacionamentos

Aplicações

• Redes de Atores

Rede de atores do romance Les Misérables de Victor Hugo [NEWMAN, M. E. J.; GIRVAN, M., 2004]

Page 24: Predição de  Relacionamentos

Aplicações

• Emails

Page 25: Predição de  Relacionamentos

Caso Prático

Page 26: Predição de  Relacionamentos

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

Page 27: Predição de  Relacionamentos

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

Page 28: Predição de  Relacionamentos

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

Page 29: Predição de  Relacionamentos

Caso Prático

• Se λ = 2 semanas e ωout = 4

IR(Alice,Bob) = ωout(1 + 0.5) + 1 = 7

Page 30: Predição de  Relacionamentos

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

Page 31: Predição de  Relacionamentos

Caso Prático

• Suggestion score1. Top Contact

Não considera similaridade entre grupos

2. Intersecting Group Count Não considera Interactions Rank

Page 32: Predição de  Relacionamentos

Caso Prático

• Suggestion score3. Intersecting Group Score

Considera similaridade e IRs

4. Weighted Intersecting Group Score

Page 33: Predição de  Relacionamentos

Caso Prático

Page 34: Predição de  Relacionamentos

Caso Prático

• Don’t forget Bob!

Page 35: Predição de  Relacionamentos

Caso Prático

• Got the wrong Bob?

Page 36: Predição de  Relacionamentos

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

Page 37: Predição de  Relacionamentos

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

Page 38: Predição de  Relacionamentos

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