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

Análise empírica de redes complexas - Atores de filmes (Strogatz e Watts)

0 votos
18 visitas
perguntada Set 22 em Sistemas Complexos por Renan Abrantes (1 ponto)  
Compartilhe

1 Resposta

0 votos
respondida Set 22 por Renan Abrantes (1 ponto)  

Contexto

Em 1998, Steven Strogatz e Duncan Watts fizeram uso de uma rede de atores de filmes para analisar características de small-world networks. Esse tipo de rede é altamente clusterizado e apresenta pequenas distâncias entre os seus vértices.

A base de dados dessa rede está disponível no sítio eletrônico do livro Complex Networks: Principles, Methods and Applications (V. Latora, V. Nicosia, G. Russo, 2017) , no capítulo 2. Cada vértice da rede é um ator e existe uma conexão entre dois atores se eles participaram de um mesmo filme ao longo de sua trajetória profissional.

Como essa é uma rede relativamente pesada, com 248.243 vértices e 8.302.734 arestas, sua análise por meio do NetworkX fica prejudicada. O NetworkX é um pacote de Python comumente utilizado para análise de redes. Entretanto, quando comparada a outras ferramentas de análise de redes, é a de menor desempenho, dificultando a leitura e análise de grandes redes. Veja os resultados de performance extraídos deste link:
A imagem será apresentada aqui.

Uma vez que o NetworkX não é das melhores ferramentas para análise de grandes redes, escolhi o NetworKit para realizar a análise da rede de atores de filmes. O NetworKit foi desenhado explicitamente para grandes redes e também pode ser utilizado via Python.

Leitura da rede

São utilizados os seguintes módulos de python para a análise:

import csv
import networkit as nk
import numpy as np
import matplotlib.pyplot as plt
import pandas as pd
import powerlaw

O primeiro passo é ler a rede e de atores e ter uma visão geral dela. Para se ter essa visão, utiliza-se a função overview. Adicionalmente, uma vez que a análise feita por Strogatz e Watts é feita integralmente sobre o largest connected component dessa rede, o resto da análise será feito em cima desse componente. O maior componente conectado da rede é o subconjunto que tem o maior número de vértices respeitando a condição de que todos eles estejam conectados ao menos a outro vértice.

#Ler a rede
G = nk.readGraph('movie_actors.net', nk.Format.EdgeListSpaceZero)
print('Overview of movie actors network:')
nk.overview(G)

#Procurar pelo largest connected component
con_c = nk.components.ConnectedComponents(G)
con_c.run()
giant = con_c.extractLargestConnectedComponent(G)
print('Overview of the largest connected component:')
nk.overview(giant)

Os resultados do overview são:
A imagem será apresentada aqui.

A imagem será apresentada aqui.

Como era de se esperar, a rede lida não é direcionada (undirected) e não tem pesos nas suas arestas (unweighted). Afinal, não é possível direcionar conexões recíprocas e basta apenas ter participado de um filme com outro ator para se ter a conexão com ele. Para essa rede, não importa se os atores estrelaram cem filmes ou apenas um filme juntos.

O número de atores isolados , que não participaram de nenhum filme com nenhum outro ator da rede (haja monólogos no cinema; ou não), é 22660.

O número de componentes conectados dessa rede é 22731, ou seja, há 22731 subconjuntos distintos de vértices em que todos eles estão conectados. Por sua vez, o maior componente conectado tem 225226 atores, representando 90,73% da rede original.

Outros dados do overview serão explorados mais à frente.

De agora em diante, toda a análise será feita considerando o maior componente conectado!

Análise de Centralidade - Os Atores Mais Importantes

Primeiro vamos criar um dataframe com os nomes dos atores, para posteriormente inserir as medidas de centralidade como atributos dos vértices.

cdata={}
df=pd.DataFrame(cdata) #cria dataframe vazio a partir do dicionário vazio acima

nnodes=list(range(G.numberOfNodes())) #cria lista com ids dos nodes
df['Node IDs'] = nnodes

names=[]
with open ('movie_actors_names_dists') as fh: #cria lista com nomes dos atores
    reader = csv.reader(fh, delimiter='\t')
    for i in reader:
        names.append(i[1])
df['ActorNames'] = names

