In [ ]:
import sys
sys.path.append('..')
import socnet as sn
Configurando a biblioteca:
In [ ]:
sn.node_size = 10
sn.node_color = (0, 0, 0)
sn.edge_width = 1
Gerando um grafo completo:
In [ ]:
g = sn.generate_complete_graph(15)
sn.show_graph(g)
Esse será o grafo da comunidade.
Atribuindo aleatoriamente tipos aos nós:
In [ ]:
from random import shuffle
def randomize_types(g, num_openers, num_closers, num_chummies):
if num_openers + num_closers + num_chummies != g.number_of_nodes():
raise Exception('a soma dos tipos não é igual ao número de nós')
nodes = g.nodes()
shuffle(nodes)
for _ in range(num_openers):
g.node[nodes.pop()]['type'] = 'opener'
for _ in range(num_closers):
g.node[nodes.pop()]['type'] = 'closer'
for _ in range(num_chummies):
g.node[nodes.pop()]['type'] = 'chummy'
randomize_types(g, 15, 0, 0)
Atribuindo aleatoriamente existências às arestas:
In [ ]:
from random import random
def randomize_existences(g):
for n, m in g.edges():
if random() < 0.5:
g.edge[n][m]['exists'] = 0
else:
g.edge[n][m]['exists'] = 1
randomize_existences(g)
Convertendo tipos e existências em cores para visualização:
In [ ]:
def convert_types_and_existences_to_colors(g):
for n in g.nodes():
if g.node[n]['type'] == 'opener':
g.node[n]['color'] = (255, 0, 0)
elif g.node[n]['type'] == 'closer':
g.node[n]['color'] = (0, 255, 0)
else:
g.node[n]['color'] = (0, 0, 255)
for n, m in g.edges():
if g.edge[n][m]['exists'] == 0:
g.edge[n][m]['color'] = (192, 192, 192)
else:
g.edge[n][m]['color'] = (0, 0, 0)
convert_types_and_existences_to_colors(g)
sn.show_graph(g)
Definindo uma medida de restrição:
In [ ]:
def neighbors(g, n):
return [m for m in g.neighbors(n) if g.edge[n][m]['exists'] == 1]
# Independentemente do tipo, a restrição é sempre entre 0 e 2.
def calculate_constraint(g, n):
neighbors_n = neighbors(g, n)
degree_n = len(neighbors_n)
# Todos os tipos evitam isolamento. A restrição é máxima nesse caso.
if degree_n == 0:
return 2
# Para um chummy, a restrição é o inverso do grau. Uma pequena
# normalização é necessária para garantir que está entre 0 e 2.
if g.node[n]['type'] == 'chummy':
return 2 * (g.number_of_nodes() - degree_n - 1) / (g.number_of_nodes() - 1)
# Fórmula de Burt.
constraint = 0
for m in neighbors_n:
neighbors_m = neighbors(g, m)
degree_m = len(neighbors_m)
sub_constraint = 1 / degree_n
for l in neighbors_m:
if n != l and g.edge[n][l]['exists'] == 1:
sub_constraint += (1 / degree_n) * (1 / degree_m)
constraint += sub_constraint ** 2
# Para um closer, a restrição é o inverso da fórmula de Burt.
if g.node[n]['type'] == 'closer':
return 2 - constraint
# Para um opener, a restrição é a fórmula de Burt.
return constraint
Definindo uma atualização de existência:
In [ ]:
from random import choice
def equals(a, b):
return abs(a - b) < 0.000000001
def invert_existence(g, n, m):
g.edge[n][m]['exists'] = 1 - g.edge[n][m]['exists']
def update_existences(g):
# Para cada nó n...
for n in g.nodes():
# Calcula a restrição de n.
cn = calculate_constraint(g, n)
# Inicializa o dicionário de ganhos.
g.node[n]['gains'] = {}
# Para cada nó m diferente de n...
for m in g.nodes():
if n != m:
# Calcula a restrição de m.
cm = calculate_constraint(g, m)
# Inverte temporariamente a existência de (n, m) para ver o que acontece.
invert_existence(g, n, m)
# Se a inversão representa uma adição e ela não faz a restrição
# de m diminuir, então o ganho é zero porque essa inversão não
# é possível: adicionar só é possível se ambos os nós querem.
if g.edge[n][m]['exists'] == 1 and calculate_constraint(g, m) >= cm:
g.node[n]['gains'][m] = 0
# Senão, o ganho é simplesmente a diferença das restrições.
else:
g.node[n]['gains'][m] = cn - calculate_constraint(g, n)
# Restaura a existência original de (n, m), pois a inversão era temporária.
invert_existence(g, n, m)
# Obtém o maior ganho de n.
g.node[n]['max_gain'] = max(g.node[n]['gains'].values())
# Obtém o maior ganho de todos os nós.
max_gain = max([g.node[n]['max_gain'] for n in g.nodes()])
# Se o maior ganho não for positivo, devolve False indicando que o grafo estabilizou.
if max_gain <= 0:
return False
# Senão, escolhe aleatoriamente uma aresta correspondente ao maior ganho e inverte sua existência.
n = choice([n for n in g.nodes() if equals(g.node[n]['max_gain'], max_gain)])
m = choice([m for m in g.node[n]['gains'] if equals(g.node[n]['gains'][m], max_gain)])
invert_existence(g, n, m)
# Devolve True indicando que o grafo ainda não estabilizou.
return True
Definindo uma calculadora de variáveis.
In [ ]:
from math import inf
from statistics import stdev
from queue import Queue
def calculate_variables(g, verbose=False):
# Cria uma cóṕia do grafo na qual as arestas realmente
# existem ou não existem. Isso facilita os cálculos.
gc = g.copy()
for n, m in g.edges():
if g.edge[n][m]['exists'] == 0:
gc.remove_edge(n, m)
# Cálculo do número de arestas. (densidade)
num_edges = gc.number_of_edges()
if verbose:
print('número de arestas:', num_edges)
# Cálculo do número de componentes. (fragmentação)
for n in gc.nodes():
gc.node[n]['label'] = 0
label = 0
q = Queue()
for s in gc.nodes():
if gc.node[s]['label'] == 0:
label += 1
gc.node[s]['label'] = label
q.put(s)
while not q.empty():
n = q.get()
for m in gc.neighbors(n):
if gc.node[m]['label'] == 0:
gc.node[m]['label'] = label
q.put(m)
num_components = label
if verbose:
print('número de componentes:', num_components)
# Cálculo do desvio do tamanho de componentes. (fragmentação)
sizes = {label: 0 for label in range(1, num_components + 1)}
for n in gc.nodes():
sizes[gc.node[n]['label']] += 1
if num_components == 1:
dev_components = 0
else:
dev_components = stdev(sizes.values())
if verbose:
print('desvio do tamanho de componentes: {:05.2f}\n'.format(dev_components))
# Cálculo do desvio do betweenness. (desigualdade)
# Cálculo do betweenness médio por tipo. (quais perfis ficaram centrais)
sn.build_betweenness(gc)
betweenness = []
mean_betweenness = {
'closer': 0,
'opener': 0,
'chummy': 0,
}
for n in gc.nodes():
betweenness.append(gc.node[n]['theoretical_betweenness'])
mean_betweenness[gc.node[n]['type']] += betweenness[-1]
if verbose:
print('betweenness do nó {:2} ({}): {:05.2f}'.format(n, gc.node[n]['type'], betweenness[-1]))
dev_betweenness = stdev(betweenness)
for key in mean_betweenness:
length = len([n for n in gc.nodes() if gc.node[n]['type'] == key])
if length == 0:
mean_betweenness[key] = 0
else:
mean_betweenness[key] /= length
if verbose:
print('\ndesvio do betweenness: {:05.2f}\n'.format(dev_betweenness))
for key, value in mean_betweenness.items():
print('betweenness médios de {}: {:05.2f}'.format(key, value))
return num_edges, num_components, dev_components, dev_betweenness, mean_betweenness
Simulando várias vezes o processo no qual os nós invertem a existência de arestas até não poderem mais diminuir a restrição.
In [ ]:
TIMES = 25
No final das simulações, a média das variáveis é impressa.
In [ ]:
num_openers = 15
num_closers = 0
num_chummies = 0
mean_num_edges = 0
mean_num_components = 0
mean_dev_components = 0
mean_dev_betweenness = 0
mean_mean_betweenness = {
'opener': 0,
'closer': 0,
'chummy': 0,
}
for _ in range(TIMES):
randomize_types(g, num_openers, num_closers, num_chummies)
randomize_existences(g)
while update_existences(g):
pass
num_edges, num_components, dev_components, dev_betweenness, mean_betweenness = calculate_variables(g)
mean_num_edges += num_edges
mean_num_components += num_components
mean_dev_components += dev_components
mean_dev_betweenness += dev_betweenness
for key, value in mean_betweenness.items():
mean_mean_betweenness[key] += value
mean_num_edges /= TIMES
mean_num_components /= TIMES
mean_dev_components /= TIMES
mean_dev_betweenness /= TIMES
for key in mean_mean_betweenness:
mean_mean_betweenness[key] /= TIMES
print('média do número de arestas: {:05.2f}'.format(mean_num_edges))
print('média do número de componentes: {:05.2f}'.format(mean_num_components))
print('média do desvio do tamanho de componentes: {:05.2f}'.format(mean_dev_components))
print('média do desvio do betweenness: {:05.2f}'.format(mean_dev_betweenness))
for key, value in mean_mean_betweenness.items():
print('média do betweenness médio de {}: {:05.2f}'.format(key, value))
Para ter insights sobre o que está acontecendo, não esqueça de examinar a versão animada da simulação!
In [ ]:
def update_positions(g, invert=False):
if invert:
for n, m in g.edges():
g.edge[n][m]['notexists'] = 1 - g.edge[n][m]['exists']
sn.update_positions(g, 'notexists')
else:
sn.update_positions(g, 'exists')
def snapshot(g, frames):
convert_types_and_existences_to_colors(g)
frame = sn.generate_frame(g)
frames.append(frame)
frames = []
randomize_types(g, num_openers, num_closers, num_chummies)
randomize_existences(g)
sn.randomize_positions(g)
snapshot(g, frames)
while update_existences(g):
update_positions(g, False)
snapshot(g, frames)
sn.show_animation(frames)
_, _, _, _, _ = calculate_variables(g, verbose=True)
Se a animação não parece dizer muito, tente trocar False por True no update_positions.