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

Prove que a multiplicação de uma matriz de adjacência de uma rede bipartite N x V por sua transposta resulta em uma matriz de adjacência de co-ocorrências para N

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

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

Tendo como base a rede de coaparições de atores em filmes utilizada por Strogatz e Watts, os autores do livro pedem para que sejam provadas as condições de construção da matriz de adjacência dessa rede a partir da matriz de adjacência da rede bipartite entre atores e filmes.

No caso, a matriz de adjacência dessa rede bipartite é formada por atores, de um lado, e filmes, do outro. Se um ator participa do filme, a célula é preenchida com o valor um, senão a célula tem valor zero.

Segue transcrição do exercício:

"2.5(a) Let A be the \(N × V\) adjacency matrix describing the IMDb bipartite network of actors and movies, with \(a_i\)\(_α \)\( = 1\) if actor i has played in movie \(α\). Prove that the adjacency matrix of the graph of collaborations between actors can be obtained by constructing the \(N × N\) matrix \(B = A\)\(A^T\), and by setting equal to 0 all the diagonal terms of \(B\), and equal to 1 all non-zero off-diagonal terms."

Compartilhe

1 Resposta

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

Resposta em elaboração.

Caso queira acessar uma análise empírica da rede de atores de filmes, clique aqui.

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.

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.

Observe que essa rede de atores não é direcionada, uma vez que a participação do ator X com o ator Y em algum filme implica uma conexão unívoca de X para Y e de Y para X.

Da mesma forma, a rede não é ponderada, ou seja, ela é unweighted. Isso decorre do fato de Steven e Strogatz não colocarem pesos para um par de atores caso tenham participados de vários filmes juntos. Independentemente de participarem de um ou vários filmes juntos, a rede considera apenas se atores já atuaram juntos em alguma produção cinematográfica.

Adjacência

A matriz de adjacência de uma rede unipartite (simples) é uma matriz quadrada de \(N x N\) para as quais as células \(a_i\)\(_j\) retornam valor igual a 1 caso haja uma conexão de \(i\) para \(j\) e valor igual a 0 caso não haja conexão. Esse tipo de matriz não admite self-loops, ou seja, a conexão de um vértice com ele próprio. Dessa forma, a diagonal da matriz de adjacência se iguala a zero. Caso a rede não seja direcionada, o que é o caso da rede de atores, a matriz de adjacência é simétrica, pois uma conexão de \(i\) para \(j\) implica uma conexão de \(j\) para \(i\).

Considere \(A\) uma matriz de adjacência de uma rede bipartite \(N x K\):

\[\begin{array}{col_1 col_2 … col_n} a_{11} & a_{12} & … & a_{1k}\\ a_{21} & a_{22} & … & a_{2k}\\ ... & .... & ... & ...\\ a_{n1} & a_{n2} & ... & a_{nk}\\ \end{array}\]

Vamos assumir que \(N\) é a dimensão dos atores e \(K\) é a dimensão dos filmes. Se o ator \(i\) em \(N\) participa do filme \(j\) em \(K\), a célula retorna valor 1. Caso contrário, a célula retorna valor 0.

Multiplicando pela transposta

Conforme pedido pelo exercício, vamos criar uma matriz B de forma que ela seja o produto da matriz de adjacência da rede bipartite com a sua transposta:

\( B = A x A^T =\)

\[\begin{array}{col_1 col_2 … col_n} \sum_{j=1}^Ka_{1j}*a_{1j} & \sum_{j=1}^Ka_{1j}*a_{2j} & … & \sum_{j=1}^Ka_{1j}*a_{nj}\\ \sum_{j=1}^Ka_{2j}*a_{1j} & \sum_{j=1}^Ka_{2j}*a_{2j} & … & \sum_{j=1}^Ka_{2j}*a_{nj}\\ ... & .... & ... & ...\\ \sum_{j=1}^Ka_{nj}*a_{1j} & \sum_{j=1}^Ka_{nj}*a_{2j} & ... & \sum_{j=1}^Ka_{nj}*a_{nj}\\ \end{array}\]

