alt="" hspace=0 src="/loja/img/Capa_SQL39_G.gif" align=bottom border=0>

Clique aqui para ler todos os artigos desta edição

Modelando redes sociais - Parte 1

 

Este artigo aborda a modelagem de uma Rede Social, como as redes virtuais de sites de relacionamentos do Orkut e do MySpace. As principais tabelas do modelo são apresentadas como uma pequena revisão da teoria dos grafos. Tanto o modelo de tabelas como as operações sobre os dados são apresentadas sob o ponto de vista de um banco de dados, sem se preocupar em apresentar detalhes de implementação na aplicação que interage com os dados. Na primeira parte deste artigo veremos uma rede de relacionamentos de exemplo e o modelo que armazena uma rede social genérica. Na segunda parte será apresentada a implementação de alguns algoritmos para navegação na rede social.

Redes Sociais

Uma possível definição de redes sociais baseia-se no conceito de redes de relacionamentos virtuais. Este tipo de rede tem como objetivo ligar as pessoas que possuem algum grau de afinidade além de proporcionar que estas pessoas interajam entre si. A ligação entre usuários que a rede proporciona pode ser representada por algum tipo de aspecto que relacione as pessoas com, por exemplo, interesses em comum, familiaridades, compartilhamento de algum tipo de trabalho ou até mesmo por simples casualidade.

Talvez o exemplo mais comum de Rede de Relacionamento seja o Orkut. Febre no Brasil, esta rede conseguiu alcançar índices de participação até então inéditos para uma aplicação deste tipo. Basta cadastrar um perfil por meio de uma série de perguntas não obrigatórias e sair à procura de relacionamentos ou comunidades para interagir com outras pessoas que já possuem perfil cadastrado. Adicione a esta Rede de Relacionamentos a capacidade de enviar mensagens, a possibilidade de publicação de um conjunto limitado de fotos e uma interface gráfica simples para transformar a aplicação em um fenômeno nunca antes visto na internet brasileira.

Em termos técnicos, este tipo de aplicação não apresenta grande complexidade. Na verdade, o grande trunfo não está na beleza ou na quantidade de funcionalidades mirabolantes da aplicação, mas sim na facilidade com que a rede se expande. No final das contas, o que importa mesmo não é a tecnologia utilizada na aplicação, mas sim a sua capacidade em agregar usuários e tornar o uso da aplicação cada vez mais popular.

Neste artigo discutiremos como implementar uma rede social, sob o ponto de vista do banco de dados. Porém, apenas a parte de gerenciamento de relações entre os usuários e algumas operações de navegação entre eles será abordada. A parte dinâmica deste tipo de aplicação, que envolve o gerenciamento de comunidades, o envio de mensagens e outras funcionalidades, não será discutida. O leitor que possuir interesse pelo aspecto dinâmico desta aplicação pode facilmente encontrar diversas soluções prontas e amplamente utilizadas que estão disponíveis na internet.

Um pouco de teoria dos Grafos

Para entender como funciona a organização e o gerenciamento dos usuários em uma Rede de Relacionamento, é útil pensar em alguma teoria que possa fornecer um suporte para tal tarefa. Uma abordagem comum para este tipo de aplicação se baseia na teoria dos Grafos.

De maneira simples, pode-se dizer que um grafo é uma estrutura baseada em dois conjuntos de elementos: um conjunto de vértices e outro de arestas. Utiliza-se a notação G(V,E) para identificar um grafo G que possui um conjunto de vértices V e um conjunto de arestas (edges) E.

Faz sentido pensar em grafos para representar uma Rede de Relacionamentos. Se pensarmos que cada perfil pode ser representado por um vértice e o relacionamento entre dois perfis representado por uma aresta, fica fácil utilizar toda a bagagem teórica que os grafos proporcionam. Deste modo, toda a estrutura de uma Rede de Relacionamentos pode ser representada por meio dos conjuntos de vértices e arestas. Para evitar confusões, este artigo utiliza o termo perfil no lugar de vértice e o termo relacionamento para se referir a uma aresta de um grafo.

A teoria dos grafos vem sendo estudada a um bom tempo. Com isso temos a vantagem de poder contar com um conjunto grande de referências, algoritmos, aplicações e visualizações para nossa Rede de Relacionamentos. Vamos ver um exemplo de uma pequena rede de relacionamento que será utilizada durante o artigo.

