Re: [Boost-users] [BGL] what is the "Power-Law Out Degree" algorithm?

From: Douglas Gregor (doug.gregor_at_[hidden])
Date: 2005-09-08 09:19:44

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