3
$\begingroup$

Suppose that we seed our network with $m$ vertices. Suppose that at each step we add a vertex and c edges adjacent to that vertex.

Should these initial $m$ vertices have no edges at the start of the growth procedure? Should they be an $m$-clique? Should they form a cycle?

It seems that in Barabasi and Albert's model, there are no edges. The problem here is that each vertex in the seed will have probability 0 of being selected as an endpoint of a new edge.

$\endgroup$
5
$\begingroup$

As you noted, any vertex with degree $0$ will have zero probability of being selected for attachment, and thus will always remain disconnected. Thus, only vertices of degree $1$ or higher matter in the initial network. In an experimental setting, it doesn't matter what connectivity you pick for your initial $m$ vertices (beyond the non-zero degree, constraint) since the network starts to forget its initial conditions pretty quickly (especially if all the initial vertices have the same degree). The two most popular implementations in practice are:

  • $1$ vertex connected to $m$ other vertices. This creates a distinguished vertex to start with (the high-degree vertex has a much higher chance of becoming a hub than the others), but otherwise the network is very typical.

  • $m + 1$ fully connected vertices. This creates a balance between any vertices being biased to become a hub, but has the unfortunate effect of artificially increasing the clustering coefficient of your network when it is young. This usually takes longer for the network to forget.

If you want more exact analytic results on the BA model, than you can't rely on the original heuristic arguments given in the Science paper, and I recommend looking at these lecture notes for a formal treatement. To prove things about the BA model, usually self-loops and multiple edges are allowed. In that case the network can be initialized as one vertex with $m$ self-loops.

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.