CODEWITHSUNDEEP
pythonalgorithmnetworkx
FaCoffee
FaCoffee

Reputation: 7909

Python: implementing a step-by-step, modified Barabasi-Albert model for scale-free networks

In Python, I need to create an Exponential Network, which is different from an Exponential Random Graph.

Exponential Networks were introduced in 2005 by Liu & Tang, and originate from a slight variation of the Barabasi-Albert model used to create Scale-Free Networks. This new algorithm still uses growth and preferential attachment, but in such a way that:

So what drives the attachment now is not the degree of existing nodes, but the average degree of their neighborhood. This implies that the algorithm generating the Barabasi-Albert model needs to be modified, and that is my goal.

I want to write a code that does this in a simple step-by-step fashion, using nested for loops for simulating growth and preferential attachment. Also, I want the nodes to be assigned specific positions, like this:

n=100 #Final number of nodes
ncols = 10 #Number of columns of a 10x10 grid
pos = {i : (i // ncols, (n-i-1) % ncols) for i in G.nodes()} #G=graph

My problem: I could do this by accessing the source code for the nx.barabasi_albert_graph() function, but I don't understand which is the growth phase, which is the preferential attachment phase, and where the degree of each node is computed. I would be glad if someone could point me in the right direction here.

The source code for the nx.barabasi_albert_graph() function:

def barabasi_albert_graph(n, m, seed=None):

    if m < 1 or  m >=n:
        raise nx.NetworkXError(\
              "Barabási-Albert network must have m>=1 and m<n, m=%d,n=%d"%(m,n))
    if seed is not None:
        random.seed(seed)

    # Add m initial nodes (m0 in barabasi-speak)
    G=empty_graph(m)
    G.name="barabasi_albert_graph(%s,%s)"%(n,m)
    # Target nodes for new edges
    targets=list(range(m))
    # List of existing nodes, with nodes repeated once for each adjacent edge
    repeated_nodes=[]
    # Start adding the other n-m nodes. The first node is m.
    source=m
    while source<n:
        # Add edges to m nodes from the source.
        G.add_edges_from(zip([source]*m,targets))
        # Add one node to the list for each new edge just created.
        repeated_nodes.extend(targets)
        # And the new node "source" has m edges to add to the list.
        repeated_nodes.extend([source]*m)
        # Now choose m unique nodes from the existing nodes
        # Pick uniformly from repeated_nodes (preferential attachement)
        targets = _random_subset(repeated_nodes,m)
        source += 1
    return G

Upvotes: 4

Views: 7660

Answers (1)

Abdallah Sobehy
Abdallah Sobehy

Reputation: 3021

I have implemented an animation for Barabasi-Albert graph growth and I think the implementation is easily adjustable for the preferential attachment criteria and nodes positions.

Nodes Positions

You will need to look into animate_BA function for nodes position (as I have it randomly chosen) at lines 39 (for starting nodes) and 69 (for newly added node)

Growth Phase

As for Growth phase, this is implemented in a separate function choose_neighbors that is called for the insertion of a new node into the graph. My implementation chooses a node to connect to with probability: (deg(i)+1)/Sum(deg(i)+1) where i is a node in the graph and deg(i) is the degree of that node and Sum(deg(i)+1) is the summation of degrees of all nodes in the graph + 1. This is achieved by creating a list of floats from 0 to 1 specifying the probability for each node to be chosen based on its degree.You can adjust that to the average degree of neighbors instead. So you will have to create this list but differently, since this function calls select_neighbors function to choose neighbors randomly based on the defined probabilities.

Other functions are mainly related to animation so you may not need to look into them. The code is documented and you can find further explanation there.

Upvotes: 3

Related Questions