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

Rede de Livros sobre a política dos Estados Unidos: visualização da rede, informações úteis do grafo, análise sobre a predominância vértices por meio de medidas de centralidade

0 votos
20 visitas

1 Resposta

0 votos
respondida Nov 13 por Andrei Leite (1 ponto)  
editado Nov 16 por Andrei Leite

A rede que será objeto de estudo desta análise empírica é uma rede de livros sobre a política dos EUA, a qual foi publicada na época da eleição presidencial de 2004 e vendida pela Amazon. Os vértices da rede correspondem aos livros e as arestas entre os livros representam a compra frequente de dois livros pelos mesmos compradores.

Para analisar a rede utilizaremos principalmente a biblioteca NetworkX. Para a visualização da rede, usaremos a biblioteca Matplotlib.
A rede pode ser obtida em http://www-personal.umich.edu/~mejn/netdata/ e está disponível para download em GML, formato no qual é possível importar os arquivos para Python utilizando a biblioteca Networkx.

import matplotlib.pyplot as plt
import networkx as nx
import os
G = nx.read_gml(r'(incluir aqui o diretório do arquivo no seu pc)')
print(nx.info(G))
Name: 
Type: Graph
Number of nodes: 105
Number of edges: 441
Average degree:   8.4000

Importamos, portanto, a rede no formato de um grafo. Um grafo é um par de conjuntos: um conjunto de vértices e um conjunto de arestas. Cada aresta é um par ordenado de vértices. O primeiro vértice do par é a ponta inicial do vértice e o segundo é a ponta final. Como podemos ver acima, o grafo em questão possui 105 vértices e 441 arestas.

Os grafos podem ser directed ou undirected. Utilizando o comando nx.is_directed(G) vemos que a rede é undirected, o que significa que se o nó A está conectado ao nó B, então necessariamente o nó B está conectado ao nó A.

A estrutura de dados de gráfico no NetworkX é como um dicionário Python. Nessa rede, a cada livro é associado um atributo, chamado value. Esse atributo pode ter valor l, c ou n. L corresponde a leftist, (livro associado à esquerda no espectro político), c, que corresponde a conservative, associado ao conservadorismo no espectro político e n corresponde a neutral (um livro que não é classificado nem como leftist nem como conservative). Para verificar qual o atributo de um vértice podemos usar o código G.nodes['nome do livro'].

Para visualizar a rede, utiliza-se o comando nx.draw() da seguinte forma:
nx.draw(G,nodecolor='Black',nodesize=120,width=0.5,edge_color='Grey')
A imagem será apresentada aqui.
Apesar de ainda não podermos tirar muitas conclusões da rede desenhada dessa forma, já podemos perceber que parece que ela se divide em dois grupos de vértices bem conectados entre si. É possível supor que esses vértices estejam separados de acordo com as classificações l, c ou n, uma vez que livros de um mesmo espectro político tendem a ser mais comprados juntos por um mesmo comprador do que livros de espectro políticos opostos. Para verificar se isso ocorre de fato, coloriremos os vértices utilizando a cor vermelha para os vértices com atributo *l*, azul para os vértices com atributo *c* e verde para os vértices com atributo *n*.

left_nodes = [n for (n,value) in nx.get_node_attributes(G,'value').items() if value == 'l']
conservative_nodes = [n for (n,value) in nx.get_node_attributes(G,'value').items() if value == 'c']
color_map = []
for node in G.nodes():
    if node in left_nodes:
        color_map.append('Red')
    elif node in conservative_nodes:
        color_map.append('Blue')   
    else:
        color_map.append('Green')
nx.draw(G, node_color=color_map,node_size=120,width=1,edge_color='Grey')
plt.savefig('rede_2.pdf')

A imagem será apresentada aqui.
Percebe-se que, como esperávamos, a rede divide-se em dois grupos nos quais os nós se conectam a nós com atributos similares: o dos livros c, que tendem a estar ligados entre si, e os livros l, que também tendem a estarem conectados entre si.

