1

I have an implementation of Louvain that is creating communities with unconnected nodes. I want to know if I am doing Louvain wrong or if this is possible in a correct implementation of Louvain? Please see the picture below.

Louvain being implemented wrong?

What is happening is:

  1. The green node both of those blue nodes are connected to (1KwXk7) started out blue and the nodes on the end were two random colors
  2. The two nodes on the end (1FqzYq & 1Eevy8) decided they should be blue (one at a time obviously)
  3. The green color crept up on 1KwXk7 changing the node which bridges this community to green

Is this always going to happen in a correct implementation of Louvain? (If by chance you have a suggestion to fix it, I would be extra grateful)

Jeff Diederiks
  • 113
  • 4

1 Answers1

1

Yes, it can. This problem has been recently addressed by this paper: From Louvain to Leiden: guaranteeing well-connected communities by Vincent Traag, Ludo Waltman, Nees Jan van Eck

https://arxiv.org/abs/1810.08473

Math Helper
  • 126
  • 4
  • Nice. Haven't read the full paper, but I downloaded the PDF and this is definitely the answer I was looking for – Jeff Diederiks Nov 02 '18 at 04:47
  • 1
    Welcome to Cross Validated, & thank you for providing this reference. Do you think you could add a little information on the contents, so we've an answer on-site? – Scortchi - Reinstate Monica Nov 02 '18 at 09:04
  • 1
    Welcome to the site. We are trying to build a permanent repository of high-quality statistical information in the form of questions & answers. Thus, we're wary of link-only answers, due to linkrot. Can you post a full citation & a summary of the information at the link, in case it goes dead? – gung - Reinstate Monica Nov 02 '18 at 11:15