Motivação e Origem dos Dados
Como estudantes de Engenharia de Computação e Informação, somos apaixonados por grafos e seus algoritmos. Acreditamos que este tipo de abstração é muito poderosa e nos permite extrair diversas características importantes para analisarmos e compreendermos como as redes se organizam.
Em um ambiente de Redes Par-a-Par, em que existe uma conectividade ad-hoc muito presente, capturar uma configuração das conexões em um dado momento nos permite transformar todo o sistema em um grafo, convertendo cada peer (par) em um vértice e cada conexão em uma aresta direcionada. Assim, uma aresta partindo do vértice 1 para o vértice 2 significa uma requisição realizada pelo par 1 para o par 2. Os dados utilizados para esta análise são todos provenientes do serviço Gnutella (cujo funcionamento pode ser visto em detalhes na página Aplicações deste website) coletados em Agosto de 2002. A obtenção dos dados foi realizada pelo Stanford Network Analysis Project (STAMP), da Universidade de Stanford, que os disponibiliza em arquivo de texto.
Abaixo, podemos ver um exemplo meramente ilustrativo mostrando como um grafo desse tipo se parece:
Métricas Buscadas
Algumas características observadas podem nos dar informações sobre o funcionamento da rede. Tendo um grafo G = (V, A), em que V é o conjunto de vértices e A é o conjunto de arestas, estamos particularmente interessados nas seguintes métricas:
distribuição de graus e grau médio: um vértice v ∈ V, em um grafo direcionado, possui duas métricas interessantes. A primeira delas é deg−(v), o grau de entrada, que representa o número de arestas chegando em v, enquanto a segunda, o grau de saída deg+(v), simboliza o número de arestas saindo de v. Por exemplo, na ilustração acima, deg−(3) = 2 e deg+(3) = 1. Intuitivamente, a soma de todos os deg−(v) precisa ser igual à soma de todos os deg+(v), já que toda aresta precisa ter um ponto de partida e um ponto de chegada. Assim, verificamos a seguinte relação:
A soma deg−(v) + deg+(v) para um dado v ∈ V corresponde ao número total de conexões que o par v possuía no momento em que a captura da rede Gnutella foi realizada. Assim, se definirmos deg(v) = deg−(v) + deg+(v) e realizarmos uma estatística em todos os nós, poderemos ter uma noção de grau médio, correspondendo ao número médio de conexões, recebidas e requisitadas, que cada nó da rede possuía.
coeficiente de agrupamento (CA) médio: cada vértice v ∈ V possui seu próprio coeficiente de agrupamento local Cv , que quantifica o quão próximo seus vizinhos estão de formarem um grafo completo (ou seja, com uma aresta entre todo par de vizinhos). Dado o subgrafo formado por todos os vizinhos de v, calculamos Cv através da razão entre o número de arestas existentes sobre o número total de arestas que poderiam existir. O exemplo abaixo ilustra este procedimento para o vértice em azul:
Assim, tendo todos os coeficientes de agrupamento local calculados para cada vértice, podemos falar em um coeficiente de agrupamento médio característico do grafo inteiro, que nada mais é do que a soma de todos os coeficientes de agrupamento local divido pelo número total de vértices.
diâmetro: pense no menor caminho entre cada par de vértices. Por exemplo, na ilustração acima, o caminho mínimo entre os vértices 5 e 1 são as arestas [5→7, 7→4, 4→1]. Assim, definimos o diâmetro do grafo como sendo o comprimento do caminho mais longo entre todos os menores caminhos. Isto pode servir de material para estudos futuros observarem o padrão de utilização de cada par na extremidade do diâmetro (assim como em outros caminhos mínimos longos). Apesar de carecermos de fontes, acreditamos que pares muitos distantes possam ter padrões de utilização bastante diferentes (e.g.: um par extremo interessado em baixar artigos científicos enquanto a outra extremidade possui interesse em conteúdo pornográfico). Dessa forma, encorajamos pesquisas futuras acerca do tema.
subtorneio máximo: imagine um grafo completo, ou seja, em que cada par de vértices possui uma aresta entre eles. No caso dos grafos orientados, tal configuração é chamada de torneio, e um exemplo ilustrativo com |V| = 4 pode ser visto abaixo:
Em um dado grafo G = (V, A) do Gnutella com milhares de nós, como os que iremos analisar, é intuitivamente inviável que cada nó mantenha |V|–1 conexões e, por consequência, jamais observaremos um torneio. No entanto, se olharmos pra subgrafos de G, iremos encontrar alguns. Por exemplo, quaisquer dois vértices com uma aresta entre si formarão um subtorneio de tamanho 2. Da mesma foma, um triângulo qualquer no grafo corresponde a um subtorneio de tamanho 3. Portanto, surge a pergunta: qual será o tamanho do maior subtorneio que poderemos encontrar num grafo desse tipo?
Nota-se que este problema é equivalente a encontrar um clique máximo num grafo não-direcionado e, portanto, pertence a NP-difícil. Porém, iremos utilizar técnicas de otimização para construir um algoritmo branch-and-bound que utilizará limites primais e duais para ser guiado mais rapidamente à resposta correta, podando sua árvore de busca e, assim, encontrando a resposta em um tempo viável. O artigo do qual este algoritmo foi retirado chama-se "An improved branch and bound algorithm for the maximum clique problem" e encontra-se listado na bibliografia. Encorajamos pesquisas futuras para identificar se pares participantes do mesmo torneio possuem interesses e tendências de uso similares.
Resultados Obtidos
Para diversificarmos nossos resultados, utilizamos diferentes capturas de configuração da rede Gnutella durante o mês de Agosto de 2002. Algumas informações já estavam presentes no repositório de dados do qual os grafos foram retirados, enquanto outras (como a distribuição dos graus e o subtorneio máximo) precisaram ser calculadas para este trabalho. No entanto, não foi possível determinar se os grafos analisados representam a totalidade da rede ou apenas uma parcela. Abaixo, verificamos suas características:
| Data da captura | Total de nós | Total de arestas | Grau total médio | CA médio | Diâmetro | Tamanho do Subtorneio Máximo |
|---|---|---|---|---|---|---|
| 08/08/2002 | 6 301 | 20 777 | 6,59 | 0,0109 | 9 | 5 (Nós 7, 145, 177, 367, 753) |
| 09/08/2002 | 8 114 | 26 013 | 6,41 | 0,0095 | 10 | 5 (Nós 350, 837, 1309, 1365, 4294) |
| 24/08/2002 | 26 518 | 65 369 | 4,93 | 0,0055 | 10 | 4 (Nós 16965, 18856, 19887, 21067) |
| 30/08/2002 | 36 682 | 88 328 | 4,81 | 0,0063 | 10 | 4 (Nós 4619, 6550, 17034, 26238) |
| 31/08/2002 | 62 586 | 147 892 | 4,73 | 0,0055 | 11 | 4 (Nós 18169, 44996, 45753, 45754) |
Além disso, foi possível construir gráficos mostrando o grau de cada nó da rede. O primeiro gráfco representa a quantidade de nós que possuem um dado grau de entrada. Por exemplo, um nó com grau de entrada igual a 5 possui cinco outras máquinas que tomaram a iniciativa de se conectar a ele. Por outro lado, o segundo gráfico mostra como se distribuem os graus de saída, que correspondem às requisições realizadas por um dado nó. Por fim, incluímos um gráfico da soma dos graus de entrada e saída de cada nó, que apelidamos de grau total. Os dados estão disponíveis abaixo para os cinco grafos analisados neste trabalho:
Análise dos Resultados
Uma das primeiras conclusões a qual chegamos é que não existem nós de grau total 0 nos dados, o que significa que todos os pares estavam enviando ou atendendo a requisições. De acordo com o gráfico dos Graus de Saída, 60% a 75% dos nós possuíam grau de saída 0 e estavam apenas servindo conteúdo a outros pares. Por outro lado, nós que requisitavam um conteúdo se conectavam, em geral, a 9 ou 10 outros pares para baixá-lo.