0
$\begingroup$

Does anyone have a pointer to a resource or, even better, a tip to provide on how to efficiently generate a very large matrix representing a connected graph.

Graph can be randomly created although I would ideally generate a graph of desired size and topology similar to what one can do with JGraphT.

My general intent is to create a very large graph representation (billions of nodes and edges) in parallel by first generating an adjacency matrix to ensure connectedness and then create a representation (RDF, etc) in parallel.

Any further suggestions or alternative approaches are welcome.

Improve this question
$\endgroup$
4
  • $\begingroup$ I m sorry but something not clear. do you mean that you want to efficiently verify connectivity of a very large graph ? Or you are looking for efficient ways to store and process a very large graph ? $\endgroup$ – AJed Jan 4 '13 at 4:09
  • $\begingroup$ Hi AJed, I am looking for both :-) but addressing even one at the time would be helpful. $\endgroup$ – Edmon Jan 4 '13 at 4:22
  • $\begingroup$ have a look at I/O efficient graph algorithms. $\endgroup$ – AJed Jan 4 '13 at 4:52
  • $\begingroup$ You should first find out if you'll be dealing with dense or sparse graphs. This information is very helpful for you $\endgroup$ – Jernej Jan 4 '13 at 10:05
1
$\begingroup$

Yes there is an easy way to generate a random DAG. If a graph is a DAG it can be separated into levels or ranks. The idea is to rank the nodes and randomly generate edges from lower ranked nodes to higher ranked nodes. A little bit of Googling finds the exact same question asked on stackoverflow a few months ago (with sample code!).

My only concern is that an adjacency matrix representation for a graph with billions of nodes/edges won't fit in memory. However, it's possible I misunderstood your intent in that part of the question.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.