<SYSTEM_TASK:>
Given the following text description, write Python code to implement the functionality described below step by step
<END_TASK>
<USER_TASK:>
Description:
 Encontro 10
Step1:  Configurando a biblioteca
Step2:  Gerando um grafo completo
Step3:  Esse será o grafo da comunidade.
Atribuindo aleatoriamente tipos aos nós
Step4:  Atribuindo aleatoriamente existências às arestas
Step5:  Convertendo tipos e existências em cores para visualização
Step6:  Definindo uma medida de restrição
Step7:  Definindo uma atualização de existência
Step8:  Definindo uma calculadora de variáveis.
Step9:  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.
Step10:  No final das simulações, a média das variáveis é impressa.
Step11:  Para ter insights sobre o que está acontecendo, não esqueça de examinar a versão animada da simulação!
<ASSISTANT_TASK:>
Python Code:
import sys
sys.path.append('..')
import socnet as sn
Explanation: Encontro 10: Lacunas Estruturais
O enunciado da Escrita 4 continua ao longo deste notebook.
Preste atenção nas partes em negrito.
Importando a biblioteca:
End of explanation
sn.node_size = 10
sn.node_color = (0, 0, 0)
sn.edge_width = 1
Explanation: Configurando a biblioteca:
End of explanation
g = sn.generate_complete_graph(15)
sn.show_graph(g)
Explanation: Gerando um grafo completo:
End of explanation
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)
Explanation: Esse será o grafo da comunidade.
Atribuindo aleatoriamente tipos aos nós:
End of explanation
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)
Explanation: Atribuindo aleatoriamente existências às arestas:
End of explanation
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)
Explanation: Convertendo tipos e existências em cores para visualização:
End of explanation
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
Explanation: Definindo uma medida de restrição:
End of explanation
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
Explanation: Definindo uma atualização de existência:
End of explanation
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
Explanation: Definindo uma calculadora de variáveis.
End of explanation
TIMES = 25
Explanation: 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.
End of explanation
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))
Explanation: No final das simulações, a média das variáveis é impressa.
End of explanation
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)
Explanation: Para ter insights sobre o que está acontecendo, não esqueça de examinar a versão animada da simulação!
End of explanation
<END_TASK>