Estrutura de Grafos - Medidas de Centralidade

Bem-vindo a mais uma postagem. E não é sobre pontos turísticos em Teresina :-).

Falaremos hoje um pouco sobre estrutura de Grafos. E, por falar em estrutura de Grafos e pontos turísticos, ontem passei de carro pelo ponte estaiada sobre o rio Poty e pensei em Teresina como um Grafo gigante. Eis o belo Graf...quer dizer, Teresina vista focando a Ponte Estaiada:

Teresina, conhecida como Mesopotâmia Brasileira, é cortada pelos rios Poty e Parnaíba (semelhante aos rios Tigres e Eufrates - os da Mesopotâmia, atual Iraque e Kwait). Abaixo, Teresina e suas várias pontes (um Grafo!):

Pois bem, por falar em pontes, de fato existe um problema bem antigo do qual lembro da época da universidade, para o qual não existe solução. Chama-se "Problema das Pontes de Königsberg", o qual você pode saber mais detalhes clicando AQUI. Esse probleminha insolúvel das pontes gerou a Teoria dos Grafos e o estudo sobre a estrutura dessas redes.

Há muitas formas de, estatisticamente, medir estruturas de redes. Se nosso grafo é pequeno (contendo poucos nós e poucas arestas ou links) não será difícil perceber os padrões de conectividade, estrutura de agrupamento dos nós e a topologia geral do grafo e talvez assim não precisaremos usar estatística.

Todavia, se a rede cresce consideravelmente a avaliação apenas visual, sem uso de outras técnicas auxiliares, não poderá ajudar-nos muito. Precisaremos então recorrer a metodologias mais sofisticadas de análise. Um dos importantes conceitos envolvidos com essas metodologias é o de Centralidade, o qual exploraremos a seguir:

Centralidade

É uma medida que nos possibilita entender a influência relativa de nós dentro da rede. Há muitas formas de determiná-la e, por isso, existem três principais tipos de centralidade, falaremos deles um a um.

Closeness Centrality (Centralidade de Proximidade) - É uma medida que representa a proximidade de um determinado nó aos demais nós dentro do mesmo Grafo. Um nó com uma alta Centralidade de Proximidade tipicamente teria muitos pequenos caminhos para chegar a todos os outros nós dentro do grafo. Uma pessoa com alta Centralidade de Proximidade social é aquele cara que conhece muita gente, está sempre próximo de todos e já pode se candidatar a vereador :-).

Eis um exemplo típico:

Considerando o maior grau de Centralidade de Proximidade encontrado como 100%, obtemos o seguinte resultado no cálculo dessa medida para cada nó:

Ou seja, Paulo tem o maior grau de Closeness Centrality do grafo (considerando o a maior medida encontrada como cem por cento). Podemos concluir que partindo de Paulo e considerando todo o grafo, ele se torna o nó que está mais próximo de todos. No caso, o número máximo de passos para sairmos de Paulo e chegarmos a qualquer nó é 2 (máxima distância é igual a 2 para qualquer outro nó do grafo). A localização central de Paulo torna simples a travessia do grafo e, por isso, ele possui alta Centralidade de Proximidade.

Betweeness Centrality (Centralidade de Intermediação) - Para essa medida encontraremos nós que tem alta influência na comunicação entre regiões distantes do Grafo. É normal ocorrer que um nó tenha alta centralidade de intermediação e cujas outras medidas de centralidade sejam baixas, portanto cada medida de Centralidade possui um significado bem diferente de outro. Nós com alta centralidade de intermediação formam verdadeiras "pontes" entre partes do gráfico, o que significa que sem a presença deles a comunicação entre grupos distantes fica dificultada. Eles tornam a travessia do grafo mais fácil. Eles também fazem comunicação de Clusters. Lembra dos Clusters (ou partições)? Caso não lembre ou não saiba o que são, leia minha postagem sobre eles aqui.

Observe o Grafo abaixo:

Observe que Marta serve como uma espécie de ponte entre dois pequenos sub-redes dentro do Grafo. Calculando as Centralidades de Intermediação, obtemos os seguintes índices:

Marta tem, portanto, alto grau de Centralidade de Intermediação.

Centralidade de Autovetor (eingenvector Centrality) - Esta é uma medida de Centralidade que está relacionada à conectividade dos vizinhos próximos. É uma medida relacionada à pergunta "Quem você conhece?". Um dado nó pode não ser importante por si, mas ele se relaciona a outros nós com alta conectividade, o que pode indicar alto nível de influência. Por exemplo: No mundo real, uma pessoa que seja confidente de várias celebridades populares pode ter esse perfil.

Abaixo um exemplo de Grafo para o qual o nó "Fábio" possui alto Eigenvector Centrality:

Perceba na figura acima como Fábio é conectado a pessoas bem conectadas. Abaixo, vemos os cálculos da autocentralidade, Centralidade de Autovetor ou Eigenvector Centrality para o caso acima:

Por Hoje é só...voltarei em breve por aqui para escrever mais algumas coisas interessantes. Obrigado pela visita!