Estrutura comunitária

Em ciência das redes, uma rede tem estrutura comunitária se os nós dessa rede podem ser divididos em conjuntos onde os nós são densamente conectados internamente. Esses conjuntos podem ter sobreposição ou serem disjuntos. No caso disjunto, é assumido que os nós são esparsamente conectados com os nós de outros conjuntos. De forma geral, é mais provável um nó em uma rede com estrutura comunitária tenha uma aresta com outro nó de sua(s) comunidade(s) do que outros nós na rede, em contraste com redes aleatórias onde todo par de nós tem a mesma chance de ter uma ligação.

Definição

Fig. 1: Ilustração de uma rede evidenciando estruturas comunitárias, onde há três grupos com interligações densas internamente e esparsas entre os grupos.

Comunidades disjuntas

Nessa seção, vamos considerar apenas estruturas de comunidade disjuntas. Os primeiros trabalhos sobre estrutura comunitária disjunta assumiam que as comunidades eram cliques. De fato, cliques são subgrafos densos na rede, isso constitui uma comunidade. Por outro lado, definir comunidades somente como cliques é muito restritivo porque geralmente em redes complexas é raro cliques de número de nós superiores a três e podemos deixar de classificar comunidades legítimas. Por exemplo, na Fig. 1 à direita, nenhuma das comunidades destacadas são cliques.

Para relaxar a definição de comunidades através de cliques, foram propostas duas definições: comunidades fortes e comunidades fracas. Dada uma rede representada por um grafo $G=(V,E)$, é denotado como $\deg(i)$ o grau do vértice $i\in V$. Seja $S\subset G$ um subgrafo tal que $i\in S$, vamos chamar de $\deg _{S}^{in}(i)$ o número de arestas conectado o nó $i$ com os nós em $S$. E similarmente, $\deg _{S}^{out}(i)$ o número de arestas conectando o nó $i$ com os nós não pertencentes a $S$.

Comunidades fortes

O subgrafo $S\subset G$ é uma comunidade forte se

$$\deg _{S}^{in}(i)>\deg _{S}^{out}(i),\,\,\forall i\in S.$$

Em outras palavras, todo nó pertencente a uma comunidade forte tem mais ligações internas em relação a comunidade do que externas.

Comunidades fracas

O subgrafo $S\subset G$ é uma comunidade fraca se

$$\sum _{i\in S}\deg _{S}^{in}(i)>\sum _{i\in S}\deg _{S}^{out}(i).$$

Nas comunidades fracas, a soma de todos os graus internos de $S$ é maior que a soma dos graus externos. Note que todo clique é uma comunidade forte e toda comunidade forte também é uma comunidade fraca. Por outro lado, comunidades fracas nem sempre são comunidades fortes.

É possível observar que há diversas definições para comunidades, algumas mais restritivas como definir comunidades como cliques e outras menos, como comunidades fortes e fracas. Adicionalmente, há diversas outras formas de definir comunidades que podem ser mais apropriadas dependendo do contexto.

Modularidade

Em redes aleatórias, não é possível observar nenhum tipo de estrutura comunitária, pois é esperado que as chances de ligações ocorram de forma uniforme por todos os nós. Através dessa observação, é possível criar uma métrica de modularidade calculando a diferença do padrão de ligações com de uma rede aleatória. Dessa forma, é possível medir quantitativamente se uma partição tem estrutura de comunitária.

Vamos supor uma rede representada pelo grafo $G=(V,E)$ com a matriz de adjacência $A=\left[a_{ij}\right]$ e uma partição da rede em comunidades ${\mathcal {S}}=\{S_{1},\dots ,S_{m}\}$. Note que $S_{i}$ é um subgrafo, vamos denotar como $E(S_{i})$ o número de links internos da comunidade $S_{i}$ e $\deg(S_{i})$ a soma do graus dos nós em $S_{i}$ em relação a $G$. Para cada comunidade $c=\{1,\dots ,m\}$, podemos definir a diferença entre suas ligações em $A$ e o número esperado de ligações $p_{ij}$ entre dois nós $i$ e $j$ caso a rede fosse aleatória:

$$M_{c}={\frac {1}{2|E|}}\sum _{(i,j)\in S_{c}}\left(a_{ij}-p_{ij}\right)$$

Em uma rede aleatória, a probabilidade de dois nós $u$ e $v$ estarem conectados é

$$p_{ij}={\frac {\deg(i)\deg(j)}{2L}},$$

então, a modularidade da rede toda é

$$M={\frac {1}{2|E|}}\sum _{i=0}^{N}\sum _{j=1}^{N}\left(a_{ij}-{\frac {\deg(i)\deg(j)}{2|E|}}\right)\delta _{ij}$$

