How to access the hierarchical structure of Lieden communities?

[davegies]

The Leiden algorithm is working fine, as described in the tutorials. I can see the final community membership information via partition.membership. However, this is only for the highest community hierarchy? How can I access the hierarchical tree structure to see community memberships at other, intermediate levels -- i.e., as shown in Fig 3 of the original paper.

[vtraag]

This is not accessible from the algorithm. However, all lower-level functions are also exposed, so you can easily replicate this in Python. See the example provided in the documentation at https://leidenalg.readthedocs.io/en/stable/advanced.html#optimiser, the notes about move_nodes.

[davegies]

Thanks, but that example involving move_nodes appears to summarize the Louvain algorithm. Is that right? Do you have some example code showing how to use lower-level functions to access all hierarchy levels for the Leiden algorithm?

[vtraag]

It is essential the same thing, but you have to add the refine step. You then get the following:

optimiser = la.Optimiser()

# Set initial partition
partition = la.ModularityVertexPartition(G)
refined_partition = la.ModularityVertexPartition(G)
partition_agg = refined_partition.aggregate_partition()

while optimiser.move_nodes(partition_agg):

  # Get individual membership for partition
  partition.from_coarse_partition(partition_agg, refined_partition.membership)

  # Refine partition
  refined_partition = la.ModularityVertexPartition(G)
  optimiser.merge_nodes_constrained(refined_partition, partition)

  # Define aggregate partition on refined partition
  partition_agg = refined_partition.aggregate_partition()

  # But use membership of actual partition
  aggregate_membership = [None] * len(refined_partition)
  for i in range(G.vcount()):
    aggregate_membership[refined_partition.membership[i]] = partition.membership[i]
  partition_agg.set_membership(aggregate_membership)

Thinking about it, is a good idea to also add this to the documentation, I will do that next.

[davegies]

Very helpful. Thanks very much! Is it expected that this way of executing the algorithm is significantly slower than simply calling optimize_partition? My quick test showed approx 10x slower.

[vtraag]

Yes, it is expected to be substantially slower, stuff that is normally done in C is now translated back and forth between Python, and some stuff is done in Python instead of C.