Agora vamos calcular as seguintes medidas de centralida: degree, closeness, pagerank e betweenness.

    #Degree
dc=nk.centrality.DegreeCentrality(giant)
dc.run()
list_dc=dc.scores()
df['Degree']= list_dc

    #Closeness (como rodar o closeness exato é impossível considerando o tamanho dessa rede e as restrições do PC, opta-se pelo ApproxCloseness)
cc=nk.centrality.ApproxCloseness(giant, nSamples=1500, normalized=True)
cc.run()
list_cc=cc.scores()
df['Closeness']= list_cc

    #PageRank
pc=nk.centrality.PageRank(giant)
pc.run()
list_pc=pc.scores()
df['PageRank']= list_pc

    #Betweenness (como rodar o betweenness exato é impossível considerando o tamanho dessa rede e as restrições do PC, opta-se pelo ApproxBetweenness)
bc=nk.centrality.ApproxBetweenness(giant, epsilon=0.01, delta=0.1, 
universalConstant=1.0)
bc.run()
list_bc=bc.scores()
df['Betweenness']= list_bc

É importante notar que os cálculos exatos de closeness e betweenness são virtualmente impossíveis dadas as restrições de processamento e memória do meu computador. Dessa forma, optou-se por usar medidas aproximadas. Para mais informações sobre o algoritmo de aproximação de closeness, clique aqui. Para mais informações sobre o algoritmo de aproximação de betweenness, clique aqui.

Agora vamos organizar as medidas de centralidade e mostrar os top 10 atores conforme cada uma delas.

  #Organizar as medidas de centralidade e mostrar os top 10 de cada uma

sorteddf_d=df.sort_values(by=['Degree'], ascending=False)
sorteddf_c=df.sort_values(by=['Closeness'], ascending=False)
sorteddf_p=df.sort_values(by=['PageRank'], ascending=False)
sorteddf_b=df.sort_values(by=['Betweenness'], ascending=False)
print(sorteddf_d.head(10))
print(sorteddf_c.head(10))
print(sorteddf_p.head(10))
print(sorteddf_b.head(10))

Os atores com maior grau de conexão (degree), ou seja, que atuaram com o maior número de atores diferentes, são:

A imagem será apresentada aqui.

Irving Bacon é o ator com maior grau de conexão, atuando com 3080 diferentes atores ao longo de sua trajetória profissional.

Os atores com maior closeness centrality, ou seja, que têm a menor distância média para os outros da rede, são:

A imagem será apresentada aqui.

Rod Steiger tem a maior centralidade de acordo com closeness. Além de atuar em inúmeros filmes (seu grau de conexão é 1599), sua carreira passou por diversas fases, com atuações em filmes aclamados, estrangeiros, independentes e tipo B. Dentre seus filmes mais famosos, estão Doutor Jivago e No Calor da Noite, ambos da década de 1960.

A betweenness centrality calcula o número de menores caminhos entre todos os vértices e que passam por um vértice específico, atuando como uma espécie de broker de informação. Os atores com maior betweenness são:

A imagem será apresentada aqui.

Max Von Sidow é o ator com maior betweenness. Von Sidow foi um ator sueco extremamente prolífico. É a cara conhecida dos filmes de Ingmar Bergman (O Sétimo Selo, Morangos Silvestres, A Fonte da Donzela, dentre outros), além de ter feito inúmeros filmes em Hollywood (O Exorcista, Duna, Minority Report, dentre outros). É possível que Von Sidow tenha alto betweenness por justamente servir de ponte entre filmes "estrangeiros" e hollywoodianos.

Por fim, vejamos os atores com maior pagerank, que é uma derivação da centralidade de autovetor, tentando captar a importância de um vértice a partir da importância dos vértices vizinhos a ele. O pagerank é um dos algoritmos utilizados pela Google para classificar páginas de internet.

A imagem será apresentada aqui.

John Carradine é o ator com maior pagerank. Carradine foi um dos expoentes do cinema de John Ford, tendo atuado em As Vinhas da Ira e Nos Tempos da Diligência. Henry Fonda, John Wayne e diversos outros famosos atores atuaram com Carradine, apontando uma possível explicação para seu alto pagerank.

Análise de Centralidade - Distribuições, Power Law, Scale-Free e Clustering

