Predição de Ligações em Redes Sociais: um problema
de classificação
20 de setembro de 2012
Antonio Augusto Teixeira Ribeiro Coutinho,
Rafael Glauber Nascimento e Silva
Instituto de Matemática – Departamento de Ciência da Computação
Universidade Federal da Bahia (UFBA)
Avenida Adhemar de Barros S/N – Ondina – Salvador – Bahia – Brasil
[email protected], [email protected]
Resumo
Este trabalho formaliza e desenvolve uma solução para o problema da predição
de ligações em redes sociais com base em medidas de proximidade entre seus vértices e nos métodos de classificação C4.5, AdaBoostM1 e Logistic. O experimento
empregou diferentes configurações de rede para demonstrar que informações sobre
futuras interações entre seus membros podem ser extraı́das da topologia de rede. O
algoritmo C4.5 obteve os melhores resultados quantitativos na maioria das amostras
de redes sociais analisadas.
Palavras-chave: Predição de Ligação - Rede Social - Mineração de Dados.
1
Introdução
Sites de redes sociais como Facebook 1 , MySpace 2 , Twitter 3 são exemplos de redes
grandes e complexas que representam pessoas e organizações, bem como os relacionamentos entre elas. Nesses ambientes virtuais, é possı́vel realizar diversas atividades tais
como: compartilhar recursos multimı́dia, emitir ou retransmitir opiniões, expressar idéias
e sentimentos, dentre outras possibilidades. Devido a sua crescente importância, diversos
aspectos dessas redes vem sendo estudados atualmente.
1
http://www.facebook.com/
http://www.myspace.com/
3
http://www.twitter.com/
2
1
Um dos objetivos importantes das pesquisas recentes em redes sociais é buscar inovações ou tecnologias que melhorem e expandam os relacionamentos entre seus integrantes.
Para isso, são investigados aspectos ligados com a estrutura das redes e seus relativos
impactos no comportamento humano. O crescente uso dessas redes por parte dos usuários
para as mais diversas atividades (BOYD; ELLISON, 2007) tem estimulado tanto o surgimento de dados para as pesquisas, como o desenvolvimento de trabalhos que mapeiam as
caracterı́sticas estruturais dessas redes (NEWMAN, 2003).
Neste trabalho, examinamos o problema da predição de ligações, que visa fundamentalmente verificar a seguinte proposição: dada uma configuração inicial de uma rede social,
podemos inferir que novos relacionamentos entre seus membros são suceptı́veis de ocorrer
num futuro próximo? Muitos pesquisadores trançaram estratégias para verificar se a proposição acima é possı́vel (JENSEN; NEVILLE, 2003), (HASAN et al., 2006), (LIBEN-NOWELL;
KLEINBERG, 2007), (SONG et al., 2009), (COSCIA; GIANNOTTI; PENSA, 2009), (KAHANDA;
NEVILLE, 2009), (HOFF, 2009), (P.NANCY; RAMANI, 2011), (FIRE et al., 2011), são alguns
exemplos. Nessas pesquisas, a análise computacional é realizada considerando as pessoas, organizações, documentos, textos, produtos ou qualquer outra entidade, como nós
de uma rede. As interações entre esses elementos é retratada como ligações, sendo que
estas ligações podem ainda informar outras caracterı́sticas sobre os relacionamentos do
que simplesmente a presença ou não de um vı́nculo entre as entidades.
Segundo (LIBEN-NOWELL; KLEINBERG, 2007) as redes sociais são objetos altamente
dinâmicos, tendo como consequência a adição de novas ligações em um ritmo acelerado ao
longo do tempo. Essas ligações significam o surgimento de novas interações na estrutura
social subjacente a rede social virtual. Por conta dessa caracterı́stica, muitos pesquisadores tem dedicado esforços para o desafio de criar e aperfeiçoar as técnicas de predição
de ligações existentes. Motivações para esse estudo estão em torno, principalmente, das
seguintes aplicações: aprimoramento de sistemas de recomendação, detecção de ligações
(redes terroristas e criminosas), monitoração e controle de viroses de computador, ampliação da colaboração em meios acadêmicos e profissionais.
A metodologia aplicada neste trabalho é baseada em pesquisas que tratam o problema
da predição de ligações como um problema de classificação. Medidas de similaridade baseadas na vizinhança dos vértices são descritas e avaliadas no contexto dos algoritmos de
classificação. Essas medidas são responsáveis por fornecer as caracterı́sticas dos relacionamentos da rede social, sendo usadas como dados de entrada pelos classificadores. Assim,
é possı́vel empregar os algoritmos existentes para mineração de dados sobre as informações extraı́das da rede. (HUAN, 2006) coloca que o problema da predição de ligações foi
formulado, recentemente, como uma tarefa genérica de extração de informações em dados
2
relacionais. Primeiro, o processo deve ser capaz de obter as caracterı́sticas das ligações
atuais da rede para, em seguida, realizar a classificação sobre o banco de dados criado.
Três métodos de classificação foram avaliados: C4.5 (QUINLAN, 1993), baseado em um
algoritmo de árvore de decisão; AdaBoostM1 (FREUND; SCHAPIRE, 1996), que aplica um
algoritmo baseado em boosting; e Logistic (CESSIE; HOUWELINGEN, 1992), um classificador baseado em regressão. Todos os classificadores foram avaliados usando quatro redes
distintas e bem conhecidas, com caracterı́sticas controladas de densidade, grau, diâmetro,
quantidade de vértices e número de arestas.
O restante deste trabalho está organizado da seguinte forma: na seção 2, é discutida
a modelagem em grafos além da discussão sobre as restrições do modelo para o problema.
As principais medidas de similaridade utilizadas para o processo de predição de ligações
são vistas na seção 3. Na seção 4, são determinados os procedimentos e as configurações
utilizadas no experimento. Na seção 5, são apresentados e discutidos os resultados obtidos
e, na seção 6, a conclusão deste trabalho.
2
Modelagem do Problema
Suponha uma rede social representada pelo grafo G =< V, E >, onde cada vértice
v ∈ V represente os elementos da rede (pessoas, organizações, etc.). Cada aresta e =
(u, v) ∈ E representa uma interação entre os vértices u e v que ocorreu em um determinado
momento t(e), e onde diferentes interações entre u e v são representados como arestas
paralelas com tempos potencialmente diferentes. Para dois tempos t < t0 , temos que
G[t, t0 ] denota um subgrafo de G que consiste de todas as arestas com um tempo entre t
e t0 .
Dessa forma, o problema da predição de ligações consistem em, dados quatro tempos
t0 < t00 < t1 < t01 , obtermos uma lista de arestas L que não estão presentes em G[t0 , t00 ]
e que formam exatamente as predições que aparecem na rede G[t1 , t01 ]. Nos referimos
a [t0 , t00 ] como um intervalo de treinamento e [t1 , t01 ] como um intervalo de teste. Um
algoritmo de predição p deve possuir acesso a rede social G[t0 , t00 ] e obter, como resultado
de sua execução, uma lista de arestas L que não estão presentes em G[t0 , t00 ] e que são
mais prováveis de aparecer em G[t1 , t01 ].
Devemos considerar que as redes sociais não crescem apenas pela adição de novas
arestas, mas também através da adição de novos vértices. Não é sensato predizer ligações
para as arestas cujos vértices não estão no intervalo de treinamento. Para avaliação dos
métodos de predição, normalmente é definido um conjunto Núcleo consistindo de todos os
vértices incidentes a pelo menos alguma aresta em G[t0 , t00 ] e a pelo menos alguma aresta
3
em G[t1 , t01 ]. São consideradas apenas as novas arestas entre os elementos do conjunto
T
∗
núcleo, ou seja, Enovo
= Enovo (N ucleo × N ucleo).
Neste trabalho, a natureza dos participantes da rede e das suas relações não é importante, pois as medidas de similaridade escolhidas para os algoritmos dizem respeito
apenas à topologia da rede social. Evidentemente, existem dois métodos básicos para selecionar um conjunto de dados para avaliação dos sistemas de análise no contexto de redes
sociais: coleta de um ou mais conjuntos de dados reais (na expectativa de que eles sejam
representativos) ou a geração de conjuntos de dados com caracterı́sticas bem conhecidas
e presentes nas redes sociais. Como o intuito deste trabalho se restringe à compreensão
e implementação dos métodos de predição de ligações, e não na sua utilização para fins
especı́ficos, escolhemos a segunda abordagem. As amostras empregadas são descritas na
Seção 4, onde todos os vértices de uma dada amostra fazem parte do conjunto Núcleo
analisado em cada experimento. Ou seja, para todo v ∈ V de G[t0 , t00 ] em uma predição
de ligação p considerada, é gerado como saı́da uma lista Lp de pares em (V ×V )−Eanterior .
3
Medidas para Predição
Nesta seção, examinamos um conjunto de métodos voltados a predição de ligações.
Todos os métodos atribuem um peso à ligação entre os pares de vértices < x, y > definido
pela função escore(x, y) com base no grafo Gentrada . Em seguida, produz uma lista L em
ordem decrescente da pontuação escore(x, y). Este procedimento pode ser visto como o
cálculo de uma medida da proximidade ou semelhança entre os vértices x e y em relação à
topologia da rede. Em geral, essas medidas de proximidade são baseadas tanto na teoria
de grafos quanto no comportamento dos integrates da rede social.
Por exemplo, dentre as medidas possı́veis, uma abordagem básica é a classificação de
pares < x, y > pelo comprimento do seu caminho mais curto em Gentrada . Essa medida é
usada em redes de colaboração, seguindo a noção de que elas são estruturadas na forma
de pequenos mundos 4 onde os indivı́duos se relacionam através de caminhos curtos (NEWMAN, 2001). Neste caso, classificamos os pares em ordem decrescente definindo a função
escore(x, y) como o negativo do comprimento do caminho mais curto.
Na análise das redes sociais, é importante considerar diferentes caracterı́sticas significativas em conjunto buscando refletir melhor a dinâmica do seu comportamento. Isso
porque a escolha das caracterı́sticas influenciam diretamente nos resultados, restringindo
ou ampliando o conhecimento adquirido sobre a rede.
4
Em particular, estruturas conhecidas como pequenos-mundos estão presentes em outras redes e são
estudadas intensamente desde que foram descritas pela primeira vez em (WATTS; STROGATZ, 1998).
4
Nos experimentos discutidos na Seção 4, diferentes medidas foram empregadas simultaneamente junto com diferentes métodos de mineração de dados para realização das
predições. As medidas podem ser classificadas em três categorias: medidas monádicas,
medidas diádicas e medidas do grafo. Nas próximas seções, mostramos alguns exemplos
de medidas conhecidas em cada categoria, evidenciando aquelas utilizadas neste trabalho.
3.1
Medidas Monádicas
As medidas monádicas são aquelas calculadas a partir de um único vértice. Na Tabela 1, são listadas algumas medidas monádicas conhecidas.
Tabela 1: Exemplos de medidas monádicas.
Nome
Definição
Descrição
Grau
|Γ(vi )|
O número de ligações de vi
com outros vértices.
Grau normalizado
|Γ(vi )|
|V | − 1
O grau normalizado (assume valores entre 0 e 1).
max({dist(vi , vj ) : vj ∈ V })
O tamanho do caminho
mais curto para o vértice
mais distante de vi , onde
dist(vi , vj ) é o tamanho do
caminho mais curto entre os
vértices vi e vj .
Excentricidade

