[BGL] what is the "Power-Law Out Degree" algorithm?

On Sep 7, 2005, at 12:51 PM, Rui Carvalho wrote:

Thanks for this. Just out of curiosity, what were the reasons to choose this particular power-law generator?

It doesn't rely on alternately adding vertices then edges. Because it starts with a fixed number of vertices and adds edges from there, it's easier to construct a graph with "n" vertices and then have the generator create only the edges. That fits well with the adjacency_list constructors (both in the BGL and for our distributed adjacency list in the Parallel BGL).

Shouldn't the BGL also target more accepted algorithms like the Barabasi-Albert?

If someone provides an implementation, we'd be happy to review and integrate it. The BGL expands in a very demand-driven way: we add components when we need them or when someone else provides them. PLOD came from our need to generate really big distributed graphs to test/benchmark on.

I mean, the PLOD model does not really stand shoulder to shoulder with the small word and erdos-renyi, does it?

It's not as popular, no, but that doesn't mean it isn't worthy :) Does is generate graphs poorly? Doug

On Sep 8, 2005, at 5:12 AM, Rui Carvalho wrote:

I've had a look at the paper by Palmer & Steffan. The paper proposes a generator for power-law graphs in "real internet graphs". Is this a model that may be relevant in a more general context? (e.g. Biology where many users of the BGL come from)

It's relevant to a context if it captures the essential properties of graphs needed by that context. The Palmer & Steffan paper describes a few such properties and shows how the generator performs for them.

The point I'm trying to make is not whether PLOD is interesting or not, I think that should be left to the wider research community to decide. In this sense, the Barabasi-Albert model is, so far, *the* accepted model and its use goes beyond modelling the internet -so shouldn't it have priority?

No algorithm has priority. The Barabasi-Albert generator didn't work for us when we needed a power-law graph generator, so we implemented and added PLOD. When someone submits a Barabasi-Albert generator, we'll integrate it and let the user decide. The deeper question I could ask is whether the Barabasi-Albert model is the accepted model because it has been experimentally shown to be the best model, or whether "preferential attachment" has made it the accepted model. When we get several power law graph generators, we can decide for ourselves. Doug