networkx icon indicating copy to clipboard operation
networkx copied to clipboard

Add Leiden algorithm file

Open juanis2112 opened this issue 3 years ago • 1 comments

This is a work in progress of the Leiden's algorithm implementation. I've included a new Leiden.py file with the algorithm implementation (which is not complete yet) which is basically a copy of the Louvain's file but with the relevant changes for Leiden. Up until now:

  • I have added both the Leiden_communities and leiden_partitions functions (following the Louvain's implementation) and I have changed the Louvain's code corresponding to the 'Local moving' phase to turn it into 'Fast local moving' for the Leiden's '_one_level' function.
  • I have also included the description of the algorithm (for the documentation), including the bibliography.
  • I tested these changes with a simple example and it seems to work fine (as in not throwing any errors but I will have to test for graphs that have different output from Louvain than Leiden) I'm missing:
  • The implementation of the refinement phase
  • Changing the parameters of the _gen_graph function once I have the refined partition.
  • Adding tests (which I might need guidance in order to do them).

A couple of questions for @dschult:

  • The code of _convert_multigraph, _gen_graph and _neighbor_weights remains the same for both algorithms. Should I leave them as they are which means defining them exactly the same in the leiden.py file or should I make them available from the louvain.py file and call those ones.
  • Does it make sense to keep these two functions in separate files or does it make sense to group them?

I'll keep working on the refinement phase and upload some code soon.

juanis2112 avatar Sep 06 '22 01:09 juanis2112

Thanks Dan! I will update the init.py for now to avoid some of the errors. I think I wasn't clear about my question. I meant keeping louvain and leiden in separate files since I will be using the auxiliary functions for both of them. But I think you've answered it already. We'll keep them separately as it is right now.

juanis2112 avatar Sep 06 '22 04:09 juanis2112