Essa matriz é de tamanho \( N x K * K x N = N x N\) e é uma forma de representar uma rede unipartite na dimensão N.

Observe também que a matriz resultante é simétrica, de forma que para todo i, j, \(b_{ij} = b_{ji}\). Essa é uma propriedade da multiplicação de uma matriz por sua transposta. É isso que garante que a rede não seja direcionada.

Zerar a diagonal

Observe que a diagonal da matriz B representa a contagem para quantos dos \(K\) filmes cada ator \(i = 1, 2, ..., n\) participa. Suponha que o número de filmes da rede seja igual a 5. Se o ator \(i = 1\) participou dos filmes \(k = 3, 4, 5\), temos que \(b_{11} = 0*0 + 0*0 + 1*1 + 1*1 + 1*1 = 3\).

Como estamos interessados apenas em coparticipações entre dois atores distintos, não faz sentido a existência de self-loops na rede. É necessário, portanto, excluir da matriz os valores da diagonal, substituindo-os por zero. É exatamente o que o comando do exercício pede. Nesse caso, a matriz B seria:

\[\begin{array}{col_1 col_2 … col_n} 0 & b_{12} & … & b_{1n}\\ b_{21} & 0 & … & b_{2n}\\ ... & .... & ... & ...\\ b_{n1} & b_{n2} & ... & 0\\ \end{array}\]

Transformar uma matriz de rede ponderada para uma matriz de rede não ponderada

Da mesma forma que a diagonal contava em quantos filmes cada ator participou, os outros elementos dessa matriz contabilizam em quantos filmes os atores \(i\) e \(j\) coestrelaram. Essa é uma informação muito interessante, que poderia servir de análise para a proximidade entre certos atores no mundo do cinema.

Na rede de Strogatz e Watts, entretanto, não interessa se Johnny Depp e Helena Bonham Carter coestrelaram diversos filmes do Tim Burton. Temos que buscar somente uma variável binária, representando se os atores não participaram de um mesmo filme (igual a zero) ou se já participaram juntos de qualquer número de filmes (igual a um).

Dessa forma, é necessário substituir por um todos os valores dessa matriz que sejam maiores que um. Assim conseguimos transformar a matriz de forma a representar a variável binária "coestrelou" vs "não coestrelou".

Finalmente, chegamos a uma matriz de adjacência (unipartite) nos termos da rede de coparticipação de atores. Para tal, seguimos os seguintes passos, na ordem: 1. multiplicar a matriz de adjacência da rede bipartite de atores e filmes pela sua transposta; 2. zerar a diagonal; e 3. substituir os valores maiores que um por um.

Exemplo - Filmes do Tarantino

Infelizmente, não há disponibilidade de dados para a rede bipartite (atores x filmes) que foi utilizada para construir a rede de coparticipação de atores em filmes. Afinal, essa matriz provavelmente seria enorme, apresentando dificuldades de performance para seu tratamento. Adicionalmente, como a rede final tem 248243 atores e 8302734 coparticipações de atores, sua utilização não parece trazer ganhos para o entendimento dos passos descritos acima.

Para demonstrar os passos, proponho utilizar uma rede produzida apenas com os filmes dirigidos pelo Quentin Tarantino. Desde o começo de sua carreira, Tarantino afirma que fará apenas dez filmes na sua carreira. Como só falta um filme para fechar a conta (será?), espero que esse exercício siga bem atualizado nas próximas décadas.

Os filmes que Tarantino escreveu e dirigiu foram: Cães de Aluguel, Pulp Fiction, Jackie Brown, Kill Bill (Volumes 1 e 2), Grindhouse: Death Proof, Bastardos Inglórios, Django Livre, Os Oito Odiados, e Era Uma Vez Em Hollywood.

