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