Suponha que tenhamos seis perfis cadastrados na nossa rede de Relacionamento: Mauro, Leda, Erika, Maike, Edilson e Aline. Deste modo, o conjunto V seria o seguinte: V = {Aline, Erika, Leda, Mauro, Maike, Edilson}. Agora vamos supor que estes perfis se relacionam da seguinte maneira:

·         Mauro é amigo de todos os perfis;

·         Leda é amiga apenas dos perfis Mauro, Erika, Maike e Edilson;

·         Erika é amiga apenas dos perfis Mauro, Leda e Aline;

·         Maike é amigo apenas dos perfis Mauro, Leda, Edilson;

·         Edilson é amigo apenas dos perfis Mauro, Leda e Maike;

·         Aline é amiga apenas dos perfis Mauro, Érika.

 

O conjunto E, contendo os relacionamentos dos perfis do conjunto V, armazenará os pares de relacionamentos entre duas pessoas sem se preocupar com a ordem. Então E = {(Mauro,Leda), (Mauro,Erika), (Mauro,Maike), (Mauro,Edilson), (Mauro,Aline), (Leda,Erika), (Leda,Maike), (Leda,Edilson), (Erika,Aline), (Maike,Edilson)}.  Como o relacionamento de amizade é bidirecional, ou seja, se uma pessoa A é amiga de uma pessoa B obrigatoriamente B é amigo de A, temos que o relacionamento entre A e B pode ser indicado apenas com uma relação no conjunto E.

Existem várias estruturas de dados utilizadas para armazenar os dados de um grafo. As mais comuns são matrizes e listas de adjacências. Existe ainda a abordagem que segue os princípios da orientação a objeto, onde a modelagem do armazenamento do grafo faz uso de classes relacionadas por meio da composição. É importante notar que a estrutura de dados chamada árvores, sejam elas binárias, rubro-negras ou de qualquer tipo, são consideradas grafos especiais e também podem ser armazenadas utilizando as mesmas estruturas de dados que os grafos.

As diversas operações feitas sobre grafos não dependem diretamente da maneira na qual o grafo foi implementado. Isso se deve ao fato de que estas operações geralmente são descritas em alto nível, sem levar em consideração as operações atômicas, como visitar um vértice ou remover uma aresta. Deste modo, a descrição da operação é separada da implementação, permitindo um alto grau de abstração na manipulação dos elementos que compõem o grafo. Por exemplo, na utilização de árvores binárias, que são representadas por grafos contendo valores numéricos em cada vértice, podemos descrever o algoritmo para a inclusão de um novo nó (vértice) da seguinte maneira:

 

Se a árvore está vazia, então inclua um novo nó neste ponto. Senão, faça o seguinte:

a) Se o novo dado for menor que o dado da raiz, inclua-o na sub-árvore Esquerda

b) Se o novo dado for maior que o dado da raiz, inclua-o na sub-árvore Direita

 

Note que no algoritmo estão descritas apenas operações abstratas, como a inserção de um nó. Ou seja, estas são apresentadas sem a necessidade de descrever passo a passo como efetivamente esta operação será implementada.

A partir dos dados do grafo de exemplo podemos montar várias visualizações dos relacionamentos. A Figura 1 apresenta os dados do grafo formatados como um mapa mental (mind map), a Figura 2 apresenta os dados na forma de uma árvore hiperbólica, a Figura 3 apresenta os dados em forma de um grafo bidimensional, a Figura 4 apresenta os dados em forma de um grafo tridimensional e a Figura 5 apresenta os dados em forma de um mapa conceitual (CMAP). A Figura 6 apresenta a lista de imagens ligando os perfis do exemplo.

Cada representação do grafo tem uma função específica e permite que o usuário interaja com o grafo através da modificação da posição dos vértices para visualizar melhor a rede. Os mapas mentais são mais úteis para a separação dos relacionamentos em torno de uma idéia central. As árvores hiperbólicas representam as informações na forma de uma árvore circular com o objetivo de visualizar as informações em torno de um vértice que sempre fica no centro.

A visualização bidimensional de um grafo é a mais tradicional e realça a noção de ligação entre os vértices. Já a representação tridimensional do grafo permite destacar o foco dos vértices colocando ...

Quer ler esse conteúdo completo? Seja um assinante e descubra as vantagens.
  • 473 Cursos
  • 10K Artigos
  • 100 DevCasts
  • 30 Projetos
  • 80 Guias
Tenha acesso completo