Search All of the Math Forum:

Views expressed in these public forums are not endorsed by NCTM or The Math Forum.

Notice: We are no longer accepting new posts, but the forums will continue to be readable.

Topic: Barabasi-Albert graph model, documentation
Replies: 0

 waku Posts: 14 Registered: 1/27/11
Barabasi-Albert graph model, documentation
Posted: Jan 27, 2011 3:42 AM

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