[boost] Boost.Graph GSoC 2010

Subject: [boost] Boost.Graph GSoC 2010
From: Cezary Bartosiak (cezary.bartosiak_at_[hidden])
Date: 2010-03-23 23:49:02

Hi,

I am Cezary, a student of computer science at the Cybernetics Faculty,
Military University of Technology, Warsaw. I am interested in developing the
BGL.

I've got an idea related to the Topology Generators. I have participated in
a project concerning epidemics spreading and, as a part of the project, we
have implemented several social networks generators (Barabási–Albert model
for instance). I hit upon an idea to implement these algorithms apart from
proposed topology generators.

I know that Boost.Graph contains some algorithms for generating networks, I
would like to add some extensions:

1. There is Erdős-Rényi model generator in two versions G(n, p) and G(n, m).
I think I could provide some additional implementations for specific cases,
I mean:

a) Fast generator of sparse graphs inspired by
http://www.inf.uni-konstanz.de/algo/publications/bb-eglrn-05.pdf.

b) Fast generator of dense graphs, algorithm by Keith M. Briggs Mar 31, 2006
(the only implementation of this one I've seen in NetworkX library).

2. There is only Beta-model generator of Small World network in the library.
I would like to add Alfa-model generator as well as Kleinberg model
generator. Here are some interesting materials:

http://tam.cornell.edu/tam/cms/manage/upload/SS_nature_smallworld.pdf
http://www.bsos.umd.edu/socy/alan/stats/network-grad/summaries/Watts-Six%20Degrees-Ghosh.pdf
http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.83.381&rep=rep1&type=pdf

3. At the moment we've got only PLOD algorithm to generate ScaleFree
networks. I could provide other ones:

a) Basic generator often seen in popular libraries, for instance NetworkX.

b) Generalized generator with probabilities of adding new edges and rewiring
existing ones.

c) Simplified models generators: A (uniform attachment) and B (no growth).

Coming back to Topology Generators I would implement them for some "basic"
topologies, let's say: path, star, cycle, wheel, ladder, grid, hypercube,
barbell, complete, frucht and many others if time remains...

I would be glad to know your opinion.

Best,
Cezary