Observing low modularity with Static/Dynamic Leiden on temporal graphs

[wolfram77]

Compared to Static Louvain.

[wolfram77]

Here is the results with large graphs (5050). Slightly lower modularity with Leiden, and poor modularity with Dynamic Frontier Leiden. What is causing this?

[wolfram77]

Disabling aggregation tolerance seems to help!

[wolfram77]

On large graph with random batch updates (80% edge insertions, 20% deletions), also run Static Louvain and Static Leiden as reference. However, no issues are observed here. But Dynamic Frontier Leiden is returning communities of lower modularity.

After a small batch update, Dynamic Louvain converges very quickly and does not need to perform aggregation. With Dynamic Leiden, the local-moving phase also converges very quickly, but then there is the refinement phase. The refinement phase now splits the large communities into smaller communities. Here, the algorithm stops - this is the cause of the issue.

The only solution I can see is to keep running more passes - like Static Leiden, until it converges.

[wolfram77]

disable aggregation tolerance for temporal graphs

[wolfram77]

restrict refinement phase

The idea is to restrict the refinement of communities to those in which vertices actually change their community membership.

---

restrict refinement for ND and DS approaches

---

reduce unneeded copies

Limit to order of current graph.