Quem é "importante" na rede?

No campo da ciência de redes, uma das perguntas que podemos fazer é quais são os nós mais influentes na rede? Pense em uma rede social online, por exemplo, como medir o poder de influência de perfis no Facebook ou Twitter? Esta é uma pergunta importante e tais influenciadores poderiam ser utilizados (e são na verdade) para o marketing de serviços e produtos ou, no caso de uma rede social real, para serem escolhidos para imunização.

Mas como medir esta influência? Nós temos uma forma de quantificar objetivamente a influência e importância de um nó da rede? 

Antes de tudo, vale dizer que há várias maneiras de nos aproximarmos deste problema e que não existe necessariamente uma resposta correta. O número de seguidores ou o número de compartilhamentos são bons indicativos da influência de um perfil em uma rede do social online, mas não são a única forma de medir a influência, já que um outro perfil com menos popularidade pode ser importante por servir, por exemplo, de ponte entre grupos distintos ajudando a disseminar ideias entre os influenciadores destes grupos.

O fato é que, através dos anos, diferentes definições foram criadas para determinar o que significa ser importante em uma rede complexa. Costumamos chamar as diferentes formas de capturar este conceito de medidas de centralidade. O que nós faremos neste artigo é apresentar algumas delas e discutiremos as vantagens e desvantagens de cada abordagem.

A forma mais óbvia de medir a importância de um nó é a centralidade de grau, em que nós usamos o grau de um nó para determinar sua importância na rede. Em uma rede não-dirigida, simplesmente contamos o número de vizinhos de cada nó (grau) e padronizamos o valor dividindo pelo máximo grau possível em uma rede ($n-1$, onde $n$ é o número de nós da rede). Em redes dirigidas, fazemos uma abordagem similar porém diferenciando a centralidade de grau de entrada e de saída. Em todo caso, a centralidade de grau é dada pela fração dos nós a que um nó está conectado.

Para demonstrar o cálculo da centralidade do grau utilizaremos a rede didática mostrada abaixo. Esta rede é conhecida como grafo de pipa de Krackhardt, e deve este nome a seu formato peculiar e o nome de seu criador David Krackhardt, pesquisador da área de redes sociais. A rede apresenta 10 nós rotulados com nomes de pessoas fictícias e demonstrando relações de amizade também fictícias.

Considerando, Heather, por exemplo, pode-se ver que sua centralidade de grau é $\frac{3}{9}=0,333 \ldots$, já que possui $3$ vizinhos e que o número máximo de vizinhos que qualquer nó poderia ter nesta rede é de 9. O gráfico abaixo compara a centralidade de grau de cada nó desta rede e, como era de se esperar, Diane é o nó mais central nesta rede. Em segundo lugar ($0,555\ldots$), empatados, temos Fernando e Garth, seguidos por Andre e Beverley, que empatam com o terceiro maior valor de centralidade de grau ($0,444\ldots$). Jane fica por último nesta lista com uma centralidade de grau de $0,111\ldots$.

Então chegamos à questão, seria esta medida de centralidade razoável? Repare que esta medida consegue capturar diferentes aspectos. Provavelmente nós concordamos que Jane deveria ser considerada como menos importante nesta rede, já que ela está apenas conectada à Ike. Se olharmos pares, como Carol e Ed, ou Fernando e Garth, ou ainda Andre e Beverley, também concordaremos que os nós de cada par deveriam ser igualmente importantes, porque as posições que ocupam na rede são um tanto simétricas.

Contudo, você observa como Fernando e Garth estão mais "próximos" de todos os nós, a despeito de terem uma centralidade do grau mais baixa do que a de Diane?

Tomemos um deles apenas para efeito de exemplo, observe os menores caminhos de Fernando para cada um dos outros nós na rede. Você percebe que ele está mais próximo de Heather, Ike e Jane, do que Diane está? Diane, por outro lado, está mais próxima de outros dois nós (Ed e Beverley), que estão mais distantes do Fernando. Isso faz com que, "em média", Fernando esteja um pouco melhor posicionado do que Diane. Caso quiséssemos atingir rapidamente toda a rede com mensagens, Fernando está em uma situação que o permite atingir todos os nós em apenas três saltos.

Algo similar ocorre com Heather. A partir de sua posição na rede, podemos alcançar todos os nós da rede mais rapidamente do que se partíssemos da posição de Carol, que possui a mesma centralidade de grau do que Heather. 

Isso tudo indica que a centralidade do grau tem limitações. Assim, deveríamos ter uma medida de centralidade que pudesse indicar os nós mais centrais pela sua proximidade de outros nós. Esta centralidade de proximidade de um nó $u$ (também chamada closeness centrality), que designaremos por $C(u)$, pode ser computada calculando a média dos menores caminhos do nó $u$ e invertendo este valor. 

A razão de tomarmos o valor inverso é porque nós queremos que a centralidade de proximidade indique aqueles nós "mais próximos" dos outros, o que é uma ideia inversa à ideia dos menores caminhos. Assim, quanto menor for a média das distâncias maior será a medida de proximidade obtida e vice-versa.

Formalmente temos que

$C(u)=\frac{n-1}{\sum_{v=1}^{n-1}{d(v,u)}}$

onde $d(v,u)$ é a distância do menor caminho entre os nós $v$ e $u$. Observe que a proximidade é calculada considerando apenas os nós alcançáveis a partir de $u$, deixando de fora aqueles nós que não estejam na mesma componente conectada.