Assume valor 1 se vi é um

1, se excentricidade(vi ) =

Centralidade
vértice central (excentricimin{excentricidade(vj ) : vj ∈ Vn }
de Jordan 
dade mı́nima) no grafo. Se

0, caso contrário
não, assume valor 0.
1
Proximidade
X
dist(vi , vj )
vj ∈Vn ,vj 6=vi
5
O quão perto um vértice
está de todos os outros, variando de 0 (muito longe) até
1/(|V | − 1) (muito central)
Intermediação
X
X
vj ∈V vk ∈Vn ,vk 6=vi
Classificação
de Página
(pagerank )
|P (vj , vk , vi )|
|P (vj , vk )|
O ponto fixo da seguinte definição
recursiva: pagerank(vi ) =
X
vj ∈V,ui,j ∈U
pagerank(vj )
|{uj,k : uj,k ∈ U }|
A soma de todos os caminhos mais curtos entre
todos os vétices que contêm vi como uma percentagem de todos os caminhos
mais curtos entre todos os
vértices, variando de 0 até
[(|V | − 1)(|V | − 2)]/2
Esta é uma definição básica
do algoritmo de classificação
de páginas web do Google.
Intuitivamente, um vértice
tem importância se outros
vértices de importância estão conectados a ele.
Dentre as medidas monádicas apresentadas, apenas o grau normalizado do vértice foi
utilizada em nossos experimentos. Essa medida reflete a popularidade de cada indivı́duo
na rede social, pois representa o número de ligações que esta pessoa possui com outros
indivı́duos, porém não considera as caracterı́sticas dessas ligações.
3.2
Medidas Diádicas
As medidas diádicas são calculadas para um par de vértices. Na Tabela 2 são listadas
algumas medidas diáticas conhecidas.
Tabela 2: Exemplos de medidas diádicas
Nome
Distância
Definição
Descrição
dist(vi , vj )
O comprimento do caminho
mais curto entre vi e vj . Se
vj é inacessı́vel de vi , então
dist(vi , vj ) = 0. A distância
a partir de um vértice a ele
mesmo é indefinido.
6
Vizinhos
Comuns
Coeficiente
de Jaccard
|Γ(vi ) ∩ Γ(vj )|
O número de vértices ligados a ambos os vértices (ou
seja, seus amigos mútuos).
|Γ(vi ) ∩ Γ(vj )|
|Γ(vi ) ∪ Γ(vj )|
O número de vizinhos em
comum dos vértices dividido
pelo número de vértices que
são vizinhos de algum deles.
Caso geral:
1
Similaridade
log(f requencia(z))
z:caracterı́stica comum
AdaCaso de vizinhos comuns:
mic\Adar
X
1
X
vz ∈Γ(vi )∩Γ(vj )
Ligação
Preferencial
Medida de
Katz
Tempo de
alcançe
log(|Γ(vz )|)
O produto do número de
arestas incidentes para os
dois vértices.
|Γ(vi )| · |Γ(vj )|
∞
X
O número de caracterı́sticas partilhadas pelos vértices, dividido pelo log da
frequência das caracterı́sticas. Esta medida considera
as métricas raras mais fortemente.
β l · |paths<l>
vi ,vj |
l=1
A soma de todos os caminhos entre os nós de forma
exponencialmente amortecida pelo comprimento, considerando os caminhos curtos mais fortemente.0 <
β<1
O número esperado de passos de um passeio aleatório
saindo de vi para vj .
Hi,j
Distribuição estacionária de vj no pasClassificação
seio aleatório a partir de vi , com prode Página
babilidade α de voltar à origem (vi ) a
da Origem
cada passo.
7
Uma versão da medida
tempo de alcançe onde os
vértices mais próximos tem
maior importância.
O ponto fixo da seguinte definição:
simrank(vi , vj ) =
Classificação
Similar
(SimRank )
Dois vértices são semelhantes
na
medida
em que são unidos a
vizinhos
semelhantes.

