Barabasi-Albert model for generating scale-free random graphs.

Barabasi.py

#!/usr/bin/env python
# -*- coding: utf-8 -*-

from random import randint,random
import networkx as nx
import matplotlib.pyplot as plt
import time

# http://stackoverflow.com/questions/479236/how-do-i-simulate-biased-die-in-python #
def roll(probs):
    randRoll,s,result = random(),0,1 # in [0,1)
    for mass in probs:
        s += mass
        if randRoll < s: return result-1
        result+=1

def initialize_graph(init_nodes):
    G = nx.Graph()
    G.add_nodes_from([i for i in xrange(init_nodes)])
    for i in xrange(0,init_nodes):
	for j in xrange(0,init_nodes): G.add_edge(*(i,j))
    return G
    
def main(init_nodes = 2, min_edges_by_node = 1 , max_edges_by_node = 1, iterations = 100):
    G   = initialize_graph(init_nodes)
    m0  = init_nodes
    m   = randint(1,m0-1)
    for it in xrange(iterations):
	degrees = [G.degree(i) for i in xrange(0,len(G.nodes()))]
	sum_kj  = sum(degrees)
	probs   = [float(degrees[i])/max(sum_kj,1) for i in xrange(0,len(degrees))]
	n_edges = randint(min_edges_by_node,max_edges_by_node)
	for i in xrange(n_edges):
	    dest    = roll(probs) 
	    G.add_edge(*(m0,dest))
	m0 += 1
	nx.draw_circular(G)
	plt.ion()
	plt.show()
	plt.pause(0.25)
	plt.cla()
    

if __name__ == "__main__":
    
    main(init_nodes = 2, min_edges_by_node = 1 , max_edges_by_node = 3, iterations = 10000)