Artigo SQL Magazine 39 - Modelando redes sociais - Parte 1

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."