In [ ]:
import sys
sys.path.append('..')
import socnet as sn
Configurando a biblioteca:
In [ ]:
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 [ ]:
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 [ ]:
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):
# 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.
# CAMINHO: Os vizinhos válidos são os quais ainda não foram percorridos.
neighbors = g.neighbors(n)
n_percorridos = []
for node_n in neighbors:
if node_n not in nodes_reached:
n_percorridos.append(node_n)
if len(n_percorridos) > 0:
m = choice(n_percorridos)
else:
break
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
In [ ]:
build_closeness(g1)
simulate_closeness_serial_path(g1)
for n in g1.nodes():
print(g1.node[n]['label'], g1.node[n]['theoretical_closeness'], g1.node[n]['simulated_closeness'])
In [ ]:
build_closeness(g2)
simulate_closeness_serial_path(g2)
for n in g2.nodes():
print(g2.node[n]['label'], g2.node[n]['theoretical_closeness'], g2.node[n]['simulated_closeness'])
In [ ]:
def simulate_closeness_transfer_path(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.
# CAMINHO: Os vizinhos válidos são os quais ainda não foram percorridos.
neighbors = g.neighbors(n)
n_percorridos = []
for node_n in neighbors:
if node_n not in nodes_reached:
n_percorridos.append(node_n)
if len(n_percorridos) > 0:
m = choice(n_percorridos)
else:
break
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
In [ ]:
build_closeness(g1)
simulate_closeness_transfer_path(g1)
for n in g1.nodes():
print(g1.node[n]['label'], g1.node[n]['theoretical_closeness'], g1.node[n]['simulated_closeness'])
In [ ]:
build_closeness(g2)
simulate_closeness_transfer_path(g2)
for n in g2.nodes():
print(g2.node[n]['label'], g2.node[n]['theoretical_closeness'], g2.node[n]['simulated_closeness'])
In [ ]:
def simulate_closeness_serial_trail(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()
arestas_reached = set()
for n in g.nodes():
#if g.node[n]['owner']:
# TRANSFERÊNCIA: Escolhemos aleatoriamente um dos vizinhos válidos.
# TRILHA: não passa mais de uma vez por uma mesma aresta
arestas = g.edges(n)
arestas_percorridas = []
for aresta_a in arestas:
if aresta_a not in arestas_reached:
arestas_percorridas.append(aresta_a)
m = choice(arestas_percorridas)
arestas_reached.add(m)
if(m[0] == n):
node_r = m[1]
else:
node_r = m[0]
nodes_reached.add(node_r)
# 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
In [ ]:
build_closeness(g1)
simulate_closeness_serial_trail(g1)
for n in g1.nodes():
print(g1.node[n]['label'], g1.node[n]['theoretical_closeness'], g1.node[n]['simulated_closeness'])
In [ ]:
build_closeness(g2)
simulate_closeness_serial_trail(g2)
for n in g2.nodes():
print(g2.node[n]['label'], g2.node[n]['theoretical_closeness'], g2.node[n]['simulated_closeness'])
In [ ]:
def simulate_closeness_transfer_trail(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()
arestas_reached = set()
for n in g.nodes():
if g.node[n]['owner']:
# TRANSFERÊNCIA: Escolhemos aleatoriamente um dos vizinhos válidos.
# TRILHA: não passa mais de uma vez por uma mesma aresta
arestas = g.edges(n)
arestas_percorridas = []
for aresta_a in arestas:
if aresta_a not in arestas_reached:
arestas_percorridas.append(aresta_a)
m = choice(arestas_percorridas)
arestas_reached.add(m)
if(m[0] == n):
node_r = m[1]
else:
node_r = m[0]
nodes_reached.add(node_r)
# 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
In [ ]:
build_closeness(g1)
simulate_closeness_transfer_trail(g1)
for n in g1.nodes():
print(g1.node[n]['label'], g1.node[n]['theoretical_closeness'], g1.node[n]['simulated_closeness'])
In [ ]:
build_closeness(g2)
simulate_closeness_transfer_trail(g2)
for n in g2.nodes():
print(g2.node[n]['label'], g2.node[n]['theoretical_closeness'], g2.node[n]['simulated_closeness'])
In [ ]:
def simulate_closeness_transfer_walk(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.
# WALK: Podemos passar por nós e arestas jaá passadas anteriomente.
neighbors = g.neighbors(n)
m = choice(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, interroma\\\apemos 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
In [ ]:
build_closeness(g1)
simulate_closeness_transfer_walk(g1)
for n in g1.nodes():
print(g1.node[n]['label'], g1.node[n]['theoretical_closeness'], g1.node[n]['simulated_closeness'])
In [ ]:
build_closeness(g2)
simulate_closeness_transfer_walk(g2)
for n in g2.nodes():
print(g2.node[n]['label'], g2.node[n]['theoretical_closeness'], g2.node[n]['simulated_closeness'])
In [ ]:
def simulate_closeness_serial_walk(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.
# WALK: Podemos passar por nós e arestas jaá passadas anteriomente.
neighbors = g.neighbors(n)
m = choice(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, interroma\\\apemos 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
In [ ]:
build_closeness(g1)
simulate_closeness_serial_walk(g1)
for n in g1.nodes():
print(g1.node[n]['label'], g1.node[n]['theoretical_closeness'], g1.node[n]['simulated_closeness'])
In [ ]:
build_closeness(g2)
simulate_closeness_serial_walk(g2)
for n in g2.nodes():
print(g2.node[n]['label'], g2.node[n]['theoretical_closeness'], g2.node[n]['simulated_closeness'])
In [ ]:
def simulate_betweenness_serial_path(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.
# CAMINHO: Os vizinhos válidos são os quais ainda não foram percorridos.
neighbors = g.neighbors(n)
n_percorridos = []
for node_n in neighbors:
if node_n not in nodes_reached:
n_percorridos.append(node_n)
if len(n_percorridos) > 0:
m = choice(n_percorridos)
else:
break
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
In [ ]:
sn.build_betweenness(g1)
simulate_betweenness_serial_path(g1)
for n in g1.nodes():
print(g1.node[n]['label'], g1.node[n]['theoretical_betweenness'], g1.node[n]['simulated_betweenness'])
In [ ]:
sn.build_betweenness(g2)
simulate_betweenness_serial_path(g2)
for n in g2.nodes():
print(g2.node[n]['label'], g2.node[n]['theoretical_betweenness'], g2.node[n]['simulated_betweenness'])
In [ ]:
def simulate_betweenness_transfer_path(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.
# CAMINHO: Os vizinhos válidos são os quais ainda não foram percorridos.
neighbors = g.neighbors(n)
n_percorridos = []
for node_n in neighbors:
if node_n not in nodes_reached:
n_percorridos.append(node_n)
if len(n_percorridos) > 0:
m = choice(n_percorridos)
else:
break
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
In [ ]:
sn.build_betweenness(g1)
simulate_betweenness_transfer_path(g1)
for n in g1.nodes():
print(g1.node[n]['label'], g1.node[n]['theoretical_betweenness'], g1.node[n]['simulated_betweenness'])
In [ ]:
sn.build_betweenness(g2)
simulate_betweenness_transfer_path(g2)
for n in g2.nodes():
print(g2.node[n]['label'], g2.node[n]['theoretical_betweenness'], g2.node[n]['simulated_betweenness'])
In [ ]:
def simulate_betweenness_serial_trail(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()
arestas_reached = set()
for n in g.nodes():
#if g.node[n]['owner']:
# TRANSFERÊNCIA: Escolhemos aleatoriamente um dos vizinhos válidos.
# TRILHA: não passa mais de uma vez por uma mesma aresta
arestas = g.edges(n)
arestas_percorridas = []
for aresta_a in arestas:
if aresta_a not in arestas_reached:
arestas_percorridas.append(aresta_a)
m = choice(arestas_percorridas)
arestas_reached.add(m)
if(m[0] == n):
node_r = m[1]
else:
node_r = m[0]
nodes_reached.add(node_r)
# 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
In [ ]:
sn.build_betweenness(g1)
simulate_betweenness_serial_trail(g1)
for n in g1.nodes():
print(g1.node[n]['label'], g1.node[n]['theoretical_betweenness'], g1.node[n]['simulated_betweenness'])
In [ ]:
sn.build_betweenness(g2)
simulate_betweenness_serial_trail(g2)
for n in g2.nodes():
print(g2.node[n]['label'], g2.node[n]['theoretical_betweenness'], g2.node[n]['simulated_betweenness'])
In [ ]:
def simulate_betweenness_transfer_trail(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()
arestas_reached = set()
for n in g.nodes():
if g.node[n]['owner']:
# TRANSFERÊNCIA: Escolhemos aleatoriamente um dos vizinhos válidos.
# TRILHA: não passa mais de uma vez por uma mesma aresta
arestas = g.edges(n)
arestas_percorridas = []
for aresta_a in arestas:
if aresta_a not in arestas_reached:
arestas_percorridas.append(aresta_a)
m = choice(arestas_percorridas)
arestas_reached.add(m)
if(m[0] == n):
node_r = m[1]
else:
node_r = m[0]
nodes_reached.add(node_r)
# 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
In [ ]:
sn.build_betweenness(g1)
simulate_betweenness_transfer_trail(g1)
for n in g1.nodes():
print(g1.node[n]['label'], g1.node[n]['theoretical_betweenness'], g1.node[n]['simulated_betweenness'])
In [ ]:
sn.build_betweenness(g2)
simulate_betweenness_transfer_trail(g2)
for n in g2.nodes():
print(g2.node[n]['label'], g2.node[n]['theoretical_betweenness'], g2.node[n]['simulated_betweenness'])
In [ ]:
def simulate_betweenness_serial_walk(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.
# WALK: Podemos passar por nós e arestas jaá passadas anteriomente.
neighbors = g.neighbors(n)
m = choice(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
In [ ]:
sn.build_betweenness(g1)
simulate_betweenness_serial_walk(g1)
for n in g1.nodes():
print(g1.node[n]['label'], g1.node[n]['theoretical_betweenness'], g1.node[n]['simulated_betweenness'])
In [ ]:
sn.build_betweenness(g2)
simulate_betweenness_serial_walk(g2)
for n in g2.nodes():
print(g2.node[n]['label'], g2.node[n]['theoretical_betweenness'], g2.node[n]['simulated_betweenness'])
In [ ]:
def simulate_betweenness_transfer_walk(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.
# WALK: Podemos passar por nós e arestas jaá passadas anteriomente.
neighbors = g.neighbors(n)
m = choice(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
In [ ]:
sn.build_betweenness(g1)
simulate_betweenness_transfer_walk(g1)
for n in g1.nodes():
print(g1.node[n]['label'], g1.node[n]['theoretical_betweenness'], g1.node[n]['simulated_betweenness'])
In [ ]:
sn.build_betweenness(g2)
simulate_betweenness_transfer_walk(g2)
for n in g2.nodes():
print(g2.node[n]['label'], g2.node[n]['theoretical_betweenness'], g2.node[n]['simulated_betweenness'])
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.