Louvain Method (init.clusters, levels, negative edge weights)
Simona Z.
Müller Julian
Dear Simona,
> 1) In the menu there is a field called "init. clusters". What does it mean or do?
The Louvain clustering algorithm iteratively transforms one clustering into another by performing two different kinds of operations. This setting lets you set the clustering the algorithm first works on; if you don’t set anything specifically, visone will start from the clustering consisting of singleton clusters (as is usual for Louvain). You give this initial clustering by specifying an attribute: If two vertices are assigned the same value, they are considered to be in the same cluster.
Note that the Louvain algorithm can move vertices between clusters, so it’s not guaranteed that the final result is a coarsening of the initial clustering.
> 2) What does the value in the new attribute "louvain-level1" tell me?
As I said, the Louvain clustering algorithm performs two kinds of transformations. The first kind is to move single vertices between clusters. But at some point, no further improvement in modularity value is possible anymore with this transformation alone. At such a point, visone outputs the clustering as a “level”.
In preparation for the next round, the Louvain algorithm then performs the other kind of transformation: It merges all clusters into single vertices, producing a new graph. Then it moves single vertices (which represents the clusters of the previous level) in this higher-order graph between some new clusters again until there is no further increase in modularity value, yielding the clustering at the next level.
In this way, we get a hierarchy of level clusterings, producing coarser and coarser clustering, until the modularity value no longer improves. All the clusterings at intermediate levels are stored as “louvain-levelx”, and the clustering with maximum modularity is stored as “louvain” (if the standard attribute name isn’t changed).
> 3) More generally: Would it make sense to apply the Louvain Algorithm on signed networks (negative edge weights)? I am not able to deduce this from the formula ...
While I haven’t tried it, I think this is often not a good idea. Standard modularity was not designed with signed networks in mind.
Perhaps you might get away with it as long as there are only few edges with negative weight. But the moment the weighted degree of any vertex becomes negative, I would expect it to misbehave badly.
The problem is that in modularity, the degrees of two vertices are multiplied to compute the expected weight of an edge between them. For example, if two vertices have negative degree, then modularity expects them to be connected by a positive weight (!) edge. I don’t think this makes sense.
Best wishes,
Julian