Encontro 25: Preferential Attachment

Importando as bibliotecas:


In [ ]:
import sys
sys.path.append('..')

import socnet as sn
import matplotlib.pyplot as plt

%matplotlib inline

Configurando as bibliotecas:


In [ ]:
sn.node_size = 3
sn.node_color = (0, 0, 0)

sn.edge_width = 1
sn.edge_color = (192, 192, 192)

Gerando o grafo:


In [ ]:
from random import random, choice, uniform
from bisect import bisect_left


P = 0.5
N = 500


g = sn.generate_empty_graph(1)

for _ in range(N - 1):
    nodes = list(g.nodes)

    n = len(nodes)

    g.add_node(n)

    if random() < P:
        m = choice(nodes)
    else:
        cdf = [g.degree(nodes[0])]

        for m in nodes[1:]:
            cdf.append(cdf[-1] + g.degree(m))

        x = uniform(0, cdf[-1])

        m = bisect_left(cdf, x)

    g.add_edge(n, m)

Mostrando o grafo:


In [ ]:
sn.reset_node_colors(g)
sn.reset_edge_colors(g)

sn.reset_positions(g)

sn.show_graph(g)

Comparando a distribuição dos graus com a power law $x^{-(1 + 1/(1 - p))}$


In [ ]:
_, bins, _ = plt.hist([g.degree(n) for n in g.nodes], normed=True)

xs = list(range(int(bins[0]), int(bins[-1]) + 1))

plt.plot(xs, [x ** -(1 + (1 / (1 - P))) for x in xs])

plt.show()