Re: [igraph] label propagation community

[Tamas Nepusz]

Dear Prof. Freeman,

> I have tried various formats on a small data set.  I'm afraid that I don't 
> understand the different answers.  They seem to depend on the order of 
> commands.

I don't think they depend on the order of commands, it is simply that label 
propagation is an inherently instable algorithm, and different starting label 
configurations usually lead to completely different results. For instance, here 
are the results of 5 consecutive runs of the algorithm on the Zachary karate 
club network with the same parameters (one row is the membership vector of one 
run):

0 0 1 0 2 2 2 0 1 1 2 0 0 0 1 1 2 0 1 0 1 0 1 1 1 1 1 1 1 1 1 1 1 1

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

0 0 1 0 2 2 2 0 1 1 2 0 0 0 1 1 2 0 1 0 1 0 1 1 1 1 1 1 1 1 1 1 1 1

0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 1 0 0 1 0 1 0 1 1 1 1 1 1 1 1 1 1 1 1

0 0 0 0 1 1 1 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

As you can see, most of the results are different. Even the authors of the 
original Raghavan et al paper suggest to run the algorithm many times and then 
create a "consensus" clustering that summarizes the results. The exact 
technique is described in the Raghavan et al paper. The method to create the 
consensus clustering is not implemented in igraph yet, so one has to put up 
with the instability of the algorithm or write the code that infers a consensus 
clustering. Alternatively, one can try to fix the initial labels of some of the 
nodes that are known to be in different clusters. For instance, giving label 0 
to the first node in the Zachary karate club network and label 1 to the last 
node (while leaving the rest of the nodes unlabeled in the starting position) 
usually converges to one of two possible configurations, both of which are 
plausible, and the nodes with instable affiliations are on the boundary of the 
two communities in the network.

-- 
Tamas