Um grafo é conectado se cada par de vértices no grafo é conectado. Utilizando o comando nx.is_connected(G) vemos que o grafo em questão é conectado. Além disso, também é biconectado (nx.is_biconnected(G)== True), o que significa que não existem pontos de articulação no grafo. Uma ponte é um vértice cuja retirada torna o grafo disconectado. Utilizando o comando nx.has_bridges(G) vemos que esse grafo não tem pontes. Então, vamos verificar a existência de pontes locais (local bridges).
Pontes locais são arestas entre dois nós em um grafo social que são a rota mais curta pela qual as informações podem passar daqueles conectados a um para aqueles conectados ao outro. As pontes locais diferem das pontes regulares porque os pontos finais da ponte local, uma vez que a ponte foi excluída, não podem ter uma ligação direta entre eles e não devem compartilhar nenhum vizinho comum. Além disso, se a ponte local for excluída, a distância entre esses dois nós será aumentada para um valor estritamente superior a dois.

O comando list(nx.local_bridges(G)) retorna uma lista com todos os vértices que são pontes locais. Para entendermos melhor como funciona o conceito de pontes locais, visualizaremos essas arestas na rede. Para isso, faremos o seguinte: vamos criar uma lista chamada localbridges e adicionar as tuplas correspondentes aos vértices extraídos com o comando list(nx.local_bridges(G)). Em seguida, vamos criar uma lista vazia chamada *colormapedges* na qual adicionaremos a cor 'Yellow' caso um vétice em G.edges() (que retorna uma lista de tuplas com todos os vértices do grafo) também esteja na lista localbridges e 'Grey' caso esse vértice não esteja nessa lista. Com isso teremos arestas com cores diferentes no grafo.

l = list(nx.local_bridges(G))
n=len(l)
local_bridges = list()
for i in range(n):
    local_bridges.append(l[i][0:2])    
print(local_bridges)
color_map_edges = []
for edge in G.edges():
    if edge in local_bridges:
        color_map_edges.append('Yellow')
    else:
        color_map_edges.append('Grey')
left_nodes = [n for (n,value) in nx.get_node_attributes(G,'value').items() if value == 'l']
conservative_nodes = [n for (n,value) in nx.get_node_attributes(G,'value').items() if value == 'c']
color_map = []
for node in G.nodes():
    if node in left_nodes:
        color_map.append('Red')
    elif node in conservative_nodes:
        color_map.append('Blue')   
    else:
        color_map.append('Green')
nx.draw(G, node_color=color_map,node_size=120,width=0.5,edge_color=color_map_edges)

A imagem será apresentada aqui.
Perceba a aresta indicada pela seta vermelha. Ela está representada em amarelo por ser uma local bridge. Veja como ela faz uma ligação entre os grupos vermelho e azul. Portanto, a existência aumenta a velocidade de transmissão de informação entre esses dois grupos, reduzindo os menores caminhos entre pontos que pertencem a esses grupos. Por isso esse vértice é considerado uma local bridge.

Assortatividade é uma medida global (correlação) da rede que preferência dos nós se conectarem com outros nós similares. O coeficiente de assortatividade mede o nível de homofilia do gráfico, com base em alguns rótulos de vértices ou valores atribuídos aos vértices. Valores positivos do coeficiente de assortatividader indicam uma correlação entre nós de grau semelhante, enquanto valores negativos indicam relações entre nós de grau diferente. Em geral, r está entre −1 e 1. Quando r = 1, diz-se que a rede tem padrões de mistura ordenados perfeitos, quando r = 0 a rede é não ordenada, enquanto em r = −1 a rede é completamente desassortativa.

É possível calcular o coeficiente de assortatividade da rede utilizando o código nx.degree_assortativity_coefficient(G). Nesse caso, será calculado o coeficiente de assortatividade levando em consideração a grau de conexão de cada nó, ou seja, a quantos nós cada nó se conecta. Para esse rede, temos que o coeficiente de assortatividade é igual a -0.127.

Assim, considerando somente a semelhança entre quantidade de vizinhos que cada nó tem, temos que essa rede apresenta um grau de assortatividade muito baixo. Contudo, é possível modificar o parâmetro que se leva em consideração na hora de calcular o coeficiente de assortatividade. É possível utilizamos como parâmetro, em vez do grau de conexão, o atributo de cada nó (l, r ou c). Para isso basta usar o seguinte código:nx.attribute_assortativity_coefficient(G,'value'). Temos que o grau é assortatividade calculado dessa forma é igual a 0.7233.

Portanto, quando consideramos o atributo dos livros no calculo, o coeficiente de assortatividade cresce para aproximadamente 0,72, um valor bastante alto. Com isso, mostramos de forma algébrica o que percebemos visualmente nos grafos da rede.

