gephi.team team mailing list archive

[Thomas Aynaud <taynaud@xxxxxxxxx>]

Thomas Aynaud has proposed merging lp:~taynaud/gephi/statistics-correction into lp:gephi.

Requested reviews:
  Gephi Team (gephi.team)
Related bugs:
  Bug #727701 in Gephi: "Statistics: sub-optimal modularity"
  https://bugs.launchpad.net/gephi/+bug/727701

For more details, see:
https://code.launchpad.net/~taynaud/gephi/statistics-correction/+merge/61108

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.


-- 
https://code.launchpad.net/~taynaud/gephi/statistics-correction/+merge/61108
Your team Gephi Team is requested to review the proposed merge of lp:~taynaud/gephi/statistics-correction into lp:gephi.

=== 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;
     }
 }