I am trying to construct a BA graph with 500 nodes and about 37000 edges. The number of edges to attach from a new node to existing nodes should be at least 91 to make enough number of edges. I checked it from barabasi_albert_graph(n, m, seed=None) function in Networkx. The algorithm is as follows[1]:

  1. Add $m$ nodes to G.

  2. Connect nodes in $G$ randomly until you get a connected graph.

  3. Create a new node i.

  4. Pick a node j uniformly at random from the graph G. Set $ p= k(j)/k_{tot}$.

  5. Pick a real number $r$ uniformly at random between $0$ and $1$.

  6. If $ r<p$ then add $j$ to i's adjacency list.

  7. Repeat steps 4 - 6 until i has m nodes in its adjacency list.

  8. Add $i$ to the adjacency list of each node in its adjacency list.

  9. Add $i$ to to the graph.

  10. Repeat steps 3 - 9 until there are $N$ nodes in the graph.

The question is step 2. When $m$ should be at least 91, a large part of my graph have a random construction. Is it a correct way of making the BA model?

  • $\begingroup$ To make your question meaningful, you should say what you want to prove with it, or what exact variant you want to use, because the original paper did not define the model entirely. So according to that paper you can consider any way you make step 2 is correct. $\endgroup$ – Graffitics Jul 6 '16 at 10:48
  • $\begingroup$ I just wanted to make a power law netork. I found that most BA network are sparse and making a dense network by this method is to some extant odd. So for sparse networks, step 2 should not be very important. $\endgroup$ – Abolfazl Jul 8 '16 at 4:57
  • $\begingroup$ Sparsity is a property of graph sequences, not of graphs. Anyway if your objective is just to get a power law network then the way you do step 2 does not matter. $\endgroup$ – Graffitics Jul 8 '16 at 12:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.