Search All of the Math Forum:
Views expressed in these public forums are not endorsed by
NCTM or The Math Forum.


waku
Posts:
14
Registered:
1/27/11


BarabasiAlbert graph model, documentation
Posted:
Jan 27, 2011 3:42 AM


The help page for the BarabasiAlbert 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 3vertex graph is an essential piece of the algorithm, and indeed the builtin BarabasiAlbert graph generation function does not seem to do that. Depending on the definition of BA graph actually meant to be implemented, the documentation may need to be modified.
Besides, the builtin 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 3vertex 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 3vertex graph (wrong in both the number of vertices and connectedness). The implementation given in the 'Applications' section produces the expected output.
vQ



