Coeficiente de agrupamento

Na teoria dos grafos, o coeficiente de agrupamento (clustering coefficient) mede o grau com que os nós de um grafo tendem a agrupar-se. Evidências sugerem que os nós da maioria das redes do mundo real, e em especial as redes sociais, tendem a criar grupos coesos caracterizados por uma alta densidade de laços. A probabilidade de tal acontecer tende a ser maior que a probabilidade média de um laço ser estabelecido, aleatoriamente, entre dois nós. O agrupamento é uma propriedade muito comum nas redes sociais, referindo-se aos círculos de amigos ou conhecidos onde os seus membros se conhecem, formando, assim, um grupo na rede. Se determinado vértice i estiver conectado ao nó j, que por sua vez que encontra conectado com k, existe uma probabilidade elevada de i também estar conectado com k (Barabási, 2002).

Existem duas versões desta métrica: coeficiente de agrupamento global e coeficiente de agrupamento local. O coeficiente de agrupamento global foi concebido para fornecer uma visão geral do agrupamento na rede, já o coeficiente de agrupamento local fornece uma indicação da inserção dos nós individuais.

Coeficiente de Agrupamento Global

O coeficiente de agrupamento global é baseado em trios (triplets) de nós. Um trio consiste em três nós que se encontram conectados por dois (trio aberto) ou três (trio fechado) laços não direcionados. Um triângulo consiste em três trios fechados, um em cada um dos nós. O coeficiente de agrupamento global mede, assim, o número total de trios fechados (ou de 3 x triângulos) sobre o número total de trios (abertos e fechados). Uma primeira tentativa para medir o coeficiente de agrupamento global foi feita por Robert Duncan Luce e Albert Perry (1949). Esta medida dá uma indicação global do agrupamento na rede e pode ser aplicada tanto em redes direcionadas como em redes não direcionadas (conhecida também como transitividade).

Duncan Watts e Steven Strogatz definem o coeficiente de agrupamento da seguinte forma: "Supondo que um vértice v tem kv vizinhos; então no máximo poderão existir kv(kv - 1)/2 arestas entre eles (isto acontece quando todos os vizinhos de v se encontram conectados com cada um dos outros vizinhos de v). Vamos assumir que Cv representa a fração das arestas existentes num dado momento. C representa a média de Cv de todos os vértices (v)".

O rácio de transitividade é um conceito relacionado, sendo definido como:

$C={\frac {3\times n{\acute {u}}meros\,de\,tri{\hat {a}}ngulos}{n{\acute {u}}meros\,de\,trios\,de\,v{\acute {e}}rtices\,conectados}}={\frac {n{\acute {u}}mero\,de\,trios\,fechados}{n{\acute {u}}mero\,de\ trios\,de\,v{\acute {e}}rtices\,conectados}}$

No coeficiente de agrupamento os nós com baixo grau têm um peso maior, enquanto no rácio de transitividade possuem um peso maior os nós com um grau mais elevado. Uma generalização para as redes ponderadas foi proposta por Tore Opsahl e Pietro Panzarasa (2009), e uma redefinição para redes de dois-modos (ambas binárias e ponderadas) proposta por Opsahl (2009).

Coeficiente de Agrupamento Local

Exemplo do cálculo do coeficiente de agrupamento local num grafo não direccionado. O coeficiente de agrupamento local do nó azul é calculado como sendo a proporção das ligações existentes entre os seus vizinhos em relação com o total das ligações possíveis. O nó azul tem 3 vizinhos que admitem, no máximo, 3 ligações entre si. No grafo do topo, todas as 3 ligações possíveis (assinaladas pelos segmentos a negrito) entre os vizinhos do nó azul encontram-se concretizadas, obtendo-se um coeficiente de agrupamento local de 1. No grafo do meio, das 3 ligações entre vizinhos possíveis, apenas existe 1 (assinalada pelo segmento a negrito), faltando 2 ligações (assinaladas pelas linhas tracejadas a vermelho) dando, assim, um coeficiente de agrupamento local de 1/3. Finalmente, no último grafo, não existe nenhuma ligação entre os vizinhos do nó azul, pelo que o coeficiente de agrupamento local é 0

O coeficiente de agrupamento local de um vértice (nó) num grafo mede o quão perto os seus vizinhos estão de serem um clique (grafo completo). Por outras palavras, pode dizer-se que o coeficiente de agrupamento local mede o grau da densidade de ligações da vizinhança de um determinado nó, isto é, corresponde ao grau com que os vizinhos de um nó se interligam). Esta medida foi introduzida por Duncan J. Watts e Steven Strogatz em 1998 para determinar se um grafo constitui uma rede de pequeno mundo.

Um grafo G = (V, E) consiste, formalmente, num conjunto de vértices V e de um conjunto de arestas E entre si, sendo que a aresta $_{{e}_{ij}}$ conecta o vértice vi com o vértice vj. Já a vizinhança de Ni para um vértice vi é composta por todos os seus vértices adjacentes e pelas arestas que os ligam, isto é, a vizinhança corresponde a todos os vizinhos do nó imediatamente conectados.

