Primeira vez aqui? Seja bem vindo e cheque o FAQ!
x

Calcule o grau de centralização de algumas redes e compare os resultados

0 votos
28 visitas
perguntada Set 29 em Sistemas Complexos por Renan Abrantes (1 ponto)  
editado Set 29 por Renan Abrantes

O exercício é proveniente do livro Complex Networks: Principles, Methods and Applications (V. Latora, V. Nicosia, G. Russo, 2017).

Pede-se para calcular o grau de centralização para a rede de atores, e comparar o resultado com outras redes que a pessoa escolher. Segue transcrição do exercício:

"2.5(b) Evaluate by means of Eq. (2.19) the degree centralisation for the movie actor collaboration network, and compare the number you obtain with the centralisation of other networks of your choice."

Compartilhe

1 Resposta

0 votos
respondida Set 29 por Renan Abrantes (1 ponto)  
editado Set 29 por Renan Abrantes

Esta pergunta é relacionada à análise empírica feita para a rede de atores de Steven Strogatz e Duncan Watts. Caso queira acessar a análise empírica, clique aqui.

Primeiro, vamos explorar conceitualmente o significado de centralização. As medidas comuns de centralidade procuram avaliar o quão importante um vértice (agente, nó, indivíduo etc) é para a rede. Já o grau de centralização avalia como alguma medida de centralidade é distribuída pelos seus vértices, com enfoque na estrutura geral da rede. Dessa forma, o grau de centralização retorna um valor único para a rede, indicando se esta é muito centralizada (concentrada) ou não.

O grau de centralização calcula o quanto o vértice com maior centralidade na rede se destoa dos outros vértices. Conforme a equação 2.19 do livro, o grau de centralização H da rede \(G\) é dado por:

A imagem será apresentada aqui.

onde \(C_i\) é o valor da centralidade do vértice \(i\) na rede \(G\), para a medida escolhida de centralidade \(C\), e \(i^*\) é o vértice com maior centralidade.

Observe que a equação permite que diferentes distribuições de centralidade retornem o mesmo valor de grau de centralização.

O grau de centralização pode ir de zero a um. Quanto maior o valor, mais centralizada a rede é, aproximando-se de uma rede tipo estrela, em que há um único vértice (a "estrela") conectado a todos os outros, ao passo que os outros vértices não têm conexão entre si.

Além da rede de atores de cinema, para fazer a comparação do grau de centralização escolhi a rede de coautoria em física (capítulo 3 do livro), a rede da Google para WWW (capítulo 5 do livro) e a rede de casamentos das famílias de Florença (capítulo 2 do livro).

Para resolver o exercício, vamos primeiro ler as redes escolhidas. Utilizei o pacote Networkit no Python.

import networkit as nk

    #O objetivo é calcular o grau de centralização para a rede de atores, e comparar o resultado com outras redes.
    #As bases foram baixadas em http://http://www.complex-networks.net/datasets.html/.

#Ler as redes
movie = nk.readGraph('movie_actors.net', nk.Format.EdgeListSpaceZero)
author = nk.readGraph('arxiv.net', nk.Format.EdgeListSpaceZero)
google = nk.readGraph('web-Google.net', nk.Format.EdgeListSpaceZero)
flor = nk.readGraph('florentine.net', nk.Format.EdgeListSpaceZero)

É sempre interessante ver algumas características das redes antes de qualquer análise mais aprofundada. O Networkit tem uma função denominada overview, que facilmente retorna algumas estatísticas de rede.

#Overview
print('Movie actors overview:')
nk.overview(movie)
print('Coauthorship overview:')
nk.overview(author)
print ('Google WWW overview:')
nk.overview(google)
print ('Floretine overview:')
nk.overview(flor)

Veja o resultado:

A imagem será apresentada aqui.

O número de vértices (nodes) e conexões (edges*) de cada rede é bem diverso. A rede de atores tem 248243 vértices e 8302734 conexões. A rede de coautoria tem 52909 vértices e 245300 conexões. A rede de internet tem 916248 vértices e 4322051 conexões. Por último, a rede florentina tem 16 vértices e 20 conexões

Observe que a rede com maior grau médio de conexões é a de atores de filmes, com 66,89 conexões por vértice. Já as redes de coautoria e de WWW tem graus médios de conexão bem próximos entre si, com 9,27 e 9,45, respectivamente. Por sua vez, a rede das famílias florentinas tem grau médio de conexões de 2,5.

Todas as redes apresentam grau mínimo de conexão igual ao zero, ou seja, em todas há algum vértice que não tem conexão alguma. O grau máximo da rede de atores é 3080. Apenas por curiosidade, pela análise empírica, sabemos que esse vértice é Irving Bacon. Já o grau máximo das redes de coautoria, de WWW e de família florentinas são 360, 6332 e 6, respectivamente.

É importante lembrar que é a centralidade do vértice mais central que é utilizada como base para o cálculo da centralização. Neste caso, escolhi justamente a medida de centralidade de grau de conexões (degree centrality) como referência para calcular o valor de centralização das redes:

#Degree centrality
movied=nk.centrality.DegreeCentrality(movie)
movied.run()
authord=nk.centrality.DegreeCentrality(author)
authord.run()
googled=nk.centrality.DegreeCentrality(google)
googled.run()
flord=nk.centrality.DegreeCentrality(flor)
flord.run()

O próximo passo é calcular o grau de centralização:

#Degree centralization
moviec = movied.centralization()
print('The movie actors degree centralization is', moviec)
authorc = authord.centralization()
print('The physics coauthorship degree centralization is', authorc)
googlec = googled.centralization()
print('The Google WWW degree centralization is', googlec)
florc = flord.centralization()
print('The Florentine degree centralization is', florc)

Seguem os resultados:

A imagem será apresentada aqui.

A rede de maior grau de centralização é a de casamentos entre famílias florentinas, com 0,259. A rede de atores de filmes tem grau de centralização de 0,012. Já os graus de centralização da rede de coautoria e de WWW são quase idênticos, com 0,0066 e 0,00689, respectivamente.

Embora a rede florentina seja a de maior grau de centralização, é importante ressaltar que o valor está longe do máximo dessa medida, que é igual a 1. De toda forma, a família Médici, que tem maior grau de conexão na rede florentina, está mais para a estrela dessa rede do que Irving Bacon na rede de atores e do que os vértices mais centrais das redes de coautoria e WWW.

...