Para cada um dos nove filmes, extraí do Wikipedia os cinco principais atores. Se algum desses autores também tiver participado de algum filme do Tarantino sem ser um dos cinco principais, também contabilizei como participante daquele filme. A matriz de adjacência bipartite resultante tem 35 atores para os 9 filmes, com 57 participações nesses filmes. Para facilitar mais ainda o entendimento, filtrei os atores que fizeram dois ou mais filmes do Tarantino, restando 11 atores. Veja a matriz resultante de adjacência da rede bipartite do Mundo Tarantino:

A imagem será apresentada aqui.

Vamos mostrar os passos do algoritmo desse exercício no Python e, ao final, desenhar a rede do mundo Tarantino.

Primeiro, vamos ler a matriz de adjacência rede bipartite e checar o seu tamanho:

import numpy as np
import networkx as nx
import matplotlib.pyplot as plt

#Ler dados e produzir a matriz de adjacência final

A = np.loadtxt('TarantinoMovies.csv', delimiter=',', skiprows=1, usecols=np.arange(1, 10)) #ler a rede bipartite

print('This is the bipartite Tarantino network:')
print(A)
print('The bipartite Tarantino network has a size of', A.shape)

A imagem será apresentada aqui.

Veja que a matriz é de 11 x 9 (atores x filmes), como já mencionado anteriormente.

Agora vamos multiplicar a matriz por sua transposta e ver o resultado:

At = A.transpose() #gerar a transposta
B = np.matmul(A, At) #multiplicar a matriz por sua transporta
print('This is the the result of the matrix multiplication:')
print(B)
print('The result of the matrix multiplication with its transpose is a square matrix of', 
B.shape)

A imagem será apresentada aqui.

Observe que a matriz é simétrica, de tamanho 11 x 11 (atores x atores). A diagonal representa o número de filmes do Tarantino que cada ator participou. A célula \(b_{4,4}\) significa que Samuel L. Jackson fez seis filmes do Tarantino, o ator mais participativo da rede.

Já os valores de fora da diagonal representam quantos filmes o ator X coatuou com o ator Y. A célula \(b_{4,1}\) indica que Samuel L. Jackson e Harvey Keitel atuaram juntos em dois filmes (Pulp Fiction e Bastardos Inglórios).

Vamos, por último, zerar os valores da diagonal e substituir os valores da não diagonal maiores que um por um:

ZeroB = np.fill_diagonal(B, 0) #zerar as diagonais
FinalB = np.where(B > 1, 1, B) #substituir valores maiores que um por um
print('The final adjacency matrix for the Tarantino network is:')
print(FinalB)

A imagem será apresentada aqui.

A matriz produzida está conforme a rede de Strogatz e Watts, contudo aplicada apenas para o mundo de Tarantino (e de maneira muito simplista). É uma matriz de adjacência unipartite que representa se atores atuaram alguma vez juntos ou não. Surpreendentemente (ou não), Samuel L. Jackson coatuou com todos os outros dez atores da rede!

Só por curiosidade, vamos desenhar essa rede com os nomes de cada ator e o tamanho de cada vértice conforme o seu grau de conexão:

network = nx.from_numpy_array(FinalB)
deg = dict(network.degree)
names={0: 'Harvey Keitel', 1: 'Tim Roth', 2: 'Steve Buscemi', 3: 'Samuel L. Jackson', 4: 'Uma Thurman', 5: 'Michael Madsen', 6: 'Kurt Russell', 7: 'Brad Pitt', 8: 'Christoph Waltz', 9: 'Leonardo DiCaprio', 10: 'Walton Goggins'}
nx.draw_networkx(network, nodelist=deg.keys(), node_size=[i**3.5 for i in deg.values()], labels=names, font_size=8)
plt.show()

A imagem será apresentada aqui.

Observe que Michael Madsen e Tim Roth também tem alto grau de conexão. Eles só não atuaram com Christoph Waltz. Afinal, nenhum dos dois fez Bastardos Inglórios e Django Livre.

...