Passemos agora aos algoritmos de busca exaustiva em redes. São dois: Depth First Search (DFS) e Breadth First Search (BFS). Ambos têm a seguinte estrutura geral:

 procedure Graph search(Graph G, vertex u)
    while possible do
       Choose an edge (u; v) with u explored and v unexplored
       Mark v explored
    end while
 end procedure

A partir dessa estrutura geral pode-se montar os dois algoritmos. A implementação em Python pode ser encontrada em http://prorum.com/?qa=2414/implementar-extrair-informacoes-conectividade-aciclicidade. Aqui, explicarei como cada um funciona e depois usarei os algorimos DFS e BFS que já estão implementados na biblioteca NetworkX.

O DFS é um algoritmo usado para realizar uma busca ou travessia em um grafo em estrutura de árvore. Intuitivamente, o algoritmo começa num nó raiz (selecionando algum nó como sendo o raiz, no caso de um grafo) e explora tanto quanto possível cada um dos seus ramos, antes de retroceder(backtracking). Após retroceder fará isso com o nó vizinho que ainda não foi analisado e assim sucessivamente.

Vejamos a aplicação desse algoritmo na rede em que estamos estudando. Para isso, vamos importar traversal de networkx.algoritm. Ele será usado no seguinte código traversal.dfs_edges(G).

from networkx.algorithms import traversal
Gdfs= nx.Graph()
Gdfs.add_nodes_from(G)    #Importa os vértices da rede G
DFSedges= list(traversal.dfs_edges(G))      #Criando uma lista com os vértices na ordem do algoritmo DFS
Gdfs.add_edges_from(DFSedges) #Importa a lista DFSedges como links da rede Gdfs
#Colorindo os nós como fizemos anteriormente
left_nodes = [n for (n,value) in nx.get_node_attributes(G,'value').items() if value == 'l']
conservative_nodes = [n for (n,value) in nx.get_node_attributes(G,'value').items() if value == 'c']
color_map = []
for node in G.nodes():
    if node in left_nodes:
        color_map.append('Red')
    elif node in conservative_nodes:
        color_map.append('Blue')   
    else:
        color_map.append('Green')    
nx.draw(Gdfs, node_color=color_map,node_size=120,width=0.5,edge_color='Grey')
plt.savefig('rede_4.pdf')

A imagem será apresentada aqui.
O algoritmo BFS faz o oposto do algoritmo DFS: visita primeiro todos os nós vizinhos e somente após isso visita os vizinhos dos vizinhos. BFS e DFS, portanto, são muito similares, a única diferença é a ordem em que eles atravessam os nós encontrados. O DFS explorará um novo nó vizinho imediatamente conforme o vê, ao passo que o BFS
armazenará cada vizinho até que tenha visto todos eles, e só então partirá para a análise dos nós vizinhos a cada um desses nós. Portanto, embora o DFS esteja satisfeito com uma pilha para manter seus “nós a serem explorados”, o BFS requer uma fila.

   from networkx.algorithms import traversal
    Gbfs= nx.Graph()          #Criando uma nova rede
    Gbfs.add_nodes_from(G)    #Importa os vértices da rede G
    Gbfs.nodes()
    edges = traversal.bfs_edges(G,"The O'Reilly Factor")  # #Criando uma lista com os links na ordem do algoritmo BFS partido do livro "The O'Reilly Factor"
    BFSedges= list(edges)
    print(BFSedges)
    Gbfs.add_edges_from(BFSedges) #Importa a lista DFSedges como links da rede Gdfs
    left_nodes = [n for (n,value) in nx.get_node_attributes(G,'value').items() if value == 'l']
    conservative_nodes = [n for (n,value) in nx.get_node_attributes(G,'value').items() if value == 'c']
    color_map = []
    for node in G.nodes():
        if node in left_nodes:
            color_map.append('Red')
        elif node in conservative_nodes:
            color_map.append('Blue')   
        else:
            color_map.append('Green')
    nx.draw(Gbfs, node_color=color_map,node_size=120,width=0.5,edge_color='Grey')
    plt.savefig('rede_5.pdf')