Conforme o overview apresentado na seção de leitura de rede, o grau médio de conexões da rede (avg degree) é de 73,7.

Embora essa estatística seja interessante para avaliar a rede - há bastante conexão por ator, também é interessante avaliar a distribuição das medidas de centralidade conforme a sua frequência. Para tanto, plotei as distribuições de degree e betweenness em loglog, já buscando indicações de que essas distribuições possam seguir uma power law.

    #Plotar Degree e Betweenness

sorted_dc=sorted(list_dc, reverse=True)
sorted_bc=sorted(list_bc, reverse=True)

fig1 = plt.figure("Degree and Betweenness Distributions", figsize=(8, 8))
axgrid1 = fig1.add_gridspec(5, 4)

ax1 = fig1.add_subplot(axgrid1[:, :2])
ax1.loglog(*np.unique(sorted_dc, return_counts=True), '.')
ax1.set_title("Degree")
ax1.set_xlabel("Log Degree")
ax1.set_ylabel("Log Number of Nodes")

ax2 = fig1.add_subplot(axgrid1[:, 2:])
ax2.loglog(*np.unique(sorted_bc, return_counts=True), '.')
ax2.set_title("Betweenness")
ax2.set_xlabel("Log Betweenness")
ax2.set_ylabel("Log Number of Nodes")

fig1.tight_layout()
plt.show()

Veja o resultado:
A imagem será apresentada aqui.

Tanto a distribuição de degree como de betweenness se desenham em uma linha reta, aparentando seguirem uma power law. Entretanto, como suas caudas apresentam certa descontinuidade, é interessante utilizar o módulo do Python denominado powerlaw para de fato concluir isso. Fiz essa avaliação para a distribuição de degree.

    #Checar se distribuição de degrees segue power Law
fit = powerlaw.Fit(sorted_dc, discrete=True)
print('O expoente da distribuição de power law é', fit.alpha)
print('O erro-padrão da estimação é de', fit.sigma)

Veja o resultado:
A imagem será apresentada aqui.

Nesse caso, o erro-padrão da estimação para verificar se a distribuição é uma power law foi de 0,0004. A conclusão é de que a rede de atores segue uma power law, com expoente aproximado de 2,4. As redes que seguem power law em sua distribuição de conexões são chamadas de scale-free networks. Isso significa que apesar da grande maioria dos atores ter poucas conexões, a probabilidade de se achar atores com um grande nível de conexões não é negligível. Esses atores tendem a atuar como hubs na rede.

Já o coeficiente de clustering da rede é de 0,79 (conforme dados do overview). Esse coeficiente mede a probabilidade de dois vértices conectados a um terceiro também estarem conectados entre si, uma forma de mensurar o número de triângulos na rede (conexões mútuas entre três vértices). O alto coeficiente de clustering da rede de atores de filmes demonstra que essa rede se organiza formando grupos de atores com alta relação de coatuação. E é justamente a propriedade de que alguns atores que estão dentro de um cluster, mas ligados a outros atores fora desse cluster, que facilita a construção dessa propriedade de small-network.

O Experimento de Milgram e Seis Graus de Kevin Bacon

Uma das características de redes de um "mundo pequeno" é ter uma distância mínima pequena entre quaisquer vértices da rede. No caso da rede de atores, a distância média da rede é de 3,65. Ou seja, na média, um ator da rede está a 3,65 passos de distância de outro ator. Infelizmente, esse resultado foi extraído do artigo do Steven Strogatz e Duncan Watts, mas não processado no presente exercício, uma vez que é extremamente demandante para o PC em que foi feito.

De qualquer forma, foi possível realizar um exercício lúdico, denominado Seis Graus de Kevin Bacon. Essa é uma brincadeira que assume que Kevin Bacon é o centro do mundo dos artistas de filme e quantifica a que distância estaria qualquer ator de Kevin Bacon. A brincadeira foi tão longe que há um site para computar essa estatística, o Oracle of Bacon, e que o próprio Kevin Bacon lançou em 2020 um podcast chamado The Last Degree of Kevin Bacon.

