# 4.6: Generating BA graphs

- Page ID
- 46603

In the previous sections we used a NetworkX function to generate BA graphs; now let’s see how it works. Here is a version of `barabasi_albert_graph`

, with some changes I made to make it easier to read:

def barabasi_albert_graph(n, k): G = nx.empty_graph(k) targets = list(range(k)) repeated_nodes = [] for source in range(k, n): G.add_edges_from(zip([source]*k, targets)) repeated_nodes.extend(targets) repeated_nodes.extend([source] * k) targets = _random_subset(repeated_nodes, k) return G

The parameters are `n`

, the number of nodes we want, and `k`

, the number of edges each new node gets (which will turn out to be the average number of edges per node).

We start with a graph that has `k`

nodes and no edges. Then we initialize two variables:

`targets`

:- The list of
`k`

nodes that will be connected to the next node. Initially`targets`

contains the original`k`

nodes; later it will contain a random subset of nodes. `repeated_nodes`

:- A list of existing nodes where each node appears once for every edge it is connected to. When we select from
`repeated_nodes`

, the probability of selecting any node is proportional to the number of edges it has.

Each time through the loop, we add edges from the source to each node in `targets`

. Then we update `repeated_nodes`

by adding each target once and the new node `k`

times.

Finally, we choose a subset of the nodes to be targets for the next iteration. Here’s the definition of `_random_subset`

:

def _random_subset(repeated_nodes, k): targets = set() while len(targets) < k: x = random.choice(repeated_nodes) targets.add(x) return targets

Each time through the loop, `_random_subset`

chooses from `repeated_nodes`

and adds the chosen node to `targets`

. Because `targets`

is a set, it automatically discards duplicates, so the loop only exits when we have selected `k`

different nodes.