search

vtraag / leidenalg

Implementation of the Leiden algorithm for various quality functions to be used with igraph in Python.
GNU General Public License v3.0
566 stars 76 forks source link

Question on Guarantee of Connected Communities #145

Closed EllingtonKirby closed 11 months ago

EllingtonKirby commented 11 months ago

Hi there! I am working on an implementation of a new objective function for the Leiden Algorithm, and I have hit a bit of a snag on the connectedness of the resulting communities.

I apologize if this is not the correct place to pose a question regarding the proof behind the Leiden algorithm, let me know if there is a better place to ask.

When looking at the proof of the guarantee of connectivity here (specifically Theorem 5), I do not see any specific references to modularity or CPM as objective functions. I do see these references later in the proof of optimality.

This has led me to conclude that the algorithm should guarantee connectivity of the resulting communities regardless of the objective function used.

However the objective function I have developed (a new subclass of LinearResolutionParameterVertexPartition) does not result in completely connected communities when looking at some more complex examples.

Do you have any insight into where I could be making an error? My assumption is that my objective function is flawed, but the proof leads me to believe that the objective function should not affect the connectedness of the resulting communities.

Thank you for your time and work on the project, it has been hugely helpful in my research.

EllingtonKirby commented 11 months ago

After doing some more digging I think it is actually quite clear that the guarantees of Connectivity do not apply for my new objective function. Thanks for your time