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