A imagem será apresentada aqui.
Uma das primeiras abordagens de análise de redes sociais é medir o poder, a influência ou outras características individuais das pessoas com base em seus padrões de conexão. Nesse contexto, uma pergunta muito comum é: quem é mais importante na rede? Para responder essa pergunta e outra similares,abordaremos agora os conceitos de centralidade.

A centralidade de grau é simplesmente a quantidade de conexões que um nó tem. Vejamos como a centralidade de grau está distribuída nessa rede.
A imagem será apresentada aqui.
É possível verificar também como a centralidade está distribuída entre os vértices colorindo-os de acordo com suas medidas de centralidade. Para isso escolhemos um padrão de cor e indicamos os valores mínimo e máximo de centralidade de grau como normalizadores de uma escala de cores. Então, plotamos novamente o grafo da rede e é possível ver quais são os nós com maiores centralidades de grau. Utilizaremos esse mesmo processo para as próximas medidas de centralidade que falaremos em seguida.

import matplotlib.pyplot as plt
import networkx as nx
G = nx.read_gml(r'diretorio')
degree = nx.degree(G)
colors=[]
for nodes in G.nodes():
    colors.append(degree[nodes])
nc = nx.draw(G, node_color=colors,node_size=120,width=0.5,edge_color='Grey',cmap=plt.cm.hot, vmin=np.min(colors), vmax=np.max(colors))
cmap = plt.cm.coolwarm
sm = plt.cm.ScalarMappable(cmap=plt.cm.hot, norm=plt.Normalize(vmin=np.min(colors), vmax=np.max(colors)))
cbar = plt.colorbar(sm)
plt.savefig('rede_6.pdf')

A imagem será apresentada aqui.
A Closeness Centrality é baseada na soma das distâncias de um vértice em relação aos demais vértices do grafo. Calculemos essa medida para nossa rede e vejamos como essa medida está distribuída entre os vértices.

closeness_centrality = nx.closeness_centrality(G)
colors=[]
for nodes in G.nodes():
    colors.append(closeness_centrality[nodes])
print(colors)
nc = nx.draw(G, node_color=colors,node_size=120,width=0.5,edge_color='Grey',cmap=plt.cm.viridis, vmin=np.min(colors), vmax=np.max(colors))
sm = plt.cm.ScalarMappable(cmap=plt.cm.viridis, norm=plt.Normalize(vmin=np.min(colors), vmax=np.max(colors)))
sm.set_array([])
cbar = plt.colorbar(sm)
plt.savefig('rede_8.pdf')

A imagem será apresentada aqui.
A Betweenness Centrality mede até que ponto um vértice se encontra em caminhos entre outros vértices. Vértices com alta intermediação podem ter influência considerável dentro de uma rede em virtude de seu controle sobre a passagem de informações entre outras pessoas. Eles também são aqueles cuja remoção da rede mais interromperá as comunicações entre outros vértices, porque eles estão no maior número de caminhos percorridos pelas mensagens.

betweenness_centrality=nx.betweenness_centrality(G)
colors=[]
for nodes in G.nodes():
    colors.append(betweenness_centrality[nodes])
nc = nx.draw(G, node_color=colors,node_size=120,width=0.5,edge_color='Grey',cmap=plt.cm.cividis, vmin=np.min(colors), vmax=np.max(colors))
sm = plt.cm.ScalarMappable(cmap=plt.cm.cividis, norm=plt.Normalize(vmin=np.min(colors), vmax=np.max(colors)))
sm.set_array([])
cbar = plt.colorbar(sm)
plt.savefig('rede_9.pdf')

A imagem será apresentada aqui.
A centralidade de autovetor mede a importância de um nó, levando em consideração a importância de seus vizinhos. O princípio principal é que conexções com nós importantes (conforme medido pela centralidade de grau) valem mais do que conexões com nós pouco importantes.

eigenvector_centrality=nx.eigenvector_centrality_numpy(G)
colors=[]
for nodes in G.nodes():
    colors.append(eigenvector_centrality[nodes])
print(colors)
nc = nx.draw(G, node_color=colors,node_size=120,width=0.5,edge_color='Grey',cmap=plt.cm.inferno, vmin=np.min(colors), vmax=np.max(colors))
sm = plt.cm.ScalarMappable(cmap=plt.cm.inferno, norm=plt.Normalize(vmin=np.min(colors), vmax=np.max(colors)))
sm.set_array([])
cbar = plt.colorbar(sm)
plt.savefig('rede_9.pdf')

