Unificação de Usuários em Redes Sociais

Uni ação de Usuários em Redes So iais Julio Albinati, Igor Altissimo, Fernando Mourão, Gisele L. Pappa e Wagner Meira Jr. Departamento de Ciên ia da Computação Universidade Federal de Minas Gerais (UFMG) - Belo Horizonte, MG, Brasil {jalbinati,ialtissimo,fhmourao,glpappa,meira}d

.ufmg.br Entity resolution is a well-studied problem in the database ommunity. This paper, however, introdu es an entity resolution method for unifying user proles in so ial networks, namely Fa ebook and Twitter. The main motivation behind identifying whi h proles belong to the same real world person is to improve quality of servi es, su h as those provided by sear h engines or other Web-based servi es. The proposed method uses as its start point a set of proles on both networks whi h are known to be the same. These proles are identied using tools spe ially developed to post messages on Twitter and Fa ebook simultaneously. Using the relationship networks from these users we identify user proles in both networks using a depth-sear h pro edure. The results show that the approa h is promising, and a powerful method for data dedupli ation.

Abstra t.

Categories and Subje t Des riptors: H.Information Systems [H.m.

Mis ellaneous℄:

Databases

General Terms: So ial Networks, Users Uni ation, Entity Resolution Keywords: So ial Networks, Users Uni ation

1. INTRODUÇÃO O problema de resolução de entidades, frequente na integração de dados provenientes de diferentes fontes, vem sendo estudado há décadas pela comunidade de banco de dados [Garcia-Molina 2004; Newcombe et al. 1959]. Esse artigo, porém, trata do problema de resolução de entidades em um contexto mais atual: redes sociais. Com o frequente aparecimento de novas redes e micro-blogs, bem como o uso de diferentes redes para propósitos variados, usuários passaram a utilizar várias delas simultaneamente. Por exemplo, o Twitter consiste em um tipo de rede mais genérica, onde se segue e é seguido por muitos usuários, em que grande parte deles são agências de notícias, empresas, celebridades, dentre outros [Wu et al. 2011]. O Facebook, por sua vez, ainda preserva um ambiente mais fechado, com uma relação bilateral e menos usuários na rede de contato (em média 1301 ), normalmente formada por pessoas com as quais o usuário já teve algum contato anterior. O LinkedIn segue essa mesma abordagem, mas apresenta uma forte característica de redes de contatos profissionais. Considerando que um mesmo usuário possui contas (i.e., perfis) em diferentes redes, e acaba, em alguns casos, direcionando tipos diferentes de mensagens para cada uma delas, como poderíamos criar um perfil mais robusto e detalhado do usuário? A resposta seria unificar todos os seus perfis. A primeira motivação para essa unificação de perfis é permitir que o próprio usuário automaticamente reuse suas informações ao se inscrever em uma nova rede, fazendo com que todas as informações já fornecidas sejam reaproveitadas. A segunda e mais interessante é melhorar a qualidade de serviços fornecidos ao usuário, utilizando, por exemplo, informações sobre seu comportamento em diversos contextos, sua localidade geográfico ou mesmo interesses e hábitos pessoais. Este rico conjunto de 1 Informação

disponível em: http://www.fa ebook. om/press/info.php?statisti s

This work was partially supported by CNPq, CAPES, FINEP, Fapemig, Fapemig/FIAT and InWeb. SBBD - Simpósio Brasileiro de Ban o de Dados

81

66-2

·

J. Albinati et al

informações sobre os usuários pode beneficiar importantes serviços Web, tais como máquinas de busca ou recomendação de produtos. As mais diversas abordagens já foram propostas para a identificação de entidades em bancos de dados ou bibliotecas digitais [Brizan and Tansel 2006; Bhattacharya and Getoor 2006], e podem ser baseadas em similaridades de atributos e/ou na utilização de técnicas de aprendizado providas de dados de treinamento [Whitelaw et al. 2008]. Nesse sentido, uma questão primária seria quais as diferenças entre identificar entidades nas aplicações tradicionais e nas redes sociais? A principal diferença está na quantidade de dados disponível para consulta, e posteriormente na confiabilidade dos dados utilizados, fornecidos pelo próprio usuário. Enquanto em aplicações padrão de bancos de dados podemos aplicar métricas de similaridade para uma número suficientemente grande de atributos, em redes socais a única garantia que se pode ter é de que existe um nome de usuário. Dessa forma, as incertezas, inconsistências e ausência de informações públicas tornam a tarefa de resolução de entidades ainda mais desafiadora neste tipo de cenário. Apesar da relevância dessa tarefa de unificação de perfis em varias redes sociais, não encontramos na literatura trabalhos com objetivos similares aos nossos. Cabe também salientar que a unificação de usuários em redes sociais, tal como discutido acima, engloba a questão da privacidade. Porém, esse trabalho considera apenas dados públicos do usuário, e no futuro pretende utilizar a informação de suas mensagens (e.g., posts) para identificar seus interesses. Mais especificamente, utilizamos apenas os nomes dos usuários em cada rede social e a parte pública da rede de contato de cada usuário, ou uma parte que possa ser derivada a partir de dados públicos, tais como posts, dos usuários. Nossa abordagem de unificação parte de um conjunto de usuários identificados no Twitter e Facebook como sendo referentes a mesma entidade do mundo real, através de aplicações que permitem o envio de mensagens para diversas redes simultaneamente. A partir desse conjunto de usuários, utilizamos informações sobre sua rede de contatos nas duas redes supra citadas, e uma estratégia de blocagem a partir de seu nome de usuário (único atributo obrigatório), para unificar usuários das duas redes. Os resultados mostram que, apesar de simples, a técnica proposta é muito eficaz tanto para identificação quanto para deduplicação2 de usuários, provendo uma estratégia promissora de unificação de duas importantes redes reais. Esse método pode ser visto como uma adaptação das técnicas tradicionais de resolução de entidades, com o diferencial da exploração da rede de contatos dos usuários. O restante desse artigo está organizado da seguinte forma. A Seção 2 discute trabalhos relacionados a unificação de usuários em redes sociais. A Seção 3 apresenta o método proposto, enquanto a Seção 4 descreve os experimentos e resultados computacionais obtidos. Por fim, a Seção 5 apresenta conclusões e idéias de trabalhos futuros. 2. TRABALHOS RELACIONADOS Resolução de Entidades é um problema clássico que trata da identificação e integração de dados que descrevem uma mesma entidade no mundo real (e.g. uma pessoa, empresa, local, dentre outros). Tal problema vem sendo amplamente estudado em computação sob variados domínios há décadas [Newcombe et al. 1959; Elmagarmid et al. 2007]. Grande parte das abordagens atuais são variantes do modelo Fellegi-Sunter [Fellegi and Sunter 1969], no qual a resolução de entidade é vista como um problema de classificação binária em que se deseja verificar se dois objetos são ou não o mesmo dado um conjunto de atributos. Além disso, dada a natureza quadrática deste problema, visto que cada entidade virtualmente precisa ser comparada com todas as outras, as técnicas mais eficazes e eficientes existentes atualmente utilizam-se do mecanismo de blocagem [Papadakis et al. 2011]. Ou seja, tais métodos normalmente associam cada entidade a um valor de chave de bloco, baseado em um subconjunto de atributos, e em seguida comparam apenas entidades associadas ao mesmo 2 Problema

re orrente em integração de dados que onsiste em des obrir se dois registros espe í os distintos representam uma mesma entidade do mundo real.

SBBD - Simpósio Brasileiro de Ban o de Dados

82

Uni ação de Usuários em Redes So iais

·

66-3

valor de chave. Tradicionalmente, o problema de resolução de entidades é analisado sobre dados estruturados provenientes de sistemas de bancos de dados. Mais recentemente, um cenário mais complexo e dinâmico de análise passou a chamar a atenção de pesquisadores: grafos. Mais especificamente, um crescente número de redes sociais tornaram a identificação de pessoas em redes distintas um problema recorrente e interessante na Web [Hill 2009; Bilgic et al. 2006]. Tal problema decorre, principalmente, do grande número de aplicações existentes que demandam por informações presentes em redes sociais, de forma a proporcionar uma maior qualidade de serviço a seus usuários. Como não existe uma única rede social, ou mesmo múltiplas redes interoperantes, as informações sobre um dado usuário presentes em cada uma dessas redes se tornam fragmentadas e parciais. Dessa forma, aplicações que precisam de informações sociais dos usuários enfrentam problemas maiores que suas implementações em si, uma vez que precisam reconstruir a rede social. Não obstante a isso, redes sociais distintas impõem uma demanda de esforço maior por parte dos usuários, visto que a cada nova aplicação é necessário cadastrar novamente o conjunto de todos os contatos que o usuário possui. A fadiga resultante desse esforço não só aumenta a barreira à entrada de novas aplicações, mas também diminui sua utilidade para os usuários que realmente as utilizam. De forma a abordar tal problema, alguns estudos tais como o openSocial do Google3 , empenham-se na denominada portabilidade de redes sociais, que objetiva prover técnicas de projeto para redes sociais abertas e descentralizadas através de ferramentas, tais como, micro-formatos ou OpenIds [Bojars et al. 2008]. Como exemplo de esforços nesta linha podemos citar o Plaxo [Yu-lin and Jian-ping 2005], que consiste em um sistema de sincronização e atualização automática de contatos de redes sociais entre distantes redes desconexas. Outro bom exemplo é o OpenFriends, uma API de código aberto que permite ao usuário sincronizar e organizar os dados de contato em múltiplas redes sociais. Entretanto, a utilização destes micro-formatos ou OpenIds requer grandes alterações na forma de representar os dados dos usuários presentes na grande maioria das redes existentes, uma vez que nenhuma delas possuem uma representação compatível. Além disso, ainda existe um número muito pequeno de usuários que faz uso de tais ferramentas. Diferentemente desses trabalhos, nosso objetivo é, a partir de redes já consolidadas e sem nenhum esforço por parte dos usuários ou dos proprietários das redes sociais, identificar um mesmo usuário em distintas redes. Por fim, um outro conjunto de esforços fortemente associados ao problema de resolução de entidades em redes sociais é a tarefa de ‘des-anonimização’ de usuários [Hay et al. 2008]. Tais estudos objetivam, a partir de um conjunto de informações externas ou mesmo pela estrutura da rede, identificar cada usuário anonimizado na rede analisada. Por exemplo, em [Narayanan and Shmatikov 2009] os autores utilizam uma rede em que os usuários são conhecidos para identificar usuários anonimizados em outra rede. Trata-se, portanto, da mesma tarefa de identificação de um mesmo usuário em distintas redes, exceto pelo fato da identificação dos usuários em uma das redes (e.g., nome) ser desconhecida. Cabe ainda salientar que não identificamos trabalhos que objetivem realizar automaticamente a unificação de usuários de várias redes sociais distintas, tal como proposto. Os trabalhos sobre redes sociais mencionados focam suas análises em uma única rede social, almejando por exemplo, identificar duplicações de usuários ou identificar individualmente cada usuário da rede. 3. UNIFICAÇÃO DE USUÁRIOS Esta seção descreve o método proposto para unificação de usuários. Esse processo pode ser utilizado para usuários de qualquer rede, desde que sejam conhecidos o nome do usuário e, pelo menos, uma parte de sua rede de relacionamentos. O método recebe como entrada um conjunto inicial de usuários já unificados, que servirão de sementes para o restante do processo. No caso específico das redes analisadas em nosso estudo de caso, por exemplo, tais usuários iniciais são obtidos através de mensagens (posts) replicadas através de aplicações que enviam mensagens para múltiplas redes simultaneamente. 3 Disponível

em http:// ode.google. om/apis/openso ial

SBBD - Simpósio Brasileiro de Ban o de Dados

83

66-4

·

J. Albinati et al

O método proposto baseia-se na intuição de que, ao entrar em uma nova rede social, cada usuário inicialmente adiciona à rede, como amigos, indivíduos que já fazem parte de sua rede de relacionamento em outras redes sociais. Baseado nessa premissa, acreditamos ser mais fácil identificar que um perfil P1 de um usuário, em uma dada rede social R1 , e outro perfil P2 , de outra rede social R2 , referem-se à mesma pessoa se P1 e P2 estiverem na rede de contato de um usuário Ui previamente unificado em ambas redes. Ou seja, ao invés de comparar o perfil P1 com todos os perfis, ou mesmo um subconjunto de perfis presentes em blocos da rede R2 , restringimos nossa busca apenas aos perfis presentes na rede de contato de Ui em R2 , uma vez que P1 já se encontra na rede de contatos de Ui na rede R1 . Portanto, o ponto central do algoritmo é recuperar a rede de uma entidade já unificada (que serve de semente para o algoritmo) e comparar seus contatos existentes em uma das redes com seus próprios contatos na outra rede. Porém, não faz sentido comparar todos os amigos das duas redes. Assim, tanto por questões de eficiência quanto de eficácia do método, adotamos um simples método de blocagem durante o processo de comparação. Tal blocagem opera em duas fases: uma relativa ao primeiro nome e outra ao sobrenome. Para que a comparação entre usuários ocorra com sucesso, o primeiro nome de ambos deve ser idêntico. Quanto ao sobrenome, o menor deles deve estar contido no maior, permitindo que usuários que omitam ou abreviem sobrenomes ainda sejam unificados. Como um usuário participa de uma rede social com o objetivo de encontrar e ser encontrado por outros participantes, é de se esperar que ele construa uma certa identidade equivalente em redes distintas e, portanto, utilize nomes aproximados. Dessa forma, o algoritmo de unificação inicia com a comparação das redes de relacionamentos de cada semente. Sempre que uma entidade é unificada, sua rede é comparada, dando origem a um processo recursivo. Assim, um grafo de relacionamentos de usuários unificados é construído em profundidade, tal como descrito no Algoritmo 1. Algorithm 1 UnificaEntidades(semente, rede1, rede2) contatos1 ← RecuperaContatosRede(semente, rede1) contatos2 ← RecuperaContatosRede(semente, rede2) for all contato1j em contatos1 do for all contato2k em contatos2 do if (contato1j tem o mesmo primeiro nome de contato2k ) then if (todos os sobrenomes de contato1j estão contidos em contato2k ) ou (todos os sobrenomes de contato2k estão contidos em contato1j ) then novaEntidade = Informações de contato1j ∪ contato2k UnificaEntidades(novaEntidade) end if end if end for end for

4. ESTUDO DE CASO Nesta seção avaliamos o método de unificação proposto considerando duas redes sociais reais de escala mundial: Twitter e Facebook. Primeiramente, descrevemos o processo de obtenção dos subconjuntos de usuários utilizados em nossas análises sobre tais redes. Em seguida, apresentamos avaliações empíricas acerca do comportamento do algoritmo quando variamos alguns parâmetros. Por fim, descreveremos o método de avaliação de qualidade realizada sobre os resultados obtidos por nossa proposta de unificação. SBBD - Simpósio Brasileiro de Ban o de Dados

84

Uni ação de Usuários em Redes So iais

·

66-5

4.1 Coleção de Dados Nossa avaliação experimental baseia-se na unificação de subconjuntos de usuários provenientes do Facebook e do Twitter. A escolha por tais redes sociais deve-se à notória popularidade alcançada por ambas ao redor do mundo. O Facebook é um serviço Web de redes sociais lançado em 2004, e possui mais de 700 milhões de usuários ativos em todo o mundo [Inc. 2011]. Dentre os vários recursos disponíveis, os usuários podem criar um perfil pessoal, definir relacionamentos bidirecionais de amizade com outros usuários, e trocar mensagens (i.e., posts), incluindo notificações automáticas quando atualizam seu perfil. O Twitter é um serviço de micro-blogging onde um dado usuário pode ler e postar tweets (mensagens com no máximo 140 caracteres). Além disso, usuários do Twitter podem definir uma rede de relacionamentos com base em relações unidirecionais do tipo seguidor-seguido, em que um usuário pode escolher qualquer outro usuário a quem seguir na rede. Ao todo nossa coleção compreende 1.097.151 usuários do Facebook e 4.585.901 usuários do Twitter. Tais usuários foram coletados utilizando as APIs disponibilizadas pelo próprio Facebook e Twitter, respectivamente, através de um conjunto de palavras-chave previamente definidas para as buscas nestas APIs. Para o Facebook, especificamente, foram coletados um total de 34.029 usuários, a partir das buscas por palavras-chave em posts, onde o conjunto de palavras-chave está relacionado a automóveis. Em seguida, coletamos todos os posts enviados por cada um desses usuários em um período de 3 meses anteriores ao início da coleta. Isso foi necessário porque, ao contrário do Twitter, a rede de relacionamentos do Facebook não pode ser coletada através da API. Assim, para o Facebook, definimos como amigos de cada um desses usuários inciais, outros usuários que deram “like” (i.e., curtiram na terminologia do Facebook) a alguma mensagem enviada pelo usuário nestes 3 meses. Isso foi possível porque, para curtir uma mensagem, o usuário precisa necessariamente ser amigo do usuário que a enviou. Tal processo foi realizado recursivamente para todos os amigos dos usuários sementes, para os amigos destes amigos e assim sucessivamente, por 6 vezes. No caso do Twitter, foram considerados como usuários sementes todos os usuários que publicaram pelo menos um tweet com alguma das palavras-chave utilizadas (conjunto idêntico ao coletado no Facebook). Em seguida, recuperamos a lista de seguidores destes usuários, publicamente acessível, e os seguidores destes seguidores, recursivamente, por 6 níveis. Todas as coletas foram realizadas no período de 18/03/2011 a 27/05/2011. 4.2 Avaliação Experimental Em posse da coleção descrita acima, o primeiro passo para unificação consiste em definir quais serão as sementes fornecidas como entrada para o nosso algoritmo. Tais sementes foram obtidas através de posts replicados por meio de aplicações que enviam mensagens para múltiplas redes simultaneamente. Mais especificamente, consideramos as seguintes ferramentas para a identificação das sementes: TweetDeck, Socially, Selective Tweets, Smart Tweets, Flock, HootSuite, ÜbberTwitter, twitterfeed e TweetCaster. A partir deste conjunto de ferramentas, identificamos em nossa coleção 31 usuários distintos para os quais foi possível recuperar seus identificadores em ambas as redes. Para tanto, consideramos como referentes a uma mesma pessoa, usuários que postaram, através de alguma das ferramentas mencionadas, mensagens idênticas em ambas redes em um intervalo de tempo menor de 10 segundos, e que possuem exatamente o mesmo nome. Em um primeiro experimento, todos os 31 usuários foram utilizados como sementes. O gráfico da Figura 2 mostra a probabilidade de se unificar n contatos a partir de cada usuário já unificado. Como podemos observar, conseguimos unificar, em geral, um número pequeno de contatos de cada usuário. Somente para alguns usuários foi possível unificar mais de 40 contatos, por exemplo. Isso pode ser explicado pelo restrito número de contatos no Facebook que conseguimos obter para cada usuário a partir do “like”. Nossa amostra da rede de contatos do Facebook, derivada a partir do “like”, possui uma média de apenas 17,29 amigos por usuário da coleção. A fim de obter uma análise mais detalhada, a Tabela I apresenta algumas estatísticas sobre a exeSBBD - Simpósio Brasileiro de Ban o de Dados

85

66-6

·

J. Albinati et al

cução do nosso algoritmo a partir das 31 sementes identificadas. Nota-se que, a partir de um conjunto de 31 sementes, seria possível identificar no máximo 82.049 usuários (com repetições), considerando o cenário em que para serem considerados a mesma pessoa, usuários de redes distintas precisam possuir apenas o mesmo primeiro nome. Nosso algoritmo, mais restritivo quanto a isso, conseguiu unificar 24.896 usuários distintos (e 45% do máximo e usuários com repetição). Além disso, observamos que a média de contatos unificados por cada usuário foi de aproximadamente 7 usuários. Table I. Medida

Estatísti as da Uni ação de Usuários

Número de sementes Máximo possível de uni ações Total de usuários uni ados Total de uni ados distintos Média de amigos/seguidores uni ados por usuário

Valor

31 82.049 37.112 24.896 7,03

A partir desses resultados, uma questão imediata refere-se ao impacto do número inicial de sementes sobre o total de usuários unificados. O que aconteceria com o número de usuários unificados ao reduzirmos o número de sementes? Os resultados da redução do número de sementes pode ser visto na Figura 2 (a). Variamos o número de sementes entre um e 32, seguindo um padrão de crescimento exponencial na base 2. Para cada número de sementes, executamos nosso algoritmo de unificação 10 vezes e calculamos a média e o desvio padrão do total de unificações obtidas nas execuções. Pode-se observar que quanto maior o número de sementes, maior o número de unificações e que, quanto menor o número de sementes, maior o desvio padrão. Esses elevados valores encontrados para o desvio padrão podem ser explicados pelas diferenças de perfil dos usuários. Por exemplo, quando utilizando uma semente, o usuário com menos contatos em sua rede possuía 3 amigos, enquanto o maior possuía 81. O primeiro usuário levou à unificação de apenas 14 perfis, enquanto o último unificou 6.838 usuários distintos. Assim, a escolha de usuários influentes na rede tem relação direta com a quantidade total de usuários unificados.

Probabilidade de Ocorrência

Por fim, a Figura 2 (b) apresenta o número de usuários totais unificados a cada nível, ressaltando novamente o quanto a escolha dos usuários sementes é significativa. Note que o número de sementes possui um grande impacto principalmente para os primeiros níveis de expansão. À medida que se aumenta o número de níveis o total de usuários unificados tende a ser próximo para variados números iniciais de sementes. Outro ponto a se destacar é que o uso de mais sementes, tal como 31, além de implicar em um número bem maior de unificações, apresenta uma convergência mais rápida. Por exemplo, o total de unificações em 8 níveis de expansão não difere muito do total alcançado com 16 níveis. Dessa forma, além de se alcançar mais usuários, ao utilizar mais sementes temos uma convergência mais rápida do algoritmo.

Fig. 1.

10−1 10−2 10−3 10−4

0

20 40 60 80 100 Quantidade de unificados

120

Probabilidade de uni ação de usuários a partir de es olhas aleatórias de sementes

SBBD - Simpósio Brasileiro de Ban o de Dados

86

25000 20000 15000 10000 5000 0

1

2 4 8 16 Quantidade de sementes

32

105

·

66-7

31 16 8 4 2 1

104 103 102 101 100 10−1

1

2

4

8

16

Nível de expansao

(a) Quantidade de usuários uni ados Fig. 2.

Média cumulativa de unificações

Quantidade de unificações

Uni ação de Usuários em Redes So iais

(b) Média de Uni ações por nível

Comportamento do método diante da variação do número de sementes

4.3 Avaliação de Qualidade Um questão fundamental sobre os resultados descritos acima é, certamente, acerca da qualidade das unificações realizadas. Os usuários unificados pelo algoritmo representam, de fato, a mesma pessoa no mundo real? Responder essa pergunta é uma tarefa talvez mais complexa que a própria unificação. Como não temos um conjunto de usuários de validação, para o qual sabemos a priori suas contas em ambas redes avaliadas, a forma mais confiável de realizar tal verificação consiste em um processo manual de validação dos resultados. Como o número de usuários a ser verificado torna essa verificação humanamente inviável, optamos por realizar uma verificação amostral sobre os resultados. Ou seja, selecionamos aleatoriamente 950 dos usuários unificados por nosso algoritmo e requisitamos pessoas a conferir manualmente se as contas do Facebook e do Twitter de cada usuário são referentes à mesma pessoa. Tendo em vista que o número total de usuários unificados foi de 24.896, é possível obter uma aproximação estatisticamente confiável da eficácia do método dentro de uma margem de erro de 3,5%, com um grau de confiança de 95% [Advisors 2011]. A partir deste processo, identificamos uma precisão de 85,50% nos resultados obtidos por nossa técnica de unificação. Cabe ainda salientar que a avaliação de alguns usuários representou um desafio mesmo para humanos, uma vez que características tais como fotos, links, ou parte pública da rede de contatos diferiam sensivelmente em cada rede. Um dos resultados interessantes dessa avaliação manual foi perceber que a robustez do método está na deduplicação de entidades, e não somente na unificação. Pode-se dizer que o método é simples demais, uma vez que unifica utilizando apenas o nome e uma distância entre o sobrenome. Porém, considere o usuário “João da Silva". Existem mais de 100 pessoas com esse nome no Facebook, como unificá-las? A abordagem que restringe as possibilidades de unificação da rede de amigos reduz consideravelmente esse problema. 5. CONCLUSÕES E TRABALHOS FUTUROS Esse artigo apresentou um método simples para resolução de perfis de usuários em redes sociais. Como mencionado, atualmente diferentes redes acabam adquirindo propósitos variados, e a tarefa de enriquecimento de dados de usuários presentes nessas diversas redes consiste em um trabalho essencial para uma melhora em qualidade de serviços. Nossa estratégia de unificação é uma adaptação para o contexto de redes sociais de métodos tradicionais para resolução de entidades aplicados em dados relacionais, já que esses não poderiam ser utilizados dado a restrição de informações disponíveis sobre as entidades. Portanto, ela baseia-se apenas nos nomes dos usuários em cada rede social e na parte pública da rede de relacionamentos de cada usuário. A partir de um conjunto de usuários identificados em ambas redes, definidos como usuários sementes, unificamos recursivamente a rede de contato de cada usuário semente, baseado no SBBD - Simpósio Brasileiro de Ban o de Dados

87

66-8

·

J. Albinati et al

casamento aproximado de nomes, bem como dos contatos de cada usuário. Avaliações dessa estratégia sobre um subconjunto de usuários do Twitter e do Facebook permitiramnos verificar que, apesar de simples, nossa proposta mostrou-se bastante efetiva para a resolução de entidades em redes reais de escala mundial, bem como para a tarefa de deduplicação. Avaliações manuais sobre amostras obtidas aleatoriamente comprovaram a eficácia do método. Como trabalhos futuros, destacamos a utilização de outras evidências públicas dos usuários de forma a aprimorar a unificação, tais como o conteúdo de suas mensagens, bem como a análise de nossa proposta sobre outras redes reais. Um método mais eficaz para seleção das sementes inicias também será explorado.

REFERENCES http://resear h-advisors. om/tools/samplesize.htm, A

essed Aug 2011. Entity resolution in graphs, 2006. Bilgi , M., Li amele, L., Getoor, L., and Shneiderman, B. D-dupe: An intera tive tool for entity resolution in so ial networks. In Visual Analyti s S ien e And Te hnology, 2006 IEEE Symposium On. IEEE, pp. 4350, 2006. Bojars, U., Passant, A., Breslin, J., and De ker, S. So ial network and data portability using semanti web te hnologies. In 2nd Workshop on So ial Aspe ts of the Web (SAW 2008) at BIS2008. Citeseer, pp. 519, 2008. Brizan, D. and Tansel, A. A survey of entity resolution and re ord linkage methodologies. Communi ations of the IIMA 6 (3): 4150, 2006. Elmagarmid, A., Ipeirotis, P., and Verykios, V. Dupli ate re ord dete tion: A survey. IEEE Transa tions on knowledge and data engineering , 2007. Fellegi, I. and Sunter, A. A theory for re ord linkage. Journal of the Ameri an Statisti al Asso iation 64 (328): 11831210, 1969. Gar ia-Molina, H. Entity resolution: Overview and hallenges. Le ture Notes in Computer S ien e , 2004. Hay, M., Miklau, G., Jensen, D., Towsley, D., and Weis, P. Resisting stru tural re-identi ation in anonymized so ial networks. Pro eedings of the VLDB Endowment 1 (1): 102114, 2008. Hill, S. So ial network relational ve tors for anonymous identity mat hing. In Pro eedings of the IJCAI Workshop on Learning Statisti al Models from Relational Data. Citeseer, 2009. In ., F. http://www.fa ebook. om/press/info.php?statisti s, A

essed May 2011. Narayanan, A. and Shmatikov, V. De-anonymizing so ial networks. In 2009 30th IEEE Symposium on Se urity and Priva y. IEEE, pp. 173187, 2009. New ombe, H., Kennedy, J., Axford, S., and James, A. Automati linkage of vital and health re ords. S ien e vol. 130, pp. 954959, 1959. Papadakis, G., Ioannou, E., Niederée, C., and Fankhauser, P. E ient entity resolution for large heterogeneous information spa es. In Pro eedings of the fourth ACM international onferen e on Web sear h and data mining. ACM, pp. 535544, 2011. Whitelaw, C., Kehlenbe k, A., Petrovi , N., and Ungar, L. Web-s ale named entity re ognition. In Pro eeding of the 17th ACM Conferen e on information and Knowledge Management. ACM, pp. 123132, 2008. Wu, S., Hofman, J. M., Mason, W. A., and Watts, D. J. Who says what to whom on twitter. In Pro eedings of the 20th international onferen e on World wide web. WWW '11. ACM, New York, NY, USA, pp. 705714, 2011. Yu-lin, C. and Jian-ping, Y. The resear h in plaxo and its implementation. Journal of Yunnan University for Nationalites (Natral S ien es Edition) , 2005. Advisors, T. R.

Bhatta harya, I. and Getoor, L.

SBBD - Simpósio Brasileiro de Ban o de Dados

88