Merge lp:~taynaud/gephi/statistics-correction into lp:~gephi.team/gephi/0.8

[Thomas Aynaud]

Correct a bug in modularity optimisation.

The Louvain algorithm study node one by one, and for each node :

remove it from its community
look for any neighboring community and select the one which maximizes modularity gain
put the node into this community.

The implemented algorithm was not removing the node from its community, resulting in a wrong gain computation. Now, the algorithm still not remove the node from its community (which would be slow with the current implementation) but compute the gain accurately.

There was also an issue with self loops counted twice.

[Sébastien Heymann (sebastien.heymann)]

review: Approve

[Sébastien Heymann (sebastien.heymann)]

Merged on rev 2222

=== modified file 'StatisticsPlugin/src/org/gephi/statistics/plugin/Modularity.java'
--- StatisticsPlugin/src/org/gephi/statistics/plugin/Modularity.java	2011-04-07 17:40:45 +0000
+++ StatisticsPlugin/src/org/gephi/statistics/plugin/Modularity.java	2011-05-16 12:56:49 +0000
@@ -96,6 +96,7 @@
         int N;
         HashMap<Integer, Community> invMap;
 
+        
         CommunityStructure(HierarchicalUndirectedGraph hgraph) {
             this.graph = hgraph;
             N = hgraph.getNodeCount();
@@ -116,9 +117,8 @@
                 Community hidden = new Community(structure);
                 hidden.nodes.add(index);
                 invMap.put(index, hidden);
-                communities.add(nodeCommunities[index]);
+                communities.add(nodeCommunities[index]);               
                 index++;
-
                 if (isCanceled) {
                     return;
                 }
@@ -140,7 +140,7 @@
                     nodeCommunities[node_index].connections.put(adjCom, 1);
                     nodeConnections[neighbor_index].put(nodeCommunities[node_index], 1);
                     nodeCommunities[neighbor_index].connections.put(nodeCommunities[node_index], 1);
-                    graphWeightSum++;
+                    graphWeightSum++;//WARNING : may be an issue with self_loop
                 }
 
                 if (isCanceled) {
@@ -275,8 +275,10 @@
                 for(Community adjCom : iter) {
                     int target = communities.indexOf(adjCom);
                     int weight = com.connections.get(adjCom);
-
-                    weightSum += weight;
+                    if(target == index)
+                        weightSum += 2*weight;
+                    else
+                        weightSum += weight;
                     ModEdge e = new ModEdge(index, target, weight);
                     newTopology[index].add(e);
                 }
@@ -304,12 +306,10 @@
     }
 
     class Community {
-
         double weightSum;
         CommunityStructure structure;
         LinkedList<Integer> nodes;
         HashMap<Community, Integer> connections;
-        Integer min;
 
         public int size() {
             return nodes.size();
@@ -319,7 +319,6 @@
             structure = com.structure;
             connections = new HashMap<Community, Integer>();
             nodes = new LinkedList<Integer>();
-            min = Integer.MAX_VALUE;
             //mHidden = pCom.mHidden;
         }
 
@@ -332,15 +331,11 @@
         public void seed(int node) {
             nodes.add(node);
             weightSum += structure.weights[node];
-            min = node;
         }
 
         public boolean add(int node) {
             nodes.addLast(new Integer(node));
             weightSum += structure.weights[node];
-            if (!isRandomized) {
-                min = Math.min(node, min);
-            }
             return true;
         }
 
@@ -350,20 +345,8 @@
             if (nodes.size() == 0) {
                 structure.communities.remove(this);
             }
-            if (!isRandomized) {
-                if (node == min.intValue()) {
-                    min = Integer.MAX_VALUE;
-                    for (Integer other : nodes) {
-                        min = Math.min(other, min);
-                    }
-                }
-            }
             return result;
         }
-
-        public int getMin() {
-            return min;
-        }
     }
 
     public void execute(GraphModel graphModel, AttributeModel attributeModel) {
@@ -375,9 +358,7 @@
         isCanceled = false;
         Progress.start(progress);
         Random rand = new Random();
-
         hgraph.readLock();
-
         structure = new CommunityStructure(hgraph);
         if (isCanceled) {
             hgraph.readUnlockAll();
@@ -387,8 +368,6 @@
         while (someChange) {
             someChange = false;
             boolean localChange = true;
-
-
             while (localChange) {
                 localChange = false;
                 int start = 0;
@@ -398,22 +377,16 @@
                 int step = 0;
                 for (int i = start; step < structure.N; i = (i + 1) % structure.N) {
                     step++;
-                    double best = 0;
-                    double current = q(i, structure.nodeCommunities[i]);
+                    double best = 0.;
                     Community bestCommunity = null;
-                    int smallest = Integer.MAX_VALUE;
+                    Community nodecom = structure.nodeCommunities[i];
                     Set<Community> iter = structure.nodeConnections[i].keySet();
                     for(Community com : iter) {
-                        double qValue = q(i, com) - current;
+                        double qValue = q(i, com);
                         if (qValue > best) {
                             best = qValue;
                             bestCommunity = com;
-                            smallest = com.getMin();
-                        } else if ((qValue == best) && (com.getMin() < smallest)) {
-                            best = qValue;
-                            bestCommunity = com;
-                            smallest = com.getMin();
-                        }
+                        } 
                     }
                     if ((structure.nodeCommunities[i] != bestCommunity) && (bestCommunity != null)) {
                         structure.moveNodeTo(i, bestCommunity);
@@ -518,11 +491,13 @@
         }
         double weightSum = community.weightSum;
         double nodeWeight = structure.weights[node];
-        //double penalty = (nodeWeight * weightSum) / (2.0 * mStructure.graphWeightSum);
         double qValue = edgesTo - (nodeWeight * weightSum) / (2.0 * structure.graphWeightSum);
         if ((structure.nodeCommunities[node] == community) && (structure.nodeCommunities[node].size() > 1)) {
             qValue = edgesTo - (nodeWeight * (weightSum - nodeWeight)) / (2.0 * structure.graphWeightSum);
         }
+        if ((structure.nodeCommunities[node] == community) && (structure.nodeCommunities[node].size() == 1)) {
+            qValue = 0.;
+        }
         return qValue;
     }
 }