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;
}
}
_______________________________________________
Mailing list: https://launchpad.net/~gephi.team
Post to : [email protected]
Unsubscribe : https://launchpad.net/~gephi.team
More help : https://help.launchpad.net/ListHelp
