In [1]:
import sys
sys.path.append('..')
import socnet as sn
Configurando a biblioteca:
In [2]:
sn.node_size = 10
sn.edge_width = 1
sn.edge_color = (192, 192, 192)
sn.node_label_position = 'top center'
O objetivo desta atividade é realizar $24$ simulações de centralidade diferentes, para avaliar o desempenho de medidas clássicas em relação a diferentes processos de fluxo. Dessas $24$ simulações, são $12$ sobre o grafo g1 e $12$ sobre o grafo g2.
In [3]:
g1 = sn.load_graph('renaissance.gml', has_pos=True)
g2 = sn.load_graph('../encontro02/1-introducao.gml', has_pos=True)
O primeiro grafo corresponde aos casamentos entre famílias de Florença durante a Renascença.
J. F. Padgett, C. K. Ansell, 1993. Robust action and the rise of the Medici, 1400–1434. American Journal of Sociology 98, págs. 1259-1319.
In [4]:
sn.show_graph(g1, nlab=True)
O segundo grafo corresponde ao estudo de caso do primeiro encontro.
In [ ]:
sn.show_graph(g2, nlab=True)
Das $12$ simulações sobre um dos grafos, são $6$ de closeness e $6$ de betweenness:
In [ ]:
from random import choice
TIMES = 1000
Em uma simulação de closeness, para cada origem s e destino t, mede-se o tempo que o fluxo leva para chegar de s a t. O closeness simulado de um nó s é a soma de todos os tempos medidos quando esse nó é uma origem. Como o fluxo pode ter passos aleatórios, o processo é repetido TIMES vezes e considera-se a média.
A função abaixo calcula o closeness simulado em relação a transferência através de geodésicas.
In [ ]:
def simulate_closeness_transfer_geodesic(g):
# Inicialização das médias.
for n in g.nodes():
g.node[n]['simulated_closeness'] = 0
for _ in range(TIMES):
for s in g.nodes():
# Inicialização do closeness de s.
g.node[s]['closeness'] = 0
for t in g.nodes():
if s != t:
# Função caixa-preta que calcula, para cada nó, seu subconjunto
# de vizinhos que pertencem a geodésicas de s a t. Esse subconjunto
# é armazenado no atributo shortest_neighbors. Vocês vão aprender
# a abrir essa caixa-preta em encontros posteriores.
sn.build_shortest_paths(g, s, t)
# Dependendo do processo, o fluxo pode não ter sucesso, ou seja,
# pode ficar preso em uma parte do grafo sem nunca atingir t.
# Quando isso acontece, simplesmente tenta-se novamente.
success = False
while not success:
# Chamamos de "dono" um nó que possui o bem conduzido pelo
# fluxo. No início do processo, sabemos que o único dono é s.
for n in g.nodes():
g.node[n]['owner'] = False
g.node[s]['owner'] = True
time = 1
while True:
# O conjunto nodes_reached indica os nós que o fluxo
# alcança ao "avançar mais um passo".
nodes_reached = set()
for n in g.nodes():
if g.node[n]['owner']:
# TRANSFERÊNCIA: Escolhemos aleatoriamente um dos vizinhos válidos.
# GEODÉSICA: Os vizinhos válidos são os que pertencem a geodésicas.
m = choice(g.node[n]['shortest_neighbors'])
nodes_reached.add(m)
# TRANSFERÊNCIA: O fluxo transfere o bem para os nós que o fluxo
# alcança, portanto o nó deixa de ser dono. Nos processos baseados
# em duplicação, a linha abaixo não pode ser executada.
g.node[n]['owner'] = False
# Todos os nós que o fluxo alcança tornam-se donos.
for n in nodes_reached:
g.node[n]['owner'] = True
# Se alcançamos t, interrompemos o fluxo e paramos de tentar.
if t in nodes_reached:
success = True
break
# Se não alcançamos ninguém, interrompemos o fluxo e tentamos novamente.
if not nodes_reached:
break
time += 1
# Soma do tempo de s a t ao closeness de s.
g.node[s]['closeness'] += time
# Incremento das médias.
for n in g.nodes():
g.node[n]['simulated_closeness'] += g.node[n]['closeness']
# Finalização das médias.
for n in g.nodes():
g.node[n]['simulated_closeness'] /= TIMES
Vamos comparar o closeness simulado com o closeness teórico.
Para calcular o segundo, basta usar o algoritmo de busca em largura que vimos em encontros anteriores.
In [ ]:
from math import inf, isinf
from queue import Queue
def build_closeness(g):
for s in g.nodes():
# início da busca em largura
q = Queue()
for n in g.nodes():
g.node[n]['d'] = inf
g.node[s]['d'] = 0
q.put(s)
while not q.empty():
n = q.get()
for m in g.neighbors(n):
if isinf(g.node[m]['d']):
g.node[m]['d'] = g.node[n]['d'] + 1
q.put(m)
# fim da busca em largura
g.node[s]['theoretical_closeness'] = 0
for n in g.nodes():
g.node[s]['theoretical_closeness'] += g.node[n]['d']
Comparação de closeness no grafo g1:
(vai demorar alguns segundos)
In [ ]:
build_closeness(g1)
simulate_closeness_transfer_geodesic(g1)
for n in g1.nodes():
print(g1.node[n]['label'], g1.node[n]['theoretical_closeness'], g1.node[n]['simulated_closeness'])
Comparação de closeness no grafo g2:
(vai demorar alguns segundos)
In [ ]:
build_closeness(g2)
simulate_closeness_transfer_geodesic(g2)
for n in g2.nodes():
print(g2.node[n]['label'], g2.node[n]['theoretical_closeness'], g2.node[n]['simulated_closeness'])
Em uma simulação de betweenness, para cada origem s, destino t e intermediário n, mede-se a quantidade de vezes que o fluxo passa por n antes de chegar de s a t. O betweenness simulado de um nó n é a soma de todas as quantidades medidas quando esse nó é um intermediário. Como o fluxo pode ter passos aleatórios, o processo é repetido TIMES vezes e considera-se a média.
A função abaixo calcula o betweenness simulado em relação a transferência através de geodésicas.
In [ ]:
def simulate_betweenness_transfer_geodesic(g):
# Inicialização das médias.
for n in g.nodes():
g.node[n]['simulated_betweenness'] = 0
for _ in range(TIMES):
# Inicialização de todos os betweenness.
for n in g.nodes():
g.node[n]['betweenness'] = 0
for s in g.nodes():
for t in g.nodes():
if s != t:
# Função caixa-preta que calcula, para cada nó, seu subconjunto
# de vizinhos que pertencem a geodésicas de s a t. Esse subconjunto
# é armazenado no atributo shortest_neighbors. Vocês vão aprender
# a abrir essa caixa-preta em encontros posteriores.
sn.build_shortest_paths(g, s, t)
# Dependendo do processo, o fluxo pode não ter sucesso, ou seja,
# pode ficar preso em uma parte do grafo sem nunca atingir t.
# Quando isso acontece, simplesmente tenta-se novamente.
success = False
while not success:
# Chamamos de "dono" um nó que possui o bem conduzido pelo
# fluxo. No início do processo, sabemos que o único dono é s.
for n in g.nodes():
g.node[n]['owner'] = False
g.node[s]['owner'] = True
for n in g.nodes():
if n != s and n != t:
g.node[n]['partial_betweenness'] = 0
while True:
# O conjunto nodes_reached indica os nós que o fluxo
# alcança ao "avançar mais um passo".
nodes_reached = set()
for n in g.nodes():
if g.node[n]['owner']:
# TRANSFERÊNCIA: Escolhemos aleatoriamente um dos vizinhos válidos.
# GEODÉSICA: Os vizinhos válidos são os que pertencem a geodésicas.
m = choice(g.node[n]['shortest_neighbors'])
nodes_reached.add(m)
# TRANSFERÊNCIA: O fluxo transfere o bem para os nós que o fluxo
# alcança, portanto o nó deixa de ser dono. Nos processos baseados
# em duplicação, a linha abaixo não pode ser executada.
g.node[n]['owner'] = False
# Todos os nós que o fluxo alcança tornam-se donos.
for n in nodes_reached:
g.node[n]['owner'] = True
# Se alcançamos t, interrompemos o fluxo e paramos de tentar.
if t in nodes_reached:
success = True
break
# Se não alcançamos ninguém, interrompemos o fluxo e tentamos novamente.
if not nodes_reached:
break
for n in nodes_reached:
if n != s and n != t:
g.node[n]['partial_betweenness'] += 1
# Soma de todos os betweenness parciais dos intermediários.
for n in g.nodes():
if n != s and n != t:
g.node[n]['betweenness'] += g.node[n]['partial_betweenness']
# Incremento das médias. Divide-se o valor por 2 para
# desconsiderar a simetria de um grafo não-dirigido.
for n in g.nodes():
g.node[n]['simulated_betweenness'] += g.node[n]['betweenness'] / 2
# Finalização das médias.
for n in g.nodes():
g.node[n]['simulated_betweenness'] /= TIMES
Vamos comparar o betweenness simulado com o betweennesss teórico.
Para calcular o segundo, basta usar a função caixa-preta build_betweenness. Vocês vão aprender a abrir essa caixa-preta em encontros posteriores.
Comparação de betweenness no grafo g1:
(vai demorar alguns segundos)
In [ ]:
sn.build_betweenness(g1)
simulate_betweenness_transfer_geodesic(g1)
for n in g1.nodes():
print(g1.node[n]['label'], g1.node[n]['theoretical_betweenness'], g1.node[n]['simulated_betweenness'])
Comparação de betweenness no grafo g2:
(vai demorar alguns segundos)
In [ ]:
sn.build_betweenness(g2)
simulate_betweenness_transfer_geodesic(g2)
for n in g2.nodes():
print(g2.node[n]['label'], g2.node[n]['theoretical_betweenness'], g2.node[n]['simulated_betweenness'])
In [ ]:
def simulate_closeness_serial_path(g):
pass
In [ ]:
def simulate_closeness_transfer_path(g):
pass
In [ ]:
def simulate_closeness_serial_trail(g):
pass
In [ ]:
def simulate_closeness_transfer_trail(g):
pass
In [ ]:
def simulate_closeness_serial_walk(g):
pass
In [ ]:
def simulate_closeness_transfer_walk(g):
pass
In [ ]:
def simulate_betweenness_serial_path(g):
pass
In [ ]:
def simulate_betweenness_transfer_path(g):
pass
In [ ]:
def simulate_betweenness_serial_trail(g):
pass
In [ ]:
def simulate_betweenness_transfer_trail(g):
pass
In [ ]:
def simulate_betweenness_serial_walk(g):
pass
In [ ]:
def simulate_betweenness_transfer_walk(g):
pass
Para encontros posteriores, serão pedidas análises dos resultados dessas simulações.
Na consolidação do módulo de centralidade, você pode atingir conceito avançado no objetivo traduzir conceitos sociológicos para teoria dos grafos e algoritmos em grafos se formular e implementar uma proposta coerente de degree simulado. Essa proposta deve ser entregue na mesma data.