A imagem será apresentada aqui.
Perceba como os nós com maior centralidade de auto-vetor estão concentrados na rede. Isso era de se esperar, uma vez que quanto maior a importância do nó a que um nó se conecta maior sua centralidade de auto-vetor o que faz com que os que estão associados a nós que têm alta centralidade de auto-vetor também tenham centralidade de auto-vetor alta.

Por fim, vamos definir uma função para cada medida de centralidade que tem como objetivo capturar os nomes dos livros que estejam simultaneamente entre os 10 livros com maior medida de centralidade para as 4 centralidades calculadas.

def books_in_all_measures(network):
    l1 = list()
    closeness_centrality = nx.closeness_centrality(network)
    top_10_nodes_by_closeness_centrality = sorted(closeness_centrality.items(),key=lambda x:x[1],reverse=True)[0:10]
    for i in range(0,9):
        l1.append(top_10_nodes_by_closeness_centrality[i][0])
    l2 = list()
    betweenness_centrality=nx.betweenness_centrality(G)
    top_10_nodes_by_betweenness_centrality = sorted(betweenness_centrality.items(),key=lambda x:x[1],reverse=True)[0:10]
    for i in range(0,9):
        l2.append(top_10_nodes_by_betweenness_centrality[i][0])
    l3 = list()
    eigenvector_centrality=nx.eigenvector_centrality_numpy(G)
    top_10_nodes_by_eigen_centrality = sorted(eigenvector_centrality.items(),key=lambda x:x[1],reverse=True)[0:10]
    for i in range(0,9):
        l3.append(top_10_nodes_by_eigen_centrality[i][0])
    l4 = list()
    degree = nx.degree(network)
    top_10_nodes_by_degree_centrality = sorted(degree(),key=lambda x:x[1],reverse=True)[0:10]
    for i in range(0,9):
        l4.append(top_10_nodes_by_degree_centrality[i][0])
    all_measures=list()
    for i in top_10_degree_books_names(network):
        if i in top_10_closeness_books_names(network):
            if i in top_10_betweenness_books_names(network):
                if i in top_10_eigen_books_names(network):
                    all_measures.append(i)
    if len(all_measures)==0:
        return "List is Empty. No book belongs to all the calculated measures"
    else:
        print(all_measures)
        for i in all_measures:
            print(i,G.node[i])

Essa função retorna a seguinte lista: ['American Dynasty', 'The Price of Loyalty']. Portanto, esses dois livros, provavelmente, são os livros mais importantes da rede.

comentou 3 dias atrás por Renata Oliveira (46 pontos)  
Olá, Andrei. Muito interessantes os dados que tu pegaste para fazer esta análise. Consegui fazer o download e reproduzir os resultados. Algumas observações sobre a tua resposta: primeiramente, lá no início quando há o primeiro gráfico da rede, logo antes da primeira figura, o "nx.draw..." não está formatado como código. Sugiro apenas alterar o formato daquela linha. Em relação ao último código, que define uma função para encontrar os livros mais importantes da rede, fiz algumas alterações para chegar à resposta pois copiando exatamente da forma como está na tua resposta recebi uma mensagem de erro quando tentei definir a função. As alterações que fiz foram: 1) trocar "betweenness_centrality=nx.betweenness_centrality(G)" por "betweenness_centrality=nx.betweenness_centrality(network)" e "nx.eigenvector_centrality_numpy(G)" por "nx.eigenvector_centrality_numpy(network)" para que não haja problema caso se queira aplicar a função a qualquer rede "network" dada como parâmetro; 2) as listas l1, l2, l3 e l4 são aquelas que guardam os nomes dos top 10 livros de acordo com cada medida, por isso obtive o erro "name 'top_10_degree_books_names' is not defined". Assim, substitui no loop que completa a lista "all_measures" os nomes que tu colocaste por l1, l2, l3, l4: algo como "for i in l1: if i in l2: if i in l3: if i in l4: all_measures.append(i)", com as devidas identações.  Finalmente, as duas últimas linhas de código foram excluídas pois não se fizeram necessárias. Com estas alterações e incluindo a linha "books_in_all_measures(G)" que de fato aplica a função definida à rede G, obtive a mesma lista de livros considerados mais importantes.
...