FACULDADE DE E NGENHARIA DA U NIVERSIDADE DO P ORTO
Caracterização das Ligações entre
Utilizadores em Redes Sociais
Daniel José Rodrigues de Sousa
Mestrado Integrado em Engenharia Informática e Computação
Orientador: Prof. Doutora Eduarda Mendes Rodrigues
28 de Junho de 2010
Caracterização das Ligações entre Utilizadores em Redes
Sociais
Daniel José Rodrigues de Sousa
Mestrado Integrado em Engenharia Informática e Computação
Aprovado em provas públicas pelo júri:
Presidente: Luis Paulo Gonçalves dos Reis (Professor Auxiliar)
Vogal Externo: Paulo Alexandre Ribeiro Cortez (Professor Auxiliar)
Orientador: Maria Eduarda Silva Mendes Rodrigues (Professora Auxiliar Convidada)
27 de Julho de 2010
Resumo
Nos últimos anos, as redes sociais têm-se tornado um fenómeno global na Internet.
Actualmente, são dos serviços mais populares na Internet e tornaram-se parte integrante da vida de muitas de pessoas pelo mundo fora. A popularidade destes serviços
proporciona uma oportunidade para o estudo das suas características globais e das comunidades que se formam nas redes sociais com o objectivo de revelar conhecimento
possível de ser aplicado em diversos domínios como por exemplo, em sistemas de recomendação, em algoritmos de pesquisa e recuperação de informação, em marketing e
publicidade, entre outros.
Nesta dissertação, é realizada uma caracterização exaustiva de uma colecção de dados actual de um serviço de micro-blogging bastante popular, o Twitter. É apresentada
uma descrição detalhada desta rede social e do conjunto de dados utilizado neste estudo.
A colecção de dados utilizada é composta pelas mensagens enviadas por utilizadores do
Twitter em Portugal durante o período de 1 de Janeiro de 2010 e 16 de Maio de 2010.
Para além de proporcionar uma caracterização exaustiva e de serem apresentadas características e propriedades observadas em diversas redes sociais, que permitem validar o
conjunto de dados utilizado, é apresentada uma análise quantitativa da interacção presente
na rede social implícita nesta colecção. Os resultados confirmam as características frequentemente observadas neste tipo de redes, como é o caso das power-law distributions,
do small-world effect e das propriedades de auto-similaridade (self-similarity).
Além disso, é analisada a topologia da rede de interacção e evidenciada a existência
de grupos coesos e sub-comunidades na rede social. Posteriormente, é apresentado um
estudo sobre a influência dos tópicos nas ligações entre utilizadores na tentativa de evidenciar que a componente social prevalece sobre os tópicos no momento das interacções.
Verifica-se que com o aumento da rede egocêntrica, os utilizadores têm uma tendência
para segmentarem a sua rede por tópicos, no entanto, o carácter social da rede é bastante
relevante.
Para finalizar, foi desenvolvida uma aplicação que permite monitorizar uma rede social genérica e foram aplicados métodos, descritos na literatura, que permitem detectar
comunidades e a análise dos conteúdos da rede de forma a proporcionar uma caracterização detalhada dos grupos que se formam numa rede social.
i
ii
Abstract
Over the years, social networks have become a global phenomenon on the Internet.
Nowadays, social networking sites are among the most popular online services and
have become an integral part of the social life of many people around the world. The popularity of these sites provides an opportunity to study the characteristics of online social
networks and the communities that emerge in them with the aim of revealing knowledge.
This has a possible application in various fields such as information retrieval, recommendation systems, marketing and advertising, among others.
This dissertation presents an exhaustive characterization of a dataset from a popular
micro-blogging service, Twitter. The dissertation presents a thorough description of the
social network and the dataset used in this study. The dataset consists of a large collection
of tweets sent by Portuguese users between January 1st , 2010 and May 16th , 2010. In
addition to providing a comprehensive characterization and presenting several characteristics and properties of the dataset and underlying social network, also observed in other
social networks, a quantitative analysis of the users’ interaction in the implicit network
derived from tweet replies, is presented. The results confirm the power-law, small-world,
scale-free and self-similarity properties of online social networks.
Furthermore, detailed analysis of the network topology is carried out in order to
demonstrate the existence of cohesive groups and sub-communities in the implicit social network. Subsequently, a study of the topics’ influence on the interaction among
users is presented, in an attempt to show that the social aspect prevails over the topic in
the moment of interaction.
To conclude, an analysis tool was developed to provide the characterization of social
networks, applying the general methods described in the state-of-the-art, which allows the
detection of communities, and analysis of the content, to provide a detailed characterization of these groups.
iii
iv
Agradecimentos
O desenvolvimento do presente trabalho não teria sido possível sem a colaboração de
algumas pessoas.
Assim, em primeiro lugar, não podia deixar de expressar o mais sincero agradecimento
e reconhecimento à Prof. Doutora Eduarda Mendes Rodrigues e ao Eng. Luís Sarmento
pela orientação, acompanhamento e pelos conhecimentos transmitidos ao longo de todo
este trabalho de dissertação. Agradeço ainda, pela disponibilidade e empenho que demonstraram para que o trabalho fosse bem sucedido.
Não podia deixar de agradecer, ao Eng. Gustavo Laboreiro, à equipa do sapo.pt e a
todos os envolvidos directa ou indirectamente neste projecto, por tornarem esta colecção
de dados disponível para investigação.
Quero também agradecer à minha família e amigos que sempre me incentivaram ao
longo deste projecto.
É com enorme agrado que agradeço às pessoas que me disponibilizaram novos recursos quando em algumas ocasiões me deparei com a falta deles.
E agradeço ainda a todos aqueles que, ao longo deste período, contribuíram com a
sua opinião, crítica ou sugestão e que, de certa forma, influenciaram a realização deste
trabalho.
Obrigado a Todos,
Daniel Sousa
v
vi
Conteúdo
1
Introdução
1.1 Motivação e Objectivos . . . . . . . . . . . . . . . . . . . . . . . . . . .
1.2 Contribuições Científicas . . . . . . . . . . . . . . . . . . . . . . . . . .
1.3 Estrutura da Dissertação . . . . . . . . . . . . . . . . . . . . . . . . . .
2
Revisão Bibliográfica
2.1 Análise de Redes Sociais e Detecção de Comunidades . .
2.1.1 Representação dos Grafos . . . . . . . . . . . .
2.1.2 Métricas utilizadas na Análise das Redes Sociais
2.1.3 Propriedades e classes de redes complexas . . .
2.1.4 Métodos de detecção de comunidades . . . . . .
2.1.5 Trabalhos relacionados . . . . . . . . . . . . . .
2.2 Análise de conteúdos . . . . . . . . . . . . . . . . . . .
2.3 Sistemas de recomendação . . . . . . . . . . . . . . . .
2.4 Sumário . . . . . . . . . . . . . . . . . . . . . . . . . .
3
4
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
1
3
4
4
7
8
8
10
13
17
20
23
29
34
Análise de uma Rede Social de Micro-blogging: “Twittosfera” portuguesa
3.1 Micro-blogging . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.2 Twitter . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.2.1 @replies e/ou @mentions . . . . . . . . . . . . . . . . . . . . .
3.2.2 #hashtags . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.2.3 RT retweets . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.2.4 Interface de interacção com o serviço . . . . . . . . . . . . . . .
3.2.5 Redes explícitas e implícitas no Twitter . . . . . . . . . . . . . .
3.3 Descrição da Colecção de Dados . . . . . . . . . . . . . . . . . . . . . .
3.4 Comportamento Individual dos Utilizadores . . . . . . . . . . . . . . . .
3.5 Análise da interacção entre os utilizadores . . . . . . . . . . . . . . . . .
3.5.1 Frequência de interacção e participação dos utilizadores . . . . .
3.5.2 Correlação entre o número de respostas enviadas e número de
respostas recebidas . . . . . . . . . . . . . . . . . . . . . . . . .
3.6 Análise da estrutura global da rede . . . . . . . . . . . . . . . . . . . . .
3.7 Invariância Temporal . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.8 Sumário . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
35
36
37
38
38
39
39
40
42
46
48
52
Análise da influência dos tópicos nas ligações entre utilizadores
4.1 Selecção dos tópicos . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4.2 Segmentação da rede por tópicos . . . . . . . . . . . . . . . . . . . . . .
63
64
64
vii
54
55
59
61
CONTEÚDO
4.3
.
.
.
.
.
.
.
.
69
70
71
72
74
76
78
79
.
.
.
.
.
.
.
81
82
82
82
83
87
88
88
Conclusões e Trabalho Futuro
6.1 Resumo do trabalho . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
6.2 Resultados e Trabalho Futuro . . . . . . . . . . . . . . . . . . . . . . . .
91
91
92
4.4
4.5
4.6
4.7
4.8
5
6
Teste da Hipótese . . . . . . . . . . . . . . . .
4.3.1 Tabela de Contingência . . . . . . . . .
4.3.2 Informação Mútua Pontual Normalizada
Desporto e Política . . . . . . . . . . . . . . .
Desporto e Religião . . . . . . . . . . . . . . .
Religião e Política . . . . . . . . . . . . . . . .
Discussão de Resultados . . . . . . . . . . . .
Sumário . . . . . . . . . . . . . . . . . . . . .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
“SocialAnalytics”: ferramenta para análise de redes sociais
5.1 Formato da colecção de dados . . . . . . . . . . . . . .
5.2 Descrição da aplicação . . . . . . . . . . . . . . . . . .
5.2.1 Funcionalidades . . . . . . . . . . . . . . . . .
5.2.2 Interface da aplicação . . . . . . . . . . . . . .
5.3 Ferramentas de Análise do Twitter . . . . . . . . . . . .
5.4 Conclusão . . . . . . . . . . . . . . . . . . . . . . . . .
5.5 Sumário . . . . . . . . . . . . . . . . . . . . . . . . . .
Referências
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
97
A “SocialAnalytics”: Manual do Utilizador
105
Índice Remissivo
105
viii
Lista de Figuras
1.1
Diversidade de interacções sociais na Web [Tur08] . . . . . . . . . . . .
2
2.1
2.2
2.3
2.4
2.5
2.6
2.7
2.8
Exemplo de sociograma . . . . . . . . . . . . . . . . . . . . . . . . . . .
Grafo não dirigido, não pesado . . . . . . . . . . . . . . . . . . . . . . .
Grafo dirigido ou digrafo, não pesado . . . . . . . . . . . . . . . . . . .
Grafo não dirigido e pesado (à esquerda) e grafo dirigido e pesado (à direita)
Exemplo de grafo utilizado para explicar as medidas de centralidade . . .
Exemplo de propriedades (cliques, cycles, geodesic paths, spanning trees)
Exemplo de rede com comunidades coesas em redes . . . . . . . . . . .
Comparação das distribuições apresentadas no grau de centralidade dos
nós numa “power-law network” e uma rede aleatória (random network) .
Exemplificação da teoria dos seis graus de separação (six-degrees of separation) [Sig09] . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Exemplificação do comportamento auto-similiar de uma rede complexa
[SHM05] . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Exemplo de rede com comunidades sobrepostas [CZG09] . . . . . . . .
Exemplo de comunidades em blogs não consideradas devido à ausência
do conhecimento mútuo [rLSC+ 06] . . . . . . . . . . . . . . . . . . . .
Linear Support Vector Machine . . . . . . . . . . . . . . . . . . . . . . .
Decomposição da distribuição de palavras por documentos nas distribuições
de palavras por tópicos e de tópicos por documentos [HFS08] . . . . . .
Exemplo de 3 tópicos associados ao termo play [SGL+ 07] . . . . . . . .
Processo generativo e processo de inferência estatística dos tópicos de
uma colecção de documentos [SGL+ 07] . . . . . . . . . . . . . . . . . .
Exemplo de recomendação de itens semelhantes realizado pela Amazon
[LSY03] . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Exemplo de sistema de recomendações baseadas no histórico de pesquisas
e compras de todos os utilizadores da rede, utilizado pela Amazon . . . .
Exemplo do sistema de recomendação híbrido implementado pelo IMDb .
8
9
10
10
12
13
14
2.9
2.10
2.11
2.12
2.13
2.14
2.15
2.16
2.17
2.18
2.19
3.1
3.2
3.3
3.4
3.5
Página pessoal do utilizador no Twitter . . . . . . . . . . . . . . . . . . .
Distribuição diária de tweets presentes na colecção de dados utilizada . .
Percentagem de respostas da amostra B . . . . . . . . . . . . . . . . . .
Percentagem de utilizadores interactivos da amostra B . . . . . . . . . . .
Distribuição do número de tweets e do número de utilizadores por dia da
semana . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
ix
15
16
17
19
22
26
26
27
28
31
32
33
40
43
45
45
46
LISTA DE FIGURAS
3.6
52
53
3.17
Distribuição do número de tweets e do número de utilizadores por hora
do dia . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Distribuição do número de tweets por hora do dia dos 5 utilizadores com
mais participação no Twitter . . . . . . . . . . . . . . . . . . . . . . . .
Distribuição do grau de centralidade dos utilizadores da rede de respostas
construída a partir da amostra B . . . . . . . . . . . . . . . . . . . . . .
Distribuição do número distinto de utilizadores com quem um utilizador
comunica e do número distinto de utilizadores que comunicam com ele .
Comparação da distribuição do grau de centralidade dos vértices da rede
obtida a partir da amostra B e de uma rede aleatória com o mesmo número
de utilizadores e ligações . . . . . . . . . . . . . . . . . . . . . . . . . .
Distribuição da frequência de interacção entre pares de utilizadores . . . .
Distribuição do número de respostas recebidas (à esquerda) e do número
de respostas enviadas (à direita) pelos utilizadores do Twitter em Portugal
Correlação entre o número de mensagens enviadas (x) e o número de
mensagens recebidas (y) . . . . . . . . . . . . . . . . . . . . . . . . . .
Tamanho dos componentes fortemente conexos da rede . . . . . . . . . .
Tamanho dos cliques existentes na rede . . . . . . . . . . . . . . . . . .
Comparação do número e tamanho das comunidades obtidas pelos métodos de detecção de comunidades de Wakita-Tsurumi e de ClausetNewmanMoore . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Comportamento auto-similar da estrutura da rede. . . . . . . . . . . . . .
4.1
4.2
4.3
4.4
4.5
4.6
4.7
4.8
4.9
4.10
4.11
4.12
4.13
4.14
4.15
Distribuição diária de tweets no tópico Desporto . . . . . . . . . . . . . .
Distribuição diária de tweets no tópico Política . . . . . . . . . . . . . .
Distribuição diária de tweets no tópico Religião . . . . . . . . . . . . . .
Número de respostas por tópico. . . . . . . . . . . . . . . . . . . . . . .
Número de utilizadores por cada tópico. . . . . . . . . . . . . . . . . . .
Número de utilizadores por cada tópico. . . . . . . . . . . . . . . . . . .
Distribuição das redes disjuntas nos tópicos Desporto e Política . . . . . .
Distribuição das redes com sobreposição nos tópicos Desporto e Política .
Informação Mútua Pontual Normalizada nos tópicos Desporto e Política .
Distribuição das redes disjuntas nos tópicos Desporto e Religião . . . . .
Distribuição das redes com sobreposição nos tópicos Desporto e Religião
Informação Mútua Pontual Normalizada nos tópicos Desporto e Religião
Distribuição das redes disjuntas nos tópicos Religião e Política . . . . . .
Distribuição das redes com sobreposição nos tópicos Religião e Política .
Informação Mútua Pontual Normalizada nos tópicos Religião e Política .
66
66
66
68
69
71
73
73
74
75
75
76
77
77
78
5.1
Análise do fluxo de respostas entre as 19:00:00 e as 23:59:59 horas do dia
09 de Maio de 2010. . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Exemplo das comunidades coesas presentes no grafo de interacção e dos
conteúdos enviados pelos utilizadores entre as 19:00:00 e as 23:59:59 horas do dia 09 de Maio de 2010. . . . . . . . . . . . . . . . . . . . . . . .
Comparação das tagclouds de 3 comunidades diferentes . . . . . . . . . .
3.7
3.8
3.9
3.10
3.11
3.12
3.13
3.14
3.15
3.16
5.2
5.3
47
48
50
51
53
55
56
58
59
60
84
85
86
A.1 Exemplo da interface: grafo de interacção . . . . . . . . . . . . . . . . . 106
A.2 Exemplo da interface: análise da estrutura da rede . . . . . . . . . . . . . 107
x
LISTA DE FIGURAS
A.3 Exemplo da interface: análise quantitativa da rede (número de utilizadores
e mensagens) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
A.4 Exemplo da interface: análise diária da actividade da rede . . . . . . . . .
A.5 Exemplo da interface: análise horária da actividade da rede . . . . . . . .
A.6 Exemplo da interface: análise da interacção entre utilizadores . . . . . . .
A.7 Exemplo da interface: análise do fluxo de respostas da rede . . . . . . . .
A.8 Exemplo da interface: análise do comportamento dos utilizadores mais
activos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
xi
107
108
108
109
110
111
LISTA DE FIGURAS
xii
Lista de Tabelas
2.1
2.2
3.1
3.2
3.3
3.4
4.1
4.2
Complexidade temporal dos algoritmos de detecção de comunidades mais
utilizados (adaptado de [For10]) . . . . . . . . . . . . . . . . . . . . . .
Exemplo de filtragem colaborativa . . . . . . . . . . . . . . . . . . . . .
Descrição do conjunto de dados recolhido . . . . . . . . . . . . . . . . .
Comparação do clustering coefficient da rede presente na colecção de dados utilizada e uma rede aleatória com o mesmo número de utilizadores e
ligações . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Comparação do diâmetro do componente gigante de diferentes redes sociais (adaptado da fonte [MMG+ 07]) . . . . . . . . . . . . . . . . . . .
Comparação dos tempos de execução dos algoritmos de detecção de comunidades Wakita-Tsurumi e ClausetNewmanMoore . . . . . . . . . . .
Conjunto de palavras (keywords) utilizadas no processo de selecção das
mensagens por tópicos. . . . . . . . . . . . . . . . . . . . . . . . . . . .
Mensagens na intersecção dos três tópicos: Desporto, Política e Religião .
xiii
20
30
43
52
57
58
65
68
LISTA DE TABELAS
xiv
Abreviaturas e Símbolos
API
ARS
Bow
IMDb
LDA
NIPS
NPMI
RT
SVM
TF-IDF
WWW
Application Programming Interface
Análise de Redes Sociais
Bag-of-words
Internet Movie Database
Latent Dirichlet Allocation
Neural Information Processing Systems
Normalised Pointwise Mutual Information
Retweet
Support Vector Machine
Term Frequency - Inverse Document Frequency
World Wide Web
xv
ABREVIATURAS E SÍMBOLOS
xvi
Capítulo 1
Introdução
O ser humano é um indivíduo com uma tendência natural para viver em sociedade e
com uma necessidade de pertencer a um determinado grupo social e de se relacionar com
os seus semelhantes [Mor53]. Há pouco mais de uma década, o aparecimento das redes
sociais na Internet permitiu às pessoas a criação de comunidades virtuais e a interacção
através da Web, expondo assim as suas redes sociais online. A primeira rede social na
Internet, SixDegrees.com, surgiu em 1997 e desde então apareceram diversas redes sociais
que actualmente fazem parte do quotidiano das pessoas [BE07].
Hoje em dia existem inúmeras redes sociais, desde redes explícitas a redes implícitas,
que fornecem diferentes tipos de serviços e com conteúdo bastante diverso. Entre estas
encontram-se:
• as redes que permitem a partilha de imagens, informações pessoais e eventos e que
surgem com uma vertente mais pessoal e social como o caso do Facebook 1 , do hi52
ou do MySpace3 ;
• as denominadas redes de partilha (share) que permitem a publicação de conteúdos online desde fotografias, vídeos e outras informações, como por exemplo o
YouTube4 , o Flickr5 ou o Delicious6 ;
• as designadas redes de publicação (publish) através das quais qualquer indivíduo
pode publicar e expressar livremente a sua opinião como o caso dos blogs ou das
1 http://www.facebook.com/
2 http://www.hi5.com/
3 http://www.myspace.com/
4 http://www.youtube.com/
5 http://www.flickr.com/
6 http://delicious.com/
1
Introdução
redes de microblogging com um carácter maioritariamente de divulgação de informação como por exemplo, o Twitter7 ;
• as comunidades sociais dedicadas essencialmente à discussão de assuntos específicos como é o caso dos grupos de discussão (newsgroups); É de salientar que estas
comunidades são anteriores às redes sociais, pois surgiram por volta de 1980 com o
aparecimento da Usenet [Den98];
• e as comunidades dedicadas exclusivamente à divulgação e comercialização de produtos ou serviços, como por exemplo a Amazon8 ou o eBay9 .
Estas redes proporcionam diferentes meios de comunicação e são um meio de integração social devido à diversificada interacção estabelecida entre os indivíduos. Por outro
lado, propiciam a partilha de informação, experiências, debate ou discussão, aquisição de
conhecimento, etc.
A Figura 1.1 pretende expor a diversidade de redes, meios sociais ou fontes de partilha
e aquisição de conteúdos existentes na Web, através dos quais um utilizador se relaciona
de certa forma com uma comunidade.
Figura 1.1: Diversidade de interacções sociais na Web [Tur08]
Pode então constatar-se que o conteúdo presente nestas redes é bastante diversificado.
Assim sendo, a diversidade de ligações estabelecidas nas redes sociais, a quantidade distinta de conteúdo partilhado e a heterogeneidade de interesses presentes nas mesmas são
aspectos que despertam o interesse da comunidade científica neste tipo de redes.
7 https://twitter.com/
8 http://www.amazon.com/
9 http://www.ebay.com/
2
Introdução
Assim, o estudo de procedimentos automáticos para a caracterização dos relacionamentos entre as pessoas e detecção automática de comunidades constitui ao mesmo tempo
uma temática interessante e um desafio, pois envolve questões de carácter social e tecnológico. De um ponto de vista sociológico, os interesses e comportamentos do ser humano, mesmo que influenciados pelas pessoas com quem interage e pela comunidade na
qual se está inserido, podem divergir bastante dentro de uma mesma comunidade. Desta
forma, o estudo e a identificação dos interesses das pessoas, o reconhecimento de padrões
de comportamento, a identificação de comunidades e análise dos conteúdos da rede, pode
contribuir para a caracterização das relações entre os indivíduos e desenvolvimento de
novos sistemas.
1.1
Motivação e Objectivos
O interesse nas redes sociais resulta do facto de estas demonstrarem uma vasta diferenciação nas características sociais dos seus membros e uma elevada complexidade na
estrutura de ligações entre os indivíduos que por vezes pode não transmitir o verdadeiro
motivo ou significado das relações entre os elementos da rede. Por exemplo, a estrutura
de ligações numa rede social, por si só, pode não captar a semântica das relações uma vez
que comportamentos e interesses das pessoas envolvidas podem ser bastante diferentes e
em alguns casos as ligações podem até ser resultantes de vinculações esporádicas.
Assim, além da estrutura das ligações, existe um conjunto de informação latente nas
redes sociais proveniente do conteúdo que conjuntamente com a análise da topologia
da rede permite caracterizar de forma mais fidedigna as relações e interacções entre os
indivíduos.
Desta forma, esta dissertação tem como objectivos:
• o estudo das propriedades das redes sociais;
• a aplicação de métodos que permitam caracterizar as relações estabelecidas entre
os utilizadores e que permitam a detecção e a caracterização das comunidades que
se formam nas redes não só através de uma análise da estrutura de ligações mas
também através dos conteúdos;
• a caracterização exaustiva de um conjunto de dados específico para investigações
académicas;
• a investigação acerca da influência dos tópicos nas relações através de fundamentos estatísticos que permitam retirar conclusões acerca do comportamento dos utilizadores.
Além disso, com a crescente popularidade das redes sociais [BE07, MSST07], e à
medida que as interacções entre os utilizadores se tornam mais complexas, torna-se uma
3
Introdução
mais-valia saber distinguir e caracterizar diferentes tipos de ligações e comunidades. O
enriquecimento da informação acerca das relações entre os utilizadores nas redes sociais
é bastante útil na medida em que esta informação pode ser utilizada em diversas aplicações com objectivos e contextos diferentes como por exemplo, a elaboração de sistemas
de recomendação de conteúdos mais personalizados, filtro de conteúdos mais avançado,
pesquisa e recuperação de informação, marketing direccionado, previsões de consumo de
determinados produtos e serviços, criação automática de perfis de utilizador e de sistemas
classificação automática de perfis, entre outras.
1.2
Contribuições Científicas
Neste trabalho de investigação, é realizada uma caracterização exaustiva de uma colecção
de dados constituída por um conjunto vasto de utilizadores do Twitter em Portugal. De
referir, que este conjunto de dados surge no âmbito de um projecto colaborativo entre a
Faculdade de Engenharia da Universidade do Porto e o sapo.pt10 . Até à data, não há conhecimento de nenhum estudo que caracterize extensivamente a “Twittosfera” portuguesa
em termos de propriedades da rede e estrutura de ligações com o objectivo de perceber
o comportamento dos utilizadores e revelar tendências na utilização do serviço. Assim,
trata-se do primeiro trabalho sobre a “Twittosfera” portuguesa que apresenta múltiplas
estatísticas e que permite avaliar as propriedades que caracterizam o serviço de microblogging como uma rede social.
Além disso, é apresentado um estudo científico acerca das motivações dos utilizadores
e critérios de selecção da sua rede no momento de estabelecerem um acto de comunicação
com os restantes membros do serviço. Desta forma, é avaliada a influência dos tópicos
nas relações e é descrita a metodologia utilizada que é sustentada por fundamentos estatísticos.
Por outro lado, foi desenvolvida uma aplicação para caracterização de um conjunto de
dados genérico, e para a detecção e caracterização de comunidades nas redes sociais com
base na estrutura de ligações e na análise dos conteúdos.
1.3
Estrutura da Dissertação
Além da Introdução, esta dissertação contém mais 5 capítulos. No Capítulo 2 são
apresentados os conceitos fundamentais da Análise de Redes Sociais (ARS) e as propriedades das redes em geral. São também identificadas as técnicas de detecção automática de comunidades e apresentados alguns dos métodos que permitem a análise de
conteúdos. Além disso, são apresentados alguns estudos e trabalhos de referência que
servem de base para o trabalho desenvolvido nesta dissertação.
10 http://labs.sapo.pt/up/
4
Introdução
No Capítulo 3 é feita uma descrição detalhada do conjunto de dados utilizado e apresentada uma caracterização exaustiva da rede implícita na colecção, com o objectivo
de validar os conteúdos do conjunto de dados utilizado e de demonstrar que a colecção
utilizada é um conjunto representativo de uma rede social. No Capítulo 4 é analisada a
influência dos tópicos nas relações com o objectivo de perceber até que ponto é que os
tópicos são um factor que levam os utilizadores a interagir numa rede social. No Capítulo 5 é apresentada a aplicação desenvolvida ao longo deste trabalho de investigação. A
aplicação desenvolvida trata-se de uma ferramenta capaz de proporcionar uma caracterização combinada das comunidades, ou seja, permite a detecção das comunidades através
da análise da estrutura das ligações e a caracterização das mesmas com base no conteúdo.
Para finalizar, o Capítulo 6 apresenta um sumário das conclusões retiradas ao longo
de toda a dissertação e identifica as oportunidades para novas investigações futuras.
5
Introdução
6
Capítulo 2
Revisão Bibliográfica
Neste capítulo são descritos alguns conceitos e métodos frequentemente utilizados
na detecção automática de comunidades em redes, métodos utilizados na compreensão e
processamento de linguagem natural, mais especificamente nas técnicas de classificação e
categorização de texto, e são ainda apresentadas algumas abordagens utilizadas pelos sistemas de recomendação actuais. É também efectuada uma análise crítica e sucinta sobre
algumas das abordagens utilizadas e situações peculiares presentes no estudo e análise
dos relacionamentos sociais das pessoas. Por outro lado, pretende-se introduzir algumas
técnicas úteis para o trabalho desenvolvido nesta tese, como por exemplo, técnicas possibilitam a classificação de conteúdos e a identificação de comunidades de indivíduos com
interesses mútuos e/ou padrões de comportamento semelhantes.
A detecção automática de comunidades em redes aborda essencialmente questões relacionadas com a teoria de grafos. Desta forma, é efectuada uma revisão resumida sobre
algumas propriedades inerentes aos grafos, que são frequentemente utilizadas pelos métodos de detecção de comunidades, que permitem efectuar uma análise global da estrutura
das redes e/ou caracterizar determinados indivíduos em particular.
Quanto ao processamento e compreensão da linguagem natural, são enumerados alguns métodos e classes de métodos mais frequentes nas tarefas de classificação e categorização de documentos e apresentados alguns exemplos da sua possível utilização nas
redes sociais.
Relativamente aos sistemas de recomendação, são analisadas algumas das técnicas utilizadas pretendendo desta forma obter um conhecimento geral acerca do funcionamento
e das limitações de alguns dos sistemas actuais. Por outro lado, pretende-se evidenciar
de que forma é que estes sistemas poderão contribuir para a caracterização dos relacionamentos entre as pessoas e na identificação comunidades em redes.
7
Revisão Bibliográfica
Assim, através da apresentação de alguns conceitos, métodos e casos de estudo pretendese não só adquirir conhecimento sobre as técnicas utilizadas mas também reconhecer
aspectos relevantes que poderão contribuir para o estudo e análise das redes sociais na
Internet.
2.1
Análise de Redes Sociais e Detecção de Comunidades
Desde há muitos anos que a modelação e observação das relações entre as pessoas,
grupos e organizações têm sido alvo de interesse e estudo por parte da comunidade científica. Mesmo antes da existência das redes sociais na Internet, já eram analisadas as
ligações entre as pessoas como forma de estudar a estrutura de pequenos grupos de indivíduos.
Na década de 1930, mais precisamente em 1934, Jacob L. Moreno desenvolveu um
diagrama de nós e arestas, denominado de sociograma, no qual representava os relacionamentos sociais das pessoas [Mor53, WF94, Sco00]. Segundo Moreno, o Homem é um ser
social que necessita dos outros indivíduos para sobreviver e como tal pode ser estudado
através da análise das suas relações interpessoais [Mor53].
Desta forma, através da representação gráfica dos relacionamentos entre os indivíduos,
exemplificada na Figura 2.1, e analisando a quantidade de ligações associadas a cada um
deles, Moreno começou por realizar estudos em pequenos grupos de forma a identificar
os indivíduos mais populares de uma comunidade e determinar as pessoas mais isoladas
da sociedade [WF94, Sco00].
Figura 2.1: Exemplo de sociograma
Desde então, têm sido realizados diversos estudos sobre redes sustentados na representação gráfica das mesmas e apoiados na teoria de grafos [WF94, Sco00].
2.1.1
Representação dos Grafos
A Teoria dos Grafos é actualmente uma das áreas mais importantes da matemática
discreta. Na literatura, atribui-se a criação da teoria dos grafos ao matemático Euler, ao
8
Revisão Bibliográfica
resolver o problema das pontes de Königsberg em 1736 [Deo74].
Um grafo G=(V,E) consiste:
• num conjunto finito e não vazio de pontos V, denominado de vértices;
• num conjunto finito E, constituído por pares de vértices ordenados ou não ordenados
no caso de se tratarem de grafos dirigidos ou não dirigidos respectivamente, e que
é denominado por arestas. Uma aresta e ∈ E é um par de vértices v, w ∈ V, que
constituem as extremidades de e.
Existem diversos problemas de interesse prático que podem ser formulados através
de grafos uma vez que um grafo consiste num modelo matemático para o estudo das
relações entre objectos discretos de qualquer tipo. Hoje em dia, a Teoria dos Grafos tem
sido aplicada a muitas áreas como a Informática, a Investigação Operacional, a Economia,
a Sociologia, a Genética, entre outras.
Resumindo, diversos problemas de áreas distintas, bem como a análise das redes sociais e os problemas de detecção de comunidades em redes, têm sido estudados maioritariamente através de métodos ou modelos assentes na teoria de grafos [MSST07, For10].
Dependendo do domínio do problema, as arestas podem ter ou não uma direcção e
pode ser ou não permitido que as arestas liguem um vértice a ele próprio e/ou ainda que
estas tenham um peso associado.
No que diz respeito à representação das redes sociais em forma de grafo, a representação mais simples resulta da observação das relações recíprocas onde é verificada a
presença ou a ausência de ligações entre os membros da rede. Desta forma, a rede é
representada através de um grafo não dirigido como exemplificado na Figura 2.2.
Figura 2.2: Grafo não dirigido, não pesado
No entanto, nas redes sociais nem sempre se verifica a correspondência das relações ou
interacções entre os utilizadores, podendo então ser necessário a representação do sentido
das relações. Assim, a rede deve ser representada através de um grafo dirigido ou digrafo
como apresentado na Figura 2.3.
Para além do sentido da relação, pode também ser representada a intensidade da
mesma. Frequentemente, a modelação das ligações entre os elementos da rede atribui
9
Revisão Bibliográfica
pesos às ligações definindo assim o grau de importância da ligação, uma distância ou
ainda uma medida de similaridade entre os elementos da rede.
Figura 2.3: Grafo dirigido ou digrafo, não pesado
Desta forma, as redes podem ser representadas através de grafos pesados, dirigidos
ou não dirigidos conforme apresentado na Figura 2.4. O valor estabelecido na ligação
depende do domínio do problema e do objectivo pretendido.
Figura 2.4: Grafo não dirigido e pesado (à esquerda) e grafo dirigido e pesado (à direita)
2.1.2
Métricas utilizadas na Análise das Redes Sociais
Actualmente, a análise das redes sociais tem sido alvo de interesse por parte da comunidade científica que estuda os relacionamentos entre os indivíduos através da modelação
gráfica das redes e da extracção e análise das características inerentes à estrutura das mesmas. Considerando a estrutura de ligações presentes nas redes sociais, é recorrente a
representação destas utilizando um grafo nos qual os nós representam os utilizadores e as
arestas representam as relações entre os elementos da rede.
Desta forma, sustentados nos conceitos provenientes da teoria de grafos e extraindo
determinadas propriedades [WF94, Sco00, OCL08], torna-se possível caracterizar a estrutura das redes numa perspectiva global e analisar determinados grupos ou indivíduos
em particular. Entre estas propriedades encontram-se medidas como:
10
Revisão Bibliográfica
• Densidade (Density): a densidade indica a coesão global de uma rede e é dada pelo
número de ligações estabelecidas pelos elementos da rede a dividir pelo número
possível de ligações que poderiam ser estabelecidas. Desta forma, é sempre um
valor no intervalo [0, 1], sendo que o valor 1 corresponde a uma rede completa, ou
seja, um clique;
• Grau de centralidade ou degree: quantifica o número de ligações associadas a um
determinado indivíduo. Esta métrica é representada por outras duas quando se trata
de grafos dirigidos: o in-degree - número de arestas incidentes no nó - e o out-degree
- número de arestas emergentes do nó;
• Closeness: reflecte a proximidade entre um indivíduo e os restantes membros da
rede. Esta medida é um factor que indica se o grau de centralidade (degree) de um
indivíduo está próximo do dos restantes membros da rede. Esta medida reflecte
a capacidade de “acesso à informação” através dos outros indivíduos da rede. A
proximidade é o inverso da soma das menores distâncias entre cada indivíduo e
todas as outras pessoas na rede. Como definido por Freeman em 1979 [Sco00],
a medida de centralidade closeness é dada pela soma das distâncias dos caminhos
mais curtos entre o nó e todos os outros nós da rede. No contexto do fluxo de
informação, pode ser encarado como um índice de chegada de informação da rede
a esse nó [Bor05];
• Betweenness: mede a capacidade de um nó ser intermediário na rede. Esta medida
tem em conta as ligações dos vizinhos do nó, atribuindo um valor maior aos nós
que são uma espécie elos de ligação entre grupos/indivíduos. Num grafo G = (V,E)
com N vértices, a medida de centralidade betweenness CB (v) de um vértice v é dada
por:∑s6=v6=t∈V,s6=t σstσ(v)
, em que σst representa o número de caminhos mais curtos
st
entre o vértice s e o vértice t, e σst (v) o número de caminhos mais curtos entre s to
t que contêm o vértice v, isto é, o número de caminhos mais curtos entre s e t que
passam por v;
• Edge Betweenness: propriedade que quantifica a importância de uma determinada
ligação entre dois membros da rede. Uma aresta é tão mais importante quanto mais
caminhos geodésicos passarem pela aresta;
• Clustering coefficient: esta métrica mede a tendência que um vértice tem para formar grupos coesos com os seus nós vizinhos. Por outra palavras, o clustering coefficient de um vértice é dado pela proporção de ligações existentes entre o vértice
e todos os seus vértices adjacentes, divido pelo número total de ligações possíveis
entre eles;
11
Revisão Bibliográfica
• Eigenvector centrality: mede a importância de um nó na rede atribuindo valores relativos a todos os nós baseado no princípio de que as ligações a nós com valores mais
elevados contribuem mais para o valor do nó em questão. Pode ser encarado como
uma versão recursiva do grau de centralidade (degree), isto é, começa-se por atribuir
o mesmo valor a todos os nós da rede, por exemplo o valor 1 e de seguida os valores
de cada nó são calculados através de uma soma pesada dos valores dos vizinhos do
nó sendo efectuada uma normalização (divisão pelo maior valor). Um valor elevado
para esta métrica indica que um nó está numa posição central na rede na medida em
que esse nó está ligado a outros que são centrais na rede. Esta medida é semelhante
ao PageRank [PBMW98]. O PageRank é um método, apenas é utilizado em grafos
dirigidos, que a partir da análise das ligações permite determinar a importância de
um nó na rede. A importância de um nó na rede depende de quão importantes são
os nós aos quais está ligado.
De seguida, é apresentado um pequeno exemplo que permite entender melhor algumas
das medidas de centralidade enunciadas. No exemplo da Figura 2.5, o elemento D é o
vértice que tem o valor mais elevado para a medida de centralidade betweenness uma
vez que está relacionado indirectamente com mais indivíduos do que todos os outros
elementos da rede. Por outro lado, os elementos I e K têm um valor mais alto para a
medida de centralidade closeness uma que vez que, em média, são os que estão mais
próximos dos restantes membros da rede.
Verifica-se ainda que o elemento B é o elemento que tem o maior grau de centralidade
(degree), uma vez que este detém mais ligações directas com outros elementos da rede.
Neste exemplo, o elemento B está ligado directamente a 5 elementos da rede tendo mais
do que todos os outros elementos.
Figura 2.5: Exemplo de grafo utilizado para explicar as medidas de centralidade
Desta forma, algumas destas características evidenciam os indivíduos mais influentes
ou relevantes numa comunidade e ainda as ligações mais importantes entre os elementos
da rede. Assim, é frequente que os estudos realizados em redes sociais abordem questões
12
Revisão Bibliográfica
de centralidade e de ligação [New03] como por exemplo: detectar o conjunto de indivíduos que têm mais ligações na rede; identificar os indivíduos que constituem elos de
ligação entre determinados membros ou grupos; detectar os elementos com as relações
mais relevantes e/ou os indivíduos mais isolados da comunidade; e ainda outras questões
relacionadas com a estrutura da rede como o caso da detecção comunidades coesas ou
identificação de grupos de interacção.
2.1.3
Propriedades e classes de redes complexas
Além das métricas enunciadas na secção anterior, existem outras estruturas [WF94,
Sco00, Mik07] provenientes da teoria de grafos que permitem através da análise das ligações da rede identificar grupos de indivíduos ou comunidades coesas, como por exemplo:
• a detecção de componentes totalmente conexos (cliques), que consistem em comunidades nas quais cada indivíduo está ligado directamente a todos os restantes;
• a detecção de componentes em grafos (components), que consistem em grupos de
indivíduos ligados directa ou indirectamente entre si que formam comunidades coesas, isto é, comunidades com muitas ligações entre os elementos do grupo;
• a detecção de ciclos na rede (cycles);
• o cálculo de distâncias mínimas entre membros da rede e extracção de caminhos
geodésicos (geodesic path);
• árvores de expansão mínima spanning tree.
A Figura 2.6 ilustra alguns dos conceitos enumerados e a Figura 2.7 apresenta um
exemplo de uma rede na qual são identificadas comunidades coesas.
Figura 2.6: Exemplo de propriedades (cliques, cycles, geodesic paths, spanning trees)
13
Revisão Bibliográfica
Figura 2.7: Exemplo de rede com comunidades coesas em redes
[Mik07]
De um modo geral, a extracção destas características permite compreender a estrutura
global de uma rede e a distribuição das pessoas pela mesma. Ademais, na literatura têm
sido estudadas diversas propriedades de várias classes de redes complexas. De seguida,
apresentam-se algumas classes e propriedades que permitem caracterizar diversos sistemas do mundo real.
2.1.3.1 Power-law Networks
As Power-law Networks são um tipo de redes caracterizadas por terem uma distribuição peculiar no grau de centralidade (degree) dos seus nós. Estas distribuições,
denominadas de power-law distributions, contêm alguns vértices com um grau de centralidade muito elevado e muitos vértices com um grau de centralidade baixo. Em termos
matemáticos, são redes em que a probabilidade de um vértice ter um grau de centralidade
k é proporcional a k−γ , onde k é um número muito e γ > 1. O parâmetro γ é denominado de
coeficiente da distribuição (power-law coefficient). Na realidade, existem inúmeras redes
reais que possuem esta distribuição muito característica. Por exemplo, nas redes sociais, esta distribuição reflecte a presença de indivíduos centrais que interagem com muitos
outros e que desempenham um papel fundamental na difusão da informação. Além desta
propriedade, tem-se verificado que os vértices com um maior grau de centralidade tendem
a estar ligados a vértices com um grau de centralidade também elevado. Este conjunto
de redes são denominadas de scale-free networks [LAT+ 05] e são uma subclasse das
power-law networks.
2.1.3.2
Redes Aleatórias (Random Networks)
As redes aletórias são geralmente construídas acrescentando ligações aleatórias a um
conjunto estático de vértices. Estudos realizados [KR96] mostram que este tipo de redes
tendem a ter caminhos muito curtos entre quaisquer dois vértices. Desta forma, estas redes
14
Revisão Bibliográfica
reproduzem bem uma das características das redes do mundo real [New03], o denominado small-world effect [New00]. No entanto, tem-se demonstrado que as propriedades
de uma rede aleatória não coincidem com as propriedades das redes sociais nem com
outras redes do mundo real [New03]. Por exemplo, as redes aleatórias tem um valor
médio para a métrica clustering coefficient consideravelmente mais baixo do que as redes
sociais e redes de comunicação. Além disso, a distribuição do grau de centralidade dos
seus nós segue o modelo semelhante a uma distribuição Poisson [New03]. No entanto,
recentemente têm sido estudados métodos para a construção de redes aleatórias com distribuições específicas [MR95], construídas de forma a conterem um componente gigante
[MRC00] simulando assim o comportamento das redes sociais e de redes comunicação.
A Figura 2.8 pretende evidenciar as diferenças entre as distribuições do grau de centralidade dos nós apresentadas pelas power-law networks e as redes aleatórias. Além das
propriedades das classes anteriores, existem outros dois fenómenos que permitem caracterizar as redes e que são frequentemente observados nas redes sociais: o small-world
effect e a auto-similaridade (self-similarity).
Figura 2.8: Comparação das distribuições apresentadas no grau de centralidade dos nós numa
“power-law network” e uma rede aleatória (random network)
2.1.3.3 Small-world effect
O small-world effect ou a teoria dos seis graus de separação (six-degrees of separation) é a ideia de que qualquer par de pessoas no mundo estão ligadas entre si através de
um conjunto de pessoas intermediárias que é tipicamente de cerca de seis pessoas. Este
fenómeno tem sido nos últimos anos um assunto de grande interesse para a comunidade
científica. A Figura 2.9 pretende ilustrar este conceito.
15
Revisão Bibliográfica
Figura 2.9: Exemplificação da teoria dos seis graus de separação (six-degrees of separation)
[Sig09]
A explicação mais simples deste fenómeno recorre a um grafo aleatório [New00].
Sendo N o número total de pessoas no mundo e z o número médio de “conhecidos” que
cada pessoa tem, implica que existem pelo menos Nz
2 ligações entre as pessoas de todo
o mundo. Assim, um modelo muito simples para estudar este fenómeno, consiste em
construir uma rede aleatória com N vértices e Nz
2 arestas que representam ligações entre
pares aleatoriamente escolhidos. Desta forma, é fácil de verificar que um grafo aleatório
apresenta o efeito de mundo pequeno (small-world effect) [New00].
Por exemplo, imaginando que uma determinada pessoa A na rede aleatória, tem z
“conhecidos” (vértices adjacentes) e que por sua vez cada um dos seus “conhecidos” também tem z vértices adjacentes, então tem-se que A tem cerca de z2 pessoas às quais está
ligada numa rede de nível 2, e estaria ligada a cerca de z3 pessoas numa rede de nível 3
e assim por diante. Acredita-se, tal como referido por Newman [New00], que a maioria
das pessoas terá mais de cem “conhecidos” e que na sua rede de nível 5 (z5 conhecidos), o valor obtido é comparável à população mundial (menor do que 7.000.000.000 de
pessoas)1 .
Por outro lado, estudos recentes têm demonstrado, através do diâmetro2 da rede, que
a teoria dos seis graus de separação é também válida nas redes sociais [MMG+ 07]
[KNT06].
2.1.3.4
Auto-similaridade (Self-similarity)
As propriedades referidas anteriormente, o small-world effect e as propriedades na
distribuição do grau de centralidade dos vértices (power-law distributions) presentes nas
1 Worldometers:
2 Média
estatísticas em tempo real (http://www.worldometers.info/). Consultado a 20 de Junho de 2010
das distâncias geodésicas entre todos os pares de vértices da rede
16
Revisão Bibliográfica
redes do tipo scale-free, são propriedades fundamentais para entender a estrutura e topologia de redes complexas. No entanto, a auto-similaridade presente na natureza e observada
em muitos outros domínios como, por exemplo na física, na biologia e até mesmo na
psicologia e sociologia, tem-se tornado num dos princípios fundamentais para a compreensão da estrutura das redes. Assim, surgiram estudos com o objectivo de demonstrar
que diversas redes são invariantes ou auto-similares quando sofrem alterações significativas na escala, isto é, as redes mantêm as suas propriedades em níveis de granularidade
diferentes. Estudos recentes [GDD+ 03, SHM05] demonstram que inúmeras redes complexas, tais como a World Wide Web (WWW), redes biológicas, redes de comunicação e
redes sociais possuem uma estrutura característica organizada e são invariantes às transformações de escala. Os autores revelam que estes resultados são surpreendentes uma vez
que as propriedades das redes ditas small-world aparentemente implicariam que, com o
aumento do número de vértices, o diâmetro da rede aumentasse exponencialmente. Contudo, contrariamente a esta hipótese, verifica-se que diversas redes consistem em padrões
repetidos em diversas escalas diferentes. A Figura 2.10 pretende ilustrar o carácter autosimilar de uma rede complexa.
Figura 2.10: Exemplificação do comportamento auto-similiar de uma rede complexa [SHM05]
2.1.4
Métodos de detecção de comunidades
No que diz respeito às técnicas utilizadas na detecção automática de comunidades
em redes, têm sido propostos diversos métodos e classes de métodos com abordagens
distintas. As abordagens mais tradicionais são os métodos de partição de grafos (graph
partitioning), métodos de clustering particionais (partitional clustering) ou os métodos
de clustering hierárquico (hierarchical clustering) [CZG09]. Nos métodos de clustering
particionais, o número de grupos ou comunidades a obter encontra-se definido a priori e
17
Revisão Bibliográfica
o objectivo consiste em maximizar ou minimizar uma função de custo baseada nas distâncias entre os elementos da rede. Por outro lado, nos métodos de clustering hierárquico
o número de grupos que se obtém na extracção de comunidades não se encontra previamente definido. Assim, nesta classe de métodos, os grupos surgem de uma forma natural
considerando apenas as medidas de similaridade definidas entre os elementos da rede. De
referir ainda, que os métodos pertencentes a esta classe apenas devem ser utilizados em
problemas cuja estrutura evidencia à partida uma hierarquia entre os elementos. Contudo,
esta classe de métodos nem sempre é realista, uma vez que na maioria dos casos um grafo
não apresenta uma estrutura hierárquica bem definida [For10].
Uma outra classe de métodos frequentemente utilizada na detecção automática de comunidades são os métodos de clustering espectral (spectral clustering) que utilizam a representação matricial do grafo para, através de propriedades algébricas como é o caso dos
vectores e valores próprios, induzirem grupos nos dados. Estes métodos são frequentemente utilizados uma vez que são fáceis de implementar e obtêm soluções recorrendo a
métodos tradicionais da álgebra linear [WS05]. Um dos critérios de partição mais populares e frequentemente adoptados nesta classe de métodos consiste no corte normalizado
[WS05, XCK+ 09, vL07].
Além destes, o conjunto de algoritmos que maximizam uma função denominada de
modularidade, constitui também uma classe de métodos muito popular nos problemas de
extracção de comunidades em redes [For10, NG03]. A modularidade é uma heurística
que permite avaliar a qualidade de uma determinada decomposição da rede em comunidades. Por outras palavras, a modularidade determina quando é que uma divisão da rede
é satisfatória, na medida em que existem muitas arestas no interior de cada comunidade
obtida e poucas arestas entre as comunidades [CNM04]. Esta última classe de métodos
foi desenvolvida por Newman e Girvan e a modularidade é reconhecida por muitos como
sendo uma das melhores medidas para avaliar a qualidade dos possíveis grupos que se
formam nas redes [NG03, dSEdLE09].
Resumindo, e como já foi referido anteriormente, os problemas de detecção de comunidades em redes são, substancialmente, problemas sustentados na teoria de grafos. No
entanto, obter uma bissecção óptima num grafo é considerado um problema de análise
combinatória e um problema NP-completo [XCK+ 09, For10, WS05]. Assim, os métodos utilizados constituem todos soluções aproximadas para este problema.
Outro aspecto muito importante a salientar, é o facto de alguns destes métodos assumirem que cada elemento da rede apenas pertence a um determinado grupo ou comunidade, isto é, algumas destas abordagens apenas obtêm comunidades disjuntas não
admitindo que um indivíduo seja incluído em mais do que um grupo [CZG09]. No entanto, observando a realidade de algumas redes sociais é muito frequente que uma pessoa
possa fazer parte de diversos grupos simultaneamente devido à variedade de interesses
que manifesta e diversidade de relações que estabelece [DWP+ 07, CZG09].
18
Revisão Bibliográfica
Dependendo do caso de estudo e da rede social considerada, esta realidade pode constituir uma limitação para a utilização de alguns destes métodos. Por exemplo, através de
alguns dos métodos existentes um indivíduo que interage frequentemente e de igual modo
com dois ou mais grupos distintos seria apenas associado a um deles. Considerando estas
circunstâncias, foram explorados métodos baseados em lógica difusa e algumas propostas
com alterações dos métodos existentes que possibilitam a extracção de comunidades com
sobreposição [MSST07, CZG09, Gre07, Piz09, NG03]. Deste modo, surgiram alguns
métodos que obtêm comunidades sobrepostas, permitindo assim que um indivíduo possa
ser incluído em mais do que uma comunidade como exemplificado na Figura 2.11.
Figura 2.11: Exemplo de rede com comunidades sobrepostas [CZG09]
Em suma, existe um conjunto muito vasto de técnicas e classes de métodos utilizados nos problemas de detecção de comunidades em redes. A maioria dos métodos difere
não só na abordagem adoptada mas também na respectiva ordem de complexidade computacional. Uma vez que este constitui também um factor muito importante a considerar,
tem sido frequente ao longo dos anos a comparação entre diversos métodos através de
avaliações de desempenho benchmarks.
De seguida, são apresentadas algumas referências para os métodos recentemente utilizados na detecção automática de comunidades em redes. Na Tabela 2.1, são apresentados não só as referências mas também os nomes dos autores que mais contribuiram para
o estudo e detecção de comunidades em redes, os respectivos ano de publicação e ordens
de complexidade.
O trabalho realizado por Fortunato [For10] apresenta uma descrição mais detalhada
das técnicas utilizadas e as respectivas referências às avaliações de desempenho dos métodos apresentados (benchmarks).
19
Revisão Bibliográfica
Tabela 2.1: Complexidade temporal dos algoritmos de detecção de comunidades mais utilizados
(adaptado de [For10])
Autor
Eckmann & Moses
Zhou & Lipwosky
Lapaty & Pons
Clauset, Newman & Moore
Newman & Girvan
Girvan & Newman
Guimerà et al.
Duch & Arenas
Fortunato, Latora & Marchiori
Radicchi et al.
Donetti & Muñoz
Bagrow & Bollt
Capocci et al.
Wu & Huberman
Palla et al.
Reichardt & Bornholdt
Wakita & Tsurumi
2.1.5
Referência
[EM02]
[ZL04]
[PL05]
[CNM04]
[NG03]
[GN02]
[GA05]; [GAD+ 04]
[DA05]
[FLM04]
[RCC+ 04]
[DM04]
[BB05]
[CSCC04]
[WH04]
[PDFV05]
[RB04]
[WT07]
Sigla
EM
ZL
LP
CNM
NG
GN
SA
DA
FLM
RCCLP
DN/DMN
BB
CSCC
WH
PK
RB
WT
Complexidade temporal
O(m(k2 ))
O(n3 )
O(n3 )
O(nlog2 n)
O(nm2 )
O(n2 m)
dependente de parâmetros
O(n2 logn)
O(m3 n)
4
O( mn2 )
O(n3 )
O(n3 )
O(n2 )
O(n + m)
O(exp(n))
dependente de parâmetros
dependente da heurística
Trabalhos relacionados
Como já foi referido, a detecção automática de comunidades constitui um dos problemas fundamentais em redes e é um problema de enorme interesse para a comunidade
científica. Nos últimos anos, este problema tem sido estudado e aplicado em diversas
áreas como por exemplo, as ciências sociais, a ciência dos computadores ou os estudos
biológicos [BE07, MSST07, RZ07, New03, For10].
Na realidade, existe uma variedade de problemas nos quais são estudados métodos
para a obtenção grupos com entidades relacionadas, como por exemplo, a obtenção de
grupos de pessoas que trocam frequentemente mensagens de e-mail entre si através da
observação das respectivas comunicações por e-mail; a criação de conjuntos de páginas
Web relacionadas através da análise da estrutura de ligações entre as mesmas; a detecção
de comunidades em redes de co-autoria nas quais se pretende obter grupos de autores que
publicam artigos em conjunto; ou a análise de redes de citação nas quais se pretende obter
grupos de artigos relacionados analisando apenas a estrutura emergente das citações; entre
outros.
Na maioria dos problemas mencionados, é de certa forma natural que a detecção de
comunidades através da análise da estrutura das redes crie grupos cujos membros estão
relacionados e/ou comunidades em que existem interesses mútuos entre as pessoas. Por
exemplo, no caso de um grupo de indivíduos que interagem frequentemente entre si é
provável que estes manifestem interesses comuns, no entanto, este facto é uma conjectura
20
Revisão Bibliográfica
que parte da estrutura de ligações da rede e do domínio das relações estabelecidas, uma
vez que na maioria das ocasiões os conteúdos da rede não são analisados.
De seguida são apresentados e analisados de forma mais detalhada alguns casos de
estudo nos quais foram aplicados alguns métodos anteriormente enunciados na detecção
de comunidades coesas em redes.
Um dos problemas consiste na detecção de comunidades de co-autores em redes de
publicação de artigos [WS05]. O caso estudado trata da rede de autores que publicam
artigos na conferência NIPS (Neural Information Processing Systems). A solução apresentada recorre a métodos de clustering espectral para obter grupos de pessoas que
efectuam publicações de artigos em conjunto. Para o efeito, a rede consistia nos autores
dos artigos publicados entre os volumes 0 a 12 da conferência NIPS perfazendo um total
de 2037 autores para os 1740 artigos publicados. Nesta rede foi construído um grafo no
qual os nós representam os autores e as ligações entre dois membros da rede significa que
estes publicaram pelo menos um artigo em conjunto para a conferência NIPS.
Nesta rede, o peso das ligações estabelecidas entre dois autores era dado pela seguinte
função ou medida de similaridade:
Wij = ∑
k
1
1 − nk
(2.1)
De notar que a constante k consiste no número de artigos que os autores i e j publicaram em conjunto. Contudo, um artigo pode ser escrito por mais do que duas pessoas e
assim sendo, nk representa o número de autores do artigo k. Desta forma, Wi j representa o
peso da ligação entre o autor i e o autor j. Desta forma, e através da aplicação de métodos
de clustering espectral, o objectivo pretendido consistia em obter grupos de autores que
publicaram artigos em conjunto. No entanto, na construção da rede com os dados iniciais,
verificou-se a ocorrência de muitos nós entre os quais não era estabelecido um número
significativo de ligações e que de certa forma não permitia obter bons resultados. Devido a este facto, foram realizadas novas experiências considerando apenas um conjunto
de autores com relações mais dominantes. Na rede final construída foram aplicados dois
algoritmos de clustering espectral parametrizados de forma a obter 100 grupos distintos
de autores que frequentemente publicam artigos em conjunto [WS05].
Assim, este problema revela que é possível obter comunidades de pessoas relacionadas
através da representação da rede em forma de grafo e da adopção de métodos de clustering
espectral para induzir grupos nos dados. Contudo, nesta rede a relação entre os autores
apenas dependia de um factor que pesava na ligação.
Todavia, nas redes sociais as ligações entre os utilizadores podem depender de vários
factores que de algum modo contribuem de formas distintas na caracterização dos seus
relacionamentos interpessoais. Neste sentido, o exemplo seguinte evidencia que é pos21
Revisão Bibliográfica
sível combinar diversos factores para a detecção de comunidades em blogs cujos utilizadores têm conhecimento mútuo das acções dos outros.
Os blogs ou weblogs são meios de comunicação social na Internet que permitem
aos utilizadores publicar conteúdo e partilhá-lo com a comunidade. Neste meio, os utilizadores comunicam uns com os outros essencialmente através de mensagens e comentários. Por outro lado, é ainda possível por intermédio de notificações explícitas informar um determinado utilizador de que outros publicaram conteúdos referentes às suas
mensagens. Assim, através destes meios de interacção e dependendo dos interesses dos
utilizadores, são formadas diversas comunidades na blogosfera.
Desta forma, a extracção de grupos de bloggers com conhecimento das acções uns dos
outros e que interagem frequentemente entre si foi analisado como problema de clustering
no qual foram utilizados os métodos sustentados na teoria de grafos [rLSC+ 06]. De
referir que nesta análise, os autores apenas consideram como comunidades conjuntos de
indivíduos entre os quais existe o conhecimento mútuo das acções que realizam ou uma
comunicação bidireccional entre os mesmos.
A Figura 2.12 apresenta exemplos de grupos de bloggers não considerados como
comunidades uma vez que representam situações nas quais existe uma interacção unidireccional.
Figura 2.12: Exemplo de comunidades em blogs não consideradas devido à ausência do conhecimento mútuo [rLSC+ 06]
O conhecimento mútuo entre os utilizadores é determinado através da observação das
diferentes acções que estes realizam. Algumas destas acções supõem de imediato o conhecimento mútuo, como por exemplo, os comentários realizados a uma mensagem de um
blog ou as notificações recebidas por um utilizador, que indicam as mensagens publicadas
por outros. Por outro lado, existem acções que não permitem assumir a existência deste
conhecimento mútuo, como por exemplo, o caso de inserção de links para as entradas de
determinado blog nas mensagens ou comentários de um outro blog. Nesta situação, um
utilizador divulga uma mensagem ou weblog sem que o utilizador referenciado ou citado
tenha conhecimento desta acção [rLSC+ 06].
22
Revisão Bibliográfica
Assim, neste problema foi construído um grafo cujos nós representam os bloggers e
as ligações entre dois membros da rede são estabelecidas se ambos têm conhecimento das
acções realizadas pelo outro. Para além disso, neste caso de estudo, as ligações estabelecidas entre os utilizadores são afectadas por diversos factores como por exemplo, o tipo
de acções entre os utilizadores, a quantidade de acções entre os mesmos e o tempo em
que estas ocorreram [rLSC+ 06].
Desta forma as comunidades obtidas dependem de diversos factores que caracterizam
as relações de formas distintas. Contudo, embora as ligações entre os utilizadores sejam pesadas por diversos factores como o número ou tipo de acções entre eles e ainda
pelo tempo em que as acções decorreram, os conteúdos dos blogs como as mensagens ou
os comentários, não são inspeccionados nem considerados relevantes na detecção destas
comunidades. Desta forma, apesar de os resultados revelarem grupos de bloggers que
interagem frequentemente entre si e que provavelmente têm interesses idênticos, podem
eventualmente existir situações em que determinado indivíduo é arrastado para uma comunidade devido às suas interacções não relacionadas com os conteúdos. Assim sendo,
poderão existir grupos ou comunidades em que os utilizadores não partilham os mesmos
sub-tópicos de interesse.
Em jeito de conclusão, são diversos os casos de estudo na detecção automática de
comunidades em redes nos quais são aplicados métodos que apenas analisam a estrutura
de ligações da rede para extrair informação sobre os possíveis grupos ou comunidades
que se podem formar. Em algumas destas redes, a estrutura apenas transmite questões de
sintaxe existindo ainda alguma falta de preocupação com a semântica das relações. Neste
sentido, podem ser explorados métodos para a análise de conteúdos que poderão permitir,
através da informação latente nas redes, contextualizar e caracterizar melhor os relacionamentos entre os indivíduos. Por exemplo, através da identificação de interesses mútuos
e/ou do reconhecimento de padrões de comportamento poderá ser possível efectuar uma
segmentação da rede com um nível de granularidade mais elevado e com um maior grau
de contextualização.
2.2
Análise de conteúdos
Geralmente, os estudos realizados em redes numa perspectiva geral, e mais particularmente na análise das redes sociais, pretendem modelar a existência de ligações entre
entidades e não captam algumas propriedades importantes nas relações como por exemplo os conteúdos resultantes das interacções entre os elementos da rede. Em muitos dos
casos, a modelação e a análise das redes sociais não consideram a riqueza que o processamento da linguagem natural presente nos conteúdos resultantes das interacções entre as
pessoas poderá proporcionar [MWC07].
23
Revisão Bibliográfica
A detecção das palavras utilizadas, dos tópicos envolvidos e a análise de outras especificidades presentes nas interacções entre os utilizadores poderão, possivelmente, enriquecer a semântica das relações e caracterizar melhor as interacções entre os indivíduos
e/ou até descrever melhor as redes numa perspectiva global. Por exemplo, considerando a
estrutura de ligações de uma rede e analisando as propriedades inerentes à sua topologia,
é possível determinar pessoas influentes numa comunidade e atribuir-lhes papéis distintos
dos restantes membros. Esta análise é frequentemente realizada através da observação
do número de ligações que um determinado indivíduo detém. Contudo, é evidente que
considerar apenas as propriedades topológicas da rede pode não ser suficiente para, por
exemplo, afirmar que um indivíduo é o mais influente numa comunidade ou que desempenha um papel específico na rede [MWC07].
Da mesma forma, a detecção automática de comunidades sustentada apenas na estrutura de ligações entre os indivíduos, embora possibilite a extracção de muita informação
que permite inferir conhecimento sobre os utilizadores e/ou revelar indícios de interesses
comuns, pode não ser suficiente para captar a semântica dos grupos e identificar os interesses das pessoas pertencentes a uma mesma comunidade.
Perante esta hipótese, podem ser explorados métodos que possibilitam a análise de
alguns dos conteúdos da rede como por exemplo, métodos para a detecção de tópicos,
métodos para a sumarização de texto, métodos para a categorização de documentos e/ou
métodos para a extracção de informação relevante das mensagens como as palavras mais
representativas numa colecção de documentos.
Desta forma, torna-se possível analisar alguns dos conteúdos presentes nas redes sociais e no fluxo de informação resultante das interacções entre os elementos da rede, de
forma a identificar interesses mútuos e padrões de comportamento dos utilizadores.
Relativamente aos métodos utilizados para comparação e classificação de documentos,
é frequente a adopção do modelo vectorial para representação dos mesmos. Geralmente,
as representações segundo este modelo assumem que as palavras ocorrem nos documentos de forma independente umas das outras e são ignoradas questões sintácticas [JM00].
Esta representação, também denominada de bag-of-words (bow), juntamente com medidas estatísticas como por exemplo a frequência dos termos num documento, é muito
comum para a descrição dos documentos de uma colecção. Assim, um determinado documento pode ser representado por um conjunto de termos para os quais são contabilizadas
as suas ocorrências nesse documento.
Nesta forma, e sendo este um modelo algébrico, uma medida de similaridade entre
documentos frequentemente utilizada consiste no produto escalar entre os vectores que
representam cada um dos documentos. Assim, esta constitui uma das formas de medir a
similaridade "semântica"entre os documentos de uma colecção [JM00, HFS08, SGL+ 07,
MS99].
24
Revisão Bibliográfica
No entanto, algumas das palavras utilizadas nos documentos podem ser mais representativas do que outras uma vez que determinados termos podem aparecer com frequência muito elevada mas de certo modo não distinguirem ou caracterizarem os documentos
devido à sua vulgaridade em toda a colecção. Assim, um esquema muito utilizado na
atribuição de pesos aos termos de um documento é o popular tf-idft,d = tft,d × idft [TT04]
no qual se consideram a frequência do termo t no documento d e o número de documentos
em que o termo aparece [JM00, SGL+ 07].
Outro aspecto relevante, que constitui um dos passos importantes na utilização desta
representação e de alguns métodos de classificação e categorização de documentos, consiste no pré-processamento ou tratamento do texto de forma a melhorar a eficácia e precisão no processo de comparação e classificação.
Assim, o processo de remoção das denominadas stopwords, palavras que não acrescentam informação útil ao documento, e o processo de Porter [JM00] ou de redução das
variações morfológicas das palavras convertendo-as nos seus respectivos radicais através
da supressão dos afixos, devem ser considerados na análise dos conteúdos presentes nas
redes sociais.
Relativamente às técnicas para a classificação automática de documentos em classes
pré-definidas, existe uma diversidade de métodos e algoritmos presentes na literatura
que são frequentemente utilizados, como por exemplo, os algoritmos do tipo nearest
neighbor, as árvores de decisão, as populares Support Vector Machines (SVMs), as redes bayesianas, as redes neuronais, os algoritmos baseados em regras de associação, entre
outros [DPHS98, AE99]. De entre o conjunto de métodos enunciados as Support Vector Machines têm ganho muita popularidade uma vez que são classificadores com uma
ordem de complexidade reduzida, eficientes, fáceis de treinar e de avaliar e obtêm frequentemente resultados bastante precisos [DPHS98, Joa98].
Por exemplo, as Support Vector Machines foram utilizadas para a classificação automática de respostas às mensagens em grupos de discussão [FRM07]. Nos grupos
de discussão, os participantes interagem através de mensagens debatendo determinado
tópico ou assunto. Assim, os utilizadores podem expressar a sua opinião sobre o tema,
concordar ou discordar com os pontos de vista de outros utilizadores, colocar perguntas, responder a questões ou simplesmente divagar e escrever sobre algo não relacionado
com o assunto debatido. Assim, no estudo realizado foram utilizadas as Support Vector
Machines de forma a identificar padrões de pergunta e resposta em tópicos de discussão
de carácter mais técnico e classificar as mensagens em tópicos sobre política segundo o
nível de concordância das mesmas com a mensagem original [FRM07]. Desta forma, e
após efectuado o treino do classificador com dados previamente recolhidos e classificados
manualmente, foram submetidas novas mensagens de forma a classificar as mesmas como
pergunta (question) ou resposta (answer) no caso das mensagens dos tópicos de carácter
mais técnico ou como agree, disagree ou insult no caso das mensagens dos tópicos de
25
Revisão Bibliográfica
discussão sobre política.
Existem ainda outros exemplos nos quais foram utilizadas as Support Vector Machines
para a classificação ou categorização de mensagens como a detecção da polaridade de
sentimentos em comentários sobre filmes [AK08] ou a classificação das opiniões dos
utilizadores sobre produtos disponíveis online.
Em algumas situações a classificação é binária, ou seja, uma mensagem é classificada
numa de duas classes como por exemplo, identificar a polaridade de um determinado texto
que consiste em atribuir-lhe uma de duas classes: positivo ou negativo [DPHS98] . Por
conseguinte, as SVMs revelam-se muito apropriadas para esta tarefa uma vez que na sua
forma linear mais simples estas consistem num hiperplano que separa um conjunto de
exemplos positivos de um conjunto de exemplos negativos como representado na Figura
2.13.
Figura 2.13: Linear Support Vector Machine
Recentemente, têm também sido utilizados modelos generativos probabilísticos no
processo de classificação de documentos. Estes métodos descrevem os documentos como
uma mistura de tópicos em que cada tópico consiste numa distribuição probabilística
de palavras. Assim, considerando um documento como uma mistura de tópicos z, a
distribuição de palavras w por documentos d, p(w|d), pode ser decomposta numa distribuição de palavras por tópicos p(w|z) juntamente com uma distribuição de tópicos por
documentos p(z|d) como ilustrado na Figura 2.14.
Figura 2.14: Decomposição da distribuição de palavras por documentos nas distribuições de
palavras por tópicos e de tópicos por documentos [HFS08]
26
Revisão Bibliográfica
Desta forma, cada tópico é formado por um conjunto de termos correlacionados que
o representam de forma coerente e permitem que este possa ser interpretado individualmente. Por outro lado, é natural que um determinado termo possa estar presente em mais
do que um tópico, no entanto caracteriza-os de formas distintas.
Por exemplo, na Figura 2.15 é apresentado um conjunto de tópicos com o termo
“play”. Esta palavra está associada a cada um dos tópicos com probabilidades diferentes
uma vez que depende do sentido e contexto em que é utilizada. Neste exemplo, pode
concluir-se que o termo “play” está mais fortemente associado ao contexto desportivo do
que associado às áreas da música ou do teatro [SGL+ 07].
Figura 2.15: Exemplo de 3 tópicos associados ao termo play [SGL+ 07]
Como já foi referido, estes métodos são modelos generativos para documentos, ou
seja, definem procedimentos probabilísticos através dos quais os documentos podem ser
criados. Por outro lado, através métodos estatísticos é possível inverter o processo generativo e inferir o conjunto de tópicos responsáveis por gerar uma determinada colecção de
documentos (ver Figura 2.16) [SGL+ 07]. Desta forma, e após obtidas as distribuições
responsáveis por gerar uma determinada colecção de documentos, é possível classificar
novas instâncias.
Relativamente aos métodos utilizados para modelação por tópicos, existe uma variedade de técnicas de entre as quais se destaca o Latent Dirichlet Allocation (LDA) [BNJ03].
Esta técnica tem ganho popularidade e tem sido aplicada em alguns estudos em redes sociais para, por exemplo, analisar e classificar as mensagens dos utilizadores e/ou prever
determinados comportamentos. De seguida é apresentado um exemplo da sua utilização
na análise dos conteúdos em blogs sobre política [YCS09].
27
Revisão Bibliográfica
Figura 2.16: Processo generativo e processo de inferência estatística dos tópicos de uma colecção
de documentos [SGL+ 07]
Devido ao impacto social dos blogs em diversas temáticas como a cultura, o ensino, o
jornalismo e a política, estes são um excelente meio de discussão e debate. Desta forma,
os blogs proporcionam um óptimo meio para a análise da linguagem natural envolvida
nos seus conteúdos que os torna alvo de interesse e estudo por parte da comunidade científica. No estudo realizado por Yano, Cohen e Smith [YCS09], o objectivo consistia em
desenvolver métodos para a criação automática de comentários ou mensagens em blogs
e previsão das mensagens que determinado utilizador terá probabilidade de comentar.
Analisando os conteúdos das mensagens que um utilizador comentou no passado e os
conteúdos dos seus comentários é possível determinar as mensagens que um utilizador
tem probabilidade de comentar no futuro e ainda gerar o conteúdo dos seus comentários.
Para tal, foram desenvolvidos dois modelos probabilísticos generativos baseados no modelo Latent Dirichlet Allocation: o LinkLDA e o CommentLDA. Estes modelos, permitem
prever as mensagens que um determinado utilizador irá comentar e ainda determinar o
conteúdo dos seus comentários respectivamente [YCS09].
O modelo generativo denominado pelos autores de LinkLDA pretende determinar uma
distribuição dos utilizadores pelas mensagens do blog permitindo deste modo prever as
mensagens que um utilizador tem probabilidade de comentar. Por outro lado, o CommentLDA pretende modelar as palavras que uma determinada pessoa utiliza nos seus comentários e assim determinar o possível conteúdo dos seus futuros comentários [YCS09].
Desta forma, os métodos desenvolvidos permitem analisar o conteúdo das mensagens
nas redes sociais e identificar padrões de comportamento dos utilizadores. De referir,
que não são extraídas comunidades mas sim identificadas propriedades que permitem
caracterizar parcialmente determinado indivíduo ou conteúdo. Por outro lado, o recon28
Revisão Bibliográfica
hecimento deste tipo de padrões de comportamento e de análise de conteúdos pode eventualmente ajudar no processo de identificação de comunidades com interesses mútuos.
Outro caso de estudo analisado no qual foi utilizada a técnica de modelação por tópicos, consistiu na descrição do quotidiano ou rotinas diárias das pessoas através de uma
combinação probabilística de actividades. No estudo realizado foi utilizado o modelo
LDA com o objectivo de obter grupos de actividades que caracterizam algumas rotinas
pré-definidas [HFS08]. Assim, era pretendido que o modelo captasse aspectos relevantes
na caracterização de determinadas rotinas definidas, como por exemplo, que o tempo de
trabalho no escritório consiste maioritariamente em permanecer sentado e que pode conter
pequenos intervalos de tempo para debates ou idas ao WC; ou ainda que as deslocações
de casa para o trabalho ou do trabalho para casa consistem maioritariamente num período
de tempo em que se está a conduzir, seguido de pequenos intervalos em que se anda a pé
[HFS08].
Apesar do caso de estudo analisado não estar directamente relacionado com as redes
sociais, pretende-se salientar que a modelação por tópicos permite descrever determinadas
acções como uma combinação probabilística de outras. Esta verificação evidencia que
estas técnicas poderão ser úteis, por exemplo, para identificar e descrever padrões de
comportamento ou padrões de interacção entre os utilizadores.
A modelação por tópicos providencia assim uma excelente forma de condensar, descrever e caracterizar os documentos de uma colecção. No entanto, estes métodos frequentemente utilizados na extracção de tópicos, assumem que a colecção de documentos
(corpus) é um conjunto estático e discreto. Porém, na realidade de algumas redes esta suposição não é válida como por exemplo, nos chats em que existem interacções em tempo
real entre diversas pessoas sendo o conteúdo dinâmico [TT04]. Nestas circuntâncias,
poderá ser explorada a definição de janelas temporais, ou seja, a definição de intervalos de tempo em que se consideram as mensagens de cada intervalo como a colecção de
documentos para a extracção dos tópicos envolvidos nas conversações [TT04].
2.3
Sistemas de recomendação
As redes sociais proporcionam diferentes meios de interacção e incentivam a partilha
de informação entre os utilizadores. Frequentemente, muitos dos serviços de partilha de
conteúdos e de troca de mensagens oferecem um conjunto de funcionalidades que permitem ao utilizador recomendar e classificar os conteúdos da rede. Em algumas redes,
a colaboração dos utilizadores na classificação dos conteúdos e criação de conhecimento
sobre os conteúdos desempenha um papel relevante no processo social da rede. Por exemplo, este tipo de funcionalidades está muito presente em redes dedicadas maioritariamente
à divulgação e comercialização de produtos e/ou serviços como é o caso da Amazon3 .
3 http://www.amazon.com/
29
Revisão Bibliográfica
Assim, o processo de classificação de conteúdos por parte dos utilizadores contribui
para a possibilidade de concepção de sistemas de recomendação. De um modo geral, os
sistemas de recomendação têm como objectivo fornecer aos utilizadores novos conteúdos
ou alternativas que são potenciais itens ou entidades do seu interesse. Um dos grandes desafios em sistemas de recomendação consiste em associar os utilizadores com conteúdos
do seu interesse. Desta forma, estes sistemas estão de relacionados com os problemas de
clustering e têm sido alvo de estudo por parte da comunidade científica [AM07].
Em sistemas de recomendação podem distinguir-se essencialmente duas classes de
métodos utilizadas na filtragem dos conteúdos: os métodos de filtragem colaborativa e os
métodos de filtragem cognitiva ou baseados no conteúdo.
No que diz respeito aos métodos de filtragem cognitiva ou baseados no conteúdo, as
recomendações são efectuadas considerando os dados sobre um determinado utilizador
e as informações associadas aos conteúdos da rede [SK09]. Por exemplo, nesta classe
de métodos um livro sobre programação poderia ser recomendado a um estudante de
informática.
Relativamente aos métodos de filtragem colaborativa, as recomendações são realizadas tendo em conta as preferências dos restantes utilizadores da rede. De seguida,
é apresentado um exemplo através do qual se pretende explicar o princípio de funcionamento dos métodos de filtragem colaborativa.
Por exemplo, idealize-se um sistema no qual os utilizadores classificam os conteúdos
da rede numa escala de 1 a 5 e cujas classificações se encontram representadas na Tabela
2.2. No caso de se estar a recomendar novos produtos ao Utilizador4, poderíamos esperar
que através dos métodos de filtragem colaborativa lhe fosse recomendado o Produto6 uma
vez que comparadas as classificações do Utilizador4 com as dos restantes utilizadores,
verifica-se que este classifica os produtos de forma semelhante ao Utilizador2. Por conseguinte, visto que o Utilizador2 atribuiu uma boa classificação ao Produto6 considera-se
que o Utilizador4 também irá atribuir uma boa classificação ao Produto6 e desta forma
esta consistiria numa boa recomendação.
Tabela 2.2: Exemplo de filtragem colaborativa
Utilizador
Utilizador1
Utilizador2
Utilizador3
Utilizador4
Produto1
1
3
5
2
Produto2
5
4
2
4
Produto3
Produto4
2
5
Produto5
4
1
5
2
3
Produto6
5
3
No exemplo apresentado, as classificações e preferências dos utilizadores foram indicadas explicitamente pelos mesmos e consistiam num valor numérico numa escala de 1
a 5. No entanto, as classificações e preferências das pessoas podem também ser identificadas ou observadas de forma implícita como por exemplo, através do número de visu30
Revisão Bibliográfica
alizações de determinado produto ou outro tipo de indícios ou podem ainda consistir em
classificações não númericas, ou seja, classificações por categorias, como por exemplo,
gostar ou não gostar de um determinado produto [SK09].
Nos métodos de filtragem colaborativa são ainda especificadas duas classes: os métodos de filtragem colaborativa baseados em memória (memory-based collaborative filtering) e os métodos de filtragem colaborativa baseados em modelos (model-based collaborative filtering). Na primeira classe de métodos as recomendações são realizadas segundo
medidas de similaridade entre os utilizadores calculadas através da comparação das classificações que estes atribuem aos produtos. Este conjunto de métodos são fáceis de implementar, no entanto, as recomendações podem perder um pouco de credibilidade quando a
informação é escassa, isto é, quando existem muitos itens sem classificação atribuída ou
quando há poucos items comuns entre as preferências dos utilizadores.
Por outro lado, os métodos de filtragem colaborativa baseados em modelos utilizam
algoritmos de aprendizagem automática que, através das classificações e preferências do
utilizador, criam ou aprendem modelos capazes de reconhecer padrões e inferir as preferências dos utilizadores [SK09].
Por exemplo, a Amazon 4 utiliza as técnicas de filtragem colaborativa de forma personalizada para efectuar as recomendações dos produtos aos utilizadores [SK09]. Em vez
de efectuarem recomendações com base nas medidas de similaridade entre utilizadores,
as recomendações são baseadas na semelhança entre os itens. Esta técnica é designada de
item-to-item collaborative filtering. Assim, para cada item que o utilizador comprou ou
avaliou, são procurados os itens similares e é criada uma lista de recomendações com os
itens semelhantes como se pode verificar na Figura 2.17 [LSY03].
Figura 2.17: Exemplo de recomendação de itens semelhantes realizado pela Amazon [LSY03]
4 http://www.amazon.com/
31
Revisão Bibliográfica
Contudo, além de recomendar com base no que um utilizador comprou ou classificou,
é também analisado o seu histórico de pesquisa e são recomendados itens através da
análise do comportamento dos utilizadores que procuraram pelo mesmo item, isto é, são
recomendados itens que outros utilizadores procuraram quando efectuaram a pesquisa do
item comum. Um outro tipo de recomendação realizada pela Amazon, é baseada nos itens
que os outros utilizadores compraram como apresentado na Figura 2.18.
Figura 2.18: Exemplo de sistema de recomendações baseadas no histórico de pesquisas e compras
de todos os utilizadores da rede, utilizado pela Amazon
Concluindo, os métodos de filtragem colaborativa são uma das abordagens mais bem
sucedidas na construção de sistemas de recomendação. No entanto, tal como os métodos de filtragem cognitiva, estes têm limitações evidentes. Enquanto que os métodos de
filtragem colaborativa não utilizam explicitamente as propriedades ou a informação relacionada com o conteúdo dos produtos, os métodos de filtragem cognitiva não consideram
as preferências dos restantes utilizadores da rede.
32
Revisão Bibliográfica
Todavia, existem ainda os métodos híbridos que combinam ambas as abordagens anteriores tentando minimizar as limitações de cada uma. Por exemplo, o site ou base de dados
online IMDb (Internet Movie Database) efectua as recomendações dos filmes através dos
conteúdos que os descrevem os filmes e das preferências e classificações dos utilizadores
[MMN02].
Figura 2.19: Exemplo do sistema de recomendação híbrido implementado pelo IMDb
Resumindo, de forma análoga aos métodos híbridos utilizados em sistemas de recomendação, a utilização de métodos de detecção automática de comunidades em redes e
a análise das redes sociais com base na estrutura das mesmas combinados com os métodos de análise de conteúdos poderão evindenciar aspectos relevantes nas ligações entre os
membros da rede e permitir caracterizar melhor os relacionamentos dos indivíduos.
Por outro lado, a caracterização detalhada das relações permite identificar propriedades
particulares e revelar informações detalhadas sobre os utilizadores que poderão ser consideradas na concepção de sistemas de recomendação actuais. Por exemplo, a identificação de sub-comunidades e caracterização dos conteúdos das comunidades podem ter
implicações práticas nos métodos de recomendação de conteúdos.
33
Revisão Bibliográfica
2.4
Sumário
Neste capítulo foram apresentados os conceitos e descritas algumas técnicas ou métodos que servem de base nesta dissertação. Relativamente ao conteúdo, foi realizada uma
revisão geral de cada tema descrito para ter uma melhor percepção sobre o estado de
evolução e desenvolvimento da temática. Por outro lado, os conhecimentos adquiridos
permitem efectuar uma caracterização detalhada das relações dos indíviduos numa rede
social, identificar os temas mais populares entre as comunidades virtuais, identificar subcomunidades com características particulares e indíviduos influentes nas redes sociais. No
capítulo seguinte, é realizado um estudo exaustivo sobre uma rede social específica com
o intituito de aplicar os conhecimentos adquiridos, confirmar a validade de determinadas
propriedades, e analisar e caracterizar o comportamento dos utilizadores portugueses face
a uma rede social, o Twitter.
34
Capítulo 3
Análise de uma Rede Social de
Micro-blogging: “Twittosfera”
portuguesa
Neste capítulo é efectuada uma análise exaustiva sobre um conjunto de dados específico do Twitter1 , um serviço de micro-blogging bastante popular em todo o mundo
[JSFT07]. A colecção de dados utilizada é, essencialmente, constituída por um conjunto
vasto de utilizadores do Twitter em Portugal e é apresentada na Secção 3.3. Este conjunto de dados foi criado com o intuito de proporcionar uma colecção de dados para
investigações académicas e foi obtida no âmbito de um projecto colaborativo - Sylvester2
- entre a Faculdade de Engenharia da Universidade do Porto e o sapo.pt3 .
De seguida é apresentada uma caracterização detalhada da rede social implícita nesta
colecção de dados e são descritas diversas propriedades verificadas nas redes sociais. Ao
mesmo tempo, é feita uma análise exaustiva das propriedades da rede ao nível da sua
estrutura global e observado o nível de interacção dos seus utilizadores com o objectivo
de compreender e validar os dados fornecidos.
Nas secções 3.1 e 3.2 são descritas de forma sintética as características essenciais
dos serviços de micro-blogging e é apresentado de forma resumida o Twitter, serviço
do qual fazem parte os dados recolhidos. Como referido, na Secção 3.3 é descrita a
colecção de dados disponível e são apresentadas algumas estatísticas sobre a constituição
da amostra utilizada. Além disso, são também verificados comportamentos individuais
dos utilizadores e os períodos de utilização do Twitter conforme se encontra descrito na
Secção 3.4. Na Secção 3.5 é analisada a interacção dos utilizadores através do fluxo
de comunicação e é quantificada a participação dos utilizadores no que diz respeito ao
volume de respostas enviadas e recebidas.
1 http://www.twitter.com
2 Projecto
apresentado em http://robinson.fe.up.pt/ projects/Sylvester
3 http://labs.sapo.pt/up/
35
Análise de uma Rede Social de Micro-blogging: “Twittosfera” portuguesa
Relativamente à estrutura global da rede social apresentada na Secção 3.6, é inspeccionada a existência de grupos fortemente coesos e a presença de comunidades cuja densidade de ligações é mais preponderante.
Para finalizar, são demonstradas as propriedades de auto-similaridade e invariância
temporal da estrutura da rede na Secção 3.7, de forma a garantir que os resultados não
dependem radicalmente das amostras recolhidas.
3.1
Micro-blogging
O micro-blogging é um meio de comunicação social que permite aos utilizadores interagirem uns com os outros através da difusão de mensagens curtas (em tempo real).
As mensagens são divulgadas publicamente num serviço disponível na Web e poderão
ser vistas por qualquer utilizador do serviço ou apenas por um grupo restrito de pessoas
definido pelo autor da mensagem. No que diz respeito às características principais deste
tipo de serviços, pode destacar-se um princípio fundamental: as mensagens são curtas e
sintéticas, geralmente com um limite máximo entre 140 a 200 caracteres.
Por conseguinte, a natureza concisa das mensagens permite que estas sejam enviadas
e recebidas por, praticamente, qualquer dispositivo ligado à Internet. Além disso, esta
natureza “micro” faz com que as mensagens sejam rápidas de escrever e facilmente lidas
pelos utilizadores.
Assim, os serviços de micro-blogging tiram partido da curiosidade do utilizador, capacidade natural e inata do ser humano, bem como da necessidade humana de comunicar.
A simplicidade do micro-blogging é uma das razões pelas quais este tipo de serviços é
popular e utilizado por inúmeras pessoas com finalidades muito diversas como por exemplo: difusão/publicação de notícias, marketing e publicidade, divulgação de eventos,
conversação, diário pessoal, entre outros.
Outro aspecto importante, e talvez o mais importante para esta dissertação, é que, tal
como nas redes sociais, também nos serviços de micro-blogging é possível observar as
relações estabelecidas pelos utilizadores quer sejam estabelecidas de forma implícita ou
de forma explícita.
O carácter dinâmico, informal e espontâneo inerente a este tipo de serviços, e que incentivam a interacção, torna os serviços de micro-blogging interessantes para o estudo das
características e fenómenos presentes em redes de comunicação e redes sociais pois proporcionam uma oportunidade para analisar diferentes perfis de interacção dos utilizadores
bem como, os conteúdos emergentes nas comunidades.
Actualmente, existem diversos serviços exclusivamente dedicados ao micro-blogging
36
Análise de uma Rede Social de Micro-blogging: “Twittosfera” portuguesa
como por exemplo, o Twitter4 , o Jaiku5 , o Tumblr6 ou o Pownce7 . Porém, o conceito tem
sido adoptado por inúmeras redes sociais através de funcionalidades como “actualizações
de estado” e embora a maioria dos serviços trate de mensagens curtas e directas em formato de texto, existem serviços de micro-blogging que permitem também a publicação
de conteúdos de vídeo ou de áudio.
Na secção seguinte são descritos os conceitos básicos do Twitter, funcionalidades do
serviço e diferentes tipos de interacção possíveis, com o objectivo de perceber a essência
dos dados recolhidos e a rede social analisada nesta dissertação.
3.2
Twitter
O Twitter é um serviço de micro-blogging, fundado em Março de 2006, que permite
às pessoas partilharem mensagens curtas em formato de texto e receberem informações
actualizadas sobre os restantes utilizadores do serviço [BGL10].
Na realidade, o Twitter baseia-se num conceito muito simples, isto é, cada utilizador
deve aderir ao serviço predisposto a responder a uma simples pergunta: “O que estás a
fazer?”. A ideia consiste em responder à mesma pergunta diversas vezes durante o dia
criando assim uma espécie de “diário”. Desta forma, o Twitter pode ser descrito como
uma rede social na qual os membros de uma comunidade partilham as suas actividades
do quotidiano. As mensagens devem ser curtas e directas, e cada mensagem implica uma
única ideia.
No Twitter, as mensagens têm um limite máximo de 140 caracteres e são denominadas
por tweets. Curiosamente, este limite foi estabelecido pelo simples facto do sistema ter
sido desenvolvido para também poder ser utilizado através de um qualquer dispositivo
móvel por intermédio do sistema de SMS [BGL10, HSS10].
O conceito parece relativamente simples e combina as características do micro-blogging
com características de uma rede social uma vez que o carácter pessoal das mensagens faz
com que as pessoas se sintam relacionadas e parte integrante da vida umas das outras.
Contudo, ainda que o Twitter seja considerado um serviço de micro-blogging para conversação com um carácter de rede social, contrariamente à maioria das redes sociais as
relações não são obrigatoriamente mútuas ou recíprocas, isto é, um utilizador pode subscrever as mensagens enviadas por outro sem que o contrário se verifique.
No que diz respeito aos utilizadores com os quais alguém se relaciona, os utilizadores
que subscrevem e recebem as mensagens de um outro são denominadas por followers
desse utilizador. Por outro lado, as pessoas a que um determinado utilizador subscreve e
4 www.twitter.com
5 www.jaiku.com
6 www.tumblr.com
7 www.pownce.com
37
Análise de uma Rede Social de Micro-blogging: “Twittosfera” portuguesa
de quem recebem informação actualizada, ou seja, conjunto de pessoas que um determinado utilizador “segue” (following) são designadas por friends.
Relativamente às mensagens, um dos aspectos fundamentais além do facto de serem
curtas, está relacionado com a terminologia ou sintaxe presente nas mesmas. Por outras
palavras, as mensagens podem conter determinadas sequências de caracteres que têm
significado próprio. É o caso do ’@’ seguido do nome de um utilizador que é utilizado
para mencionar ou responder a uma pessoa, o caso do carácter ’#’ seguido de uma palavra
para a representação de hashtags, ou a combinação de caracteres ’RT’ específica para os
retweets. De seguida, é apresentada a terminologia e a semântica associada às sequências
de caracteres listadas e que representam respectivamente as replies ou mentions, hashtags
e retweets.
3.2.1
@replies e/ou @mentions
No Twitter todas as mensagens são públicas, o que significa que qualquer um pode
lê-las. No entanto, os utilizadores têm a possibilidade de indicar que a sua mensagem
se destina a alguém em particular. Para isso, basta incluir na mensagem o nome do utilizador, precedido pelo carácter ’@’ para indicar que a mensagem é especificamente destinada a aquele utilizador particular. Desta forma, é possível serem estabelecidos diálogos
tornando assim o fluxo de informação mais claro e perceptível. Apesar de destinadas a
utilizadores particulares, estas mensagens continuam públicas e serão também visíveis
por toda a comunidade.
Contudo, nem todas as respostas são definitivamente @replies uma vez que o utilizador pode, nas suas mensagens, simplesmente mencionar o nome de outro utilizador.
Assim sendo, pode ser necessário distinguir-se entre as mensagens que são para alguém e
aquelas que são sobre alguém. O Twitter faz uma distinção técnica entre as @replies e as
@mentions. Apenas nos casos em que os tweets começam com o símbolo ’@’ seguido
do nome do utilizador, são considerados respostas (@replies) [HSS10].
3.2.2
#hashtags
As hashtags são palavras-chave (keywords) curtas que são utilizadas para facilitar a
pesquisa de tweets. A presença de uma hashtag numa mensagem permite associar e
agrupar o tweet com outros que se referem ao mesmo acontecimento, evento, entidade
ou objecto.
No Twitter as hashtags são identificadas pelo símbolo ’#’ seguido de uma palavra
que geralmente descreve um evento, um interesse, tópico, assunto. Desta forma, é possível obter o conjunto de mensagens que discutem determinado tema ou evento e estar a par sobre todos os acontecimentos em torno de um determinado assunto. Assim,
caso o utilizador pretenda associar a sua mensagem a um determinado assunto ou tema
38
Análise de uma Rede Social de Micro-blogging: “Twittosfera” portuguesa
ou outras categorias, deve colocar uma hashtag característica desse tema. Por exemplo, nas mensagens alusivas ao Campeonato do Mundo de Futebol FIFA de 2010 podem
estar associadas diferentes hashtags como por exemplo: #worldcup, #FIFA, #Portugal,
#Mundial2010, entre outras definidas pelos utilizadores.
As hashtags são bastante úteis essencialmente para a pesquisa pois permitem agrupar
os tweets e também adicionar meta-informação às mensagens, por isso, recomenda-se que
não se faça um uso abusivo e inadequado das mesmas uma vez que assim a utilidade das
hashtags ficariam diluídas.
3.2.3
RT retweets
A partilha de mensagens é uma das partes mais importantes do Twitter, e para além
de o utilizador partilhar as suas mensagens tem também a possibilidade de partilhar as
mensagens que leu mas que foram enviadas por outros utilizadores [HSS10].
O retweet é um mecanismo que permite aos utilizadores divulgarem mensagens enviadas por outros utilizadores dando crédito ao autor original. Pode considerar-se uma espécie de reencaminhamento de mensagens ou referência a mensagens, tornando-as visíveis
a pessoas que, eventualmente, não as teriam visto de outra forma. Por exemplo, se um
utilizador lê um tweet interessante que foi publicado por uma das pessoas que ele segue
(friends) e pretende torná-la visível para as pessoas que o seguem (followers), pode fazer
retweet da mensagem através dos caracteres ’RT’ seguido do carácter ’@’ e do nome do
utilizador que enviou a mensagem, seguido de um espaço e da mensagem correspondente.
3.2.4
Interface de interacção com o serviço
Descrevendo resumidamente a interface de interacção com o serviço, o Twitter apresenta uma interface Web bastante simples como se pode ver na Figura 3.1. Cada utilizador
contém uma página pessoal na qual encontra uma caixa de texto onde pode escrever os
seus tweets. Na mesma página encontra uma lista de mensagens ordenadas cronologicamente, que consistem nas mensagens enviadas pelas pessoas ou entidades que o utilizador
segue (friends). No entanto, além da interface Web o Twitter disponibiliza uma API ou
conjunto de bibliotecas que permite aos utilizadores desenvolverem aplicações próprias
para comunicarem com o serviço.
Além desta página, o utilizador têm acesso a uma página de configuração onde pode
alterar os seus dados pessoais como por exemplo o nome, e-mail ou localização geográfica. Estes dados disponibilizados pelos utilizadores podem ser bastantes úteis para estudos em redes sociais. Por exemplo, um dos estudos mais relevantes sobre o Twitter, além
de apresentar a taxa de crescimento do serviço apresenta também a distribuição geográfica dos utilizadores através mapeamento das suas informações de perfil em coordenadas
geográficas [JSFT07].
39
Análise de uma Rede Social de Micro-blogging: “Twittosfera” portuguesa
Figura 3.1: Página pessoal do utilizador no Twitter
3.2.5
Redes explícitas e implícitas no Twitter
No Twitter, os utilizadores podem estar relacionados de diversas formas, quer de forma
explícita sob a forma de amigos (friends) e/ou seguidores (followers), quer de forma implícita através de @replies, @mentions, #hashtags e/ou ‘RT’ retweets. O conteúdo estruturado do serviço permite estabelecer diversos tipos de relações entre os utilizadores
e assim definir redes com significados distintos que são dependentes das motivações e
finalidades de cada estudo [HSS10]. De seguida, são apresentadas algumas das redes que
se podem extrair a partir da informação presente no Twitter.
3.2.5.1
Redes Explícitas - Redes de amigos (friends) e/ou seguidores (followers)
Através dos conceitos de amigo (friend) e seguidor (follower) podem ser definidas
redes com propriedades e significados distintos. Por exemplo, uma rede simples tratarse-ia da rede não dirigida na qual dois utilizadores estão ligados se um deles é amigo
ou seguidor do outro. No entanto, uma vez que as relações não são necessariamente
recíprocas, podem ser definidas duas redes distintas (rede de seguidores e rede de amigos)
ou mais explicitamente uma rede dirigida. Por exemplo, num dos estudos já anteriormente
40
Análise de uma Rede Social de Micro-blogging: “Twittosfera” portuguesa
referidos na subsecção 3.2.4 [JSFT07], os autores determinam o grau de correlação
entre o número de seguidores e o número de amigos que os utilizadores têm. Os autores,
segmentam o seu estudo por continentes, isto é, para cada continente é extraída uma rede
social considerando apenas o subconjunto de utilizadores em que ambos pertencem ao
mesmo continente. No final, comparam os resultados obtidos e concluem que no geral,
os utilizadores da Europa e da Ásia contêm uma maior reciprocidade nas suas relações do
que os utilizadores do continente Norte-Americano.
3.2.5.2
Redes Implícitas - Redes de mensagens (@replies, @mentions, RT ou #hashtags)
Como já foi referido, além das relações explícitas estabelecidas através das ligações
de amigo (friend) ou seguidor (follower), é possível definir outras redes através da análise
do fluxo de informação presente no Twitter. Por exemplo, através do fluxo de respostas é
possível definir uma rede em que os utilizadores estão relacionados caso tenham recebido
ou enviado uma resposta de/para outro utilizador.
De certa forma, o fluxo de respostas pode ser um melhor indicador das relações sociais do que as simples ligações de amizade ou seguidor. Por exemplo, uma das formas
mais utilizadas para medir quão significativa é uma ligação social consiste em medir a
frequência de interacção entre as duas pessoas envolvidas. Este factor é utilizado em estudos realizados sobre as redes sociais a fim de distinguir o quão forte ou fraca é a ligação
entre os utilizadores [GK09].
Um outro estudo [WBS+ 09], realizado sobre a rede social Facebook, revela que a
actividade de interacção é significativamente desviada para uma pequena parcela de relações sociais de cada utilizador. Desta forma, esta constatação demonstra que as diferentes relações sociais não têm um valor igualmente significativo para o utilizador. Estes
evidências sugerem que as aplicações sociais devem ser desenvolvidas considerando a
interacção do utilizador, de modo que reflictam a actividade real da rede em vez de uma
simples estrutura de ligações sociais.
Além do fluxo de respostas, podem também ser utilizadas as hashtags para construir
redes cujos utilizadores falam sobre um mesmo assunto e daí extrair as suas comunidades,
ou ainda, a partir dos retweets detectar a evolução e expansão de mensagens ou determinados comportamentos característicos dos utilizadores.
Recentemente, Boyd et al [BGL10] analisaram os aspectos conversacionais dos retweets.
Para os autores, o retweet não se trata apenas de um acto de conversação mas de uma
forma de difundir mensagens e de incluir mais pessoas nas conversas, convidando-os a
participar indirectamente. Destacam ainda que os utilizadores do Twitter têm diferentes
formas de encarar os retweets e diferentes maneiras de pensar em relação à forma como
este mecanismo deve ser utilizado. Assim, nesse estudo, os autores têm como objectivo
principal descrever e mapear as diferentes convenções e práticas no acto de retweet. Entre
41
Análise de uma Rede Social de Micro-blogging: “Twittosfera” portuguesa
o conjunto de conclusões retiradas, descobriram por exemplo que mais de 9% de todos os
retweets incluem uma referência a quem os envia. Por outras palavras, quando o utilizador
A faz retweet de uma mensagem do utilizador B, a mensagem contém uma referência ao
utilizador A. Esta prática é um pouco egocêntrica, e como tal, os autores denominaram
estes retweets por “ego retweets”. Outro aspecto curioso detectado por Boyd et al, está
relacionado com o facto de que 11% dos retweets contêm algum texto incluído antes do
RT e que parecem ser maioritariamente comentários sobre o conteúdo do tweet. Estes
são apenas alguns exemplos de estudos sobre como as redes sociais podem revelar informações úteis e conhecimento que pode ser utilizado em diversas áreas de aplicação, como
o marketing e a publicidade ou até no desenvolvimento de novos métodos de pesquisa.
Como se pode verificar, existem muitas possibilidades e casos de estudo sobre análise
de redes sociais. Nesta dissertação, foi efectuada uma análise focada na rede de respostas
presentes no conjunto de dados recolhido com o intuito de descrever as propriedades de
uma rede de comunicação e analisar diferentes perfis de interacção dos utilizadores. Na
secção seguinte, é descrito de forma detalhada o conjunto de dados utilizado nesta dissertação, bem como a rede criada que serve de suporte para a caracterização das relações
entre os utilizadores, das comunidades e estudo das suas propriedades gerais da rede e do
serviço de micro-blogging.
3.3
Descrição da Colecção de Dados
O conjunto de dados utilizado nesta dissertação foi disponibilizado pelo sapo.pt8 no
âmbito de um projecto colaborativo com a FEUP9 . A recolha dos dados foi realizada
recorrendo a um sistema de detecção das mensagens enviadas pelos utilizadores do Twitter em Portugal. Desta forma, sabe-se a priori que a colecção é constituída por um conjunto vasto de tweets enviados pelos utilizadores do Twitter em Portugal, no entanto, não
foi disponibilizada mais nenhuma informação referente ao processo de recolha dos dados.
Ademais, não há garantias de que tenha sido efectuada uma recolha exaustiva uma vez
que foram detectadas falhas como se pode constatar através da Figura 3.2, e como tal,
não se sabe quão representativa da população portuguesa é esta colecção.
Além disso, foram também detectadas algumas inconsistências nos dados e como tal
foi necessário proceder ao filtro e limpeza dos mesmos como por exemplo, remover registos replicados e as mensagens dos utilizadores sobre os quais apenas se tem informação
parcial. O tratamento dos dados é uma das fases mais importantes do processo de extracção de conhecimento pois consiste na fase de compreensão do domínio do problema.
8 http://labs.sapo.pt/up/
9 Faculdade
de Engenharia da Universidade do Porto
42
Análise de uma Rede Social de Micro-blogging: “Twittosfera” portuguesa
Figura 3.2: Distribuição diária de tweets presentes na colecção de dados utilizada
Ademais, tratando-se de bases de dados dinâmicas e incompletas, o tratamento de situações irregulares ou simplesmente a alteração do formato dos dados para um outro mais
apropriado consiste numa tarefa árdua e morosa.
Ainda relativamente ao processo de recolha de dados, é de salientar que este se trata de
um processo dinâmico e contínuo e que por isso o volume de dados aumenta de dia para
dia. Contudo, as estatísticas globais apresentadas de seguida são referentes ao conjunto
de dados disponível no dia 16 de Maio de 2010 que corresponde à data em que foram iniciados os últimos estudos que se encontrarão descritos no Capítulo 4. A tabela seguinte,
Tabela 3.1, apresenta de forma sucinta as características da colecção disponibilizada.
Tabela 3.1: Descrição do conjunto de dados recolhido
Data do primeiro tweet
Data do último tweet
Número total de utilizadores da colecção
Número total de tweets da colecção
Número total de tweets da amostra B (sample B)
Número total de tweets da amostra C (sample C)
2010-01-12 14:01:00
2010-05-16 23:59:57
150.568 utilizadores
2.530.767 tweets
879.607 tweets
612.556 tweets
Numa primeira fase, iniciada no dia 20 de Abril de 2010 e que se prolongou durante
as 4 semanas seguintes, foi realizada uma análise através da obtenção de estatísticas e observação de propriedades e fenómenos próprios das redes sociais, com o intuito de validar
os conteúdos da colecção de dados utilizada. Contudo, devido ao processo de recolha não
exaustivo, às inconsistências detectadas e às descontinuidades presentes nesta colecção,
43
Análise de uma Rede Social de Micro-blogging: “Twittosfera” portuguesa
foi seleccionada uma amostra num intervalo contínuo e “estável” com o objectivo de obter
resultados mais representativos da realidade do Twitter em Portugal. O intervalo seleccionado vai desde 17 de Março de 2010 até ao dia 20 de Abril de 2010 inclusive, como se
encontra representado na Figura 3.2. Este intervalo foi denominado de amostra B para se
tornar mais clara a sua referência ao longo do texto e foi extraída para a análise topológica da rede (Sample B – Topological Analysis) . Por outro lado, é importante referir que
apesar de estável e sem replicação de dados, verificou-se a ausência de informação sobre
alguns dos utilizadores presentes nesta amostra (Sample B).
Do total dos 879.607 tweets recolhidos para o intervalo de tempo correspondente à
amostra B (Sample B), verificou-se que 211.294 foram enviados para utilizadores dos
quais não há qualquer tipo de informação sobre as suas mensagens. Esta ausência de dados é devida a factores não controlados nesta dissertação, tais como: utilizadores com perfis privados ou falhas na recolha e armazenamento dos dados. Assim sendo, este conjunto
de mensagens foi descartado dos estudos seguintes dado que não existe informação sobre
os utilizadores que as receberam. Apesar das limitações encontradas devido à recolha dos
dados, é expectável que os resultados obtidos sejam significativos uma vez que foi mantida uma porção elevada dos dados recolhidos, que corresponde a 75,98% das mensagens
inicialmente recolhidas. Assim, a amostra analisada nas secções seguintes é constituída
por 633.998 tweets enviados por 37.592 utilizadores. Deste conjunto de dados, verifica-se
que a maioria dos tweets não são respostas (@replies) o que indica que a interacção no
Twitter se deve a uma quantidade reduzida do total de mensagens enviadas.
Como se pode ver pela Figura 3.3, apenas cerca de 12% das mensagens são respostas.
Além disso, no que diz respeito à quantidade de utilizadores, verifica-se que a maioria
não interage com os restantes utilizadores do serviço, isto é, não recebem nem enviam respostas. Neste caso em particular, e conforme é representado na Figura 3.4, 15,71% dos
utilizadores receberam pelo menos uma resposta e cerca de 16% enviaram pelo menos
uma resposta a outro utilizador. Ademais, apesar de não se encontrar representado na
Figura 3.4, existe uma enorme sobreposição entre os utilizadores que não receberam
nenhuma resposta e aqueles que nunca responderam a ninguém. Neste caso, foram contabilizados e aproximadamente 76,76% dos utilizadores (28.854 utilizadores) da amostra
não interagem10 com os outros utilizadores do serviço e são denominados de singleton
users.
10 Estabelecer um acto de comunicação com outro utilizador, isto é, enviar ou receber pelo menos uma resposta
(@reply)
44
Análise de uma Rede Social de Micro-blogging: “Twittosfera” portuguesa
Figura 3.3: Percentagem de respostas da amostra B
Figura 3.4: Percentagem de utilizadores interactivos da amostra B
Estes resultados são indicadores importantes da actividade produzida no Twitter pelos
utilizadores de Portugal. No geral, os resultados assemelham-se ao que acontece noutras
redes sociais, como por exemplo no Facebook [VMCG09] ou no Flickr [MMG+ 07].
De acordo com os resultados obtidos, verifica-se que a interacção nas redes sociais é
ocasionada por um conjunto reduzido de utilizadores quando comparado com o total dos
utilizadores do serviço. De notar ainda que, a inexistência de utilizadores que apenas
45
Análise de uma Rede Social de Micro-blogging: “Twittosfera” portuguesa
recebem respostas é um factor representativo do nível de correcção da amostra uma vez
que foram descartados os utilizadores sobre os quais não existia informação disponível.
Após apresentado o conjunto de dados e quantificado o volume de mensagens e utilizadores presentes nesta colecção, são apresentadas algumas características referentes ao
comportamento individual dos utilizadores.
3.4
Comportamento Individual dos Utilizadores
Um dos aspectos interessantes está relacionado com os hábitos e frequência de utilização do Twitter por parte dos utilizadores de Portugal. De seguida, apresenta-se o número
de tweets enviados por dia da semana na tentativa de revelar tendências na utilização
diária deste serviço de micro-blogging. Observando a distribuição apresentada na Figura
3.5, verifica-se que o período de fim-de-semana é aquele em que os utilizadores enviam
menos tweets destacando-se o Sábado como o dia em que os utilizadores em Portugal
utilizam menos o Twitter.
Figura 3.5: Distribuição do número de tweets e do número de utilizadores por dia da semana
De seguida, apresenta-se a distribuição de tweets enviados por cada hora do dia, a fim
de medir a propensão que os utilizadores têm para enviar tweets a uma determinada hora.
Conforme demonstra a Figura 3.6, os utilizadores enviam mais tweets à noite, após a
hora do jantar, apresentando indícios de que as pessoas esperam por um período de tempo
livre para se dedicarem às redes sociais.
46
Análise de uma Rede Social de Micro-blogging: “Twittosfera” portuguesa
Além disso, é possível observar que o período de menor utilização acontece de madrugada entre aproximadamente as 02h00 e as 08h00 da manhã. Este resultado não é surpreendente, uma vez que este é o período natural de repouso para a maioria da população
portuguesa. Ao mesmo tempo, é apresentada a distribuição de utilizadores por cada hora
do dia. Como seria de esperar, quantos mais tweets são enviados, maior é a quantidade de
utilizadores presentes na rede e, naturalmente, ambas as distribuições apresentam comportamentos idênticos apesar das ordens de magnitude diferentes.
Figura 3.6: Distribuição do número de tweets e do número de utilizadores por hora do dia
Além da distribuição diária e horária foram analisados os comportamentos individuais
dos 5 utilizadores que mais tweets enviaram durante todo o período de tempo analisado.
Observando a Figura 3.7, verifica-se que existem comportamentos diferentes entre os
utilizadores. Como se pode constatar, existem utilizadores que enviam tweets maioritariamente localizados num ou dois períodos do dia enquanto que outros enviam mensagens
de forma mais regular ao longo de todas as horas do dia.
Analisando a Figura 3.7 com um pouco mais de atenção, e tendo em conta o período
de repouso natural em Portugal apresentado na Figura 3.6, denota-se a existência de
distribuições aproximadamente regulares ao longo do tempo como é o caso dos dois utilizadores com mais mensagens enviadas. Estas distribuições apresentam um comportamento peculiar, são de certa forma regulares e assim sendo, foi levantada a hipótese de
que a distribuição pode ser utilizada para identificar utilizadores particulares como por
exemplo, utilizadores bot11 ou spammers12 .
11 Diminutivo de robot, utilitário concebido para simular acções humanas.
automático.
12 Utilizadores que enviam, em massa, mensagens não solicitadas.
47
Neste caso, utilizador que publica conteúdo
Análise de uma Rede Social de Micro-blogging: “Twittosfera” portuguesa
Figura 3.7: Distribuição do número de tweets por hora do dia dos 5 utilizadores com mais participação no Twitter
De facto, e após um processo de pesquisa manual no Twitter, descobriu-se que as 4
primeiras distribuições pertencem a utilizadores referentes a jornais diários, a um fórum
de discussão no qual são publicadas notícias e ainda a uma agência de viagens que utiliza
o Twitter para divulgação de ofertas e promoções.
De salientar que, apenas a última distribuição pertence a um utilizador com um carácter social e uma componente mais pessoal, não utilizando o Twitter para fins comerciais.
Trata-se de um utilizador “comum” que faz uso do serviço para comunicar com os seus
amigos. Analisando ao pormenor, este é também o utilizador que apresenta uma distribuição mais semelhante e ajustada à que é apresentada na Figura 3.6.
3.5
Análise da interacção entre os utilizadores
Após ter sido efectuada uma caracterização do conjunto de dados e da actividade individual dos utilizadores e se ter verificado que apenas 23,34% das pessoas comunicam
entre si através de actos de resposta, foi seleccionado este conjunto (8736 utilizadores)
a fim de caracterizar a população “interactiva” do Twitter em Portugal. De acordo com
os resultados obtidos num estudo realizado sobre a rede social Facebook [GWH07],
confirma-se que as pessoas apenas comunicam com um grupo reduzido dos seus amigos. Conforme demonstrado no estudo, os utilizadores apenas trocam mensagens com
um número reduzido de pessoas apesar de terem um grande número declarado de amigos.
Outro exemplo destas evidências, embora um pouco informal, diz respeito aos inquéritos
48
Análise de uma Rede Social de Micro-blogging: “Twittosfera” portuguesa
realizados às pessoas sobre a quantidade de contactos armazenados no seu telemóvel e o
número de contactos com quem realmente comunicam [HRW08]. Verifica-se que apenas uma pequena percentagem dos contactos armazenados no telemóvel são realmente
contactados pelas pessoas.
Apesar de, na colecção utilizada nesta dissertação, não estar disponível a informação
relativa aos seguidores (followers) e amigos (friends), existem evidências de que à semelhança do que acontece nos exemplos anteriormente referidos, também no Twitter os utilizadores apenas comunicam com um grupo muito restrito dos seus seguidores e amigos.
De facto, estas evidências são demonstradas num estudo realizado por Huberman et al
[HRW08].
Todas estas observações sugerem que as ligações estabelecidas são de naturezas distintas e que os utilizadores seleccionam as ligações que realmente importam para dedicar a
sua atenção. Por outro lado, sugerem também que a construção de uma rede baseada nas
comunicações efectivamente estabelecidas pelo utilizador constitui um indicador social
melhor do que a rede construída a partir da lista de todos os amigos ou conhecidos.
Assim sendo, nesta secção foi construída uma rede baseada nos actos de comunicação
entre os utilizadores e foram analisadas as suas propriedades básicas. A rede resultante,
uma rede implícita construída a partir das respostas (@replies), é representada através
de um grafo dirigido G = (V, E). Cada vértice v ∈ V representa um utilizador e cada
aresta <v1 ,v2 > ∈ E tem associada um peso w12 que indica o número de comunicações
entre os utilizadores v1 e v2 que é diferente da aresta <v2 ,v1 >. Apesar de se tratar de um
grafo dirigido, numa primeira fase, começou-se por contabilizar o número de utilizadores
distintos com quem cada utilizador interage ou que interagem com ele, isto é, foi feita uma
análise sobre os actos de comunicação entre os utilizadores (correspondente à análise de
um grafo não dirigido).
Através da análise da Figura 3.8 constata-se que a maioria dos utilizadores estabelece
contacto com poucas pessoas e que existe uma quantidade pequena de utilizadores que
estabelece no mínimo um acto de comunicação com diversos utilizadores. Neste caso,
pode observar-se a existência de um utilizador com 209 ligações estabelecidas no período
das 5 semanas analisadas.
De acordo com o referido no Capítulo 2, existem muitas redes, incluindo redes sociais,
que pertencem à classe das denominadas scale-free networks e que são caracterizadas por
apresentarem este tipo distribuições particulares no grau de centralidade dos seus nós power-law distributions. Neste caso, também a rede implícita nesta colecção de dados
apresenta este tipo de distribuições muito característica.
49
Análise de uma Rede Social de Micro-blogging: “Twittosfera” portuguesa
Figura 3.8: Distribuição do grau de centralidade dos utilizadores da rede de respostas construída a
partir da amostra B
De seguida, foi também observado um comportamento igualmente consistente com
uma power-law nas distribuições do grau de entrada (in-degree) e no grau de saída de
cada vértice (out-degree), conforme é representado na Figura 3.9. Estas distribuições
correspondem respectivamente ao número de pessoas que comunicam com o utilizador e
o número distinto de utilizadores a quem ele responde. Em média, cada pessoa estabelece
contacto com 3 ou 4 utilizadores diferentes.
Mais uma vez, tal como em muitas redes de comunicação e redes sociais, também o
Twitter apresenta as denominadas power-law distributions no que diz respeito ao grau de
centralidade dos seus vértices. Assim, estes valores reflectem a existência de alguns utilizadores com um grau muito elevado, que desempenham o papel de hubs13 , e muitos nós
com um grau de centralidade baixo uma característica não encontrada em redes aleatórias
[ALPH01].
13 Utilizadores com muitas ligações que desempenham um papel fundamental na rede pois interligam muitos dos
utilizadores da rede
50
Análise de uma Rede Social de Micro-blogging: “Twittosfera” portuguesa
Figura 3.9: Distribuição do número distinto de utilizadores com quem um utilizador comunica e
do número distinto de utilizadores que comunicam com ele
Na realidade nas redes aleatórias é esperado que a maioria dos vértices tenha um grau
de centralidade próximo de um valor médio mais baixo do que as redes do tipo scalefree. Como tal, de forma a contrastar estes conceitos com as distribuições apresentadas
anteriormente, foi construída uma rede completamente aleatória com o mesmo número
de utilizadores e ligações presentes na rede de respostas utilizada, e foi determinada a
distribuição do grau de centralidade dos seus nós. A Figura 3.10 evidencia a teoria
enunciada anteriormente e reforça os conceitos apresentados na literatura e demonstrados
pela Figura 2.8 do Capítulo 2.
Além do mais, em quase todos os aspectos, as propriedades do gráfico aleatório, não
coincidem com as propriedades das redes no mundo real. Por exemplo, e novamente
como enunciado na revisão da literatura, as redes aleatórias têm um valor bastante baixo
para o valor médio do clustering coefficient que é dado por, C = n1 ∑ni=1 Ci . Este valor reflecte a probabilidade p de dois vértices estarem ligados independentemente de terem uma
ligação comum ou não e nas redes aleatórias verifica-se que C = p tende para 0 quando o
número de vértices (n) da rede é muito elevado [New03]. Além disso, quando comparado
com o valor obtido para as redes do tipo scale-free, verifica-se que o valor médio do clustering coefficient das redes aleatórias é significativamente menor. Sabendo a priori destes
resultados, foi calculado o valor médio do clustering coefficient para a rede implícita presente nesta colecção (representado por Cs f ) e para a rede aleatória com o mesmo número
de utilizadores e ligações (representado Crn ). Os valores obtidos apresentados na Tabela
3.2, estão de acordo com os conceitos anteriormente enunciados, verificando-se que Cs f
é significativamente maior do que Crn (Cs f > 171 Crn ).
51
Análise de uma Rede Social de Micro-blogging: “Twittosfera” portuguesa
Figura 3.10: Comparação da distribuição do grau de centralidade dos vértices da rede obtida a
partir da amostra B e de uma rede aleatória com o mesmo número de utilizadores e ligações
Tabela 3.2: Comparação do clustering coefficient da rede presente na colecção de dados utilizada
e uma rede aleatória com o mesmo número de utilizadores e ligações
Rede
Rede de respostas implícita na colecção de dados
Rede aleatória
3.5.1
Clustering coefficient (C)
Cs f = 0.0856
Crn = 0.0005
Frequência de interacção e participação dos utilizadores
Considerando a distribuição dos pesos nas arestas que simbolizam a frequência de interacção entre pares de utilizadores é possível verificar que, para além de estabelecerem
laços com um conjunto reduzido de pessoas, a maioria das ligações devem-se a comunicações esporádicas como sugere a Figura 3.11. De salientar que esta distribuição (Figura
3.11), tem em conta o número total de actos de comunicação em que um utilizador está
envolvido, isto é, para um utilizador são contabilizadas as mensagens em que ele responde
a alguém (outdegree) e as mensagens que lhe são dirigidas (indegree). Assim, para um
determinado utilizador v1 o número de comunicações é dado pela soma dos pesos w12 ,
correspondente às arestas <v1 , v2 >, e w21 correspondente às arestas <v2 , v1 >, onde v2 representa um qualquer utilizador a quem v1 enviou uma mensagem ou de quem v1 recebeu
uma resposta.
Por outro lado, analisando o fluxo de comunicação entre os utilizadores, verifica-se
que as pessoas enviaram aproximadamente o mesmo número de respostas que receberam.
52
Análise de uma Rede Social de Micro-blogging: “Twittosfera” portuguesa
A Figura 3.12 apresenta o número de utilizadores agregados pelo número de respostas
que enviam e pelo número de respostas que recebem.
Figura 3.11: Distribuição da frequência de interacção entre pares de utilizadores
Figura 3.12: Distribuição do número de respostas recebidas (à esquerda) e do número de respostas
enviadas (à direita) pelos utilizadores do Twitter em Portugal
53
Análise de uma Rede Social de Micro-blogging: “Twittosfera” portuguesa
3.5.2
Correlação entre o número de respostas enviadas e número de respostas recebidas
Estudos anteriores indicam que diversas variáveis e fenómenos nas redes sociais estão
correlacionados. Alguns destes exemplos são:
• o número de mensagens que um determinado utilizador envia e da quantidade de
pessoas que o “segue” [HRW08];
• a quantidade de pessoas que seguem um determinado utilizador e o número de utilizadores com ele comunica [HRW08] [JSFT07];
• o número de pessoas que um utilizador segue e o número de pessoas que o seguem
a ele [JSFT07];
• o número de mensagens enviadas e/ou recebidas por uma pessoa e o número de
contactos que a pessoa tem armazenado no seu telémovel [XTT+ 05].
Nesta secção, é medida a correlação entre o número de respostas enviadas e o número
de respostas recebidas por cada utilizador. Através de um gráfico de dispersão, conforme
mostrado na Figura 3.13, em que cada ponto corresponde a um utilizador e os valores
de suas coordenadas correspondem ao número de respostas enviadas (x) e recebidas (y),
pode verificar-se que há uma alta correlação entre as variáveis. Apesar destas evidências,
foi ainda calculado também o coeficiente de correlação de Pearson dado por:
cov(X,Y )
∑ni=1 (xi − x)(yi − y)
p n
=p
ρ =p n
2
2
var(X).var(Y )
∑i=1 (xi − x) . ∑i=1 (yi − y)
onde, x = 1n . ∑ni=1 xi e x = n1 . ∑ni=1 xi y = 1n . ∑yi=1 yi correspondem respectivamente à média
aritmética de das váriaveis x e y.
O resultado obtido é bastante significativo com ρ = 0.91 que indica uma correlação
forte positiva validando assim as evidências apresentadas no gráfico de dispersão.
A alta correlação verificada pode ser explicada pela tendência que os utilizadores têm
para retribuir a atenção dos outros e assim responderem àqueles que lhes enviam mensagens. Na verdade, hoje em dia muitos utilizadores deparam-se com um grande número
de ligações sociais, e é natural que retribuam a atenção a apenas os que realmente lhes
interessam.
Por outro lado, conjectura-se ainda que existe um elevado número de ligações simétricas, isto é, suspeita-se que no Twitter também há uma tendência para os utilizadores
seguirem (friends) aqueles que os que os seguem (followers). Contudo, nesta dissertação
não foi possível verificar a validade desta hipótese devido à falta de informação sobre
os amigos e seguidores de cada utilizador. Apesar disso, de acordo com a investigação
54
Análise de uma Rede Social de Micro-blogging: “Twittosfera” portuguesa
realizada noutras redes sociais [MMG+ 07], confirma-se que a alta correlação é também
devida à existência de ligações recíprocas.
Figura 3.13: Correlação entre o número de mensagens enviadas (x) e o número de mensagens
recebidas (y)
Note-se ainda que a partir deste gráfico, é possível verificar a existência de utilizadores
muito activos, muito populares (muitas respostas recebidas) ou ainda daqueles que não
captam a atenção dos outros (muitas respostas enviadas e poucas recebidas). No entanto, o
gráfico apenas permite observar a existência de utilizadores com um determinado número
de respostas enviadas e recebidas, uma vez que tratando-se de um gráfico de dispersão
não quantifica o número de utilizadores que cada ponto representa.
3.6
Análise da estrutura global da rede
Estudos recentes [MMG+ 07, KLPM10, KNT06, VMCG09] têm revelado a existência
de um conjunto de propriedades partilhadas pelas diversas redes sociais. Frequentemente
são abordados três conceitos na análise das redes e na caracterização da estrutura e topologia das mesmas. As características mais relevantes das redes sociais que as diferenciam
das redes aleatórias são:
• Propriedades (scale-free): distribuições características denominadas de power-laws,
que indicam a existência de pessoas que são elos de ligação entre diversos utilizadores como referidas anteriormente;
55
Análise de uma Rede Social de Micro-blogging: “Twittosfera” portuguesa
• Clustering coefficient: que indica a possível existência de sub-grupos na rede, já
referido na Secção 3.5;
• Small-world effect: que se trata da concretização da teoria dos seis graus de separação (Six Degrees of Separation);
No entanto, para além destas foi analisada a composição da rede através da detecção
dos componentes conexos da mesma. Para isso, foi aplicado o algoritmo de Tarjan
[Tar72], um algoritmo que permite determinar os componentes fortemente conexos num
grafo, a fim de expor a estrutura de rede.
Como se pode ver na Figura 3.14, a rede contém um componente gigante constituído
pela maioria dos vértices e muitos componentes pequenos. Apesar da existência de muitos
grupos pequenos compostos por duas ou três pessoas, é de salientar que a maioria dos
utilizadores está ligada com os restantes membros da rede, quer seja directamente fazendo
parte no núcleo da rede ou por intermédio das suas ligações, encontrando-se assim na
periferia do componente gigante. De acordo com a literatura [MMG+ 07], o componente
gigante tende a conter a maioria dos utilizadores da rede. Neste caso é constituído por
cerca de 77% do total dos utilizadores.
Figura 3.14: Tamanho dos componentes fortemente conexos da rede
Após revelada a constituição da rede e verificada a existência de um componente gigante, foi utilizado esse conjunto de utilizadores para verificar que a teoria dos seis de
separação (six-degrees of separation) é realmente válida nas comunidades online. A ideia
do pequeno mundo (small-world effect) tem-se revelado um conceito essencial na compreensão da estrutura das redes [KLPM10].
56
Análise de uma Rede Social de Micro-blogging: “Twittosfera” portuguesa
Através da representação da rede em forma de grafo, pode reformular-se a teoria dos
seis graus de separação recorrendo ao diâmetro da rede, isto é, a média dos caminhos
mais curtos (geodesic paths) entre todos os pares de nós. Surpreendentemente, o diâmetro
obtido na rede em estudo é exactamente 6.00 e a maior distância entre dois utilizadores
nesta rede inclui 21 pessoas.
Contudo, mais uma vez recorrendo a estudos realizados noutras redes sociais, verificase a validade da teoria dos seis graus de separação. A Tabela 3.3 compara os resultados
obtidos no cálculo do diâmetro do componente gigante noutras redes sociais com o resultado obtido para esta colecção de dados.
Tabela 3.3: Comparação do diâmetro do componente gigante de diferentes redes sociais (adaptado
da fonte [MMG+ 07])
Rede
Flickr
LiveJournal
Orkut
YouTube
Twitter
Diâmetro
5.67
5.88
4.25
5.10
6.00
Além de se revelar a composição da rede, procedeu-se também à detecção de grupos fortemente coesos e à detecção de cliques14 com o intuito de evidenciar a formação
de sub-comunidades nas redes. Assim sendo, foram calculados os cliques existentes na
rede de respostas até aqui analisada. A Figura 3.15 demonstra a presença de grupos de
10 utilizadores que comunicam todos entre si num período de 5 semanas. Estes grupos
permitem revelar círculos de amigos com relações fortes.
No entanto, além da detecção destes grupos totalmente coesos, foram utilizados dois
dos métodos de detecção de comunidades enunciados na Tabela 2.1 do capítulo de revisão bibliográfica. Os métodos utilizados, ClausetNewmanMoore [CNM04] e WakitaTsurumi [WT07] que se encontram implementados e disponíveis na biblioteca do NodeXL15 ,
têm uma complexidade temporal mais reduzida do que os restantes, e foram utilizados
para decompor a rede em comunidades coesas.
Além disso, foram comparados os desempenhos de ambos os métodos através do
tamanho das comunidades, do número total de comunidades detectadas e dos tempos
de execução dos algoritmos, com o intuito de seleccionar o mais eficiente para a detecção
e posterior caracterização dos grupos existentes na rede como será descrito no capítulo 5
que diz respeito à aplicação desenvolvida.
14 Grupos
em que cada um dos elementos está relacionados com todos os restantes
de visualização e análise de redes ou grafos: http://nodexl.codeplex.com/
15 Ferramenta
57
Análise de uma Rede Social de Micro-blogging: “Twittosfera” portuguesa
Figura 3.15: Tamanho dos cliques existentes na rede
Através da Figura 3.16, verifica-se que os resultados obtidos, no que diz respeito ao
tamanho das comunidades, não diferem radicalmente pois ambos os algoritmos apresentam distribuições semelhantes podendo até verificar-se ainda alguma sobreposição nas
distribuições respectivas.
Relativamente aos tempos médios de execução e ao total de comunidades detectadas
pelos algoritmos, a Tabela 3.4 resume os resultados obtidos após um total de 50 execuções16 numa rede constituída por 8738 utilizadores.
Tabela 3.4: Comparação dos tempos de execução dos algoritmos de detecção de comunidades
Wakita-Tsurumi e ClausetNewmanMoore
Número total de comunidades
Tempo médio de execução (ms)
Wakita-Tsurumi
1075 Comunidades
2575.78 ms
ClausetNewmanMoore
1007 Comunidades
2487.5 ms
Desta forma conclui-se que embora sejam semelhantes, a implementação do algoritmo
ClausetNewmanMoore disponível na biblioteca NodeXL v.1.0.1.123 é mais eficiente do
que a implementação do algortimo Wakita-Tsurumi disponível na mesma biblioteca. Contudo, o algortimo Wakita-Tsurumi obtém uma segmentação maior da rede pois revela
mais comunidades do que o outro método.
Assim sendo, estes resultados permitem justificar a escolha do algoritmo ClausetNewmanMoore para a detecção das comunidades, por ser o mais eficiente de entre os dois.
16 Ambiente
de execução: 4GB RAM, Pentium(R) Dual-Core CPU 2.10GHz
58
Análise de uma Rede Social de Micro-blogging: “Twittosfera” portuguesa
Figura 3.16: Comparação do número e tamanho das comunidades obtidas pelos métodos de detecção de comunidades de Wakita-Tsurumi e de ClausetNewmanMoore
Ademais, uma vez que os utilizadores das redes sociais tendem a confiar e partilhar interesses com os seus utilizadores adjacentes [MMG+ 07], posteriormente nesta dissertação
procede-se à detecção de comunidades utilizando este algoritmo para de seguida caracterizar as comunidades através dos conteúdos gerados pelos utilizadores que as compõem.
3.7
Invariância Temporal
A fim de verificar a invâriancia temporal e a auto-similaridade (self-similarity) da rede,
foram analisadas as propriedades da amostra em diferentes espaços temporais. Para isso,
foi realizada uma análise cumulativa semanal até ao total de 5 semanas no período de
tempo referente à amostra utilizada.
Desta forma, verificou-se que as propriedades da rede, como por exemplo, o número
total de respostas e a percentagem relativa de utilizadores interactivos17 , se mantêm nos
diversos intervalos de tempo. Aliás, verificou-se também o comportamento consistente ao
de uma power-law distribution nas distribuições do grau de centralidades dos utilizadores.
Relativamente à topologia das redes, pode constatar-se através da Figura 3.17 que a
estrutura se mantém ao longo do tempo. Como se pode verificar, a rede apresenta em
todos os intervalos de tempo um componente que contém a maioria dos utilizadores componente gigante - e a sua estrutura apresenta sempre um comportamento idêntico ao
17 Utilizadores
que recebem ou enviam pelo menos uma resposta.
59
Análise de uma Rede Social de Micro-blogging: “Twittosfera” portuguesa
apresentado anteriormente na Figura 3.14. Desta forma, verifica-se que a estrutura da
rede obdece a um padrão que se repete em diferentes dimensões.
Figura 3.17: Comportamento auto-similar da estrutura da rede.
Além disso, foi também observado um comportamento semelhante quando removidas
as ligações com interacções menos frequentes. Assim sendo, verifica-se desta forma que
as proporções referentes às comunicações “esporádicas” se distribuem por todos os componentes da rede. Desta forma, pode concluir-se que as propriedades das redes sociais
verificadas nesta colecção de dados e os resultados obtidos não variam com a dimensão
da amostra utilizada.
60
Análise de uma Rede Social de Micro-blogging: “Twittosfera” portuguesa
3.8
Sumário
Neste capítulo foi realizado um estudo exaustivo sobre a colecção de dados disponibilizada, com o objectivo de validar os conteúdos da mesma e verificar o carácter representativo da colecção no que diz respeito à esturura e organização de uma rede social.
Assim, a confirmação de que os fenómenos observados nas diversas redes sociais também
se verificam neste conjunto de dados, aliado ao carácter auto-similar e invariante característico das redes sociais, permite validar o conjunto de dados utilizado bem como, a sua
utilização em estudos posteriores.
Por outro lado, pode dizer-se que a colecção de dados utilizada nesta dissertação, é
sub-conjunto representativo da população portuguesa que utiliza o Twitter. Assim, os
estudos realizados permitem descrever e caracterizar os hábitos de utilização e comportamento dos utilizadores do Twitter em Portugal. Além disso, a observação de determinados fenómenos, como a existência de grupos fortemente coesos, permitem levantar
algumas hipóteses relacionadas com a formação de comunidades e com a interacção dos
utilizadores no Twitter.
No capítulo 4 é apresentada uma das hipóteses analisadas nesta dissertação, que está
relacionada com a motivação dos utilizadores para interagirem com os restantes membros
da rede e com a influência dos tópicos na formação de comunidades.
61
Análise de uma Rede Social de Micro-blogging: “Twittosfera” portuguesa
62
Capítulo 4
Análise da influência dos tópicos nas
ligações entre utilizadores
Como observado no Capítulo 3, a colecção de dados utilizada nesta dissertação apresenta características comuns a diversas redes sociais. Assim, a demonstração de que a
amostra possui determinadas propriedades indica que, em geral, esta é um subconjunto
representativo de uma rede social e, neste caso, um conjunto representativo do comportamento dos utilizadores do Twitter em Portugal.
Por outro lado, a análise da estrutura da rede e a utilização de métodos de detecção
de comunidades permitiram evidenciar a existência de sub-comunidades coesas na rede.
Contudo, os métodos de detecção de comunidades, detectam grupos coesos através da
análise exclusiva das ligações e da topologia da rede revelando apenas grupos de utilizadores que comunicam mais entre si. Desta forma, estes métodos apenas permitem
uma caracterização dos grupos considerando a densidade de ligações e a dimensão de
cada comunidade. Assim sendo, conjectura-se que a criação de grupos a partir da análise
das interacções não proporciona uma segmentação da rede por tópicos de interesse, ou
seja, os grupos que se formam não evidenciam os tópicos de interesse das relações até
porque não são analisados os conteúdos das mensagens.
Assim, neste capítulo, é discutida a seguinte questão: “Será que as pessoas interagem
motivadas pelos tópicos ou são as interacções puramente sociais?”, isto é, as comunicações estabelecidas pelos utilizadores são devidas à componente social e pessoal da rede
de cada um ou as pessoas segmentam a sua rede egocêntrica dependendo do tópico de
interesse?
Desta forma, investiga-se sobre a necessidade de análise dos conteúdos no processo
de segmentação da rede e no processo de detecção de comunidades. Assim, no caso das
relações não serem motivadas pelos tópicos de discussão, a decomposição da rede através
da análise das ligações e da topologia da mesma poderá eventualmente ser suficiente.
Colocada esta hipótese, foram recolhidos três tópicos ortogonais e analisadas as redes
63
Análise da influência dos tópicos nas ligações entre utilizadores
sociais dos utilizadores, segmentadas pelos tópicos respectivos, a fim de determinar se as
relações dos utilizadores são motivadas pelo tópico ou se o carácter social da rede de cada
um prevalece no momento de decidir com quem comunicar.
Na Secção 4.1 é descrito o processo de selecção dos tópicos. Na Secção 4.2 é descrito
o processo de segmentação da rede por tópicos e o conjunto de palavras (keywords) utilizadas no processo de recolha das mensagens. No que diz respeito à hipótese em causa,
é descrita a metodologia de teste na Secção 4.3 sendo os resultados apresentados nas
secções seguintes.
4.1
Selecção dos tópicos
De forma a verificar se na rede social as pessoas interagem com os seus contactos
independentemente do tópico, isto é, se a componente social da rede é mais predominante
do que os assuntos discutidos, foram seleccionados três tópicos distintos: desporto (mais
especificamente futebol), política e religião; e analisados, através de métodos estatísticos, os critérios de selecção dos utilizadores no momento de interacção com os restantes
membros da sua rede.
É de salientar que a escolha destes tópicos está relacionada com o carácter diversificado e ortogonal das temáticas, isto é, acredita-se que os tópicos não estão fortemente
correlacionados ao ponto dos utilizadores que manifestam interesse num tema discutirem
os restantes de igual modo. Posto isto, parte-se do pressuposto de que as pessoas têm interesses diversos, e no caso de segmentarem a sua rede por tópicos esperar-se-á que cada
um dos assuntos seja discutido com grupos de pessoas significativamente diferentes. Por
outro lado, além de serem tópicos distintos no ponto de vista do interesse das temáticas,
a escolha deve-se ainda ao facto de se acreditar que se tratam de tópicos permanentes no
tempo, isto é, são tópicos debatidos constantemente e não estão apenas associados a acontecimentos particulares. Partindo desta hipótese, foi feita uma recolha das mensagens de
cada tópico.
4.2
Segmentação da rede por tópicos
A segmentação da rede por tópicos foi realizada utilizando um conjunto de palavras
(keywords) relacionadas com cada um dos temas. A Tabela 4.1 apresenta as palavras
utilizadas na recolha das mensagens para cada um dos tópicos.
De referir que a colecção de dados utilizada para esta análise (amostra B + amostra
C), é constituída pelo conjunto de dados analisado no capítulo anterior mais o conjunto
de dados recolhidos nas semanas seguintes (3 semanas referentes à amostra C). Assim,
o período utilizado para a recolha das mensagens por tópicos varia entre 17 de Março
64
Análise da influência dos tópicos nas ligações entre utilizadores
de 2010 e 16 de Maio de 2010, sendo que os dados da amostra C foram incluídos nesta
análise para proporcionar uma maior significância estatística nos resultados.
Tabela 4.1: Conjunto de palavras (keywords) utilizadas no processo de selecção das mensagens
por tópicos.
Tópico
Desporto
Política
Religião
Palavras-chave (keywords) utilizadas na segmentação das respostas
fcporto; campeão; benfica; sporting; slb; fcp; campeonato; rio ave; braga;
sp.braga; futebol; baliza; bola; temporada; liga; lampiões; dragão; falcão; jesualdo; golo; penálti; penalti; penalty; champions; taça; jogo; árbitro; arbitragem; mourinho; barça; barcelona; liverpool; messi; ronaldo; real madrid;
clube; título; competições europeias; selecção nacional; estádio; Luz; leixões;
académica; águias; jornada; treinador; maradona; alvalade; jogador; marcador
expulso; expulsão; cartão amarelo; cartão vermelho; equipa; época; epoca;
trofeu
parlamento; PSD; socrates; sócrates; ministro; finanças; crise; economia;
económica; politica; política; comunista; socialista; democrata; democracia;
bloco de esquerda; freeport; chavez; parlamento; taxa; IVA; sociedade; governo; partido; leis; iva; impostos; SCUT; fiscal; salario; salário; emprego;
défice; défice; tribunal; tribunais; greve; sindicato; sindicais; dívidas; fisco;
segurança social; lei; IRS; instituições; declaração; rendimentos; funcionário
público; funcionario publico; funcionário público; politico; político partido
social; junta de freguesia; paulo portas; monarquia; OCDE; voto; eleição; legislativa; empresas; estado
papa; sé; fé; bento; religiao; catolicismo; catolico; cristão; cristao; santidade;
santo; igreja; comunhao; comunhão; biblia; bíblia; rezar; Fátima; peregrinação; peregrinos; santuário; santuario; pecado; confissão; Deus; confissao;
promessa; cruz; amén; amen; hóstia; paróquia; paroquia; irmã lúcia; irma lucia; missa; acolito; acólito; sagrado; pedofilia; baptizado; casamento; cristo;
cristianismo; casamento; evangelho; vaticano; bispo; cardeal; padre; pastor;
nossa senhora; pontifice; joao paulo II; catequese; patriarca; policarpo; arcebispo; diacono; diácono; eucaristia; leigos; episcopal; presbítero; diocese
A fim de verificar a permanência dos tópicos ao longo do tempo, foram obtidas as
distribuições diárias das mensagens enviadas em cada tópico. As Figuras 4.1, 4.2 e 4.3
ilustram as distribuições das mensagens sobre os tópicos Desporto, Política e Religião
respectivamente.
65
Análise da influência dos tópicos nas ligações entre utilizadores
Figura 4.1: Distribuição diária de tweets no tópico Desporto
Figura 4.2: Distribuição diária de tweets no tópico Política
Figura 4.3: Distribuição diária de tweets no tópico Religião
66
Análise da influência dos tópicos nas ligações entre utilizadores
Verifica-se que o tema “Política” é o tema mais regular ao longo do tempo, enquanto
que no “Desporto” parece existir alguns eventos que despoletam mais discussão originando períodos com mais mensagens. Apesar disso, o tema “ Desporto” apresenta também uma distribuição consistente ao longo do tempo não existindo discrepâncias muito
acentuadas em toda a sua distribuição, o que pode indicar que se tratar de um tópico permanente ao longo do tempo. No que diz respeito à “Religião” é, dos três tópicos, aquele
que tem menos mensagens verificando-se ainda um acréscimo acentuado no número de
mensagens enviadas a partir do dia 11 de Maio de 2010 que é explicado por um evento
“marcante” em Portugal como é descrito de seguida.
Relativamente aos fenómenos observados nas últimas duas semanas nas distribuições
diárias do tópico “Desporto” e do tópico “Religião”, mais especificamente nos dias 2 de
Maio de 2010 e 9 de Maio de 2010 na Figura 4.1 e no dia 11 de Maio de 2010 na Figura
4.3, o elevado número de mensagens é justificado pelos acontecimentos “marcantes” na
sociedade portuguesa que ocorreram nesse período e que coincidiram com a data de início
deste estudo. O primeiro, no dia 2 de Maio de 2010, é marcado por um jogo de futebol
decisivo, disputado na penúltima jornada do campeonato nacional, que envolveu dois dos
clubes mais importantes na história do futebol português. A vitória do Futebol Clube
do Porto1 no seu estádio perante o seu adversário e rival, o Sport Lisboa e Benfica2 ,
adiava assim a conquista do título de campeão nacional de futebol para a última jornada
disputada no dia 9 de Maio de 2010. Este jogo gerou um enorme alvoroço devido à
grande rivalidade entre os dois clubes. Porém, no dia 9 de Maio de 2010, a conquista
do título de campeão nacional de futebol por parte do Sport Lisboa e Benfica, explica o
aumento do número de mensagens apresentado na Figura 4.1. Coincidentemente, no que
diz respeito à “Religião”, o dia 11 de Maio de 2010 fica marcado pelo primeiro dia da
visita oficial e episcopal do Papa Bento XVI a Portugal. O Santo Padre Bento XVI, líder
da Igreja Católica, correspondendo ao convite dos Bispos portugueses e do Presidente
da República, aceitou visitar Portugal entre os dias 11 e 14 de Maio, por ocasião da
peregrinação aniversária das Aparições de Nossa Senhora de Fátima que, segundo a Igreja
Católica, apareceu pela primeira vez a três pastorinhos no lugar de Fátima no dia 13 de
Maio de 1917.
Uma vez que a hipótese colocada pretende analisar as motivações nas interações dos
utilizadores, apenas foram recolhidas as mensagens que são actos de comunicação entre
os mesmos. De salientar ainda que o conjunto de palavras (keywords) utilizadas para a selecção das mensagens por tópicos, é suficientemente discriminativo uma vez que existem
poucas mensagens nas intersecções dos tópicos. Como se pode verificar pelo diagrama
apresentado na Figura 4.4, o número de mensagens nas intersecções é significativamente
baixo quando comparado com o total de mensagens recolhidas para cada tópico. Desta
1 Site
2 Site
oficial do clube: http://www.fcporto.pt/
oficial do clube: http://www.slbenfica.pt/
67
Análise da influência dos tópicos nas ligações entre utilizadores
forma, denota-se que a probabilidade dos utilizadores estarem na rede correspondente a
um determinado tópico sem manifestarem verdadeiramente interesse na temática é reduzida.
Contudo, apesar do esforço realizado na tentativa de reduzir ao máximo este efeito no
processo de selecção das mensagens, acabaram por surgir respostas que se enquadram em
mais do que um tópico. A Tabela 4.2 apresenta as 3 mensagens na intersecção dos três
tópicos e que se enquadram igualmente em cada um dos tópicos.
Figura 4.4: Número de respostas por tópico.
Tabela 4.2: Mensagens na intersecção dos três tópicos: Desporto, Política e Religião
@JMF1957 com SLB Campeão, as escolhas de treta do queiroz e SS o Papa em Portugal, o socas
pode subir o IVA para 30%... etc. k ninguem nota!
@ptnik Nao culpes o slb pelos impostos... Culpa o governo e a crise... E por falar em slb andavam
uns malucos no marques a apitar...o papa!
@ProtoKun E não te esquecas do benfica campeão e da visita do papa. Tudo para alegrar o povo.
Acabou-se a crise!!
No que diz respeito aos utilizadores, a sobreposição evidencia a existência de utilizadores que se interessam por mais do que um tema como se pode verificar na Figura
4.5. Desta forma, a existência destes utilizadores permite, através da análise dos utilizadores com redes nos diferentes tópicos, testar a hipótese colocada no início deste
capítulo: “São as interacções motivadas pelos tópicos ou independentes do tópico?’.
68
Análise da influência dos tópicos nas ligações entre utilizadores
Figura 4.5: Número de utilizadores por cada tópico.
4.3
Teste da Hipótese
De forma a testar a hipótese colocada neste capítulo, foram construídas, para todos
os utilizadores, as redes egocêntricas relacionadas com cada um dos tópicos, isto é, por
cada utilizador foram definidas 3 redes: a sua rede de Desporto, a sua rede de Política e
a sua rede de Religião. Cada rede corresponde a um determinado tópico e o utilizador
está relacionado com todas as pessoas a quem respondeu ou que lhe responderam nesse
tópico.
De seguida, através de métodos estatísticos, procede-se ao teste da hipótese em causa
de forma a verificar se os utilizadores que se interessam por mais do que um tópico (utilizadores nas intersecções de pares de tópicos representado no diagrama 4.5) interagem
com as mesmas pessoas em ambos os tópicos ou se pelo contrário, as suas redes são
significativamente diferentes em tópicos distintos.
Desta forma, a grandeza a utilizar no teste desta hipótese corresponde, para cada utilizador, à informação da co-ocorrência das pessoas nas redes egocêntricas relativas aos
tópicos. O objectivo consiste em medir a associação existente entre as redes de cada utilizador nos tópicos distintos. Neste caso, realizando o teste para cada par de tópicos, as
váriaveis X e Y corresponderão ao número de pessoas a quem um utilizador responde no
tópico X e ao número de pessoas a quem um utilizador responde no tópico Y e a hipótese
em causa, H0 , será dada por:
H0 : o utilizador comunica com os restantes utilizadores independentemente dos tópicos X e Y.
69
Análise da influência dos tópicos nas ligações entre utilizadores
Para testar esta hipótese existem diversas métricas, denominadas de medidas de associação, que permitem medir o grau de dependência entre duas variáveis através da informação sobre a co-ocorrência das mesmas [Eve05]. Enquanto algumas medidas derivam
da Estatística e são conhecidas essencialmente pelos Testes de Significância Estatística
como o caso do teste Z, o teste X 2 de Pearson ou o teste t-Student, outras são dadas
por Coeficientes de Associação como por exemplo: o coeficiente de Jaccard ou o coeficiente de Dice. Além destas, existem outras medidas que são baseadas em conceitos
da Teoria da Informação como por exemplo, a Informação Mútua. Apesar das diferentes
fórmulas utilizadas pelas medidas de associação, é frequente representarem-se os valores
relevantes para o cálculo destas medidas através de uma tabela denominada por Tabela de
Contingência.
4.3.1
Tabela de Contingência
As tabelas de contingência são utilizadas para registar os valores relevantes para o
cálculo das medidas de associação e permitem analisar o relacionamento entre duas ou
mais variáveis. Neste caso, analisando pares de tópicos e sendo que a variável X representa o número de pessoas com quem um utilizador comunica no tópico X e a variável Y
representa o número de pessoas com quem um utilizador comunica no tópico Y, a Tabela
de Contingência (TC) corresponde a uma matriz 2x2 que contém os valores relativos das
frequências das combinações possíveis para as ocorrências de X e Y, ou seja, é definida
pelos seguintes quatro valores:
1. p(X,Y ): probabilidade do utilizador comunicar com as outras pessoas sobre os tópicos X e Y;
2. p(X, !Y ): probabilidade do utilizador comunicar com as outras pessoas sobre o
tópico X e não comunicar sobre o tópico Y;
3. p(!X,Y ): probabilidade do utilizador comunicar com as outras pessoas sobre o
tópico Y e não comunicar sobre o tópico X;
4. p(X!,Y !): probabilidade do utilizador comunicar com as outras pessoas sem ser
sobre o tópico X nem sobre o tópico Y;
e é representada por:
"
TCXY =
p(X,Y ) p(X, !Y )
p(!X,Y ) p(!X, !Y )
#
"
=
a b
c d
o que corresponde ao apresentado no diagrama da Figura 4.6
70
#
Análise da influência dos tópicos nas ligações entre utilizadores
Figura 4.6: Número de utilizadores por cada tópico.
Além disso, verifica-se que p(X,Y ) + p(X, !Y ) + p(!X,Y ) + p(!X, !Y ) = a + b + c +
d = N, em que N corresponde ao total de ligações do utilizador independentemente dos
tópicos. De salientar que a simples inspecção da tabela de contingência revela indícios
do grau de associação entre duas variáveis, isto porque quanto mais vezes dois elementos
ocorrerem em simultâneo (p(X,Y) = a), e menos vezes ocorrerem separadamente (p(X,!Y)
= b e p(!X,Y) = c) maior será o grau de associação entre as variáveis X e Y.
4.3.2
Informação Mútua Pontual Normalizada
Após definidas as tabelas de contingência para cada utilizador na intersecção de cada
par de tópicos, foi utilizada a Informação Mútua Pontual Normalizada (NPMI) para determinar o grau de associação das redes de cada utilizador nos diferentes tópicos. De referir
que a Informação Mútua Normalizada, como o próprio nome indica, é uma variação normalizada da Informação Mútua Pontual, que por sua vez é uma das medidas de associação
com destaque na literatura [CH89, SXW+ 06] bastante utilizada para, por exemplo, analisar a associação entre palavras [CH89, SXW+ 06]. De salientar ainda que se trata de
uma medida de associação bi-direccional, isto é, permite distinguir entre a situação de
associação positiva em que X e Y têm tendência a co-ocorrer e a situação de associação
negativa na qual X e Y tendem a excluir-se mutuamente. Por outro lado, a normalização
desta medida, introduzida por Bouma [Ger09], torna mais fácil a interpretação dos resultados e ao mesmo tempo torna a medida menos sensível às frequências na tabela de
contingência sendo o resultado sempre um valor compreendido entre -1 e 1.
Assim, a informação mútua pontual normalizada (NPMI) é dada por:
NPMI(X,Y ) =
p(X,Y )
(ln( p(X)p(Y
) ))
−ln(p(X,Y ))
71
Análise da influência dos tópicos nas ligações entre utilizadores
em que p(X) representa a probabilidade do utilizador discutir com outros utilizadores
devido ao tópico X, p(Y) representa a probabilidade do utilizador comunicar com outros utilizadores a respeito do tópico Y e p(X,Y) representa a probabilidade do utilizador
conversar com outros utilizadores acerca de ambos os tópicos X e Y.
Desta forma, se os acontecimentos forem fortemente dependentes verifica-se que p(X,Y ) >
p(X)p(Y ) e 0 < NPMI < 1. Por outro lado, no caso de serem mutuamente exclusivos
verifica-se que p(X,Y ) < p(X)p(Y ) e −1 < NPMI < 0.
Neste caso, sendo H0 : “os utilizadores comunicam com os restantes utilizadores independentemente do tópico X e do tópico Y”;
• NPMI > 0 indica que o utilizador comunica com os utilizadores independentemente
dos tópicos, revelando assim indícios de que a componente social da rede é mais
forte pois o utilizador discute os diversos assuntos com sensivelmente as mesmas
pessoas;
• NPMI < 0 indica que o utilizador interage com pessoas diferentes para cada tópico
de discussão o que revela que os utilizadores seleccionam as pessoas com quem
falam dependendo do tópico.
De seguida, foi calculada a NPMI para cada utilizador presente nas intersecções dos
pares de tópicos de forma a testar hipótese levantada (H0 ).
4.4
Desporto e Política
Relativamente aos utilizadores que discutiram os temas “Desporto” e “Política” (669
utilizadores), foi calculada a NPMI para cada utilizador. Como é óbvio, todos os utilizadores que discutem estes dois tópicos têm uma rede correspondente em cada um dos
temas. Contudo, apesar de terem uma rede definida em ambos os tópicos, estas podem ser
disjuntas, ou seja, sem sobreposição de indivíduos o que significa que o utilizador efectua
uma separação total das pessoas por tópicos não existindo nenhuma pessoa com quem ele
fale sobre os dois assuntos (a = 0 ⇒ NPMI = 0). Contabilizando, 42% dos utilizadores
que falam sobre os dois assuntos separam completamente a sua rede por tópicos. Apesar
deste número elevado, verifica-se através da distribuição apresentada na Figura 4.7 que
estas redes são compostas essencialmente por dois ou três utilizadores, o que torna este
resultado um pouco menos surpreendente. Comparando com a distribuição apresentada
na Figura 4.8, verifica-se que nas redes maiores é difícil efectuar uma segmentação tão
discriminativa.
72
Análise da influência dos tópicos nas ligações entre utilizadores
Figura 4.7: Distribuição das redes disjuntas nos tópicos Desporto e Política
Figura 4.8: Distribuição das redes com sobreposição nos tópicos Desporto e Política
Assim, de forma a compreender o comportamento dos utilizadores cujas redes têm no
mínimo a sobreposição de uma pessoa, foi calculada a respectiva NPMI e apresentada na
Figura 4.9 sob a forma de um gráfico de dispersão. Além da NPMI por cada utilizador,
que permite identificar a existência determinados indivíduos particulares, como por exemplo, os que separam completamente a rede por tópico (NPMI ≈ −1) ou aqueles que
73
Análise da influência dos tópicos nas ligações entre utilizadores
falam sobre ambas as temáticas com os mesmos utilizadores (NPMI ≈ 1), é também apresentada a média aritmética da NPMI para todos os utilizadores com o mesmo número
de ligações com o objectivo de detectar tendências no comportamento das pessoas.
Figura 4.9: Informação Mútua Pontual Normalizada nos tópicos Desporto e Política
Tendo em conta a distribuição apresentada na Figura 4.8, e analisando a distribuição
da média aritmética representada na Figura 4.9, até ao ponto com coordenada X = 21,
verifica-se que em média a NPMI parece ter tendência para decrescer, o que revela que
os utilizadores têm tendência para se especializarem mais à medida que as suas ligações
aumentam (segmentação por tópicos). De referir que a partir da coordenada X = 22,
por se tratarem de situações pontuais (por exemplo, apenas 1 utilizador), a média segue
exactamente a distribuição da NPMI não sendo viável generalizar para estes casos (ver
Figura 4.8).
Por outro lado, pode verificar-se que apesar da tendência para separar as suas ligações
pelos tópicos à medida que a rede aumenta, a componente social (a afinidade pelas pessoas) é um factor que pesa significativamente e que influencia a selecção dos utilizadores
uma vez que a NPMI é quase sempre positiva.
4.5
Desporto e Religião
No que diz respeito aos tópicos “Desporto” e “Religião” (625 utilizadores), verificase que o utilizador com mais ligações neste conjunto de tópicos tem um comportamento
diferente do que o utilizador com mais ligações no par de tópicos anterior. Enquanto que
o utilizador com mais ligações nos tópicos “Desporto” e “Política” é menos dependente
da componente social e efectua uma divisão da rede tendo em consideração os tópicos
74
Análise da influência dos tópicos nas ligações entre utilizadores
envolvidos (NPMI ≈ −0, 07, ver Figura 4.9), o utilizador com mais ligações nos tópicos
“Desporto” e “Religião” apresenta um valor positivo o que indica que este não faz uma
divisão da sua rede por tópicos (NPMI ≈ 0, 19, ver Figura 4.12).
No entanto, de uma forma geral, verificam-se que os resultados são semelhantes ao
par de tópicos anterior em que as redes disjuntas são maioritariamente as mais pequenas
como ilustra a Figura 4.10.
Figura 4.10: Distribuição das redes disjuntas nos tópicos Desporto e Religião
Figura 4.11: Distribuição das redes com sobreposição nos tópicos Desporto e Religião
75
Análise da influência dos tópicos nas ligações entre utilizadores
Da mesma forma, para compreender o comportamento dos utilizadores cujas redes
não são disjuntas, foi calculada a respectiva informação mútua pontual normalizada e a
respectiva média aritmética, como se encontra apresentada na Figura 4.12.
Figura 4.12: Informação Mútua Pontual Normalizada nos tópicos Desporto e Religião
Considerando também a distribuição apresentada na Figura 4.11, e analisando a distribuição da média aritmética até ao ponto com coordenada X = 17, verifica-se a mesma
tendência do que o par de tópicos anterior.
4.6
Religião e Política
Analogamente aos pares de tópicos anteriores, também nos tópicos “Religião” e “Política”
(542 utilizadores) a informação mútua pontual normalizada de cada utilizador é, na maioria dos casos, positiva. Desta forma, indica que apesar da tendência para segmentar as
relações por tópicos à medida que a rede egocêntrica é maior, também se verifica que o
aspecto social da rede prevalece sobre os tópicos como apresentado na Figura 4.15.
76
Análise da influência dos tópicos nas ligações entre utilizadores
Figura 4.13: Distribuição das redes disjuntas nos tópicos Religião e Política
Figura 4.14: Distribuição das redes com sobreposição nos tópicos Religião e Política
Da mesma forma que nos tópicos anteriores verifica-se que, apesar dos 42%, os utilizadores com comunidades mutuamente exclusivas são essencialmente utilizadores com
redes egocêntricas pequenas.
Por outro lado, apesar da tendência para separar a rede por tópicos à medida que
o número de ligações da rede egocêntrica de cada um aumenta, verifica-se que os utilizadores com mais ligações nestes dois tópicos têm uma componente social mais forte.
77
Análise da influência dos tópicos nas ligações entre utilizadores
Por outro lado, pode também querer dizer que este par de tópicos é o mais provável de
ser debatido em conjunto, sendo que poderão existir utilizadores mais “generalistas” que
discutem estes dois tópicos com várias pessoas. No entanto, no geral, a tendência parece
ser de decréscimo sendo que estes utilizadores se tratam de situações pontuais (apenas um
utilizador em cada ponto do gráfico de dispersão).
Figura 4.15: Informação Mútua Pontual Normalizada nos tópicos Religião e Política
4.7
Discussão de Resultados
Após realizadas estas experiências, pode verificar-se que nas comunidades mais pequenas a componente social é muito forte, sendo que a probabilidade dos utilizadores debaterem qualquer tipo de assunto com qualquer um dos seus amigos é mais elevada. Por
outro lado, como seria de esperar, à medida que o número de ligações da rede egocêntrica de um indivíduo aumenta, há uma ligeira tendência para seleccionar cada vez mais
a rede por tópicos. Ainda assim, verifica-se que a componente social da rede é bastante
importante uma vez que a maioria tem um valor positivo para a NPMI. Além disso, este
resultado não é muito surpreendente, uma vez que está de acordo com a intuição, e ademais, quanto maior é a rede egocêntrica de um utilizador, menor é a probabilidade de este
discutir o mesmo assunto com duas pessoas distintas da sua rede, a menos que este se
trate de um especialista e que discuta um único assunto com a maioria dos utilizadores.
Ainda assim, é curioso de observar que o par de tópicos “Religião” e “Política” é, dos
três, aquele que tem um valor médio para a NPMI mais elevado. Este fenómeno, pode
estar relacionado com o facto de se tratarem de tópicos mais genéricos do que o “Desporto” que por exemplo, parece dos três o tema em que há um grau de especialização
maior. Isto porque, observando novamente a Figura 4.5, trata-se do tópico em que quase
78
Análise da influência dos tópicos nas ligações entre utilizadores
metade dos utilizadores fala única e exclusivamente apenas de “Desporto”, algo não verificado nos outros dois tópicos. Quando comparado com o valor na intersecção dos três
tópicos, verifica-se que é o único tema com um valor superior, chegando quase ao dobro,
enquanto que na “Política” e na “Religião” o número de pessoas que fala exclusivamente
só do tópico é menor do que as que falam dos três.
Outro aspecto interessante, está relacionado com o facto de se observar que apenas
no par de tópicos “Desporto” e “Política” se verifica a existência de um utilizador com
elevado número de ligações com tendência para distinguir a sua rede por tópicos. Esta
situação, embora pontual, não se verifica quando um dos tópicos envolvidos é a “Religião”.
Para concluir, pode dizer-se que a NPMI é um indicador a ter em conta no processo de
caracterização dos utilizadores podendo constituir uma característica essencial (feature),
por exemplo, num processo de classificação dos utilizadores.
4.8
Sumário
Neste capítulo foi apresentada uma análise com base em fundamentos estatísticos sobre a influência dos tópicos nas ligações entre os utilizadores. Para tal, foram recolhidas
três redes referentes a três tópicos distintos e analisadas as redes egocêntricas dos utilizadores em cada um dos tópicos. Desta forma, verifica-se que à medida que um utilizador contém mais ligações, este tende a separar a sua rede por tópicos. Contudo, esta
tendência não é muito saliente uma vez que se verifica que a componente social da rede
é, na maioria dos casos, o factor que prevalece no critério de selecção dos utilizadores no
momento da comunicação.
79
Análise da influência dos tópicos nas ligações entre utilizadores
80
Capítulo 5
“SocialAnalytics”: ferramenta para
análise de redes sociais
Neste capítulo é apresentada a aplicação desenvolvida ao longo de todo este trabalho
de investigação. Além da caracterização exaustiva de uma colecção de dados composta
por um subconjunto da comunidade portuguesa activa no Twitter, que foi descrita no
Capítulo 3, e da discussão acerca da influência dos tópicos nas relações apresentada no
Capítulo 4, o trabalho realizado nesta dissertação culminou com o desenvolvimento de
uma ferramenta para a análise das características e propriedades das redes sociais.
“SocialAnalytics” é uma ferramenta que permite a obtenção de conhecimento sobre
uma rede social através de uma descrição do conjunto de dados da rede. Esta aplicação,
trata-se de uma ferramenta que auxilia a análise das interacções numa rede social pois
apresenta dados detalhados e visualizações gráficas sobre a actividade da rede. É uma
ferramenta que apresenta uma descrição quantitativa dos dados e permite a caracterização
de comunidades coesas através da estrutura de ligações da rede e dos conteúdos gerados
por cada comunidade.
De referir ainda que a aplicação desenvolvida ao longo deste projecto de investigação,
foi utilizada para a extracção de alguns dos resultados apresentados nos capítulos anteriores.
Outro aspecto importante, é o facto de se tratar de uma ferramenta genérica, isto é,
apesar de ter sido desenvolvida com a finalidade de analisar a rede social implícita num
conjunto de dados do Twitter, a aplicação é fácil de adaptar permitindo assim a sua utilização na análise de outras redes sociais. Para isso, é apenas necessário que o utilizador
forneça o conjunto de dados no formato especificado na Secção 5.1. Assim nas secções
seguintes são apresentados alguns dos detalhes de implementação. Na Secção 5.2 são
apresentadas as funcionalidades e a interface da aplicação. Para finalizar, são enumerados
alguns dos domínios de aplicação desta ferramenta e apresentados alguns sistemas que
permitem ao utilizador a análise de alguns fenómenos no Twitter.
81
“SocialAnalytics”: ferramenta para análise de redes sociais
5.1
Formato da colecção de dados
Os conteúdos que dão suporte à aplicação deverão encontrar-se armazenados numa
base de dados MySQL1 e esta deverá ser criada pelo utilizador. O esquema de dados
utilizado pela aplicação é bastante simples e consiste apenas numa tabela que contém
essencialmente os seguintes campos:
• id: representa o identificador numérico da mensagem;
• id_reply: representa o identificador da mensagem que é resposta à mensagem id;
• text: representa o texto da mensagem;
• date: representa a data em que foi enviada a mensagem;
• from_user_id: representa o identificador do utilizador que enviou a mensagem;
• to_user_id: representa o identificador do utilizador que recebeu a mensagem uma
vez que esta pode ser destinada a alguém em particular; No caso de não se destinar
a nenhum utilizador particular, este campo terá o valor 0.
Desta forma, fornecendo um conjunto de dados neste formato, o utilizador poderá
analisar qualquer rede utilizando a aplicação “SocialAnalytics”. Para tal, deverá criar
uma base de dados MySQL e criar uma tabela denominada de “replies” respeitando a
estrutura de dados acima enumerada. Deverá ainda alterar um ficheiro de configuração
onde deve indicar as credenciais de acesso à base de dados. É ainda importante destacar a
necessidade de indexar os conteúdos quando o volume de dados é elevado uma vez que os
índices criados podem ser encarados como a estrutura que permite aceder à informação de
forma rápida e eficaz. Neste caso, foram indexados os campos from_user_id, to_user_id
e date, uma vez que é sobre os mesmos que incide a maior quantidade das pesquisas
efectuadas.
De seguida, são descritas as funcionalidades e apresentada a interface da aplicação.
5.2
5.2.1
Descrição da aplicação
Funcionalidades
No que diz respeito às funcionalidades, a aplicação permite ao utilizador:
• Definir o intervalo de tempo a analisar;
1 http://www.mysql.com/
82
“SocialAnalytics”: ferramenta para análise de redes sociais
• Obter um conjunto de estatísticas gerais da rede, tais como: o número de mensagens enviadas por todos os utilizadores e a percentagem de respostas enviadas
(mensagens destinadas a utilizadores específicos); o número total de utilizadores
que enviaram mensagens no intervalo de tempo definido e ainda, o número total de
utilizadores isolados da rede, isto é, o total de utilizadores que nunca interagiram
com ninguém;
• Descrever a estrutura global da rede de interacção através da observação dos componentes conexos da mesma e da existência de comunidades coesas;
• Analisar o fluxo de informação através de estatísticas que evidenciam a quantidade
de respostas enviadas e recebidas por cada utilizador;
• Observar os períodos do dia e da semana em que há mais actividade na rede. Esta
análise é proporcionada através da apresentação da distribuição horária e semanal
das mensagens enviadas;
• Determinar as comunidades coesas através da análise da interacção entre as pessoas
da rede; Esta funcionalidade permite ainda a utilização de 2 métodos discutidos na
literatura e implementados na biblioteca NodeXL (Wakita-Tsurumi e ClausetNewmanMoore);
• Obter um resumo dos conteúdos gerados pelas comunidades sendo apresentadas
apenas as palavras mais frequentes numa comunidade.
5.2.2
Interface da aplicação
Relativamente à interface, a aplicação apresenta uma secção de configuração dos
parâmetros a utilizar na análise da rede social em questão. Além disso, é ainda composta por diversos separadores onde serão apresentados os diferentes resultados. Para
começar, na área de configuração o utilizador deve ajustar os parâmetros de acordo com
a análise pretendida. Nessa secção, deverá então definir o intervalo de tempo sobre o
qual incide a sua análise e ainda definir o tamanho mínimo dos componentes conexos que
serão apresentados na aplicação. Desta forma, é possível excluir do seu estudo as comunidades mais pequenas como por exemplo, aquelas que são compostas por dois ou três
utilizadores uma vez que podem ser consideradas situações pontuais por não interagem
com a globalidade da rede e se tratarem de grupos muito pequenos.
Além disso, o utilizador pode ainda definir o número mínimo obrigatório de actos
de comunicação para que exista uma ligação entre dois utilizadores. Desta forma, removendo as ligações menos frequentes, o utilizador tem a possibilidade de analisar apenas o conjunto de pessoas mais activas da rede. De salientar que estes parâmetros podem
83
“SocialAnalytics”: ferramenta para análise de redes sociais
ser ajustados consoante os resultados obtidos, por exemplo, através da análise dos gráficos respectivos ao fluxo de respostas (Figura 5.1), permitindo assim determinar o número
mínimo de comunicações mais adequado.
Figura 5.1: Análise do fluxo de respostas entre as 19:00:00 e as 23:59:59 horas do dia 09 de Maio
de 2010.
Para além dos diversos gráficos que permitem a análise de uma colecção de dados e
que foram maioritariamente expostos no Capítulo 3 desta dissertação, é também apresentado o grafo de interacção correspondente ao intervalo de tempo definido e a respectiva nuvem de palavras (tagcloud) que apresenta os termos mais utilizados no período de
tempo estabelecido. Além disso, como referido anteriormente, o utilizador tem ainda a
possibilidade de determinar as comunidades coesas da rede presentes no grafo de interacção. A Figura 5.2, apresenta um exemplo do conjunto de utilizadores que enviaram
mensagens entre as 19:00:00 e as 23:59:59 horas do dia 09 de Maio de 2010. Por outro
lado, são ainda apresentadas as comunidades detectadas pelo algoritmo de ClausetNewmanMoore [CNM04] nessa rede e o resumo dos conteúdos enviados pelos utilizadores
que a compõem. Como se pode verificar, os utilizadores das diferentes comunidades são
representados por símbolos e cores diferentes.
De referir, que a apresentação dos conteúdos das mensagens em forma de nuvem de
palavras (tagcloud) considera também a polaridade a priori de cada palavra. Esta informação é obtida no âmbito do projecto colaborativo Sylvester, através de um dicionário
que contém definida a polaridade de cada palavra [Car06]. Assim, de acordo com a
conotação da palavra, esta é representada por uma cor diferente. Desta forma, a vermelho
84
“SocialAnalytics”: ferramenta para análise de redes sociais
encontram-se as palavras com uma conotação negativa, a verde encontram-se as palavras
que, à partida, têm uma conotação positiva e a azul são representadas as palavras com
conotação neutra. Além da nuvem de palavras, é possível verificar o conteúdo da última
mensagem enviada por cada utilizador. Assim, ao colocar o cursor em cima do utilizador
é apresentada a última mensagem enviada por ele. Este pormenor, permite de forma
muito rudimentar, enquadrar o utilizador na respectiva (tagcloud) quando esta apresenta
um conjunto de tópicos mais vasto.
Figura 5.2: Exemplo das comunidades coesas presentes no grafo de interacção e dos conteúdos
enviados pelos utilizadores entre as 19:00:00 e as 23:59:59 horas do dia 09 de Maio de 2010.
Tal como enunciado nas funcionalidades da aplicação, o utilizador tem ainda a possibilidade de analisar determinada comunidade em particular. Assim, após serem calculadas
as comunidades com base na interacção, o utilizador deverá seleccionar um elemento da
comunidade que pretende analisar e solicitar o resumo das mensagens enviadas dentro
dessa comunidade. Como seria de esperar, as pessoas discutem assuntos diversos e desta
forma os resultados das tagclouds referentes a cada comunidade podem ser completamente diferentes. Por outro lado, pode ainda verificar-se a existência de comunidades que
provavelmente discutem o mesmo assunto mas que o fazem com intensidades diferentes,
e ainda de outras comunidades que misturam uma diversidade maior de temas.
A Figura 5.3 permite comparar as tagclouds de três das comunidades apresentadas no
grafo de interacção da figura anterior.
85
“SocialAnalytics”: ferramenta para análise de redes sociais
Figura 5.3: Comparação das tagclouds de 3 comunidades diferentes
Como se pode verificar, existem comunidades em que o tópico discutido é mais saliente.
No primeiro caso, os utilizadores falam sobre o tópico “Desporto” (adeptos, adversários,
benfica, benfiquista, benfiquistas, braga, cachecol, campeão, campeonato, carvalhal, clube,
jogo, marcador, marítimo, lagarto, sporting, sportinguista, pedroto, taça, tácticas, treinador).
Por sua vez, a segunda comunidade apresentada na figura anterior, além do futebol parece
debater bastante o tema “Política” (crise, decisão, dedução, défice, finança, ministro, grécia, moeda, pib, psi20, sócrates, submarino, irs, iva). Relativamente à terceira não se
evidencia nenhum tópico mais saliente uma vez que as palavras são variadas. Apesar
disso, dá para perceber, através das palavras “fátima” ,“céu” e “santa”, que chegam a
abordar o tópico “Religião”.
86
“SocialAnalytics”: ferramenta para análise de redes sociais
Para finalizar, o “SocialAnalytics” é uma ferramenta de análise muito simples que permite revelar algum conhecimento relevante nas redes sociais, como por exemplo, identificar indivíduos mais influentes na rede, revelar comunidades coesas e detectar os assuntos
debatidos pelas comunidades que se formam nesta rede social.
5.3
Ferramentas de Análise do Twitter
Nas redes sociais, o fluxo de informação, a partilha de conteúdos, a divulgação de
notícias, sentimentos e opiniões são formas de construção colectiva de conhecimento implícitas a este tipo de redes e que as tornam uma fonte de informação bastante apelativa.
Com o desenvolvimento da tecnologia, surgem cada vez mais aplicações que permitem
captar de forma fácil e perceptível o fluxo de informação nas redes sociais. Por exemplo, no Twitter, rede social analisada nesta dissertação, existem diversas aplicações que
facilitam a interacção com o serviço e ajudam os utilizadores a localizar informação do
seu interesse ou a avaliar a popularidade de determinados tópicos de discussão. Alguns
exemplos são:
• Trendistic2 : Apresenta a distribuição, em diferentes escalas temporais, do número
de tweets que contêm determinada palavra introduzida pelo utilizador e permitem
prever a evolução do tópico em questão.
• Twitter Spectrum3 : Apresenta um conjunto de palavras que surgem associadas a 2
tópicos definidos pelo utilizador. Nesta aplicação, a visualização da informação é
bastante intuitiva, sendo que cada palavra é apresentada junto do termo com que
está relacionada. Desta forma, permite comparar as palavras relacionadas com dois
tópicos definidos pelo utilizador.
• TweetVolume4 : Permite comparar o volume de mensagens que contêm cada uma
das 3 palavras definidas pelo utilizador. Desta forma, é possível verificar qual das
três é a mais frequente ou mais popular na rede.
• Twitt(url)y5 : Agrupa os tweets por URL, isto é, todos os tweets que contêm um
mesmo URL são mantidos juntos e ordenados por ordem cronológica. Além disso,
é apresentado o número total de tweets diferentes que mencionaram um determinado
URL, o número total de retweets e o número total de utilizadores que enviaram uma
mensagem com um URL específico.
Como se pode verificar, existem diversas ferramentas para análise do Twitter. No entanto, a caracterização proporcionada pelo “SocialAnalytics” é um pouco mais extensiva
2 http://trendistic.com/
3 http://www.neoformix.com/Projects/TwitterSpectrum/TwitterSpectrum.html
4 http://www.tweetvolume.com/
5 http://twitturly.com/
87
“SocialAnalytics”: ferramenta para análise de redes sociais
do que as ferramentas apresentadas anteriormente. O “SocialAnalytics” proporciona uma
análise da rede através da verificação das propriedades topológicas e ainda providencia
uma forma fácil de caracterizar e monitorizar as comunidades presentes neste serviço de
micro-blogging.
Assim, a aplicação desenvolvida pode ser enquadrada no âmbito das ferramentas de
análise das redes sociais.
5.4
Conclusão
A compreensão da dinâmica das redes é fundamental para o desenvolvimento de novas
aplicações, ambientes colaborativos e sistemas para a localização, organização da informação e obtenção de conhecimento. Por exemplo, a verificação de alguns fenómenos
como a auto-similaridade e as distribuições características (power-law distributions) permitem o desenvolvimento de novos métodos ou estratégias de pesquisa neste tipo de redes
[ALPH01].
Além disso, com a popularidade crescente deste tipo de serviços, é provável que as
redes sociais venham a desempenhar um papel cada vez mais importante no futuro pessoal
de muitos utilizadores e no futuro comercial de diversas organizações.
Hoje em dia a informação é propagada por meio de diferentes tecnologias, e as redes sociais como o Twitter, aceleram a proliferação das mensagens. Desta forma, estas
são um meio de comunicação que começa a ser utilizado por muitas empresas para manterem contacto com consumidores e clientes e desenvolverem novas estratégias de mercado. Trata-se assim, de uma nova maneira de compreender e medir a popularidade dos
seus produtos. Por exemplo, a replicação de dezenas, centenas e até milhares de mensagens enviadas pelos utilizadores podem ser associados em alguns casos a um conceito
denominado de marketing viral de conteúdos. Na realidade, para muitas organizações
torna-se vital a monitorização, a análise e a compreensão das acções e comportamento
dos utilizadores nas redes sociais. Este tipo de serviços têm surgido recentemente e são
conhecidos como Buzz Intelligence.
Assim, o “SocialAnalytics”, desenvolvido com o intuito de proporcionar uma ferramenta para a caracterização dos fenómenos nas redes sociais, pode eventualmente ser
utilizada em diferentes contextos com objectivos diversos revelando-se assim uma ferramenta útil em diferentes domínios de aplicação.
5.5
Sumário
Neste capítulo foi apresentada uma ferramenta para análise das redes sociais. Esta
ferramenta, desenvolvida ao longo de todo este trabalho de investigação foi ainda utilizada
para obter os resultados apresentados no capítulo 3 desta dissertação. Apesar de ter sido
88
“SocialAnalytics”: ferramenta para análise de redes sociais
utilizada para proporcionar uma caracterização detalhada de um subconjunto de dados
do Twitter, esta foi desenvolvida de forma a poder ser utilizada numa colecção de dados
genérica, tal como referido anteriormente.
Assim, neste capítulo, foi apresentado o formato de dados utilizado pela aplicação
bem como as funcionalidades e interface. Além disso, foram descritos alguns sistemas
que permitem efectuar diferentes análises sobre Twitter com o intuito de enquadrar a
aplicação aqui desenvolvida. Por outro lado, foram identificados possíveis domínios onde
a ferramenta poderá ser utilizada.
89
“SocialAnalytics”: ferramenta para análise de redes sociais
90
Capítulo 6
Conclusões e Trabalho Futuro
Neste capítulo é feito um resumo do trabalho desenvolvido sendo descritos os aspectos
mais relevantes e apresentados, de forma sucinta, os resultados obtidos. Além disso, é
feito um balanço das dificuldades e fragilidades encontradas ao longo desta dissertação e
identificadas algumas oportunidades para trabalho futuro.
6.1
Resumo do trabalho
Esta dissertação teve como objectivos principais:
• o estudo intensivo das propriedades das redes sociais;
• a aplicação de métodos que permitem a identificação e caracterização de comunidades através da estrutura de ligações e dos conteúdos de uma rede social;
• a análise da influência de determinados tópicos nas relações sociais e no processo
de comunicação;
• o desenvolvimento de uma aplicação para análise das propriedades de uma rede,
composta por utilizadores do Twitter em Portugal, e para a caracterização de comunidades presentes num conjunto de dados.
Além disso, pretendia-se ainda proporcionar uma descrição sólida e exaustiva de uma
colecção de dados para investigações académicas futuras.
Assim, numa primeira fase começou-se por investigar sobre a detecção automática de
comunidades em redes e observou-se que a maioria dos trabalhos de referência utilizam
métodos de partição de grafos para a descoberta de grupos coesos em redes. Desta forma,
estes trabalhos providenciam à partida uma caracterização superficial das comunidades
através da estrutura de ligações de uma rede.
De seguida, foram investigadas as técnicas de análise de conteúdo e estudadas as etapas no processamento de linguagem natural de forma a perceber como é que o conteúdo
pode ser analisado e utilizado na caracterização das comunidades.
91
Conclusões e Trabalho Futuro
Para além disso, foi feita uma revisão sobre alguns estudos que apresentam características próprias inerentes às redes de comunicação, redes sociais e outras redes do mundo
real, que as distinguem doutro tipo de redes, como por exemplo, as redes aleatórias. Do
trabalho de investigação realizado, resultaram conhecimentos valiosos que serviram de
directrizes no trabalho desenvolvido nesta dissertação.
Outro aspecto importante, é o facto de a colecção de dados utilizada ser constituída por
um conjunto vasto de utilizadores do Twitter em Portugal, o que permite revelar algumas
características sobre a cultura e hábitos dos utilizadores de Portugal na utilização deste
serviço de micro-blogging. Contudo, é de referir, que uma porção considerável do tempo
disponível nesta dissertação foi despendida no estudo das características do conjunto de
dados disponibilizado, de forma a validar os conteúdos dos dados e verificar o carácter
e a representatividade desta colecção no que diz respeito à composição de uma rede social. É de salientar ainda que devido ao volume de dados da colecção, o processamento
da informação e a obtenção de resultados foi um processo lento e moroso que requereu
tempo e paciência e que, por vezes foram necessárias horas no processamento dos dados para os representar num formato mais apropriado de forma a apresentar determinadas
propriedades.
Contudo, o esforço e tempo dedicados foram recompensados pelos resultados obtidos
uma vez que neste trabalho é apresentada uma caracterização exaustiva da rede implícita
nesta colecção e que para além das contribuições apresentadas anteriormente, permitiu
também identificar algumas oportunidades de investigação futuras.
Além da caracterização de um conjunto de dados específico, foi aprofundada a existência de comunidades nas redes sociais e investigada a influência de determinados tópicos
nas relações, na tentativa de perceber os critérios dos utilizadores na selecção da sua rede
de interacção. Além dos resultados obtidos e da aplicação desenvolvida para a caracterização de uma rede social, e para a detecção e caracterização de comunidades nas redes,
este estudo permitiu identificar novas oportunidades para trabalho futuro.
De seguida, é apresentado um resumo dos resultados obtidos e são descritas algumas
oportunidades para trabalho futuro.
6.2
Resultados e Trabalho Futuro
Como referido anteriormente, nesta dissertação foi realizado um estudo sobre um subconjunto de dados do Twitter disponibilizado pelo sapo.pt, e após um tratamento dos dados procedeu-se a uma análise exaustiva das características apresentadas pelos mesmos
e da respectiva rede de interacção implícita na colecção. Os resultados apresentados no
Capítulo 3 confirmam que a colecção utilizada possui características das redes sociais,
como por exemplo, as power-law distributions que são próprias das redes do tipo scalefree e o small-world effect também observado em diversas redes sociais. Por outro lado, os
92
Conclusões e Trabalho Futuro
resultados revelam ainda que as propriedades da rede implícita nesta colecção diferem em
muito das redes aleatórias como se pode verificar pelas distribuições do grau de centralidade dos nós apresentadas na Secção 3.10 e pelos valores médios do clustering coefficient
apresentados na Tabela 3.2. Estes resultados permitiram verificar que esta colecção é um
subconjunto representativo de uma rede social e que não se trata apenas de um conjunto
de dados aleatório.
Além disso, a análise da topologia da rede permitiu verificar a existência de um componente gigante que contém a maioria dos utilizadores. Estes resultados vão de encontro
aos valores apresentados por outros estudos realizados nas redes sociais. Apesar da existência de um componente gigante e de outros componentes mais pequenos na rede, a
utilização de métodos de detecção de cliques e dos métodos de detecção de comunidades,
permitiu salientar a existência de grupos coesos e comunidades nas redes sociais.
No que diz respeito ao comportamento individual dos utilizadores, os valores apresentados revelam que, à semelhança do que ocorre noutras redes sociais, apenas uma percentagem reduzida dos utilizadores é que geram toda a actividade na rede. Ademais, através da
análise de estudos realizados noutras redes sociais, verifica-se que os utilizadores apenas
comunicam com uma percentagem reduzida dos elementos da sua rede e que existe uma
forte correlação entre o número de mensagens enviadas por um utilizador e mensagens
recebidas pelo mesmo. Esta correlação positiva forte pode ser explicada pelas relações
simétricas existentes nas redes e pela tendência de reciprocar a atenção dos outros utilizadores. A observação detalhada destes resultados, permite identificar os utilizadores
mais populares ou pelo contrário, os utilizadores que recebem menos atenção dos outros.
Esta informação pode ser bastante útil para identificar os indivíduos mais influentes numa
rede.
Relativamente aos hábitos de utilização do serviço de micro-blogging por parte da
comunidade portuguesa, uma análise temporal permitiu identificar o período natural de
descanso dos portugueses, sendo este período aquele é que há menos actividade na rede
e que varia entre as 02h e as 08h da manhã. Além disso, revela ainda que o período de
maior utilização deste serviço de micro-blogging ocorre no horário nocturno, após a hora
de jantar, o que pode indicar que as pessoas esperam por um período de tempo livre para
se dedicarem às redes sociais.
Além destes resultados, uma análise do comportamento individual de determinados
utilizadores em particular, revela perfis de utilização diferentes por parte dos utilizadores.
Ademais, permite observar a existência de utilizadores peculiares caracterizados por apresentarem uma distribuição de certa forma regular e que difere da maioria da população.
Esta observação dá origem a uma oportunidade de investigação futura, não aprofundada
nesta dissertação, e que envolve a identificação de utilizadores particulares a partir desta
distribuição como por exemplo, dos utilizadores que publicam conteúdos de forma automática (bots ou spammers).
93
Conclusões e Trabalho Futuro
Outro aspecto importante de referir, foi a verificação da invariância temporal da rede
que permite constatar que os resultados obtidos não diferem radicalmente com as alterações da escala e da amostra utilizada. Esta propriedade, denominada de auto-similaridade
(self-similarity), observada nas redes sociais e nesta colecção de dados, assegura a validade dos dados utilizados e dos resultados obtidos.
Depois de analisadas as propriedades da rede implícita nesta colecção, e verificada a
validade dos dados e ainda a existência de comunidades na rede, foram realizadas experiências para analisar a influência dos tópicos nas redes. Assim, foi colocada a hipótese de
que os utilizadores interagem com a sua rede independentemente do tópico em discussão,
permitindo assim verificar a necessidade da análise dos conteúdos das redes no processo
de segmentação dos utilizadores por tópicos de interesse. Através da recolha de três
tópicos distintos, e da análise das redes obtidas para cada um dos tópicos demonstra-se,
através dos resultados obtidos no Capítulo 4, que o carácter social da rede é muito relevante, não existindo uma tendência muito acentuada dos utilizadores para separar a sua
rede egocêntrica considerando os tópicos discutidos. Contudo, verifica-se também que
à medida que a rede egocêntrica de um utilizador cresce, este tem uma tendência maior
para separar a sua rede por tópicos. Estes resultados poderão, eventualmente, ser utilizados em trabalhos futuros num processo de classificação dos utilizadores constituindo
uma característica que, conjuntamente com outras, permitirá distinguir diferentes perfis
de utilizadores nas redes sociais.
Por outro lado, apesar dos resultados indicarem que os utilizadores com mais ligações
têm tendência maior para distinguir as suas ligações, salientamos que o procedimento de
avaliação utilizado é passível de melhoramentos a curto prazo podendo ser mais aprofundado. Ademais, é de salientar que surgem daqui novas oportunidades para trabalho
futuro. Por exemplo, um primeiro aspecto a considerar, prende-se com o facto de serem
utilizados apenas três tópicos. Assim, em trabalho futuro, podem ser analisados mais
tópicos existindo ainda a possibilidade de confrontar tópicos sazonais com tópicos mais
permanentes e mais debatidos na sociedade portuguesa. Além disso, para o processo de
segmentação da rede e de recolha das mensagens por tópicos podem ser utilizadas algumas das técnicas descritas na revisão da literatura como o caso dos classificadores SVM
ou das técnicas de modelação por tópicos como o LDA.
Para concluir, após evidenciada a existência de comunidades nas redes sociais e realizada alguma investigação acerca da influência dos tópicos nas relações, foi ainda desenvolvida uma aplicação que permite a análise e monitorização de uma rede social genérica
através da detecção de comunidades e da caracterização das mesmas por meio dos conteúdos gerados pela comunidade. A caracterização das comunidades através de uma ferramenta como o “SocialAnalytics”, permite em alguns casos identificar os tópicos abordados por cada comunidade como pretende ilustrar a Figura 5.3 do Capítulo 5.
Como referido no Capítulo 5, a análise das redes sociais e o surgimento de ferramentas
94
Conclusões e Trabalho Futuro
deste tipo, tem impacto em diferentes áreas disciplinares uma vez que estas podem ser
utilizadas em diferentes domínios. Por exemplo, para muitas organizações torna-se vital
a monitorização, a análise e a compreensão das acções e comportamento dos utilizadores
nas redes sociais e como tal, ferramentas deste tipo podem ser adequadas para definir
novas estratégias de marketing e publicidade.
Por outro lado, os resultados revelados neste trabalho de investigação podem servir
para impulsionar o desenvolvimento de novos métodos de pesquisa devido às características próprias das redes e/ou novos sistemas de recomendação através da análise combinada
da rede e dos conteúdos.
95
Conclusões e Trabalho Futuro
96
Referências
[AE99]
Kjersti Aas e Line Eikvil. Text categorisation: A Survey Technical Report.
Norwegian Computing Center. Oslo, 1999.
[AK08]
Michelle Annett e Grzegorz Kondrak. A comparison of sentiment analysis
techniques: Polarizing movie blogs. In Advances in Artificial Intelligence,
pages 25–35. 2008.
[ALPH01]
L. A Adamic, R. M Lukose, A. R Puniyani e B. A Huberman. Search in
Power-Law networks. cs/0103016, March 2001. Phys. Rev. E 64, 046135
(2001).
[AM07]
Zeinab Abbassi e Vahab S. Mirrokni. A recommender system based on local random walks and spectral methods. In Proceedings of the 9th WebKDD
and 1st SNA-KDD 2007 workshop on Web mining and social network analysis, pages 102–108, San Jose, California, 2007. ACM.
[BB05]
James P Bagrow e Erik M Bollt. Local method for detecting communities.
Physical Review. E, Statistical, Nonlinear, and Soft Matter Physics, 72(4 Pt
2), October 2005.
[BE07]
Danah Boyd e Nicole Ellison. Social network sites: Definition, history, and
scholarship. Journal of Computer-Mediated Communication, 13(1), 2007.
[BGL10]
Danah Boyd, Scott Golder e Gilad Lotan. Tweet, tweet, retweet: Conversational aspects of retweeting on twitter. In HICSS-43. IEEE, 2010.
[BNJ03]
David M Blei, Andrew Y Ng e Michael I Jordan. Latent dirichlet allocation.
Journal of Machine Learning Research, 3:993–1022, 2003.
[Bor05]
Stephen P. Borgatti.
27(1):55–71, 2005.
[Car06]
Paula Carvalho. Análise e Representação de Construções Adjectivais para
Processamento Automático de Texto. lecture, Faculdade de Ciências da Universidade de Lisboa, October 2006.
[CH89]
Kenneth Ward Church e Patrick Hanks. Word association norms, mutual
information, and lexicography. pages 22–29. Computational Linguistics
v.16 n.1, March 1989.
[CNM04]
Aaron Clauset, M.E.J Newman e Cristopher Moore. Finding community
structure in very large networks. Physical Review. E, Statistical, Nonlinear,
and Soft Matter Physics, 70, December 2004.
Centrality and network flow.
97
Social Networks,
REFERÊNCIAS
[CSCC04]
Andrea Capocci, Vito D. P Servedio, Guido Caldarelli e Francesca Colaiori.
Detecting communities in large networks. cond-mat/0402499, February
2004.
[CZG09]
Jiyang Chen, Osmar R. Zaiane e Randy Goebel. Detecting communities in
large networks by iterative local expansion. In Proceedings of the 2009
International Conference on Computational Aspects of Social Networks,
pages 105–112. IEEE Computer Society, 2009.
[DA05]
Jordi Duch e Alex Arenas. Community detection in complex networks using
extremal optimization. Physical Review E, 72(2):027104, 2005.
[Den98]
Peter J. Denning. The internet after thirty years. In Internet besieged: countering cyberspace scofflaws, pages 15–27. ACM Press/Addison-Wesley
Publishing Co., 1998.
[Deo74]
Narsingh Deo. Graph Theory with Applications to Engineering and Computer Science. Prentice Hall, May 1974.
[DM04]
Luca Donetti e Miguel A Munoz. Detecting network communities: a new
systematic and efficient algorithm. cond-mat/0404652, April 2004. J. Stat.
Mech. (2004) P10012.
[DPHS98]
Susan Dumais, John Platt, David Heckerman e Mehran Sahami. Inductive
learning algorithms and representations for text categorization. In Proceedings of the seventh international conference on Information and knowledge
management, pages 148–155, Bethesda, Maryland, United States, 1998.
ACM.
[dSEdLE09] Cristian Klen dos Santos, Alexandre Gonçalves Evsukoff, Beatriz S.L.P.
de Lima e Nelson Francisco Favilla Ebecken. Potential collaboration discovery using document clustering and community structure detection. In
Proceeding of the 1st ACM international workshop on Complex networks
meet information & knowledge management, pages 39–46, Hong Kong,
China, 2009. ACM.
[DWP+ 07]
Nan Du, Bin Wu, Xin Pei, Bai Wang e Liutong Xu. Community detection
in large-scale social networks. In Proceedings of the 9th WebKDD and
1st SNA-KDD 2007 workshop on Web mining and social network analysis,
pages 16–25, San Jose, California, 2007. ACM.
[EM02]
Jean-Pierre Eckmann e Elisha Moses. Curvature of co-links uncovers hidden thematic layers in the world wide web. Proceedings of the National
Academy of Sciences of the United States of America, 99(9):5825–5829,
April 2002.
[Eve05]
Stefan Evert. The Statistics of Word Cooccurrences: Words Pairs and Collocations. PhD thesis, Stuttgart University, Stuttgart, 2005.
[FLM04]
Santo Fortunato, Vito Latora e Massimo Marchiori. Method to find community structures based on information centrality. Physical Review E,
70(5):056104, November 2004.
98
REFERÊNCIAS
[For10]
Santo Fortunato. Community detection in graphs. Physics Reports, 486(35):75 – 174, 2010.
[FRM07]
Blaz Fortuna, Eduarda Mendes Rodrigues e Natasa Milic-Frayling. Improving the classification of newsgroup messages through social network
analysis. In Proceedings of the sixteenth ACM conference on Conference
on information and knowledge management, pages 877–880, Lisbon, Portugal, 2007. ACM.
[GA05]
Roger Guimera e Luis A. Nunes Amaral. Functional cartography of complex metabolic networks. Nature, 433(7028):895–900, February 2005.
[GAD+ 04]
Roger Guimera, Alex Arenas, Leon Danon, Albert Diaz-Guilera e Pablo M
Gleiser. Community analysis in social networks. cond-mat/0312040, May
2004.
[GDD+ 03]
R Guimerà, L Danon, A Díaz-Guilera, F Giralt e A Arenas. Self-similar
community structure in a network of human interactions. Physical Review.
E, Statistical, Nonlinear, and Soft Matter Physics, 68, December 2003.
[Ger09]
Bouma Gerlof. Normalized (pointwise) mutual information in collocation
extraction. In Chiarcos Eckart de Castilho & Stede, From Form to Meaning:
Processing Texts Automatically, page 3140. Proc. of the Biennial GSCL
Conference, 2009.
[GK09]
Eric Gilbert e Karrie Karahalios. Predicting tie strength with social media.
In Proceedings of the 27th international conference on Human factors in
computing systems, pages 211–220, Boston, MA, USA, 2009. ACM.
[GN02]
M. Girvan e M. E. J. Newman. Community structure in social and biological
networks. Proceedings of the National Academy of Sciences of the United
States of America, 99(12):7821–7826, June 2002.
[Gre07]
Steve Gregory. An algorithm to find overlapping community structure in
networks. In Proceedings of the 11th European Conference on Principles
and Practice of Knowledge Discovery in Databases (PKDD 2007), pages
102, 91. Springer-Verlag, 2007.
[GWH07]
Scott A Golder, Dennis M Wilkinson e Bernardo A Huberman. Rhythms of
social interaction: Messaging within a massive online network. Proc. 3rd
Intl. Conf. on Communities and Technologies, 2007.
[HFS08]
Tâm Huynh, Mario Fritz e Bernt Schiele. Discovery of activity patterns
using topic models. In Proceedings of the 10th international conference on
Ubiquitous computing, pages 10–19, Seoul, Korea, 2008. ACM.
[HRW08]
Bernardo Huberman, Daniel Romero e Fang Wu. Social networks that matter: Twitter under the microscope. Social Science Research Network Working Paper Series, 2008.
99
REFERÊNCIAS
[HSS10]
Derek Hansen, Ben Shneiderman e Marc A. Smith. Barash Vladimir,
Golder Scott, Twitter: Conversation, Entertainment, and Information, All
in One in Analyzing Social Media Networks with NodeXL: Insights from a
Connected World. Morgan Kaufmann, September 2010.
[JM00]
Daniel Jurafsky e James H. Martin. Speech and Language Processing: An
Introduction to Natural Language Processing, Computational Linguistics
and Speech Recognition. Prentice Hall, 1 edition, February 2000.
[Joa98]
Thorsten Joachims. Text categorization with support vector machines:
Learning with many relevant features. In Machine Learning: ECML-98,
pages 137–142. 1998.
[JSFT07]
Akshay Java, Xiaodan Song, Tim Finin e Belle Tseng. Why we twitter:
understanding microblogging usage and communities. In Proceedings of
the 9th WebKDD and 1st SNA-KDD 2007 workshop on Web mining and
social network analysis, pages 56–65, San Jose, California, 2007. ACM.
[KLPM10]
Haewoon Kwak, Changhyun Lee, Hosung Park e Sue Moon. What is Twitter, a social network or a news media? In WWW ’10: Proceedings of the
19th international conference on World wide web, pages 591–600, New
York, NY, USA, 2010. ACM.
[KNT06]
Ravi Kumar, Jasmine Novak e Andrew Tomkins. Structure and evolution of
online social networks. In Proceedings of the 12th ACM SIGKDD international conference on Knowledge discovery and data mining, pages 611–617,
Philadelphia, PA, USA, 2006. ACM.
[KR96]
Jon Kleinberg e Ronitt Rubinfeld. Short paths in expander graphs. Proceedings of the 37th annual Symposium on Foundations of Computer Science,
pages 86–95, 1996.
[LAT+ 05]
Lun Li, David Alderson, Reiko Tanaka, John C Doyle e Walter Willinger.
Towards a theory of Scale-Free graphs: Definition, properties, and implications (Extended version). January 2005.
[LSY03]
G. Linden, B. Smith e J. York. Amazon.com recommendations: item-toitem collaborative filtering. Internet Computing, IEEE, 7(1):76–80, 2003.
[Mik07]
Peter Mika. Social Networks and the Semantic Web. Springer, 1 edition,
September 2007.
[MMG+ 07] Alan Mislove, Massimiliano Marcon, Krishna Gummadi, Peter Druschel e
Bobby Bhattacharjee. Measurement and analysis of online social networks.
In IMC ’07: Proceedings of the 7th ACM SIGCOMM conference on Internet
measurement, pages 29–42, San Diego, California, USA, 2007. ACM.
[MMN02]
Prem Melville, Raymond J Mooney e Ramadass Nagarajan. ContentBoosted collaborative filtering for improved recommendations. In Eighteenth National Conference on Artificial Intelligence, pages 187—192,
2002.
100
REFERÊNCIAS
[Mor53]
Jacob Moreno. Who Shall Survive?: Foundations of Sociometry, Group
Psychotherapy, and Sociodrama. New York: Beacon House, 1953.
[MR95]
Michael Molloy e Bruce Reed. A critical point for random graphs with a
given degree sequence. In Proceedings of the sixth international seminar
on Random graphs and probabilistic methods in combinatorics and computer science, pages 161–179, Pozna & Nacute, Poland, 1995. John Wiley
& Sons, Inc.
[MRC00]
Michael Molloy, Bruce Reed e Equipe Combinatoire. The size of the giant component of a random graph with a given degree sequence. Combin.
Probab. Comput, 7:295–305, 2000.
[MS99]
Christopher D. Manning e Hinrich Schuetze. Foundations of Statistical Natural Language Processing. The MIT Press, 1 edition, June 1999.
[MSST07]
Nina Mishra, Robert Schreiber, Isabelle Stanton e Robert Tarjan. Clustering
social networks. In Algorithms and Models for the Web-Graph, pages 56–
67. 2007.
[MWC07]
Andrew Mccallum, Xuerui Wang e Andres Corrada-Emmanuel. Topic and
role discovery in social networks with experiments on enron and academic
email. Journal of Artificial Intelligence Research, 30:272, 249, 2007.
[New00]
M. E. J Newman. Models of the small world: A review. January 2000. J.
Stat. Phys. 101, 819-841 (2000).
[New03]
M. E. J Newman. The structure and function of complex networks. SIAM
Review, 45(2):167–256, March 2003. SIAM Review 45, 167-256 (2003).
[NG03]
M. E. J Newman e M. Girvan. Finding and evaluating community structure
in networks. cond-mat/0308217, August 2003. Phys. Rev. E 69, 026113
(2004).
[OCL08]
Kazuya Okamoto, Wei Chen e Xiang-Yang Li. Ranking of closeness centrality for Large-Scale social networks. In Frontiers in Algorithmics, pages
186–195. 2008.
[PBMW98] Larry Page, Sergey Brin, R. Motwani e T. Winograd. The PageRank citation
ranking: Bringing order to the web, 1998.
[PDFV05]
Gergely Palla, Imre Derényi, Illés Farkas e Tamás Vicsek. Uncovering the
overlapping community structure of complex networks in nature and society. Nature, 435(7043):814–818, June 2005.
[Piz09]
Clara Pizzuti. Overlapped community detection in complex networks. In
Proceedings of the 11th Annual conference on Genetic and evolutionary
computation, pages 859–866, Montreal, Québec, Canada, 2009. ACM.
[PL05]
Pascal Pons e Matthieu Latapy. Computing communities in large networks
using random walks (long version). physics/0512106, December 2005.
101
REFERÊNCIAS
[RB04]
Jörg Reichardt e Stefan Bornholdt. Detecting fuzzy community structures
in complex networks with a potts model. Physical Review Letters, 93(21),
November 2004.
[RCC+ 04]
Filippo Radicchi, Claudio Castellano, Federico Cecconi, Vittorio Loreto e
Domenico Parisi. Defining and identifying communities in networks. Proceedings of the National Academy of Sciences of the United States of America, 101(9):2658–2663, March 2004.
[rLSC+ 06]
Yu ru Lin, Hari Sundaram, Yun Chi, Jun Tatemura e Belle Tseng. Discovery
of blog communities based on mutual awareness. In Proceedings of the
WWW06 Workshop on Web Intelligence, 2006.
[RZ07]
Jianhua Ruan e Weixiong Zhang. An efficient spectral algorithm for network community discovery and its applications to biological and social networks. In Proceedings of the 2007 Seventh IEEE International Conference
on Data Mining, pages 643–648. IEEE Computer Society, 2007.
[Sco00]
John Scott. Social Networks Analysis: a handbook. SAGE Publications
Ltd, second edition, 2000.
[SGL+ 07]
Mark Steyvers, Tom Griffiths, T Landauer, D Mcnamara, S Dennis e
W Kintsch. Probabilistic topic models. In Handbook of Latent Semantic
Analysis. Lawrence Erlbaum Associates, 2007.
[SHM05]
Chaoming Song, Shlomo Havlin e Hernan A. Makse. Self-similarity of
complex networks. Nature, 433(7024):392–395, January 2005.
[Sig09]
Mark Sigal. Pattern recognition: Makers, marketplaces and the library of
the commons. Website, 2009. acedido em Maio 2010.
[SK09]
Xiaoyuan Su e Taghi Khoshgoftaar. A survey of collaborative filtering techniques. Advances in Artificial Intelligence, 2009:20, 1, 2009.
[SXW+ 06] Qi Su, Kun Xiang, Houfeng Wang, Bin Sun e Shiwen Yu. Using pointwise mutual information to identify implicit features in customer reviews.
In Computer Processing of Oriental Languages. Beyond the Orient: The
Research Challenges Ahead, pages 22–30. 2006.
[Tar72]
Robert Tarjan. Depth-First search and linear graph algorithms. SIAM Journal on Computing, 1(2):146–160, June 1972.
[TT04]
Ville H. Tuulos e Henry Tirri. Combining topic models and social networks
for chat data mining. In Proceedings of the 2004 IEEE/WIC/ACM International Conference on Web Intelligence, pages 206–213. IEEE Computer
Society, 2004.
[Tur08]
Ryan Turner. Web social architecture: A conceptual map of the social web.
Website, 2008. acedido em Maio 2010.
[vL07]
Ulrike von Luxburg. A tutorial on spectral clustering. Statistics and Computing, 17(4):395–416, December 2007.
102
REFERÊNCIAS
[VMCG09] Bimal Viswanath, Alan Mislove, Meeyoung Cha e Krishna P. Gummadi.
On the evolution of user interaction in facebook. In Proceedings of the 2nd
ACM workshop on Online social networks, pages 37–42, Barcelona, Spain,
2009. ACM.
[WBS+ 09]
Christo Wilson, Bryce Boe, Ra Sala, Krishna P. N Puttaswamy e Ben Y
Zhao. User interactions in social networks and their implications. in ACM
Eurosys, 2009.
[WF94]
Stanley Wasserman e Katherine Faust. Social Network Analysis: Methods
and Applications. Cambridge University Press, 1 edition, November 1994.
[WH04]
F. Wu e B.A. Huberman. Finding communities in linear time: a physics
approach. The European Physical Journal B, 38(2):8, 2004.
[WS05]
Scott White e Padhraic Smyth. A spectral clustering approach to finding
communities in graphs. Proc. SIAM Int’l Conf. Data Mining (SDM ’05),
2005.
[WT07]
Ken Wakita e Toshiyuki Tsurumi. Finding community structure in megascale social networks. cs/0702048, February 2007.
[XCK+ 09]
K. Xu, Y. Chen, M. Kliger, P. Wolfe e A.O. Hero. Revealing social networks
of spammers through spectral clustering. In IEEE Intl Conf on Communications (ICC), Dresden, June 2009.
[XTT+ 05]
Yongxiang Xia, Chi K Tse, Wai Man Tam, Francis C. M Lau e Michael
Small. Telephone traffic analysis based on a scale-free user network. International Symposium on Nonlinear Theory and its Applications (NOLTA’05,
pages 110–113, 2005.
[YCS09]
Tae Yano, William W. Cohen e Noah A. Smith. Predicting response to
political blog posts with topic models. In Proceedings of Human Language
Technologies: The 2009 Annual Conference of the North American Chapter
of the Association for Computational Linguistics, pages 477–485, Boulder,
Colorado, 2009. Association for Computational Linguistics.
[ZL04]
Haijun Zhou e Reinhard Lipowsky. Network brownian motion: A new
method to measure Vertex-Vertex proximity and to identify communities
and subcommunities. In Computational Science - ICCS 2004, pages 1062–
1069. 2004.
103
REFERÊNCIAS
104
Anexo A
“SocialAnalytics”: Manual do
Utilizador
Como referido anteriormente, a aplicação dispõe de uma área de configuração dos
parâmetros na qual o utilizador poderá indicar o número mínimo de actos de comunicação que dois utilizadores têm de estabelecer para que seja definida uma ligação entre
eles no grafo de interacção social apresentado no primeiro separador (“Social Graph”).
Além do número mínimo de comunicações entre os membros da rede, o utilizador deverá
indicar o tamanho mínimo dos componentes conexos que serão apresentados no separador
“Social Graph” podendo desta forma “ignorar” os componentes mais pequenos e efectuar
uma análise focada no componente gigante da rede e nos componentes que apresentem
tamanhos mais consideráveis para o utilizador.
Ainda na secção de configuração o utilizador deverá indicar o intervalo de tempo
correspondente à análise que irá efectuar.
Assim, após indicar os parâmetros e pressionar o botão “Generate” do primeiro separador (“Social Graph”), é apresentado um grafo não dirigido que corresponde ao grafo
das interacções entre os membros da rede no intervalo de tempo indicado. Além disso, é
apresentada também a respectiva tagcloud que resume os conteúdos da rede no intervalo
de tempo seleccionado. Neste separador, o utilizador dispõe também da possibilidade de
navegar entre todos os componentes conexos da rede. Por exemplo, como representado
na Figura A.1, o utilizador pode seleccionar um dos 15 componentes conexos existentes
no grafo que foi obtido para o intervalo de 17 de Março de 2010 e 24 de Março de 2010.
É importante referir que a qualquer momento pode ser efectuada a detecção de comunidades no grafo. Para isso, deverá seleccionar um dos algoritmos disponíveis (WakitaTsurumi e ClausetNewmanMoore) e pressionar o botão “Get Clusters”. Para além disso,
e após obter os clusters que se encontram representados por cores e símbolos diferentes,
o utilizador tem a possibilidade de obter a tagcloud referente a uma comunidade específica. Para tal, deverá seleccionar pelo menos um utilizador da comunidade (cluster) para a
qual pretende obter o resumo dos conteúdos e pressionar o botão “Get Tag Cloud”. Além
destas funcionalidades, o utilizador pode ainda “redesenhar” o componente que está a visualizar sendo alterada a disposição dos utilizadores no componente respectivo (layout).
105
“SocialAnalytics”: Manual do Utilizador
Figura A.1: Exemplo da interface: grafo de interacção
No separador com o título “Graph Structure”, o utilizador poderá analisar a estrutura
da rede social (grafo de interacção) através da apresentação da distribuição dos componentes conexos da rede. Ademais, pode ainda verificar a existência de comunidades coesas na rede através das distribuição dos tamanhos das comunidades detectadas por ambos
os algoritmos já enunciados (Wakita-Tsurumi e ClausetNewmanMoore) e da detecção de
cliques no grafo de interacção. A Figura A.2 apresenta os gráficos que permitem efectuar
uma análise sobre a composição da rede.
106
“SocialAnalytics”: Manual do Utilizador
Figura A.2: Exemplo da interface: análise da estrutura da rede
No separador “General Stats”, como exemplificado na Figura A.3, é apresentada uma
análise quantitativa sobre o número de mensagens (tweets) e de utilizadores envolvidos
na rede no intervalo de tempo definido.
Figura A.3: Exemplo da interface: análise quantitativa da rede (número de utilizadores e mensagens)
107
“SocialAnalytics”: Manual do Utilizador
Relativamente aos separadores “Daily Analysis” e “Hourly Analysis”, estes apresentam uma análise diária e horária da actividade da rede. Assim, é detalhando o número de
utilizadores e de mensagens enviadas por dia e por hora do dia respectivamente, como se
pode verificar pelas Figuras A.4 e A.5.
Figura A.4: Exemplo da interface: análise diária da actividade da rede
Figura A.5: Exemplo da interface: análise horária da actividade da rede
108
“SocialAnalytics”: Manual do Utilizador
Além das distribuições apresentadas, é possível contabilizar o número de utilizadores
diferentes com quem as pessoas interagem na rede. Assim, no separador “User Interaction”, é apresentado o número de utilizadores com quem as pessoas comunicam (número
de pessoas a quem respondem + número de pessoas de quem recebem respostas).
Por outro lado, é possível quantificar através da análise de um grafo dirigido, o número
de utilizadores distintos a quem as pessoas respondem e o número distinto de utilizadores
de quem recebem respostas. Neste caso, o utilizador pode ainda visualizar ambas as distribuições em simultâneo, permitindo uma comparação visual, ou então, visualizar apenas
uma delas seleccionando as checkboxes respectivas.
Além disso, o utilizador tem a possibilidade de comparar a distribuição do grau de
centralidade das pessoas na rede em estudo, com a distribuição do grau de centralidade
dos utilizadores numa rede aleatória construída com o mesmo número de utilizadores e
ligações da rede em estudo.
Figura A.6: Exemplo da interface: análise da interacção entre utilizadores
Além da análise do número de utilizadores distintos com quem as pessoas interagem,
é possível efectuar uma análise semelhante no que diz respeito aos actos de comunicação
entre os utilizadores: número de respostas enviadas e número de respostas recebidas.
Ademais, é também apresentada a correlação entre o número de respostas enviadas pelos utilizadores e o número de respostas recebidas pelos mesmos. De notar ainda que,
através da análise da intensidade dos actos de comunicação, o utilizador tem a possibilidade de “encontrar” um valor adequado para o valor mínimo de comunicações entre os
utilizadores definido na secção de selecção dos parâmetros. Desta forma, o utilizador
tem a possibilidade de remover da sua análise, ligações resultantes de comunicações “esporádicas”.
109
“SocialAnalytics”: Manual do Utilizador
Figura A.7: Exemplo da interface: análise do fluxo de respostas da rede
Para finalizar, no separador “Top Users” é possível analisar o comportamento individual dos utilizadores que mais tweets enviaram no período definido. O número de
utilizadores apresentados é definido pelo utilizador e são apresentados numa tabela os
identificadores respectivos e o número total de tweets enviados. Além disso, é a apresentada a distribuição horária agregada pelos dias correspondentes à análise efectuada, sendo
possível assim identificar utilizadores peculiares. De referir, que o utilizador tem a possibilidade de colocar visível ou invisível qualquer uma das distribuições apresentadas pelos
utilizadores. Para tal, bastará fazer um duplo clique na linha da tabela correspondente
ao utilizador. Desta forma, é possível comparar distribuições diferentes permitindo assim
comparar os comportamentos dos utilizadores mais activos.
110
“SocialAnalytics”: Manual do Utilizador
Figura A.8: Exemplo da interface: análise do comportamento dos utilizadores mais activos
É importante referir que os gráficos apresentados são idênticos aos apresentados nas
análises efectuadas no capítulo 3 desta dissertação.
Por outro lado, é importante ainda referir que o “SocialAnalytics” foi desenvolvido na
linguagem de programação C# com auxílio das bibliotecas NodeXL1 , uma biblioteca para
análise, representação e manipulação de redes, e da bibioteca ZedGraph2 , uma biblioteca
para a manipulação e representação de gráficos em C#.
Desta forma, o SocialAnalytics é uma ferramenta que padece de possíveis melhorias
a curto prazo. No entanto, é uma aplicação que possibilita a análise das propriedades
básicas das redes sociais e das redes de comunicação, e ainda, uma análise e caracterização combinada, através da esturura e conteúdo da rede, das sub-comunidades que nela se
formam.
1 http://nodexl.codeplex.com/
2 http://zedgraph.org/wiki/index.php
111