Os seis graus de separação estão relacionados ao experimento que Stanley Milgram, psicólogo estadunidense, realizou na década de 1960. Milgram enviou postais a 160 pessoas que viviam em Omaha, Nebraska, pedindo que achassem uma pessoa específica que vivia em Boston, Massachussetts. Se não conhecessem a pessoa diretamente, os 160 deveriam encaminhar esse postal a outra pessoa que elas achassem que seriam conhecidas do destinatário final. Milgram observou que para chegar ao destinatário final as distâncias percorridas foram de duas a dez pessoas, com uma mediana de cinco pessoas, ou seja, seis graus de separação.

Baseado no exercício de Milgram e na brincadeira mencionada, vamos calcular primeiro qual é a distância média de todos os atores para Kevin Bacon, dito como centro do mundo de entrenimento. Da mesma forma, é interessante calcular a distância para Rod Steiger, pois esse é o ator que tem a menor closeness centrality, ou seja a menor distância média para todos os outros atores dessa rede.

#Six Degrees of Kevin Bacon

baconnumber=nk.distance.BFS(giant, 0) #calcula a distância de Kevin Bacon para os outros atores da rede
baconnumber.run()
list_bacon=baconnumber.getDistances()
df['BaconNumber']=list_bacon

steigernumber=nk.distance.BFS(giant, 1494) #calcula a distância de Rod Steiger para os outros atores da rede
steigernumber.run()
list_steiger=steigernumber.getDistances()
df['SteigerNumber']=list_steiger

allcon_c=con_c.getComponents()
nodesgiant = allcon_c[0]
df2 = df[df['Node IDs'].isin(nodesgiant)] #filtra o dataframe com os atores que estão no giant component

nnodesgiant=list(range(giant.numberOfNodes())) #cria lista com ids dos nodes no giant component
df2.insert(1, "Giant Node IDs", nnodesgiant)

    #Average shortest path
avgbacon=df2['BaconNumber'].sum()/giant.numberOfNodes()
print('The average distance to Kevin Bacon is', avgbacon)
avgsteiger=df2['SteigerNumber'].sum()/giant.numberOfNodes()
print('The average distance to Rod Steiger is', avgsteiger)

Ao passo que Kevin Bacon tem uma distância mínima média de aproximadamente 2,81 atores, Rod Steiger tem uma de 2,54. Não surpreende, já que na verdade Steiger é o ator com maior closeness nessa rede.

Agora vamos analisar o histograma de cada uma dessas medidas, o Bacon Number e o Steiger Number.

    #Plotar histograma de BaconNumber e SteigerNumber

fig2 = plt.figure("Bacon and Steiger Number Histograms", figsize=(8, 8))
axgrid2 = fig2.add_gridspec(5, 4)

bx1 = fig2.add_subplot(axgrid2[:, :2])
bx1.hist(df2['BaconNumber'], bins=[1, 2, 3, 4, 5, 6, 7, 8], density=True)
bx1.set_yscale('log', nonpositive='clip')
bx1.set_title("Bacon Number")
bx1.set_xlabel("Distance")
bx1.set_ylabel("Log Probability")

bx2 = fig2.add_subplot(axgrid2[:, 2:])
bx2.hist(df2['SteigerNumber'], bins=[1, 2, 3, 4, 5, 6, 7, 8], density=True)
bx2.set_yscale('log', nonpositive='clip')
bx2.set_title("Steiger Number")
bx2.set_xlabel("Distance")
bx2.set_ylabel("Log Probability")

fig2.tight_layout()
plt.show()

Observe os resultados na seguinte figura:
A imagem será apresentada aqui.

Reparem que a distância máxima de ambos os atores se iguala a oito. De qualquer forma, Steiger apresenta uma concentração maior de distâncias iguais a dois e a três do que Bacon.

Independentemente de quem seja a figura central do cinema, os resultados demonstram o quão próximos estão os atores nessa rede. Apesar de serem 225226 atores, de forma geral há uma pequena distância entre qualquer um deles.

Exportar para csv

Agora, falta só exportar todos os atributos criados no dataframe para um arquivo csv. Isso facilita análises posteriores.

#Exportar atributos dos nodes para csv

df.to_csv('Movie_Actors_Attributes.csv')

A rede de atores de Strogatz e Watts foi construída em 1997. Quem vocês acham que seriam os atores mais centrais dessa rede se ela fosse construída agora? Nicholas Cage? Glenn Close? Amitabh Bachchan? Meryl Streep? Morgan Freeman? Façam suas apostas!

...