1 , se vi = vj






X X
γ
·
simrank(va , vb )




v
∈Γ(v
)
v
∈Γ(v
)
a
i b
j


, caso contrário
|Γ(vi )||Γ(vj )|
As medidas diádicas utilizadas neste trabalho foram vizinhos em comum, coeficiente
de Jaccard, ligação preferencial e Adamic/Adar. Na rede social, a medida vizinhos em
comum representa a quantidade de integrantes que ambas as pessoas analisadas conhecem
na rede, que é diretamente proporcional para o estabelecimento de uma relação entre
elas. Entretanto, o coeficiente de Jaccard acresenta uma outra dimensão a essa medida,
considerando todos os amigos que ambas as pessoas analisadas possuem na rede de maneira
inversamente proporcinal, ou seja: quanto menor o total de amigos que ambos possuirem
na rede, mais peso terá a quantidade de amigos que eles possuem em comum. A medida
ligação preferencial apenas leva em consideração a quantidade de integrantes que as duas
pessoas apresentam em comum para o estabelecimento da relação. A medida Adamic/Adar
analisa os amigos em comum de ambas as pessoas e considera que, quanto menos amigos
seus vizinhos em comum tiverem, maior será a probabilidade dessas pessoas criarem uma
ligação entre si.
3.3
Medidas do Grafo
As medidas de grafo são calculadas para um grafo inteiro. Na Tabela 3 são listadas
algumas medidas de grafos conhecidas. Nenhuma medida dessa classificação foi usada em
nossos experimentos, pois tais medidas apresentam o mesmo valor para todas instâncias
e não intereferem no processo de classificação.
Tabela 3: Exemplos de medidas de grafo.
Nome
Definição
Descrição
8
X
Densidade
O quanto é completo um
grafo. Os valores possı́veis
estão entre 0 (todos vértices com grau zero) e 1 (um
grafo completo).
grau(vj )
vj ∈V
|V | · (|V | − 1)
Diâmetro
max(excentricidade(vi ) : vi ∈ V )
O caminho mais curto entre
os dois vértices mais distantes em um grafo.
Tamanho
|V |
Quantidade de vértices do
grafo.
Número de
arestas
|E|
Quantidade de arestas do
grafo.
4
Configuração do Experimento
Em nossa configuração experimental, usamos dados sobre quatro redes sociais, disponı́veis em InfoVis:Wiki 5 (the Information Visualization community platform). Essas amostras foram obtidas através de softwares geradores de redes sociais, com uso de parâmetros
de entrada especı́ficos para geração de cada uma delas. Na Tabela 4, são apresentadas
informações sobre cada uma das amostras empregadas.
Como pode ser visto na Figura 1, cada rede é diferente das outras, porém todas possuem o mesmo número de vértices. Em W6, é observada a presença de dois componentes,
tornando assim o grafo desconexo. Em W9, é possı́vel perceber uma maior densidade,
com os vértices apresentando um maior grau em relação as outras redes. Na Seção 5,
esses atributos são percebidos como influentes nos resultados do experimento sobre os
algoritmos de classificação.
A realização do experimento segue etapas semelhantes ao processo de mineração de
dados onde, primeiramente, são recuperados os dados brutos. Estes dados são os próprios
integrantes (vértices) e os relacionamentos entre eles (arestas). Em seguida, ainda na fase
de pré-processamento, são calculadas as médidas de similaridades propostas: grau normalizado, vizinhos em comum, coeficiente de Jaccard, ligação preferencial e Adamic/Adar.
Todas essas medidas são baseadas na vizinhança dos vértices, como descrito anteriormente
na Seção 3, cada uma delas resulta em um escore que é adicionado em cada registro de
5
http://www.infovis-wiki.net/
9
Tabela 4: Caracterı́sticas das redes sociais utilizadas no experimento.
Figura 1: Representação gráfica das redes W1, W2, W6 e W9 utilizadas no experimento.
(fonte: http://www.infovis-wiki.net/ )
relacionamento encontrado na rede. Medidas baseadas em conjunto de todos os caminhos
não foram consideradas neste experimento.
Agora com esses dados, é possı́vel dar inı́cio ao processo de aprendizado de máquina.
Nesta etapa, é fornecida como entrada aos algoritmos de mineração de dados as informações obtidas da rede e os escores de similaridade de todos os relacionamentos. Dessa forma,
cada algoritmo é capaz de, ao não classificar corretamente uma relação, predizer um novo
valor sobre o campo binário de ligação entre um vértice e outro. Excepcionalmente, é
verificado somente os falsos negativos da matriz de confusão, pois os atuais positivos não
classificados não são de interesse deste trabalho.
5
Resultados e Discussões
Com base nos dados experimentais de cada rede social, os algoritmos foram, em primeiro lugar, avaliados quanto sua capacidade de classificação correta. Essa primeira medida de acurácia aponta a qualidade de cada algoritmo em torno de cada rede social. Na
Figura 5, é apresentado cada resultado para os algoritmos. É possı́vel notar as altas taxas
de acerto na classificação de cada algoritmo utilizado, mesmo cada um deles empregando
10
abordagens diferentes no processo de apredizado.
Tabela 5: Resultado da classificação de cada algoritmo para cada rede social experimentada.
O desempenho dos algoritmos foram avaliados através da matriz de confusão sobre o
campo utilizado na predição (ou seja, se existe ou não um relacionamento entre cada par
de vértices). Na Figura 6, apresentamos este resultado em torno de cada algoritmo sobre
todas as redes sociais utilizadas no experimento.
Tabela 6: Matriz de Confusão para cada algoritmo em cada rede social experimentada.
Analisando o experimento de predição do algoritmo C4.5, é possı́vel perceber a influência das medidas de similaridade sobre a predição entre dois vértices. Na Figura 2, é
apresentado um exemplo dessa relação.
É possı́vel verificar a presença de alguns vizinhos em comum, e poucos vértices adjacentes que não são compartilhados entre os dois. Esse caso mostra o indı́cio de que
pessoas pouco populares, que possuem muitos vizinhos em comum, tendem a estabelecer
uma ligação. O caso contrário também é percebido, onde relações entre pessoas muito
populares não caracterizam uma nova ligação no futuro.
6
Conclusão
Os algoritmos de classificação utilizados apresentaram resultados diferentes na classificação das relações, mas de forma geral os valores de acurácia obtidos foram satisfatórios.
A menor taxa de classificação correta encontrada aconteceu na rede W9 para o algoritmo
11
Figura 2: Predição de Ligação entre o vértice 36 e 37 na rede W1 utilizando o algoritmo
C4.5.
AdaBoostM1, alcançando o percentual de 80, 111%. Os demais algoritmos também apresentaram as menores taxas na rede social mais densa. Em contrapartida, na rede W6
os algoritmos encontraram menos dificuldade no processo de classificação. Os resultados
para essa rede social foram todos acima de 95%, com o algoritmo Logistic apresentando
o melhor resultado: 99, 6435% das instâncias classificadas corretamente.
Avaliando a matriz de confusão dos resultados obtidos, percebemos que em redes espaças como W6 é difı́cil realizar predição no atributo binário de relacionamento. Observa-se
que é necessário existir algumas caracterı́sticas para que este processo ocorra, sendo uma
delas a presença de uma taxa de densidade superior a apresentada por essa rede (0, 21).
Ainda sobre a rede social W6, o único algoritmo capaz de realizar predição positiva foi
o Logistic. Os demais algoritmos apresentaram somente valores para predições negativas,
algo que não é relevante para este trabalho.
De modo geral, o algoritmo C4.5 apresentou os melhores resultados de classificação
para a maioria das redes sociais analisadas. Na rede social W2, foi o único algoritmo que
conseguiu realizar predição positiva. Aqui é interessante destacar que esta rede tem a
mesma densidade de W1. Isso é um indicativo de que a caracterı́stica topológica da rede
interfere no processo de predição, pois as medidas de similaridades utilizadas foram as
mesmas, mas os algoritmos não tiveram êxito similar na classificação de W1 e W2.
Cada rede social, com suas caracterı́sticas peculiares, apresentou resultados diferentes
para os três algoritmos de classificação. Isso demostra que cada abordagem pode ser
prejudicada ou valorizada pela mudança dos atributos (medida de similaridade usada)
e topologia da rede. Trabalhos futuros de investigação, analisando outros algoritmos e
12
outras medidas de similaridade, são necessários. Um novo experimento pode demonstrar
que soluções hı́bridas, combinando algoritmos e medidas de similaridade no contexto de
cada cenário, é um caminho viável para predição de ligações em redes sociais.
Referências
BOYD, d. m.; ELLISON, N. B. Social network sites: Definition, history, and scholarship.
Journal of Computer-Mediated Communication, Blackwell Publishing Inc, v. 13, n. 1, p.
210–230, 2007. ISSN 1083-6101.
CESSIE, S. L.; HOUWELINGEN, J. C. V. Ridge estimators in logistic regression.
Applied Statistics, Blackwell Publishing for the Royal Statistical Society, v. 41, n. 1, p.
191–201, 1992. ISSN 00359254.
COSCIA, M.; GIANNOTTI, F.; PENSA, R. Social network analysis as knowledge
discovery process: A case study on digital bibliography. In: Proceedings of the
2009 International Conference on Advances in Social Network Analysis and Mining.
Washington, DC, USA: IEEE Computer Society, 2009. (ASONAM ’09), p. 279–283.
ISBN 978-0-7695-3689-7.
FIRE, M. et al. Link prediction in social networks using computationally efficient
topological features. In: SocialCom/PASSAT. [S.l.]: IEEE, 2011. p. 73–80. ISBN
978-1-4577-1931-8.
FREUND, Y.; SCHAPIRE, R. E. Experiments with a new boosting algorithm. In:
International Conference on Machine Learning. [S.l.: s.n.], 1996. p. 148–156.
HASAN, M. A. et al. Link prediction using supervised learning. In: In Proc. of SDM 06
workshop on Link Analysis, Counterterrorism and Security. [S.l.: s.n.], 2006.
HOFF, P. Multiplicative latent factor models for description and prediction of social
networks. Computational & Mathematical Organization Theory, Springer Netherlands,
v. 15, p. 261–272, 2009. ISSN 1381-298X.
HUAN, Z. Link prediction based on graph topology: The predictive value of the
generalized clustering coefficient. In: . [S.l.: s.n.], 2006.
. Dynamic
JENSEN, D.; NEVILLE, J. Data mining in social networks. In:
Social Network Modeling and Analysis Workshop Summary and Papers. [S.l.]: National
Academy Press, 2003. p. 289.
13
KAHANDA, I.; NEVILLE, J. Using transactional information to predict link strength
in online social networks. In: ADAR, E. et al. (Ed.). ICWSM. [S.l.]: The AAAI Press,
2009. ISBN 978-1-57735-421-5.
LIBEN-NOWELL, D.; KLEINBERG, J. The link-prediction problem for social networks.
J. Am. Soc. Inf. Sci. Technol., John Wiley &amp; Sons, Inc., v. 58, n. 7, p. 1019–1031,
maio 2007. ISSN 1532-2882.
NEWMAN, M. The structure and function of complex networks. SIAM review, JSTOR,
v. 45, n. 2, p. 167–256, 2003. ISSN 0036-1445.
NEWMAN, M. E. J. The structure of scientific collaboration networks. Proceedings of
the National Academy of Sciences of the United States of America, Santa Fe Institute,
1399 Hyde Park Road, Santa Fe, NM 87501, USA. [email protected], v. 98, n. 2, p.
404–409, January 2001. ISSN 0027-8424.
P.NANCY; RAMANI, D. A comparison on performance of data mining algorithms in
classification of social network data. International Journal of Computer Applications,
v. 32, n. 8, p. 47–54, 2011.
QUINLAN, J. R. C4.5: programs for machine learning. San Francisco, CA, USA: Morgan
Kaufmann Publishers Inc., 1993. ISBN 1-55860-238-0.
SONG, H. H. et al. Scalable proximity estimation and link prediction in online
social networks. In: Proceedings of the 9th ACM SIGCOMM conference on Internet
measurement conference. New York, NY, USA: ACM, 2009. (IMC ’09), p. 322–335.
WATTS, D. J.; STROGATZ, S. H. Collective dynamics of ’small-world’ networks.
Nature, Nature Publishing Group, Department of Theoretical and Applied Mechanics,
Cornell University, Ithaca, New York 14853, [email protected], v. 393, n. 6684, p.
440–442, jun 1998. ISSN 0028-0836.
14