Boost logo

Boost :

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


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

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

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:

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.


Boost list run by bdawes at, gregod at, cpdaniel at, john at