java的
我正尝试在Java中实现上述社区检测算法，并且在访问C ++代码和原始文件的同时，我无法使其工作。 我的主要问题是我不明白代码的目的 - 即算法的工作原理。 实际上，我的代码陷入了mergeBestQ似乎无限循环的mergeBestQ ，列表heap似乎在每次迭代时都变得更大（正如我期望的那样），但是topQ的值总是返回相同的值值。
我正在测试的这个图很大（300,000个节点，650,000个边）。 我用于实现的原始代码来自SNAP库（https://github.com/snap-stanford/snap/blob/master/snap-core/cmty.cpp）。 如果有人能够向我解释算法的直观性，那么最好的办法是将每个节点设置在它自己的社区中，然后记录每个连接节点的模块性值（不管是什么）图，然后找到具有最高模块性的节点对并将它们移动到同一个社区。 另外，如果有人可以提供一些中级伪代码，那就太好了。 这是我迄今为止的实现，为了简洁起见，我试图将它保存在一个文件中，但CommunityGraph和CommunityNode在别处（不应该被要求）。 图维护一个所有节点的列表，每个节点维护一个到其他节点的连接列表。 在运行时，它永远不会超过该行while(this.mergeBestQ()){}
更新 - 彻底审查后发现我的代码中的几个错误。 代码现在很快就完成了，但并没有完全实现该算法，例如图中的300,000个节点，它说明大约有299,000个社区（即每个社区大约有1个节点）。 我已经列出了下面的更新代码。 /// Clauset-Newman-Moore社区检测方法。 ///在每一步中，两个为全球模块化贡献最大正值的社区被合并。 ///见：在非常大的网络中查找社区结构，A. Clauset，MEJ Newman，C. Moore，2004 public class CNMMCommunityMetric implements CommunityMetric {private static class DoubleIntInt implements Comparable {public double val1; public int val2; public int val3; DoubleIntInt（double val1，int val2，int val3）{this.val1 = val1; this.val2 = val2; this.val3 = val3; }
@Override
public int compareTo(DoubleIntInt o) {
//int this_sum = this.val2 + this.val3;
//int oth_sum = o.val2 + o.val3;
if(this.equals(o)){
return 0;
}
else if(val1 < o.val1 || (val1 == o.val1 && val2 < o.val2) || (val1 == o.val1 && val2 == o.val2 && val3 < o.val3)){
return 1;
}
else{
return -1;
}
//return this.val1 < o.val1 ? 1 : (this.val1 > o.val1 ? -1 : this_sum - oth_sum);
}
@Override
public boolean equals(Object o){
return this.val2 == ((DoubleIntInt)o).val2 && this.val3 == ((DoubleIntInt)o).val3;
}
@Override
public int hashCode() {
int hash = 3;
hash = 79 * hash + this.val2;
hash = 79 * hash + this.val3;
return hash;
}
}
private static class CommunityData {
double DegFrac;
TIntDoubleHashMap nodeToQ = new TIntDoubleHashMap();
int maxQId;
CommunityData(){
maxQId = -1;
}
CommunityData(double nodeDegFrac, int outDeg){
DegFrac = nodeDegFrac;
maxQId = -1;
}
void addQ(int NId, double Q) {
nodeToQ.put(NId, Q);
if (maxQId == -1 || nodeToQ.get(maxQId) < Q) {
maxQId = NId;
}
}
void updateMaxQ() {
maxQId=-1;
int[] nodeIDs = nodeToQ.keys();
double maxQ = nodeToQ.get(maxQId);
for(int i = 0; i < nodeIDs.length; i++){
int id = nodeIDs[i];
if(maxQId == -1 || maxQ < nodeToQ.get(id)){
maxQId = id;
maxQ = nodeToQ.get(maxQId);
}
}
}
void delLink(int K) {
int NId=getMxQNId();
nodeToQ.remove(K);
if (NId == K) {
updateMaxQ();
}
}
int getMxQNId() {
return maxQId;
}
double getMxQ() {
return nodeToQ.get(maxQId);
}
};
private TIntObjectHashMap<CommunityData> communityData = new TIntObjectHashMap<CommunityData>();
private TreeSet<DoubleIntInt> heap = new TreeSet<DoubleIntInt>();
private HashMap<DoubleIntInt,DoubleIntInt> set = new HashMap<DoubleIntInt,DoubleIntInt>();
private double Q = 0.0;
private UnionFind uf = new UnionFind();
@Override
public double getCommunities(CommunityGraph graph) {
init(graph);
//CNMMCommunityMetric metric = new CNMMCommunityMetric();
//metric.getCommunities(graph);
// maximize modularity
while (this.mergeBestQ(graph)) {
}
// reconstruct communities
HashMap<Integer, ArrayList<Integer>> IdCmtyH = new HashMap<Integer, ArrayList<Integer>>();
Iterator<CommunityNode> ns = graph.getNodes();
int community = 0;
TIntIntHashMap communities = new TIntIntHashMap();
while(ns.hasNext()){
CommunityNode n = ns.next();
int r = uf.find(n);
if(!communities.contains(r)){
communities.put(r, community++);
}
n.setCommunity(communities.get(r));
}
System.exit(0);
return this.Q;
}
private void init(Graph graph) {
double M = 0.5/graph.getEdgesList().size();
Iterator<Node> ns = graph.getNodes();
while(ns.hasNext()){
Node n = ns.next();
uf.add(n);
int edges = n.getEdgesList().size();
if(edges == 0){
continue;
}
CommunityData dat = new CommunityData(M * edges, edges);
communityData.put(n.getId(), dat);
Iterator<Edge> es = n.getConnections();
while(es.hasNext()){
Edge e = es.next();
Node dest = e.getStart() == n ? e.getEnd() : e.getStart();
double dstMod = 2 * M * (1.0 - edges * dest.getEdgesList().size() * M);//(1 / (2 * M)) - ((n.getEdgesList().size() * dest.getEdgesList().size()) / ((2 * M) * (2 * M)));// * (1.0 - edges * dest.getEdgesList().size() * M);
dat.addQ(dest.getId(), dstMod);
}
Q += -1.0 * (edges*M) * (edges*M);
if(n.getId() < dat.getMxQNId()){
addToHeap(createEdge(dat.getMxQ(), n.getId(), dat.getMxQNId()));
}
}
}
void addToHeap(DoubleIntInt o){
heap.add(o);
}
DoubleIntInt createEdge(double val1, int val2, int val3){
DoubleIntInt n = new DoubleIntInt(val1, val2, val3);
if(set.containsKey(n)){
DoubleIntInt n1 = set.get(n);
heap.remove(n1);
if(n1.val1 < val1){
n1.val1 = val1;
}
n = n1;
}
else{
set.put(n, n);
}
return n;
}
void removeFromHeap(Collection<DoubleIntInt> col, DoubleIntInt o){
//set.remove(o);
col.remove(o);
}
DoubleIntInt findMxQEdge() {
while (true) {
if (heap.isEmpty()) {
break;
}
DoubleIntInt topQ = heap.first();
removeFromHeap(heap, topQ);
//heap.remove(topQ);
if (!communityData.containsKey(topQ.val2) || ! communityData.containsKey(topQ.val3)) {
continue;
}
if (topQ.val1 != communityData.get(topQ.val2).getMxQ() && topQ.val1 != communityData.get(topQ.val3).getMxQ()) {
continue;
}
return topQ;
}
return new DoubleIntInt(-1.0, -1, -1);
}
boolean mergeBestQ(Graph graph) {
DoubleIntInt topQ = findMxQEdge();
if (topQ.val1 <= 0.0) {
return false;
}
// joint communities
int i = topQ.val3;
int j = topQ.val2;
uf.union(i, j);
Q += topQ.val1;
CommunityData datJ = communityData.get(j);
CommunityData datI = communityData.get(i);
datI.delLink(j);
datJ.delLink(i);
int[] datJData = datJ.nodeToQ.keys();
for(int _k = 0; _k < datJData.length; _k++){
int k = datJData[_k];
CommunityData datK = communityData.get(k);
double newQ = datJ.nodeToQ.get(k);
//if(datJ.nodeToQ.containsKey(i)){
// newQ = datJ.nodeToQ.get(i);
//}
if (datI.nodeToQ.containsKey(k)) {
newQ = newQ + datI.nodeToQ.get(k);
datK.delLink(i);
} // K connected to I and J
else {
newQ = newQ - 2 * datI.DegFrac * datK.DegFrac;
} // K connected to J not I
datJ.addQ(k, newQ);
datK.addQ(j, newQ);
addToHeap(createEdge(newQ, Math.min(j, k), Math.max(j, k)));
}
int[] datIData = datI.nodeToQ.keys();
for(int _k = 0; _k < datIData.length; _k++){
int k = datIData[_k];
if (!datJ.nodeToQ.containsKey(k)) { // K connected to I not J
CommunityData datK = communityData.get(k);
double newQ = datI.nodeToQ.get(k) - 2 * datJ.DegFrac * datK.DegFrac;
datJ.addQ(k, newQ);
datK.delLink(i);
datK.addQ(j, newQ);
addToHeap(createEdge(newQ, Math.min(j, k), Math.max(j, k)));
}
}
datJ.DegFrac += datI.DegFrac;
if (datJ.nodeToQ.isEmpty()) {
communityData.remove(j);
} // isolated community (done)
communityData.remove(i);
return true;
}
}
更新：目前列出的代码相当快，与“最快”解决方案相比，内存使用量减少了一半，而速度只有5％左右。 不同之处在于使用hashmap + treest vs优先级队列，并且确保任何时候只存在给定i，j对的单个对象。
所以这里是原始文件，整齐的六页，其中只有两页是关于设计和实现。 这里有一个悬崖：
Q定义为每个社区内的边数与每个社区之间的边数之比，减去您期望从完全随机分区。 i和j ，然后他们将deltaQ_ij定义为如果社区i和j合并，分区的模块性会发生多大变化。 因此，如果deltaQ_ij > 0 ，则合并i和j将提高分区的模块性。 deltaQ_ij 。 无论哪两个社区i, j拥有最大的deltaQ_ij ， deltaQ_ij这两个社区合并。 重复。 deltaQ_ij变为负值时，您将获得最大的模块化，但在本文中，作者让算法运行，直到只剩下一个社区。 这很适合理解算法。 详细介绍如何快速计算deltaQ_ij并有效存储信息。
编辑：数据结构时间！
所以，首先，我认为您所引用的实现可以以不同的方式完成文章。 我不太确定，因为代码是不可通过的，但似乎使用union-find和hashsets来代替作者的二叉树和多堆。 不知道他们为什么以不同的方式去做。 您可能需要通过电子邮件向编写该问题的人发送电子邮件。
无论如何，论文中的算法需要从deltaQ格式中存储的几种东西：
dQ的最大值。 i所有deltaQ_ik和deltaQ_ki 。 j所有deltaQ_kj和deltaQ_jk 。 作者提出的解决方案如下：
i ，每个非零 deltaQ_ik都存储在一个平衡二叉树中，由k索引（因此可以轻松找到元素），并存储在堆中（因此可以轻松找到该社区的最大值）。 i的堆的最大deltaQ_ik存储在另一个堆中，以便可以轻松找到总体最大值。 当社区i与社区j合并时，二叉树会发生以下几种情况：
i个社区的每个元素都被添加到第j个社区的二叉树中。 如果具有相同索引k的元素已经存在，则对新旧值进行求和。 j个社区的二叉树中所有剩余的“旧”值，以反映第j个社区的规模增加的事实。 k ，我们更新任何deltaQ_kj 。 i被扔掉。 同样，一些事情必须发生在堆：
i被扔掉。 j的堆。 k堆，更新条目deltaQ_kj的位置。 i在整个堆中的条目被扔掉（引起冒泡），社区j和连接到i或j每个社区k的条目都被更新。 奇怪的是，当两个社区合并时，在论文中没有提到从第k个社区的堆或树中删除deltaQ_ki值。 我认为这可以通过设置a_i = 0来处理，但我不明白该算法足够确定。
编辑：试图破译你链接的实现。 他们的主要数据结构是
CmtyIdUF ，一种联合查找结构，用于跟踪哪些节点位于哪个社区（在论文中被忽略的东西，但是除非您想从合并的痕迹重新构建社区成员资格，这似乎是必要的）， MxQHeap是一个堆，用于跟踪哪个deltaQ_ij最大。 奇怪的是，当他们更新堆中的TFltIntIntTr的值时，他们不会要求堆重新自我heapify。 这令人担忧。 它是自动执行还是其他操作？ CmtyQH ，一个将社区ID i映射到TCmtyDat结构的散列映射，该结构持有该社区的deltaQ_ik堆的deltaQ_ik 。 我认为。 奇怪的是虽然， UpdateMaxQ所述的TCmtyDat结构采用线性时间，从而避免需要任何堆。 更重要的是， UpdateMaxQ方法似乎只在堆的一个元素被删除时调用。 当堆中的任何元素的值更新时，它肯定也会被调用。 上一篇: java
下一篇: Overlapping community detection with igraph or other libaries