A fresh try at fixing disconnected communities

[wolfram77]

This is the original vanilla code, not even refine till end pass.

Disconnected communities: 5.0E-4, Modularity: 0.4450

[wolfram77]

We must run till convergence.

Disconnected communities: 5.1E-3, Modularity: 0.8845

[wolfram77]

Handle data race while changing community (this doesn't seem to fix disconnected communities).

Disconnected communities: 6.1E-3 / 5.3E-3, Modularity: 0.8844 / 0.8842

Below are with details of where disconnected communities are getting created (refinement phase).

[wolfram77]

Using a sequential refinement approach still produces disconnected communities - there is something else at play here.

[wolfram77]

I added a batch update, directly after loading the graph. Even that is leading to disconnected communities. This disconnected communities issue is then clearly due to the property/nature of the graph, and not due to how the previous community membership may be disconnected due to the batch update!

[wolfram77]

It seems most disconnected communities have just one missing vertex.

[wolfram77]

It looks like the generated batch updated is not undirected, and also has duplicate edges. Stupid batch generation!

[wolfram77]

After fixing symmetrizeOmpU(), leiden may rarely produce a few disconnected communities as follows.

A good atomic update may fix this issue.

NOTE: Indeed, a good atomic update does fix it!

[wolfram77]

Now the process of optimizing the algorithm begins. Below is runtimes without optimizations. 2464ms

Ignoring affected vertices for refinement phase maybe helps a very tiny bit. 2191ms

Now doing a swap, instead of a copy - small to no benefit (or worse?). 2024ms

[wolfram77]

Tracking affected communities seems to offer no advantage for large batch updates - however, we are getting some disconnected communities - need to fix. However, it may have good runtimes for small batch updates.

Fixing the issues required doing a full copy of community memberships as community bound, instead of a simple swap.

Although we are still seeing some rare (1/X) disconnected communities (1E-7 batch fraction).

With sequential refinement phase, this issue is not there, i.e., it does not introduce disconnected communities. So its a parallelism issue. But in some cases, disconnected communities is received as input, but why? Probably a subrefine related issue.

The input graph may have disconnected communities since a bridge got removed. This needs to be tracked, and such a community needs to be refined.

It seems the issue is now solved!

[wolfram77]

• Output logs for input-large are being generated on DGX Station A100 : aggregation tolerance set to 1 (disabled).
• Output logs for input-temporal are being generated on EPYC2 server.

Aggregation tolerance should have been enabled for large graphs!

• Updated output logs for input-large are being generated on EPYC2 : aggregation tolerance set to 0.8 (enabled).