Scale-free networks generation
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? 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)/ 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? Thank you, -David -- View this message in context: http://boost.2283326.n4.nabble.com/Scale-free-networks-generation-tp4643888.... Sent from the Boost - Users mailing list archive at Nabble.com.
Hello, We are using the unique_rmat_iterator (from the parallel graph library), that generates a scale-free networks without parallel edges. I think you can use it in serial codes. El 06/03/13 23:55, davidrey123 escribió:
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?
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)/
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?
Thank you, -David
-- View this message in context: http://boost.2283326.n4.nabble.com/Scale-free-networks-generation-tp4643888.... Sent from the Boost - Users mailing list archive at Nabble.com. _______________________________________________ Boost-users mailing list Boost-users@lists.boost.org http://lists.boost.org/mailman/listinfo.cgi/boost-users
-- Un saludo, Borja Miñano IAC3 - Universitat de les Illes Balears ParcBit - Edifici 17 (Disset); Local D7 Cra. Valldemossa km. 7,4 E-07121 Palma de Mallorca. Balears. Spain. Phone: +34 871 967 434
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
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.
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. 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? -David -- View this message in context: http://boost.2283326.n4.nabble.com/Scale-free-networks-generation-tp4643888p... Sent from the Boost - Users mailing list archive at Nabble.com.
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
participants (3)
-
Borja Miñano
-
davidrey123
-
Jeremiah Willcock