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

Subject: Re: [Boost-users] Scale-free networks generation
From: Jeremiah Willcock (jewillco_at_[hidden])
Date: 2013-03-08 12:36:14

On Thu, 7 Mar 2013, davidrey123 wrote:

> Thank you for your answers.
>
> Following the first answer by bminano, I have started using the
> unique_rmat_iterator and for the meantime it feels pretty ok. As I also
> wanted to have a connected graph and forbid "self edges", I coded a small
> script to connect isolated nodes and remove "self edges" and the resulting
> graphs fits my constraints.

You may also want to be following the thread entitled "[Boost-users] 
[Graph][parallel] Scale-free graph generator without self-loops" for 
another approach to removing self-loops.

>>> 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.
>
> Regarding the discussion on directed/undirected behavior, I believe that I
> can encode my network as undirected graph and simply consider both directed
> edges afterwards. I plan to use this network to simulate virus spreading
> patterns and I initially wanted to use a bidirected graph to model the fact
> that both nodes could infect each other but an undirected graph structure is
> enough to start with.

The CSR implementation requires that you put in both directions to have an 
undirected graph, so you'll need to use a bidirected graph now.

> Concerning the CSR implementation, this seems interesting, although as I am
> quite knew to the Boost libs, I am not sure how to create a CSR graph.
> However, since I do not plan to use Boost algorithms on my graphs, is there
> any advantage in implementing a CSR graph with respect to the "regular"
> implementation in Boost?

The one big thing the Boost implementation gives you is that it has fast 
routines to put unsorted data into a CSR graph; it does the sorting 
automatically and can take advantage of special properties of the data 
being a graph to get better performance.  You also get the abstractions 
for getting out edges, etc. without needing to write them in terms of the 
raw data structure; you will also get the opportunity to use the Boost 
algorithms if you want in the future.

-- Jeremiah Willcock