Ou seja, ${{N}_{i}}=\left\{{{v}_{i}}:{{e}_{ij}}\in E\wedge {{e}_{ji}}\in E\right\}$

Definimos ki como sendo o número de vértices, |Ni|, na vizinhança, Ni, de um vértice. Enquanto o coeficiente de agrupamento local Ci para um vértice vi é dado pela proporção de ligações entre os vértices da sua vizinhança, dividido pelo número de ligações que poderiam existir entre estes.

No caso de um grafo direcionado, ${{e}_{ij}}$ é distinto de ${{e}_{ji}}$ e, portanto, para cada vizinhança Ni correspondem ki(ki - 1) ligações que poderão existir entre os vértices dessa vizinhança (ki corresponde ao número de vizinhos de um vértice). Assim, o coeficiente de agrupamento local para grafos direcionados é calculado utilizando a seguinte fórmula:

${{C}_{i}}={\frac {\left|\left\{{{e}_{jk}}:{{v}_{j}},{{v}_{k}}\in {{N}_{i}},{{e}_{jk}}\in E\right\}\right|}{{{k}_{i}}\left({{k}_{i}}-1\right)}}$

Num grafo não direcionado $_{{e}_{ij}}$ e $_{{e}_{ji}}$ são considerados idênticos. Portanto, se um vértice vi tem ki vizinhos significa que poderão existir ${\frac {{{k}_{i}}\left({{k}_{i}}-1\right)}{2}}$ arestas entre os vértices que compõem a sua vizinhança. Assim, o coeficiente de agrupamento local para grafos não direcionados pode ser calculado utilizando a seguinte fórmula:

${{C}_{i}}={\frac {2\left|\left\{{{e}_{jk}}:{{v}_{j}},{{v}_{k}}\in {{N}_{i}},{{e}_{jk}}\in E\right\}\right|}{{{k}_{i}}\left({{k}_{i}}-1\right)}}$

Assumindo que ${{\lambda }_{G}}\left(v\right)$ indica o número de triângulos em v ∈ V(G) para o grafo não direcionado G, isto é, ${{\lambda }_{G}}\left(v\right)$ corresponde ao número de subgrafos de G com 3 arestas e 3 vértices, um dos quais corresponde a v. Seja ${{\tau }_{G}}\left(v\right)$ o número de trios existentes em v ∈ G, isto é, ${{\tau }_{G}}\left(v\right)$ refere-se ao número de subgrafos (não necessariamente induzido) com 2 arestas e 3 vértices, um dos quais corresponde a v, sendo este incidente em ambas as arestas. Assim, o coeficiente de agrupamento pode ser definido pela seguinte fórmula: ${{C}_{i}}={\frac {{{\lambda }_{G}}\left(v\right)}{{{\tau }_{G}}\left(v\right)}}$.

Pode-se facilmente demonstrar que as duas definições anteriores são idênticas, uma vez que ${{\tau }_{G}}\left(v\right)=C\left({{k}_{i}},2\right)={\frac {1}{2}}{{k}_{i}}\left({{k}_{i}}-1\right)$

Estas medidas oscilam entre 1, no caso de todos os vizinhos de vi estarem conectados com todos os outros vértices da vizinhança, e 0 se nenhum dos vértices conectados a vi estiver conectado com qualquer outro vértice conectado a vi.

Coeficiente de Agrupamento Médio da Rede

O coeficiente de agrupamento de toda a rede corresponde, segundo Watts e Strogatz, ao valor médio dos coeficientes de agrupamento local de todos os vértices n: ${\overline {C}}={\frac {1}{n}}\sum \limits _{i=1}^{n}{{C}_{i}}$. Um grafo é considerado um pequeno mundo se o seu coeficiente de agrupamento médio ${\overline {C}}$ for significativamente maior do que o de um grafo construído aleatoriamente com base no mesmo conjunto de vértices e se o menor caminho médio (mean shortest path) do grafo considerado pequeno mundo for similar ao do grafo aleatório, isto é, ambos os grafos apresentam um número de nós e arestas muito próximo.

Uma generalização para redes ponderadas foi proposta por Barrat. (2004) e uma redefinição para grafos bipartidos (também chamados de redes de dois-modos) por Latapy e Opsahl.

No entanto, a fórmula apresentada não é, por padrão, utilizada em grafos com vértices isolados. Geralmente, as redes que apresentam um maior coeficiente de agrupamento médio possível possuem uma estrutura modular e, simultaneamente, a menor distância média possível entre nós.

Ver também

• Estrutura de dados árvore ordenada - DAGs, árvores binárias e outras formas especiais de grafos.
• Grafo
• Rede complexa
• Quiver
• Teoria espectral de grafos
• Lista de adjacência
• Matriz de adjacência
• Matriz de incidência
• Redes de pequeno mundo
• Modelo de Watts e Strogatz