Find all cycles (or the initial node of each cycle) in a very large directed graph (12m nodes, 6.7m edges)

Hi if anyone could help me out with this problem I have been stuck for a while and would be really grateful for your help,

Context

I have about 7 million transactions between accounts, where a transaction is a single row that describes who the buyer account and seller account are, and the object that was sold. So an example of one row would be: [B:0x3, S:0x1, O:Object1] or to better understand 0x1 sold Object1 to 0x3

I have concatenated the object to the buyer and seller aka 0x1-Object1 -> 0x3-Object1 (because an account can sell multiple different objects) and created a directed graph from this data to create a history of how all objects have transferred between accounts.

Problem:

I want a list of all the accounts where an object has returned back to the account it originally sold from, so for example:

If I had the transactions such that: Account1-Object1 -> Account2-Object1 -> Account1-Object1 then the output should be: Account1-Object1

because the asset eventually cycled back to Account1.

Current Non-Feasible Solution:

this is interpreted as: 0xc sold Object1 to 0x5, 0x5 sold Object2 to 0xc, 0xc sold Object3 to 0x0, 0x5 sold Object5 to 0x0, etc

My code so far:

%concatenate Object to buyer and seller 
sales.BuyerAndObject = strcat(string(sales.Buyer),"-",string(sales.Object)); 
sales.SellerAndObject= strcat(string(sales.Seller),"-",string(sales.Object));
buyer = transpose(sales.BuyerAndObject);
seller = transpose(sales.SellerAndObject);   
%Directed Graph: Seller -> Buyer
G = digraph(seller,buyer);
%I have then been trying to use allcycles(G) to find all the cycles, 
cycles = allcycles(G)

then return the first node of each cycle, but the data is too massive as I have about 12 Million nodes and 6.7 MIllion edges and the time to completion is beyond reasonable. I am not great at graph theory and at a loss for how to go about what I need to do, and any help is greatly apreciated.

Answer 1

[Christine Tobler]

Have you tried using 'MaxNumCycles' to only compute the first 100 / 1000 / 1e4 cycles? That could give some indication if it's computing each cycle that's slower than acceptable for your problem, or if there are just very many cycles.

It might also be worthwhile to take a look at some of these cycles, to make sure they are all legitimate results (that is, perhaps you're seeing several cycles that can be recombined in different ways, which could cause there to be many more cycles returned than you'd expect).

[Jared Violo]

I actually have tried MaxNumCycles with no change in time completion.

I ran it on 2 million transactions of the data I knew would have less cycles cycles and it wouldn't finish even after about an hour for max 10 cycles. When I paused in debugger it had found 8 cycles.

I believe computing each cycle on such a large directed graph is the problem.

[Christine Tobler]

With the allcycles function shipped with MATLAB in R2021a, it shouldn't be possible to pause the debugger and get a partial result - all results are computed in one go in a builtin function.

Could you check what result you get if you enter which allcycles on command line? I'd like to check if you're using another implementation, perhaps an m-file allcycles.m?

That said, this is a large graph, so the R2021a version of allcycles is still likely to take quite some time.

[Jared Violo]

This was the result:

I could be confused with another calculation I processed, I was doing allcycles on 150k transactions to check the time so I might have let one of those fully finish.

I just filtered out all 'unique transactions', a transaction that has only occured once because obviously there will be no cycles. this is exactly what i implemented on my dataset: https://www.mathworks.com/matlabcentral/answers/175086-finding-non-unique-values-in-an-array

and it's brought down the graph substantially at 4.4m nodes, 3m edges. You're right that this is still a very large graph and will likely take a lot of time, do you have any insight as to how I might be able to get my results faster/maybe without the use of allcycles? I'm really only after the initial node of the cycles aka the account that sent and re-recieved the object.

nevertheless thanks for the speedy replies!

[Christine Tobler]

Can you try the following code on your graph?

>> bins = conncomp(g, "OutputForm", "cell");
>> bins(cellfun(@isscalar, bins)) = [];

The result bins should be a cell array where each element contains a set of nodes that have one or more cycles between them. It's not quite the same as allcycles returns, since one of these sets of nodes could contain several intersecting cycles. But I think it could still be the result you're looking for in this case.

I made a random graph with 12m nodes and 7m edges, and this took about 40 seconds there (that time could be improved but the code would get a bit more long-winded, let me know if that would be helpful).

[Jared Violo]

This might be near enough to exactly what I need.. oh my god. I may get back to you in the future via another question thread or even here if it's acceptable but this very helpful thank you so much for your time! This is the first question i've ever posted and I am super happy lol.

[Christine Tobler]

Thank you for posting on this! It's always good to see comments on newer functions; I'll see if we can't make allcycles be faster for this case in a future release - we may not have thought of the case when a graph has millions of nodes but very few cycles when checking performance of this function.

[Christine Tobler]

Here is the bug report for this issue:

https://www.mathworks.com/support/bugreports/2562455

The performance problem in allcycles for very large graphs with few cycles was resolved for R2021b Update 1 and for R2022a from the initial release.