Re: [Boost-users] Scale-free networks generation

Subject: Re: [Boost-users] Scale-free networks generation
From: Jeremiah Willcock (jewillco_at_[hidden])
Date: 2013-03-07 13:47:14

On Wed, 6 Mar 2013, davidrey123 wrote:

> Hello, I would to use Boost librairies to generate scale-free networks and I
> am not sure what is the best approach.
>
> I am currently using the PLOD generator, but the graphs generated are
> generally multigraphs, that is, graphs with multiple edges between two
> nodes. Although I would like to generate graphs with bidirectionnal edges
> between nodes, I also would like to bound the maximum number of possible
> edges between a pair of nodes to 2. In other words, if edges (i,j) and (j,i)
> are generated between nodes i and j, I do not want any additional edge
> between those nodes to be generated.
>
> Hence, I would like to know;
>
> 1-Is it possible to generate such graphs using the PLOD generator? If it is,
> do I need to remove "multi-edges" after the graph is generated or is there a
> smarter way to do so?

If you need to do it before the graph is generated, one easy way would be 
to write the edges as (source, target) pairs into an std::vector or 
similar container, then use std::sort and std::unique to remove 
duplicates.  Most Boost.Graph graph types (including compressed sparse row 
graphs) have (source, target) pairs as one of their input types for graph 
data; if you do sort the pairs separately, make sure to pass that tag into 
the compressed_sparse_row_graph constructor to get much better 
performance.

> 2-If using the PLOD generator is not the best option, is there any other
> random graph generator in Boost that can be adapted to design scale-free
> networks? In particular, is there a graph generator implementing the
> Barabasi-Albert model (I have looked up the forum for an answer to that
> question and it seems that the answer is "no", but things may have changed
> since)/

There are also small-world, SSCA#2, and R-MAT generators, which I believe 
are all scale-free.  I do not believe there is a Barabasi-Albert 
generator, though.

> 3-I read somewhere that Compressed Sparse Row (CSR) graphs could be used to
> represent scale-free networks, is there a way to use the corresponding Boost
> class to do so?

Yes.  As long as you have a list of (source, target) pairs, either from a 
graph generator or stored explicitly, you can create a Boost CSR graph 
with your data.  The CSR implementation only supports directed and 
bidirectional graphs, however, so you'd need to put in each edge in both 
directions if you wanted undirected behavior.

-- Jeremiah Willcock