onde $\delta _{ij}$ é $1$ caso os nós $i$ e $j$ pertencem a mesma comunidade e $0$ caso o contrário. Dessa forma, apenas os nós que estão na mesma comunidade serão considerados, então podemos reescrever a modularidade como

$${\begin{aligned}M&={\frac {1}{2|E|}}\sum _{i,j=1}^{N}A_{ij}\delta _{ij}-{\frac {1}{2|E|}}{\frac {\deg(i)\deg(j)}{2|E|}}\delta _{ij}\\&=\sum _{c=1}^{m}{\frac {1}{2|E|}}\sum _{i,j\in S_{c}}A_{ij}-\sum _{c=1}^{m}{\frac {1}{(2|E|)^{2}}}\sum _{i,j\in S_{c}}\deg(i)\deg(j)\\&=\sum _{c=1}^{m}{\frac {L(S_{c})}{|E|}}-\sum _{c=1}^{m}{\frac {\deg(S_{c})^{2}}{4|E|^{2}}}\\&=\sum _{c=1}^{m}\left[{\frac {L(S_{c})}{|E|}}-\left({\frac {\deg(S_{c})}{2|E|}}\right)^{2}\right].\end{aligned}}$$

Quanto maior for a modularidade, melhor ${\mathcal {S}}$ representa uma partição de $G$ em comunidades. Também, $M$ é sempre menor que 1.

Algoritmos para encontrar comunidades

Encontrar comunidades em uma rede arbitrária pode ser difícil computacionalmente. Normalmente, o número de comunidades é desconhecido a priori e as comunidades tem diferentes tamanhos e densidade de ligações. Apesar dessas dificuldades, algoritmos foram desenvolvidos com essa finalidade.

Método por corte mínimo

O método por corte mínimo, a rede é dividida em um número pré-determinado de comunidades, onde essas comunidades normalmente tem tamanhos iguais. Essas comunidades são escolhidas de tal forma que o número de arestas entre os grupos é minimizado. Esse método funciona bem para várias aplicações mas não tem resultados satisfatórios para redes no geral porque o método encontrará comunidades sem levar em consideração a estrutura implícita, pois o número de comunidades é sempre fixo.

Hierarchical clustering

Outro método para encontrar estruturas comunitárias é agrupamento hierárquico. Nesse método, é necessário uma medida de similidade quantificando algum tipo de similidade (normalmente topológica) entre par de nós. Algumas medidas utilizadas são similaridade por cosseno, índice de Jaccard e Distância de Hamming entre as linhas da matriz de adjacência. Então, são formadas as comunidades com nós similares levando em consideração essa métrica. Há diversos métodos para realizar o agrupamento desses nós, sendo um deles o clustering de ligação única, no qual dois grupos são considerados separados em comunidades se e somente se todos os pares de nós em grupos diferentes tem a similaridade maior que um limiar. Outra abordagem que obteve resultados melhores é o uso de várias métricas de similaridades e dissimilaridades, combinadas através de uma combinação convexa.

Algoritmo de Girvan–Newman

Outra abordagem para detecção de comunidades é o algoritmo de Girvan-Newman . Esse algoritmo identifica as arestas em uma rede que estão na fronteira de comunidades e as remove, deixando somente as comunidades isoladas. A identificação é feita utilizando intermediação, que é um número associado a cada aresta onde esse valor é maior se a aresta está "entre" muitos pares de nós.

O algoritmo de Girvan-Newman retorna resultados razoáveis em relação a qualidade mas sua popularidade advém do fato que esse método é implementado em diversos pacotes de software. Em contrapartida, sua execução é lenta levando tempo proporcional a $O(E^{2}V)$ em uma rede de $V$ vértices e $E$ arestas, por essa razão é impraticável para redes de alguns milhares de nós.

Maximização da modularidade

Apesar de suas desvantagens, um dos métodos mais utilizados para detecção de comunidades é a maximização da modularidade. A maximização da modularidade detecta comunidades realizando uma busca entre candidatos de partições e seleciona a partição (ou partições) com maior modularidade. Devido ao fato que uma busca por todas as possíveis partições é algo intratável, algoritmos baseados em aproximação são utilizados como algoritmos gulosos, simulated annealing, otimização espectral. Essas propostas oferecem diferentes resultados referente a velocidade e acurácia. Um método popular de maximização da modularidade é o método de Louvain, que iterativamente realiza a otimização de comunidades locais até que a modularidade global não seja mais melhorada através de perturbações na partição de comunidades. Atualmente, o melhor algoritmo para a otimização de modularidade utiliza o método RenELL que é um exemplo de aprendizado ensemble extremo .

A modularidade é questionada como métrica para otimização porque já foi mostrado que sua maximização falha em detectar clusters menores que certa escala que depende do tamanho da rede.