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.

  • $\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
    Commented Jan 4, 2013 at 4:09
  • $\begingroup$ Hi AJed, I am looking for both :-) but addressing even one at the time would be helpful. $\endgroup$
    – Edmon
    Commented Jan 4, 2013 at 4:22
  • $\begingroup$ have a look at I/O efficient graph algorithms. $\endgroup$
    – AJed
    Commented Jan 4, 2013 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
    Commented Jan 4, 2013 at 10:05

1 Answer 1


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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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