Clauset Newman Moore社区检测实现

Question

我试图在Java中实现上述社区检测算法，虽然我可以访问C代码和原始论文——但我根本无法使其工作。我的主要问题是我不明白代码的目的——即算法是如何工作的。实际上，我的代码陷入了mergeBestQ的无限循环中，列表heap似乎在每次迭代中都变得越来越大（正如我对代码的期望），但topQ的值总是返回相同的值。

我测试这个的图相当大（300,000个节点，650,000条边）。我用于实现的原始代码来自SNAP库（https://github.com/snap-stanford/snap/blob/master/snap-core/cmty.cpp）。如果有人能向我解释算法的直觉，它似乎首先将每个节点设置为自己的社区，然后记录图中每对连接节点的模块化值（无论是什么），然后找到模块化最高的节点对并将它们移动到同一个社区。此外，如果有人能提供一些中级伪代码，那就太好了。到目前为止，这是我的实现，为了简洁起见，我试图将其保存在一个文件中，但是Community ityGraph和Community ityNode在其他地方（不应该是必需的）。Graph维护所有节点的列表，每个节点维护其与其他节点的连接列表。运行时，它永远不会超过行，而（this.mergeBestQ()){}

更新-彻底检查后发现我的代码中有几个bug。代码现在完成得很快，但没有完全实现算法，例如，在图中的300000个节点中，它表示大约有299000个社区（即每个社区大约有1个节点）。我在下面列出了更新的代码。///克劳塞特-纽曼-摩尔社区检测方法在每一步中，都会合并两个对全局模块化贡献最大正价值的社区。///参见：在非常大的网络中查找社区结构，A.Clauset，M.E.J.Newman，C.Moore，2004 public class CNMMCommunityMetric implements CommunityMetric{私有静态类DoubleInt implements Compariable{公共double val1；公共int val2；公共int val3；DoubleInt（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){
    //html" target="_blank">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与priority queue，并确保给定i，j对在任何时候都只存在一个对象。

Answer 1

这是原始文件整整六页其中只有两页是关于设计的

• 对于给定图的分区，作者将分区的模块化Q定义为每个社区内的边数与每个社区之间的边数的比率，减去您期望的比率从一个完全随机的分区。
• 所以它实际上是“这个分区在定义社区方面比完全随机的分区好多少？”
• 给定分区的两个社区i和j，然后他们将deltaQ_ij定义为如果社区i和j合并，分区的模块化程度会发生多大变化。所以如果deltaQ_ij

这在很大程度上是为了理解算法。详细介绍如何快速计算deltaQ\u ij并高效存储信息。

编辑：数据结构时间！

所以首先，我认为您引用的实现以与论文不同的方式做事。我不太确定是如何做到的，因为代码是不可理解的，但它似乎使用联合查找和哈希集来代替作者的二叉树和多个堆。不知道他们为什么用不同的方式做这件事。你可能想给写它的人发电子邮件并询问。

无论如何，本文中的算法需要从deltaQ的存储格式来看：

• 首先，它需要能够快速恢复dQ中的最大值。
• 其次，它需要能够快速删除固定i的所有deltaQ_ik和deltaQ_ki。
• 第三，它需要能够快速更新所有deltaQ_kj和deltaQ_jk为固定的j。

作者提出的解决方案如下：

• 对于每个社区，每个非零的deltaQ\u ik存储在一个平衡的二叉树中，由k索引（因此可以很容易地找到元素），并存储在一个堆中（因此可以很容易地找到该社区的最大值）

当社区i与社区j合并时，二叉树会发生几件事：

• 首先，来自ith社区的每个元素都被添加到jth社区的二叉树中。如果具有相同索引k的元素已经存在，则将旧值和新值相加。
• 其次，我们更新jth社区的二叉树中所有剩余的“旧”值，以反映jth社区刚刚增加大小的事实。
• 对于每个社区的二叉树k，我们更新任何deltaQ_kj。
• 最后，社区i的树被扔掉了。

同样，堆必须发生几件事：

• 首先，社区i的堆被丢弃。
• 然后使用社区平衡二叉树中的元素从头开始重建社区j的堆。
• 并且对于彼此社区k的堆，条目deltaQ_kj的位置被更新。
• 最后，整个堆中社区i的条目被丢弃（导致冒泡），社区j和每个社区k的条目连接到i或j被更新。

奇怪的是，当两个社区合并时，论文中没有提到从社区的堆或树中删除deltaQ\u ki值。我认为这可以通过设置a\u I=0来解决，但我对算法的理解不够清楚，无法确定。

编辑：尝试破译您链接的实现。他们的主要数据结构是

• CmtyIdUF是一种联合查找结构，它跟踪哪些节点位于哪个社区中（这在本文中被忽略了，但似乎是必要的，除非您想从合并或其他跟踪中重建社区成员身份），