java - 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 )。如果有人可以向我解释算法的直觉，那就太好了，它似乎最初将每个节点设置在它自己的社区中，然后记录每个连接节点对的模块化值(无论是什么)在图，然后找到具有最高模块化的节点对并将它们移动到同一个社区。另外，如果有人能提供一些中级伪代码，那就太好了。到目前为止，这是我的实现，为了简洁起见，我试图将它保存在一个文件中，但是 CommunityGraph 和 CommunityNode 在其他地方(不应该是必需的)。图维护所有节点的列表，每个节点维护其与其他节点的连接列表。运行时它永远不会超过 while(this.mergeBestQ()){}
更新 - 经过彻底审查后在我的代码中发现了几个错误。代码现在完成得非常快，但没有完全实现算法，例如图中的 300,000 个节点，它指出大约有 299,000 个社区(即每个社区大约 1 个节点)。我在下面列出了更新的代码。
///Clauset-Newman-Moore 社区检测方法。
///在每一步，对全局模块化贡献最大正值的两个社区都会被合并。
///参见:在超大型网络中寻找社区结构，A. Clauset, M.E.J. Newman C. 摩尔，2004
公共(public)类 CNMMCommunityMetric 实现 CommunityMetric{
私有(private)静态类 DoubleIntInt 实现了 Comparable{
公共(public)双 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 对的单个对象。

Answer 1

所以here's原始论文，整整六页，其中只有两页是关于设计和实现的。这是一个悬崖笔记:

对于给定图的分区，作者定义了模块化，Q , of the partition 是每个社区内的边数与每个社区之间的边数的比率，减去您对完全随机分区的期望比率。

所以它实际上是“这个分区在定义社区方面比完全随机的社区好多少？”

给定两个社区 i和 j分区，然后定义 deltaQ_ij如果社区 i 分区的模块化将改变多少和 j被合并了。所以如果 deltaQ_ij > 0 , 合并 i和 j将提高分区的模块化。

这导致了一个简单的贪心算法:从它自己社区中的每个节点开始。计算 deltaQ_ij对于每对社区。任意两个社区i, j有最大的deltaQ_ij ，合并这两个。重复。

当 deltaQ_ij 时，您将获得最大的模块化全部变为否定，但在论文中，作者让算法运行直到只剩下一个社区。

这就是理解算法的全部内容。详细信息在如何计算 deltaQ_ij快速有效地存储信息。

编辑:数据结构时间!

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

无论如何，论文中的算法需要来自格式 deltaQ的几个东西。存储在:

首先，它需要能够恢复dQ中的最大值。迅速地。

其次，它需要能够删除所有deltaQ_ik和 deltaQ_ki固定i迅速地。

第三，需要能够更新所有deltaQ_kj和 deltaQ_jk固定j迅速地。

作者为此提出的解决方案如下:

每个社区i , 每个 非零 deltaQ_ik存储在 balanced binary tree 中，由 k 索引(因此可以轻松找到元素)，并在堆中(因此可以轻松找到该社区的最大值)。

最大deltaQ_ik来自各个社区i然后将 的堆存储在另一个堆中，以便可以轻松找到总体最大值。

当社区 i与社区合并 j ，二叉树发生了几件事:

首先，每个元素来自 i第一个社区已添加到 j社区的二叉树。如果一个元素具有相同的索引 k已经存在，您将旧值和新值相加。

其次，我们更新 j 中所有剩余的“旧”值。第一个社区的二叉树反射(reflect)了j社区的规模刚刚扩大。

并为彼此社区的二叉树k , 我们更新任何 deltaQ_kj .

最后，社区树i被扔掉。

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

一、社区堆i被扔掉。

然后是社区的堆j使用社区平衡二叉树中的元素从头开始重建。

并为彼此社区k的堆，入口的位置deltaQ_kj已更新。

最后，社区入口i在整个堆中被丢弃(导致冒泡)和社区条目 j和每个社区k连接到 i或 j更新。

奇怪的是，当两个社区合并时，论文中没有提到删除 deltaQ_ki来自 k 的值社区的堆或树。我认为这可以通过 a_i = 0 的设置来解决。 ，但我不太了解算法，无法确定。

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

CmtyIdUF ，一种 union 查找结构，用于跟踪哪些节点在哪个社区中(论文中忽略了这一点，但除非您想从合并的痕迹或其他内容中重建社区成员资格，否则这似乎是必要的)，

MxQHeap , 一个堆来跟踪哪个 deltaQ_ij是最大的。奇怪的是，当他们更新 TFltIntIntTr 的值时在堆中，他们不会要求堆重新堆放自己。这令人担忧。它是自动执行的还是什么？

CmtyQH ，映射社区 ID i 的哈希图到结构 TCmtyDat它保存着 deltaQ_ik 的堆对于那个社区。我认为。奇怪的是，UpdateMaxQ的TCmtyDat结构需要线性时间，不需要堆。更重要的是，UpdateMaxQ方法似乎只在堆的元素被删除时被调用。当堆中任何元素的值更新时，它肯定也应该被调用。