Clauset-Newman-Moore社区检测实现

2020年12月2日 65点热度 0条评论

我正在尝试用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与优先级队列,并确保给定的i,j对在任何时候都只存在一个对象。

解决方案如下:

因此,原始文件ozt_a整整齐齐,只有六页,其中只有两页是关于设计和实现的。这是一个悬崖笔记:

  • 对于给定图的分区,作者将分区的模块性Q定义为每个社区内的边数与每个社区之间的边数之比,减去您期望的比例。完全随机分区。
  • 因此,“在定义社区方面,这种划分比完全随机的划分要好多少?”
  • 在给定分区的两个社区ij的情况下,他们然后将deltaQ_ij定义为如果社区ij合并,分区的模块性将发生多少变化。因此,如果将deltaQ_ij > 0ij合并,将会改善分区的模块化。
  • 导致一个简单的贪婪算法:从其自身社区中的每个节点开始。为每对社区计算deltaQ_ij。哪两个社区i, j具有最大的deltaQ_ij,将这两个社区合并。重复。
  • deltaQ_ij全部变为负数时,您将获得最大的模块化,但是在本文中,作者让算法运行直到只剩下一个社区。
  • 理解算法就差不多了。详细信息涉及如何快速计算
    deltaQ_ij和有效存储信息。

    编辑:数据结构时间!

    所以首先,我认为您所引用的实现对本文的处理方式有所不同。我不太确定该怎么做,因为代码难以理解,但是它似乎使用联合查找和哈希集来代替作者的二进制树和多个堆。不知道为什么他们以不同的方式来做。您可能想通过电子邮件发送给编写它的人并询问。

    无论如何,本文中的算法需要将
    deltaQ格式存储在以下几项内容中:

  • 首先,它需要能够快速恢复dQ中的最大值。
  • 其次,它需要能够快速删除固定的deltaQ_ik的所有deltaQ_kii
  • 第三,它需要能够为固定的deltaQ_kj快速更新所有deltaQ_jkj
  • 作者为此提出的解决方案如下:

  • 对于每个社区i,每个非零 deltaQ_ik都存储在here's中,并通过k进行索引(因此可以轻松找到元素),并在堆中(因此可以轻松找到该社区的最大值)。
  • 然后将每个社区deltaQ_ik堆中的最大i存储在另一个堆中,以便可以轻松地找到最大总数。
  • 当社区
    i与社区
    j合并时,二进制树会发生几件事:

  • 首先,将i社区的每个元素添加到j社区的二叉树。如果已经存在具有相同索引k的元素,则将旧值和新值相加。
  • 第二,我们更新j社区的二叉树中所有剩余的“旧”值,以反射(reflect)j社区的大小刚刚增加的事实。
  • 对于每个其他社区的二进制树k,我们将更新任何deltaQ_kj
  • 最后,丢弃了社区i的树。
  • 同样,堆中必须发生几件事:

  • 首先,丢弃社区i的堆。
  • 然后,使用社区平衡二进制树中的元素从头开始重新构建社区j的堆。
  • 对于每个社区k的堆,条目deltaQ_kj的位置也会更新。
  • 最后,将丢弃整个堆中社区i的条目(导致冒泡),并更新社区j的条目以及连接到ki的每个社区j的条目。
  • 奇怪的是,当两个社区合并时,本文中没有提及从社区的堆或树中删除
    deltaQ_ki值。我认为这可以通过
    k的设置来解决,但是我对算法的理解不够清楚。

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

  • a_i = 0,一种联合查找结构,用于跟踪哪个节点位于哪个社区中(本文中忽略了这一点,但是除非您想从合并的痕迹或其他内容重建社区成员身份,否则似乎是必需的),
  • CmtyIdUF,用于跟踪总体上最大的MxQHeap的堆。奇怪的是,当他们更新堆中deltaQ_ij的值时,他们不要求堆重新堆自己。这令人担忧。它会自动执行吗?
  • TFltIntIntTr,一个哈希图,将社区ID CmtyQH映射到结构i,该结构保存该社区的TCmtyDat堆。我认为。但是奇怪的是,deltaQ_ik结构的UpdateMaxQ占用线性时间,从而消除了对堆的任何需要。而且,仅当删除堆中的某个元素时,才会调用TCmtyDat方法。当堆中任何元素的值更新时,也肯定会调用它。