[Date Index] [Thread Index] [Author Index]

Barabasi-Albert graph model, documentation

• To: mathgroup at smc.vnet.net
• Subject: [mg115963] Barabasi-Albert graph model, documentation
• From: waku <waku at idi.ntnu.no>
• Date: Thu, 27 Jan 2011 03:42:35 -0500 (EST)

The help page for the Barabasi-Albert graph model
(BarabasiAlbertGraphDistribution) explains the construction scheme as
follows:

"The BarabasiAlbertGraphDistribution is constructed starting from
CycleGraph[3] and a vertex with k edges is added at each step. The k
edges are attached to vertices at random following a distribution
proportional to the vertex degree. "

The implementation given in section 'Applications' does follow this
scheme.  However, I'm not sure that starting with a cyclic 3-vertex
graph is an essential piece of the algorithm, and indeed the built-in
Barabasi-Albert graph generation function does not seem to do that.
Depending on the definition of B-A graph actually meant to be
implemented, the documentation may need to be modified.

Besides, the built-in implementation does not seem to work correctly
wrt. to the algorithm given in the documentation.  With the input n=3,
k=0, the output should be the cyclic 3-vertex graph (start with the
cycle, add 0 vertices with at most 0 edges), but no graph is
produced.  With the input n=4, k=1, the output should be the cyclic 3-
vertex graph with a 'tail' added, but the actual output is a non-
cyclic 3-vertex graph (wrong in both the number of vertices and
connectedness).  The implementation given in the 'Applications'
section produces the expected output.

vQ