Cycle basis for large graph

I have a graph of around 3 million nodes and 10 million edges.

I want to get the cycle basis of the graph but it runs out of memory when using the command cyclebasis(G).

Is there a way to solve it?

[Christine Tobler]

It will depend a bit on where it runs out of memory - could you post the error message you received?

The cyclebasis method is all MATLAB code, so you can open it with "edit graph/cyclebasis" and read the code - this means you might be able to modify it to only return the output in pieces.

How well that will work will also depend on what you want to do with the output of cyclebasis - can you use only a subset of the returned cell array at a time, or do you need all cycles at once?

[Tala Dannawi]

Thank you Christine, as you have suggested I tried modifying cyclebasis but got an error (unable to save file, access denied)..

[Christine Tobler]

You can't modify a file that is part of MATLAB. You could make a copy and modify that.

Answer 1

[Muskan]

Hi Tala,

As per my understanding of the question, when dealing with large graphs such as the one you described, calculating the cycle basis using the cyclebasis(G) command in MATLAB may not be feasible due to memory constraints.

One way to solve this problem is to use a smaller representation of the graph. For example, you could use a sparse matrix representation, which would use less memory than a dense matrix representation

Finally, you could try to reduce the size of the graph by removing some of the edges. This could be done by using a graph simplification algorithm, such as the Kruskal algorithm or the Prim algorithm.

I hope the above information helps resolve your query.

Thanks

[Tala Dannawi]

Thank you Muskan :)