Directed Preferential Storage

import numpy
import random

n = 1
m = 1
digraph = {}
indeg = {}
    
def total_indegree():
    """
        returns the total indegree of the digraph
        by adding up every value in the dict indeg

"""
    
    totindeg = 0
    for node in indeg:
        totindeg += indeg[node]
    return totindeg

def distinct_multinomial(ntrials, probs):
    """
    Draw ntrials samples from a multinomial distribution given by
    probs.  Return a list of indices into probs for all distinct
    elements that were selected.  Always returns a list with between 1
    and ntrials elements.

Arguments:
    ntrials -- number of trials
    probs   -- probability vector for the multinomial, must sum to 1

Returns: 
    A list of indices into probs for each element that was chosen one
    or more times.  If an element was chosen more than once, it will
    only appear once in the result.  
    """
    ### select ntrials elements randomly
    mult = numpy.random.multinomial(ntrials, probs)

### turn the results into a list of indices without duplicates
    result = [i for i, v in enumerate(mult) if v > 0]
    return result

def populate_nodes():
    """
    Creates a complete directed graph with m nodes.

Keys in dictionary digraph represent nodes.
    Values represent neighbors for that node.

Keys in dictionary indeg represent nodes.
    Values represent the indegree for that node.

"""
    global digraph, indeg
    
    for node in range(0, m):
        digraph[node] = set([])
        indeg[node] = m - 1
        for neighbor in range(0, m):
            if node != neighbor:
                digraph[node].add(neighbor)
        
def new_nodes():
    """

Creates new nodes until there are n nodes

Each new node is connected with a two-way edge
    to up to m exiting nodes. The probability of choosing
    node j is (indeg(j) + 1) / (total_indegree() + len(digraph))

Keys in dictionary digraph represent nodes.
    Values represent neighbors for that node.

Keys in dictionary indeg represent nodes.
    Values represent the indegree for that node.

"""
    
    global digraph, indeg, m

for i in range(m, n):
        probs = get_probabilities()
        nodes = distinct_multinomial(m, probs)

digraph[i] = set(nodes)

for node in nodes:
            digraph[i].add(node)
            digraph[node].add(i)
            indeg[node] += 1

indeg[i] = len(nodes)
                
def get_probabilities():
    """
    Returns a list of probabilities for each node in
    digraph to be chosen.

The probability of choosing node j is
    indeg(j) + 1) / (total_indegree() + len(digraph))

"""
    
    probs = []
    totindeg = total_indegree()
    for node in indeg:
        probs.append(float((indeg[node] + 1)) / (totindeg + len(digraph)))
    
    return probs

def directed_preferential_attachment(b, a):

"""
    b = n
    a = m

(I can't use n and m as local variables because I'm using
    them as global variables.)

Resets digraph and indeg
    Then creates a new digraph

"""
    
    global n, m, digraph, indeg

n = b
    m = a
    digraph = {}
    indeg = {}
    
    populate_nodes()
    new_nodes()

print digraph

def test_dpa():
    """
    tests directed_preferential_attachment(b, a) with several
    different values of b and a.

"""
    directed_preferential_attachment(10, 5)
    directed_preferential_attachment(20, 4)
    directed_preferential_attachment(6, 2)

"""
    The above values tested with the following output

{0: set([1, 2, 3, 4, 7]), 1: set([0, 2, 3, 4, 5, 6, 8, 9]), 2: set([0, 1, 3, 4, 5, 6, 7, 8]),
    3: set([0, 1, 2, 4, 5, 7, 9]), 4: set([0, 1, 2, 3, 5]), 5: set([1, 2, 3, 4, 7, 8, 9]),
    6: set([8, 1, 2]), 7: set([0, 9, 2, 3, 5]), 8: set([1, 2, 5, 6, 9]), 9: set([8, 1, 3, 5, 7])}
    
    {0: set([1, 2, 3, 4, 5, 6, 15]), 1: set([0, 2, 3, 4, 5, 6, 8, 10, 12, 15, 19]),
    2: set([0, 1, 3, 4, 5, 7, 10]), 3: set([0, 1, 2, 4, 6, 9, 13, 14, 18]),
    4: set([0, 1, 2, 3, 5, 7, 11, 13, 16]), 5: set([0, 1, 2, 4, 6, 7, 8, 9, 10, 14, 16]),
    6: set([0, 1, 3, 5, 7, 12, 14, 17, 19]), 7: set([2, 4, 5, 6, 8, 14, 18]),
    8: set([1, 9, 5, 12, 7]), 9: set([3, 5, 8, 11, 15, 17, 19]), 10: set([1, 2, 5, 11, 13, 17, 19]),
    11: set([16, 9, 10, 4, 12]), 12: set([1, 6, 8, 11, 13, 16]), 13: set([12, 10, 3, 4]),
    14: set([17, 3, 5, 6, 7]), 15: set([0, 1, 9]), 16: set([12, 11, 4, 5]), 17: set([9, 10, 14, 6]),
    18: set([3, 7]), 19: set([1, 10, 6, 9])}
    
    {0: set([1, 4]), 1: set([0, 2, 3]), 2: set([1, 3, 4, 5]),
    3: set([1, 2]), 4: set([0, 2, 5]), 5: set([2, 4])}
    """

Python Fiddle

Python Cloud IDE