SISTEMA DE RECOMENDAÇÃO
DE USUÁRIOS EM REDE SOCIAIS
Natália Cabral e Tiago Ferreira
Roteiro

Motivação

Redes Sociais

Sistemas de Recomendação

Mecanismo de recomendação baseado na topologia

Extensão do Mecanismo de Recomendação

Conclusão
Motivação
“ 43,9 milhões de usuários utilizando Redes Sociais no
Brasil”
" 90,8% dos usuários da internet no Brasil,
fazem parte de alguma rede social.”
* dados da comScore - Junho de 2011 ( http://www.comscore.com/por/ )
Motivação

Como encontrar usuários relevantes em meio a uma
imensidão?
 Navegar
entre listas de amizades dos usuários
 Busca de usuários
 Catálogo de usuários

Sistemas de Recomendação pode ser a solução
Redes Sociais
“Estruturas organizacionais
dinâmicas que visam conectar
um conjunto de indivíduos,
promovendo o relacionamento,
a comunicação, e a partilha de
experiências, agrupando-os de
acordo com interesses em
comum.”
Sistema de Recomendação
Um sistema que tenta prever o gosto de cada usuário
baseado em informação submetida por si e pelos
restantes utilizadores.
Sistemas de Recomendação de Usuários


Necessidade de encontrar pessoas para adicionar na lista
de amigos
Dois objetivos:
 Encontrar pessoas que você já conhece
 Encontrar pessoas que você gostaria de conhecer
Sistemas de Recomendação de Usuários

Facebook
Sistemas de Recomendação de Usuários

Diferente dos outros sistemas de recomendação:
 Relação
de amizade bi-direcional
 Apresentação da lista de amigos no perfil
Estudo de Caso

Encontrar as repostas para:

Qual a diferença em eficiência de diferentes algoritmos de
recomendação?

Que características são diferentes na recomendação de uma
pessoa conhecida e uma desconhecida?

Um sistema de recomendação é efetivo em aumentar a
quantidade de amigos numa rede social?

Qual o impacto que um sistema de recomendação causa em um
site?
Estudo de Caso

Implementação de sistemas de recomendação de
usuários para o sistema Beehive
 Quatro

algoritmos diferentes
Realização de dois experimentos
 Personalized
Survey
 Controlled field study
Beehive

Rede Social Corporativa da IBM
 Lançada
em setembro de 2007
 Mais de 38000 usuários
 Média de 8.2 amigos por usuário
 Conceito de amizade unidirecional
Algoritmos
Baseado em
Conteúdo
Baseado na
Estrutura da Rede
Content Matching
Content-plus-Link
Friend-of-Friend
SONAR
Content Matching


“Se duas pessoas escrevem na rede sobre assuntos similares, essas
têm interesse em se conhecer”
Cada usuário passou a ter uma “nuvem de tags”
A e B são considerados
similares se eles
compartilham tags em comum
e também se somente poucas
pessoas compartilham tal tag
Content-plus-Link


Tem como objetivo diminuir a quantidade de pessoas
desconhecidas na recomendação
Content Matching + Social link information
A
similaridade entre dois usuários é aumentada em 50% se
entre esse houver um link válido na rede.
 Ex.:
Alice comentou no perfil de Bob, que é amigo de Charles
Friend-of-Friend


“Se muitos dos meus amigos têm Alice como amiga, Alice
pode ser minha amiga”
 Algoritmo base do You May Know do Facebook
Não pode fazer recomendações para pessoas sem amigos
adicionados
SONAR

Algoritmo baseado no sistema SONAR
 Sistema
que têm dados públicos sobre IBM
 Publicações,
Amizade, Blogs, Orgonograma, Patentes,
Sistema de tags dos usuários, Project Wiki
 Através
desses dados, pode-se saber se dois usuários
têm alguma interação.
 Ex.:

Ser co-autor do mesmo artigo, comentar no blog, ...
Lista de usuários foi ranqueada baseada na
proximidade e frequência da interação com cada
usuários
Primeiro Experimento: Personalized Survey


500 usuários foram selecionados para participar do
experimento
Para cada usuário foi apresentada uma página
web com 12 usuários recomendados
3
de cada algoritmo
Primeiro Experimento: Personalized Survey

Para cada recomendação feita, o usuário deveria
responder:
 Você
já conhece essa pessoa?
 Foi uma boa recomendação?
 A razão pela qual foi recomendada ajudou na decisão?
 Você vai adicionar essa pessoa?
Resultados do Primeiro Experimento

Entendendo a necessidade do usuário
 95%
considerou útil a recomendação de usuários e
gostaria que o site tivesse essa funcionalidade
 Mais de 60% disse estar interessada em conhecer
novas pessoas na rede
A
grande maioria dos entrevistados adicionam
desconhecidos por amigos em comum ou interesses similares
Resultados do Primeiro Experimento
Resultados do Primeiro Experimento


A avaliação dos usuários é diretamente proporcional a
porcentagem de conhecidos recomendados
Usuários afirmaram que mostrar o motivo da
recomendação é necessário
Muitas tags foram consideradas aleatórias, genéricas, fracas
ou irrelevantes
 Usuários querem o máximo de informação útil possível sobre a
recomendação

Resultados do Primeiro Experimento


A quantidade de pessoas adicionadas foi menor
que a quantidade de boas recomendações
Usuários sugeriram adicionar outras opções além de
adicionar
 Adicionar
pessoa à lista de interesse
 Recomendar a pessoa para outra
Segundo Experimento: Controlled Field Study

Testar os algoritmos de uma forma mais natural
Content
Matching
Content plus
Link
Friend of
Friend
SONAR
Nenhum
sistema de
recomendação
Resultados do Segundo Experimento


Porcentagem de pessoas adicionadas
SONAR
FoF
CplusLink
Content
59,7%
47,7%
40,0%
30,5%
Todos os algoritmos foram eficientes em aumentar a
quantidade de amigos na rede
SONAR – 13%
 Grupo sem sistema de recomendação – 5%

Resultados do Segundo Experimento

Sistemas de recomendação são efetivos em
aumentar a quantidade de atividades no site:
Content
Matching
Content
plus Link
Friend of
Friend
SONAR
+ 13,7%
Nenhum sistema
de
recomendação
-24,4%
Conclusão dos Experimentos


Todos os quatro algoritmos são eficientes na
recomendação de usuários e aumentam
significativamente a lista de amigos
Algoritmos baseados na estrutura da rede
obtiveram melhores avaliações que algoritmos
baseados em conteúdo
Conclusão dos Experimentos



SONAR foi o algoritmo que mais se adequou a
rede.
Algoritmos baseados na estrutura da rede são
melhores em encontrar pessoas conhecidas
Algoritmos baseados em conteúdo são melhores em
encontrar pessoas que o usuário ainda não conhece
Conclusão dos Experimentos

Algoritmo ideal:
 Inicialmente
 Formar
 Em
baseado na estrutura da rede
a lista de amigos
segundo plano, baseado em conteúdo
 Depois
da lista de amigos estabilizada, encontrar pessoas
com interesses em comum
Algoritmo Proposto
Dissertação de mestrado de Nitai B. Silva
• Proposta de um algoritmo de recomendação de
usuários para a rede Oro-Aro
• Algoritmo baseado na topologia da rede
•
Utiliza FoF
Oro-Aro



Rede social corporativa construída pelo C.E.S.A.R.
 Desenvolvido com o objetivo de facilitar a troca de
conhecimento e experiência entre os alunos do CIn e dos
colaboradores do C.E.S.A.R
Há 634 usuários e 5076 arestas (relacionamento
unidirecional)
Foram selecionados para a pesquisa apenas os
relacionamentos bidirecionais
Visão Geral do Algoritmo

Etapas do mecanismo recomendação:
 Filtering
 Ordering

Além das fases tradicionais, na fase de ordering, é
proposta uma solução utilizando Algorimo Genético
Etapa de Filtering


Baseado no conceito de coeficiente de
clusterização, das redes Small Word
“It’s more probable that you know a friend of your
friend tha any other random person”
Etapa de Ordenação



Avalia o grau de relacionamento entre o nó central
e o nó que poderá ser avaliado
A métrica utilizada é um único valor, que será
extraída de uma média ponderada entre 3 índices
Os 3 índices medem propriedades específicas de
um sub-grafo
Etapa de Ordenação

Primeiro Índice
 Conceito
de FOF (Friend-of-Friends)
 Número de nós adjacentes que são ligado ao mesmo
tempo ao nó central e ao nó que será recomendado
 Amigos em comum
Etapa de Ordenação

Segundo Índice
 Mede
o grau de coesão entre o “pequeno” grupo
formado pelos amigos em comum
 Se o índice tiver um valor baixo então as pessoas
dentro deste grupo não são bem relacionadas
Etapa de Ordenação

Terceiro Índice
 Mede
o grau de coesão entre o “grande” grupo
formado pelos amigos de ambos os nós
 O terceiro e segundo índice, apesar de parecidos, são
independentes
Algoritmo Genético
Técnica utilizada para encontrar soluções aproximadas de
problemas de otimização e busca.
Algoritmo Genético


Gerar os 3 índices automaticamente para que
possa oferecer a melhor taxa de acerto
Utilizar toda a topologia em volta do nó central
 Mais
quantidade de informação
 Modificar a etapa de filtragem para adicionar nós
adjacentes
Algoritmo Genético

Algoritmo:
1.
Geração de 200 indivíduos de forma aleatória
2.
Calcular a função de avaliação para todos os indivíduos
3.
Escolher os 13 melhores segundo a função de avaliação
4.
5.
Realizar Crossjoin entre os 13 melhores, não podendo repetir os
pesos
Para cada elemento do item anterior gerar filhos, com mutação e
crossover
6.
Recalcular a função de avaliação para os nós
7.
Pegar a média das 7 melhores funções de avaliação
8.
Enquanto a média da função de avaliação não se repetir por 4x,
repetir os passos de 1 a 7
Algoritmo Genético
200
indivíduos
Crossjoin
entre os 13
Calcula
função de
avaliação
Gerar filhos
13 melhores
indivíduos
Recalcular
função de
avaliação
Média das
7 melhores
Experimento do Algoritmo Proposto


Usuários da rede social Oro-Aro
Requisitos:
Possuir no mínimo 13 relacionamentos
 Ter acessado a rede nos últimos 45 dias




70 usuários selecionados
Dois sistemas de recomendação testados, FOF e
o Algoritmo Proposto
14 usuários para FOF e 56 para o Algoritmo
Proposto
Resultados

Oro-Aro
Friends-of-Friends
Algoritmo Proposto
72,22%
77,69%
Extensão do Mecanismo

Objetivo
 Melhorar
taxa de acerto
 Lever em conta mais dados da topologia, dados que
são exclusivos da Redes Sociais Educacionais

Abordagens propostas
 Alteração
do algoritmo genético
 Adição de mais um índice que envolva a topologia de
uma rede social educacional
 Avaliar e aplicar utilizando o Redu (Rede Social
Educacional)
Extensão do Mecanismo

Alteração do algoritmo genético
 A.G.
não converge para determinados dados
 Reavaliar a função de avaliação
Extensão do Mecanismo

Adição de mais um índice que envolva a topologia
de uma rede social educacional
 Explocar
a hierarquia do Redu
Extensão do Mecanismo
AVA
Curso
Disciplina
Curso
Disciplina
Módulos
Curso
Disciplina
Aulas
Extensão do Mecanismo

Avaliar e aplicar solução no Redu
 Escolher
usuários para utilizar os 3 tipos de sistemas
recomendações existente
 FOF,
baseado em heurísticas e o Algoritmo Proposto
 Analisar
os pontos positivos de cada sistema de
recomendação
 Escolher a melhor abordagem para cada situação
Conclusão




Sistema de recomendação é extremamente
necessário pela quantidade de informação (usuário)
Aplicação de várias técnicas auxiliam na resolução
de problemas
Quanto mais dados são analisados, menor a
eficiência na execução
A topologia é um importante meio para extrair
informações
Conclusão


As vezes a topologia não é suficiente para aplicar
boas recomendações
Para análise da topologia, deve existir dados
suficientes
Dúvidas?
Referências




Cho, H., Gay, G., Davidson, B., and Ingraffea, A. R. (2007). Social
networks, communi-cation styles, and learning performance in a cscl
community. Computers & Education,49(2), 309–329
Chen, J., Geyer, W., Dugan, C., and Guy, I. Make new friends, but
keep the old: recommending people on social networking sites. Proc.
CHI, pp. 201-210. 2009.
N. B. Silva, I.FR. Tsang, G. D. C. Cavalcanti, and I.FJ. Tsang, “A graphbased friend recommendation system using genetic algorithm,” in
Evolutionary Computation (CEC), 2010 IEEE Congress on, jul. 2010,
pp. 1 –7.
http://www.cgi.br/publicacoes/pesquisas/govbr/cgibr-nicbrcensoweb-govbr-2010.pdf