In [1]:
%matplotlib inline

In [2]:
from itertools import chain
import networkx as nx
import matplotlib.pyplot as plt
from networkx.generators.random_graphs import _random_subset

In [3]:
plt.rcParams['figure.figsize'] = (12, 7)

Hybrid graph generator - tunable random/preferential attachment. Based on Mathew Jackson's Coursera course Social and Economic Networks

In [4]:
def simple_hybrid_graph(t, m=2, alpha=0.5):
    """Generates a random graph that uses a mixed model for growth. 
       For each unit of time t, a new node links to the graph with 
       m * alpha links assigned randomly to existing nodes, and 
       m * (1 - alpha) links assigned to neighbors of the above random nodes.
       alpha near 1 produces a nearly exponential degree distribution, 
       alpha near 0 produces a nearly preferential (scale free) 
       degree distribution.
       IMPORTANT: m % alpha == 0"""
    beta = 1 - alpha
    random = int(alpha * m)
    preferential = int(beta * m)
    G = nx.empty_graph(random)
    targets = list(range(random))
    source = random
    while source < t:
        G.add_edges_from(zip([source] * random, targets))
        neighbors = chain.from_iterable([G.neighbors(node) 
                                         for node in targets])
        neighbors = filter(lambda x: x != source, neighbors)
        # Grows randomly with alpha * m # of links until there is a
        # neighbor, then adds all neighbors until len of neighbors is
        # greater than # of preferential neighbors to be added. After
        # random selection, preferential attachment of neighbors begins 
        # normally.
        if len(neighbors) > preferential:
            neighbor_targets = _random_subset(neighbors, preferential)
            G.add_edges_from(zip([source] * preferential, neighbor_targets))
        elif len(neighbors) > 0:
             G.add_edges_from(zip([source] * len(neighbors), neighbors))
        # Select new targets.
        targets = _random_subset(G.nodes(), random)
        source += 1
    return G

def deg_dist(g):
    deg_scatter = []
    for deg, count in enumerate(nx.degree_histogram(g)):
        if count:
            deg_scatter.append((deg, count))
    return deg_scatter
Degree distribution.

In [5]:
b_a = deg_dist(nx.barabasi_albert_graph(10000, m=4)) # source
g25 = deg_dist(simple_hybrid_graph(10000, m=4, alpha=0.25))
g50 = deg_dist(simple_hybrid_graph(10000, m=4, alpha=0.50))
g75 = deg_dist(simple_hybrid_graph(10000, m=4, alpha=0.75))

In [6]:
plt.scatter([x[0] for x in b_a], [x[1] for x in b_a], color='green')
plt.scatter([x[0] for x in g25], [x[1] for x in g25], color='yellow')
plt.scatter([x[0] for x in g50], [x[1] for x in g50], color='blue')
plt.scatter([x[0] for x in g75], [x[1] for x in g75], color='red')