Vamos então ilustrar o cálculo desta centralidade para Diane. Suas distâncias para cada um dos outros nós é: para Andre é $1$; para Beverly é $1$; para Carol é $1$; para Ed é $1$; para Fernando é $1$; para Garth é $1$; para Heather é $2$; para Ike é $3$; e para Jane é $4$. Logo a soma é $15$ e o inverso da média ($\frac{9}{15}$) é $0,6$. Aplicando esta medida para os demais nós do grafo de Krackhardt, temos o resultado mostrado no gráfico abaixo.

A centralidade de proximidade confirma nossa observação inicial. Como se pode ver, realmente Fernando e Garth são os mais centrais, segundo esta medida, e a proximidade deles ($0,642\ldots$) é um pouco maior do que a proximidade de Diane. Outro ponto importante é que Heather, que antes estava empatada com Carol e Ed e atrás de Andre e Beverly em importância, foi descoberta muito mais importante na rede, por causa de sua proximidade: Heather fica agora empatada com Diane, logo atrás de Fernando e Garth.

Observe como esta métrica ainda captura os outros dois pontos que observamos anteriormente: que Jane tem menor importância na topologia desta rede; e que os pares (Carol e Ed, Fernando e Garth e Andre e Beverley) também apresentam a mesma importância. Em outras palavras, a proximidade parece ser uma medida de centralidade mais razoável quando falamos de propagação de informação, porque consegue atribuir mais adequadamente a relevância de cada nó.

Mas será que esta centralidade nos diz tudo sobre a importância dos nós desta rede? Voltando à comparação entre Fernando e Diane, você observou como o caminho de Fernando para Ed pode ou não passar por Diane? A distância é a mesma caso as mensagens de Fernando para Ed fossem direcionadas por meio de Garth ou Andre. Isso significa que Diane não é assim tão a importante para manter as distâncias de Fernando a estes nós. O mesmo não pode ser dito caso estivéssemos falando do caminho de Diane para Jane, já que para este percurso Diane tem apenas duas opções, ou passa por Fernando ou por Garth.

Mas considere Heather novamente, você percebe que há algo especial em sua posição? Ela provê a única conexão que Ike e Jane possuem ao resto da rede. Podemos dizer que Ike e Jane confiam em Heather para manter sua ligação ao resto da rede. E da mesma forma os demais nós da rede dependem de Heather para manter a conectividade com Ike e Jane. Se removêssemos Heather, o grafo se partiria, formando duas componentes conectadas. O mesmo não aconteceria se removêssemos Diane.

Logo se estamos medindo a importância de nós, não lhe parece que Heather tem uma importância maior que Diane? Suas conexões parecem bastante vitais para a conectividade da rede, contudo a centralidade de grau não consegue capturar estas nuances e a centralidade de proximidade mostrou um empate entre as duas. 

Para distinguir estas situações usaremos a centralidade de intermediação (betweenness), que inclusive já mostramos em outro artigo do blog. Por conta disso, não iremos entrar nos detalhes do cálculo, mas basta lembrarmos que a intermediação captura a fração dos menores caminhos do grafo que passam por um certo nó da rede.

Calculando a centralidade de intermediação para cada nó da rede de Krackhardt, obtemos o gráfico abaixo. Nele observamos que Heather é o nó mais central segundo esta medida, já que todos os caminhos de Jane e Ike para os demais nós e dos demais nós para eles passam por Heather. Fernando e Garth, aparecem então empatados na segunda posição com Ike logo atrás, na terceira, o que é surpreendente já que ele esteve como penúltimo nos rankings das outras medidas.

O que torna Ike tão relevante nesta métrica? Basicamente, devemos observar que a intermediação de um nó é maior quanto maior for o número de menores caminhos que passam por ele de forma exclusiva. No caso de Diane, por exemplo, diversos menores caminhos passam por ela, mas não de forma exclusiva, isso ajuda a diminuir a centralidade de intermediação dela. O caso de Ike é mais parecido com o de Heather, todos os caminhos de Jane passam por Ike, exclusivamente. Isso coloca Ike numa posição de relevância, não somente para Jane, mas para a rede como um todo já que ele é a única forma dos demais nós acessarem Jane.

As figuras abaixo mostram o resultado final de cada abordagem na rede de Krackhardt. Para melhor visualização, as posições de cada nó foram mantidas e o valor das respectivas centralidades (arrendondado em duas casas decimais) é mostrada na rede como rótulo do nó. Também construímos uma escala de cor onde os valores mais escuros indicam valores maiores de centralidade.

Como se pode ver cada uma das medidas de centralidade oferece uma visão diferente sobre a importância de cada nó. O simples "número de seguidores", que é o que a centralidade do grau mede, nem sempre é o suficiente para determinar importância de um nó para rede. Contudo, isso não significa que esta seja uma "medida errada". Esta medida é usada, por exemplo, para campanhas de marketing  que desejam ter um alto impacto em curto tempo, como uma promoção relâmpago. Já as outras medidas de centralidade podem ser usadas em cenários onde deseja-se obter o efeito viral na disseminação da informação.

Por fim vale dizer que estas são apenas as medidas mais simples de centralidade, existindo inúmeras outras medidas. Para uma análise mais ampla deste assunto vale a pena conferir o livro Networks: An Introduction de Mark Newman.