search

NetLogo / NW-Extension

This is the NetLogo Network Extension. For general information about NetLogo, see:
http://ccl.northwestern.edu/netlogo/
Other
62 stars 25 forks source link

Add Leiden community detection algorithm? #191

Open nicolaspayette opened 5 years ago

nicolaspayette commented 5 years ago

This got published today: https://www.nature.com/articles/s41598-019-41695-z

A Java implementation is available at https://github.com/CWTSLeiden/networkanalysis.

I haven't looked at any of it in details, but it might warrant future consideration.

qiemem commented 5 years ago

Thanks @nicolaspayette! That paper looks great. The point about disconnected communities in Louvain is really interesting; obvious in retrospect, but never occurred to me before.

Looks like the algorithm is broadly as follows. Initialize each node to its singleton community, then:

  1. Locally move nodes between communities to maximize objective function. It uses a faster local move than Louvain; nodes are processed in a queue. When you move a node, you add any of its neighbors to the queue that aren't in its new community. This way, you don't have to scan every node every pass. Pretty clever; this is strictly better than the traditional Louvain local move, yes? I think it could actually be incorporated into Louvain without impacting behavior.
  2. This is the new bit that adds the new guarantees; within each community: a. Put each node in a singleton subcommunity b. Merge subcommunities that are well connected. I don't totally get this step. Looking at the pseudocode, it looks like will only merge singletons into a subcommunity, but that seems a little weird to me. It will only merge into subcommunities that are sufficiently well connected to the other subcommunities, and randomly merges weighted on how much it improves the objective function. c. Replace the original community with the subcommunities in a new partition.
  3. Use the partition generated in 2 to create a meta-network, Louvain-style. Repeat steps until nothing changes.

It inherits the gamma parameter from CPM (which I hadn't heard of until this paper; definitely something we should consider adding). Gamma here then defines how well connected and well separated the communities are. For a community C and subset S, S and C-S will have at least gamma * ||S|| * ||C - S|| internal links. This is the main guarantee that this algorithm has over Louvain.

They also say the algorithm is faster, though AFAICT, most of that speed boost comes from the fast local move, which (again AFAICT) could be used in Louvain.

Anyway, great find @nicolaspayette!