Creating network in python

I would like to create a network with size of maximum up to 10,000 nodes. Lets say the number of connections that needs to be made to the 10,000 node is 100.I need to select 100 node 1 by one based on the probability of the number of connections that other 9,999 nodes can have.

For a this network generate N observations in a line. Make a distribution of connections for each individual according to the rule p(n) proportional-to n*(-gamma),(p(n) is the number of connections held by individual n) where gamma is the Influence Parameter. For example* if n**(-gamma) is 2.6 then the node can have 2 or 3 ties(should be drawn based on uniform distribution).This requires solving for the number of connections that the best-connected individual needs to have in order to satisfy the constraint that everyone has at least one connection. Now randomly assign connections one person at the time starting with the best-connected member. Remove each person from the pool that connections are drawn from once they have reached the maximum number of connections assigned according to the distribution. Enter into a matrix as before.

def network(n, gamma):
    n_gamma = []
    n_ties = []
    network = [[0 for x in xrange(n)] for x in xrange(n)]
    for i in xrange(0, n):
        n_gamma.append((i + 1)**(-1*gamma))
        a = random.uniform(math.floor(n_gamma[i]),
                           math.ceil(n_gamma[i]))  #random.uniform(a, b) generates a random floating point number between a, b
        if a < n_gamma[i]:
            n_ties.append(int(math.floor(n_gamma[i])))
        else:
            n_ties.append(int(math.ceil(n_gamma[i])))
    nodes_with_ties = []
    n_gamma_reuse = n_gamma[:]
    for i in xrange(n - 1, -1, -1):
        other_nodes, other_nodes_gamma = sf_target(n, i,
                                                   n_ties, n_gamma)                     # sf_target returns a 2 lists one containing possible nodes for making a tie with current node and other with their respective n(-gamma) converted to probabilities between 0 and 1
        if (n_gamma[i] > 0 and n_ties[i] > 0 and
            len(other_nodes) >= n_ties[i]):
            for j in xrange(0, n_ties[i]):
                n_gamma[i] = n_gamma[i] - 1
                n_ties[i] = n_ties[i] - 1
                q = random.uniform(other_nodes_gamma[0],
                                   other_nodes_gamma[len(other_nodes_gamma)-1])
                b = bisect.bisect(other_nodes_gamma, q)
                c = other_nodes[b-1]
                n_gamma[c] = n_gamma[c] - 1
                n_ties[c] = n_ties[c] - 1
                network[i][c] = 1
                network[c][i] = 1
                other_nodes.remove(c)
                other_nodes_gamma = new_other_gamma(other_nodes, n_gamma)
        if check_ties(network):                  #check ties checks whether each node has atleast one tie
            if i == 0:
                return network
            elif check_neg_targ_lev(n_gamma):   #check_neg_targ_lev checks whether all nodes have n**(-gamma) < 0
                return network



def sf_target(n, i, n_ties, n_gamma): 
    other_nodes = []                              #possible nodes for ties
    other_nodes_gamma = []                        #nodes range for uniform selection based on probability
    for k in xrange(0, n):
        if k != i and n_ties[k] > 0:
            other_nodes.append(k)
            other_nodes_gamma.append(n_gamma[k])
    if len(other_nodes_gamma) > 0:
                sum_other_gamma = sum(other_nodes_gamma)
                other_nodes_gamma[0] = other_nodes_gamma[0]/sum_other_gamma
                for k in xrange(1, len(other_nodes_gamma)):
                    other_nodes_gamma[k] = ((other_nodes_gamma[k]/sum_other_gamma) +
                                other_nodes_gamma[k - 1])
    other_nodes_gamma = [0] + other_nodes_gamma
    return other_nodes, other_nodes_gamma

The above code is running exponentially for input size of 1000 its taking 50-60 sec and for 5000 its taking around 15min and for 10000 around 25min to complete