search

puzzlef / leiden-communities-openmp

Design of OpenMP-based Parallel Leiden algorithm for community detection.
https://arxiv.org/abs/2312.13936
MIT License
7 stars 0 forks source link

Dendrogram support #2

Open atmughrabi opened 7 months ago

atmughrabi commented 7 months ago

Hello,

I would like to know if this code keeps structures between iterations to build a dendrogram after executing Leiden or Louvain.

If so, can you pinpoint it? I would be more than happy to add it as a function. This code is an efficient implementation that is worth experimenting with more.

Thanks!

wolfram77 commented 7 months ago

Hello @atmughrabi thanks for your interest. I use two separate vectors to keep track of the community membership of each vertex in original and the super-vertex graph, called ucom and vcom.

https://github.com/puzzlef/leiden-communities-openmp/blob/arXiv-2312.13936/inc/leiden.hxx#L1283

Each pass, i update ucom, based on the updated community membership of each super-vertex in vcom.

https://github.com/puzzlef/leiden-communities-openmp/blob/arXiv-2312.13936/inc/leiden.hxx#L1358

To capture the dendrogram (after each pass), you could keep a copy of ucom after the first pass, and a copy of vcom after further passes. To capture the community membership of each vertex after each pass (i.e., flattened dendrogram), you could simply keep a copy of ucom after each pass.

Do you intend to create a pull request for this?

atmughrabi commented 7 months ago

Since I am not an active project member, I will create a fork and do my modifications there. I want to ensure your code stays tidy. Once I add this function, I'll let you review it. If you are interested, you can add it as a feature later on while following your standards/style.

This is the best approach.