Coeficiente de agrupamento
Na teoria dos grafos, o coeficiente de agrupamento 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.
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 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 i j {\displaystyle _{{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.
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: C ¯ = 1 n ∑ i = 1 n C i {\displaystyle {\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 C ¯ {\displaystyle {\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.
