PGX 20.1.1
Documentation

Infomap

Category community detection

Algorithm ID pgx_builtin_c3_infomap

Time Complexity O((k ^ 2) * E) with E = number of edges, k <= maximum number of iterations

Space Requirement O(10 * V + 2 * E) with V = number of vertices, E = number of edges

Javadoc

Infomap is a robust algorithm designed to find community structures in a graph that requires some pre-processing steps. This implementation needs a reciprocated or an undirected graph, as well as the ranking score from the normalized weighted version of the Pagerank algorithm. It will assign a unique module (or community) label to each vertex in the graph based on their Pagerank score, edge weights and the labels of their neighbors. It is an iterative algorithm that updates the labels of the vertices in random order on each iteration using the previous factors, converging once there are no further changes in the vertex labels, or once the maximum number of iterations is reached. The algorithm is non-deterministic because of the random order for visiting and updating the vertex labels, thus the communities found might be different each time the algorithm is run.

Signature

Input Argument Type Comment
G graph
rank nodeProp vertex property holding the normalized (weighted) PageRank value for each vertex (a value between 0 and 1).
weight edgeProp edge property holding the weight of each edge in the graph.
tau double damping factor.
tol double maximum tolerated error value. The algorithm will stop once the sum of the error values of all vertices becomes smaller than this value.
max_iter int maximum number of iterations that will be performed.
Output Argument Type Comment
module nodeProp vertex property holding the label of the community assigned to each vertex.
Return Value Type Comment
long returns the total number of communities found.

Code

/*
 * Copyright (C) 2013 - 2020 Oracle and/or its affiliates. All rights reserved.
 */
package oracle.pgx.algorithms;

import oracle.pgx.algorithm.ControlFlow;
import oracle.pgx.algorithm.EdgeProperty;
import oracle.pgx.algorithm.annotations.GraphAlgorithm;
import oracle.pgx.algorithm.PgxEdge;
import oracle.pgx.algorithm.PgxGraph;
import oracle.pgx.algorithm.PgxMap;
import oracle.pgx.algorithm.Scalar;
import oracle.pgx.algorithm.VertexProperty;
import oracle.pgx.algorithm.VertexSet;
import oracle.pgx.algorithm.annotations.Out;

import static java.lang.Math.log;
import static oracle.pgx.algorithm.ControlFlow.exit;
import static oracle.pgx.algorithm.Order.ASCENDING;
import static oracle.pgx.algorithm.Random.uniform;

@GraphAlgorithm
public class Infomap {
  public long weightedInfomap(PgxGraph g, VertexProperty<Double> rank, EdgeProperty<Double> weight, double tau,
      double tol, int maxIter, @Out VertexProperty<Long> module) {
    VertexProperty<Double> exitPr = VertexProperty.create();
    EdgeProperty<Double> normWeight = EdgeProperty.create();

    //initialize modules (each vertex is a module)
    PgxMap<Long, Long> emptyMod = PgxMap.create();
    PgxMap<Long, Long> modSize = PgxMap.create();
    PgxMap<Long, Double> modRank = PgxMap.create();
    PgxMap<Long, Double> qi = PgxMap.create();

    double sigmaQi = 0;
    double codeLength = 0;
    double codeDiff = 0;

    PgxMap<Integer, Double> initMap = PgxMap.create();
    initialization(g, tau, rank, weight, module, exitPr, normWeight, modSize, modRank, qi, initMap);
    sigmaQi = initMap.get(0);
    codeLength = initMap.get(1);

    //outer loop
    int outCnt = 0;
    boolean converged;
    long totalSum = 0;
    long totalPre = 0;
    do {

      double oldCodeLength = codeLength + codeDiff;
      converged = false;

      //fine-grain loop
      PgxMap<Long, Double> auxMap = PgxMap.create();
      fineGrainLoop(g, maxIter, tau, sigmaQi, codeDiff, codeLength, rank, normWeight, module, exitPr, emptyMod, modSize,
          modRank, qi, auxMap);
      sigmaQi = auxMap.get(0L);
      codeDiff = auxMap.get(1L);

      //coarse-grain loop
      auxMap.clear();
      coarseGrainLoop(g, maxIter, tau, sigmaQi, codeDiff, codeLength, rank, normWeight, module, exitPr, emptyMod,
          modSize, modRank, qi, auxMap);
      sigmaQi = auxMap.get(0L);
      codeDiff = auxMap.get(1L);

      if (oldCodeLength - (codeLength + codeDiff) < tol) {
        converged = true;
      }

      outCnt++;
    } while (outCnt < maxIter && !converged);

    relabelingModules(g, module);

    return modSize.size();
  }

  long getKey(PgxMap<Long, Long> emptyMod) {
    emptyMod.keys().forSequential(ControlFlow::exit);

    return -1;
  }

  double plogp(double p) {
    if (p > 0) {
      return p * log(p);
    } else {
      return 0.0;
    }
  }

  void relabelingModules(PgxGraph g, @Out VertexProperty<Long> module) {
    Scalar<Long> l = Scalar.create(-1L);
    Scalar<Long> k = Scalar.create(-1L);

    g.getVertices().orderBy(module::get, ASCENDING).forSequential(nd -> {
      if (k.get() < module.get(nd)) {
        l.increment();
      }
      if (module.get(nd) >= l.get()) {
        k.set(module.get(nd));
        module.set(nd, l.get());
      }
    });
  }

  void compareNbrModules(PgxGraph g, long oldModule, double tau, double sigmaQi, double locRank, double locExitPr,
      double ndTpWeight, PgxMap<Long, Double> qi, PgxMap<Long, Double> modRank, PgxMap<Long, Long> modSize,
      @Out PgxMap<Long, Double> outFlowToMod, @Out PgxMap<Long, Double> inFlowFromMod,
      @Out PgxMap<Integer, Double> mapOfBests, @Out PgxMap<Long, Long> emptyMod) {

    double oldExitPr1 = qi.get(oldModule);
    double oldSumPr1 = modRank.get(oldModule);
    double oldModTpWeight = modSize.get(oldModule) * 1.0 / g.getNumVertices();

    double additionalTeleportOutFlow = tau * locRank * (oldModTpWeight - ndTpWeight);
    double additionalTeleportInFlow = tau * (oldSumPr1 - locRank) * ndTpWeight;

    outFlowToMod.keys().forSequential(newModule -> {
      if (newModule == oldModule) {
        outFlowToMod.reduceAdd(newModule, additionalTeleportOutFlow);
        inFlowFromMod.reduceAdd(newModule, additionalTeleportInFlow);
      } else {
        outFlowToMod.reduceAdd(newModule, tau * locRank * modSize.get(newModule) / g.getNumVertices());
        inFlowFromMod.reduceAdd(newModule, tau * modRank.get(newModule) * ndTpWeight);
      }
    });

    double outFlowToOldMod = additionalTeleportOutFlow;
    double inFlowFromOldMod = additionalTeleportInFlow;

    if (outFlowToMod.containsKey(oldModule)) {
      outFlowToOldMod = outFlowToMod.get(oldModule);
      inFlowFromOldMod = inFlowFromMod.get(oldModule);
    }

    if (modRank.get(oldModule) > locRank && emptyMod.size() > 0) {
      long emptyTag = getKey(emptyMod);
      outFlowToMod.set(emptyTag, 0d);
      inFlowFromMod.set(emptyTag, 0d);
    }

    double newExitPr1 = oldExitPr1 - locExitPr + outFlowToOldMod + inFlowFromOldMod;

    Scalar<Double> bestDiffCodeLen = Scalar.create(0d);

    Scalar<Double> currentDiffCodeLen = Scalar.create(0d);
    Scalar<Long> currentNewModule = Scalar.create(0L);
    Scalar<Double> currentRankOldModule = Scalar.create(0d);
    Scalar<Double> currentRankNewModule = Scalar.create(0d);
    Scalar<Double> currentExitPrOldModule = Scalar.create(0d);
    Scalar<Double> currentExitPrNewModule = Scalar.create(0d);
    Scalar<Double> currentNewSigmaQI = Scalar.create(0d);

    outFlowToMod.keys().forSequential(newModule -> {
      double outFlowToNewMod = outFlowToMod.get(newModule);
      double inFlowFromNewMod = inFlowFromMod.get(newModule);

      if (oldModule != newModule) {
        double oldExitPr2 = qi.get(newModule);
        double oldSumPr2 = modRank.get(newModule);

        currentNewModule.set(newModule);
        currentRankOldModule.set(oldSumPr1 - locRank);
        currentRankNewModule.set(oldSumPr2 + locRank);
        currentExitPrOldModule.set(newExitPr1);
        currentExitPrNewModule.set(oldExitPr2 + locExitPr - outFlowToNewMod - inFlowFromNewMod);
        currentNewSigmaQI.set(sigmaQi + newExitPr1 + currentExitPrNewModule.get() - oldExitPr1 - oldExitPr2);

        double plogpOld = plogp(sigmaQi);
        double plogpNew = plogp(currentNewSigmaQI.get());
        double plogpExitOld = plogp(oldExitPr1) + plogp(oldExitPr2);
        double plogpExitNew = plogp(currentExitPrOldModule.get()) + plogp(currentExitPrNewModule.get());
        double plogpStayOld = plogp(oldExitPr1 + oldSumPr1) + plogp(oldExitPr2 + oldSumPr2);
        double plogpStayNew = plogp(currentExitPrOldModule.get() + currentRankOldModule.get()) + plogp(
            currentExitPrNewModule.get() + currentRankNewModule.get());

        double deltaAllExitLogAllExit = plogpNew - plogpOld;
        double deltaExitLogExit = plogpExitNew - plogpExitOld;
        double deltaStayLogStay = plogpStayNew - plogpStayOld;

        currentDiffCodeLen.set(deltaAllExitLogAllExit - 2 * deltaExitLogExit + deltaStayLogStay);

        if (currentDiffCodeLen.get() < bestDiffCodeLen.get()) {
          bestDiffCodeLen.set(currentDiffCodeLen.get());
          mapOfBests.set(0, currentDiffCodeLen.get());
          mapOfBests.set(1, (double) currentNewModule.get());
          mapOfBests.set(2, currentRankOldModule.get());
          mapOfBests.set(3, currentRankNewModule.get());
          mapOfBests.set(4, currentExitPrOldModule.get());
          mapOfBests.set(5, currentExitPrNewModule.get());
          mapOfBests.set(6, currentNewSigmaQI.get());
        }
      }
    });
  }

  void initialization(PgxGraph g, double tau, VertexProperty<Double> rank, @Out EdgeProperty<Double> weight,
      @Out VertexProperty<Long> module, @Out VertexProperty<Double> exitPr, @Out EdgeProperty<Double> normWeight,
      @Out PgxMap<Long, Long> modSize, @Out PgxMap<Long, Double> modRank, @Out PgxMap<Long, Double> qi,
      @Out PgxMap<Integer, Double> initMap) {
    double aux1 = 0;
    Scalar<Double> aux2 = Scalar.create(0d);
    Scalar<Double> aux3 = Scalar.create(0d);
    Scalar<Double> aux4 = Scalar.create(0d);
    Scalar<Double> sigmaQI = Scalar.create(0d);
    Scalar<Long> l = Scalar.create(0L);

    //assuming equal tp weights (1/N):
    double initTpWeight = (g.getNumVertices() - 1) / (double) g.getNumVertices();

    g.getVertices().forSequential(n -> {
      module.set(n, l.get());
      double sumWeight = n.getOutEdges().sum(weight);

      n.getOutNeighbors().forSequential(nNbr -> {
        PgxEdge e = nNbr.edge();

        normWeight.set(e, (1 - tau) * rank.get(n) * weight.get(e) / sumWeight);
      });

      double tmpQI = (tau * initTpWeight * rank.get(n)) + ((1 - tau) * rank.get(n));
      qi.set(l.get(), tmpQI);
      exitPr.set(n, tmpQI);
      modRank.set(l.get(), rank.get(n));
      modSize.set(l.get(), 1L);

      sigmaQI.reduceAdd(tmpQI);
      aux2.reduceAdd(plogp(tmpQI));
      aux3.reduceAdd(plogp(tmpQI + rank.get(n)));
      aux4.reduceAdd(plogp(rank.get(n)));

      l.increment();
    });

    aux1 = plogp(sigmaQI.get());
    initMap.set(0, sigmaQI.get());
    initMap.set(1, (aux1 - 2 * aux2.get() + aux3.get() - aux4.get()) / log(2.0));
  }

  void fineGrainLoop(PgxGraph g, int maxIter, double tau, double sigmaQI, double codeDiff, double codeLength,
      VertexProperty<Double> rank, EdgeProperty<Double> normWeight, @Out VertexProperty<Long> module,
      @Out VertexProperty<Double> exitPr, @Out PgxMap<Long, Long> emptyMod, @Out PgxMap<Long, Long> modSize,
      @Out PgxMap<Long, Double> modRank, @Out PgxMap<Long, Double> qi, @Out PgxMap<Long, Double> auxMap) {

    Scalar<Long> moved = Scalar.create(0L);
    int cnt = 0;
    auxMap.set(0L, sigmaQI);
    auxMap.set(1L, codeDiff);

    do {

      moved.set(0L);
      Scalar<Long> oldModule = Scalar.create(0L);

      g.getVertices().orderBy(nd -> uniform(), ASCENDING).forSequential(nd -> {
        oldModule.set(module.get(nd));

        double localSigmaQI = auxMap.get(0L);
        PgxMap<Long, Double> outFlowToMod = PgxMap.create();
        PgxMap<Long, Double> inFlowFromMod = PgxMap.create();

        nd.getOutNeighbors().forSequential(ndNbr -> {
          PgxEdge e = ndNbr.edge();
          outFlowToMod.reduceAdd(module.get(ndNbr), normWeight.get(e));
        });

        nd.getInNeighbors().forSequential(ndNbr -> {
          PgxEdge e = ndNbr.edge();
          inFlowFromMod.reduceAdd(module.get(ndNbr), normWeight.get(e));
        });

        PgxMap<Integer, Double> mapOfBests = PgxMap.create();
        double locRank = rank.get(nd);
        double locExitPr = exitPr.get(nd);
        double ndTpWeight = 1.0 / g.getNumVertices();

        compareNbrModules(g, oldModule.get(), tau, localSigmaQI, locRank, locExitPr, ndTpWeight, qi, modRank, modSize,
            outFlowToMod, inFlowFromMod, mapOfBests, emptyMod);

        double bestDiffCodeLen = mapOfBests.get(0);
        long bestNewModule = (long) (double) mapOfBests.get(1);
        double bestRankOldModule = mapOfBests.get(2);
        double bestRankNewModule = mapOfBests.get(3);
        double bestExitPrOldModule = mapOfBests.get(4);
        double bestExitPrNewModule = mapOfBests.get(5);
        double bestNewSigmaQI = mapOfBests.get(6);

        if (bestDiffCodeLen < 0) {

          if (emptyMod.containsKey(bestNewModule)) {
            emptyMod.remove(bestNewModule);
          }

          module.set(nd, bestNewModule);
          modSize.increment(bestNewModule);
          qi.set(bestNewModule, bestExitPrNewModule);
          modRank.set(bestNewModule, bestRankNewModule);

          modSize.decrement(oldModule.get());
          qi.set(oldModule.get(), bestExitPrOldModule);
          modRank.set(oldModule.get(), bestRankOldModule);
          if (modSize.get(oldModule.get()) < 1) {
            modSize.remove(oldModule.get());
            modRank.remove(oldModule.get());
            qi.remove(oldModule.get());
            emptyMod.set(oldModule.get(), oldModule.get());
          }
          moved.increment();
          auxMap.set(0L, bestNewSigmaQI);
          auxMap.reduceAdd(1L, bestDiffCodeLen / log(2.0));
        }
      });
      cnt++;
    } while (cnt < maxIter && moved.get() > 0);
  }

  void coarseGrainLoop(PgxGraph g, int maxIter, double tau, double sigmaQI, double codeDiff, double codeLength,
      VertexProperty<Double> rank, EdgeProperty<Double> normWeight, @Out VertexProperty<Long> module,
      @Out VertexProperty<Double> exitPr, @Out PgxMap<Long, Long> emptyMod, @Out PgxMap<Long, Long> modSize,
      @Out PgxMap<Long, Double> modRank, @Out PgxMap<Long, Double> qi, @Out PgxMap<Long, Double> auxMap) {

    // creating super-vertices and super-edges
    PgxMap<Long, VertexSet> snodes = PgxMap.create();
    PgxMap<Long, VertexSet> superNbrs = PgxMap.create();
    PgxMap<Long, VertexSet> inSuperNbrs = PgxMap.create();
    PgxMap<Long, Double> allSuperEdges = PgxMap.create();

    VertexProperty<Long> snode = VertexProperty.create();
    PgxMap<Long, Long> snodeMod = PgxMap.create();
    PgxMap<Long, Double> snodeRank = PgxMap.create();
    PgxMap<Long, Double> snodeExitPr = PgxMap.create();

    Scalar<Integer> cntE = Scalar.create(1);
    g.getVertices().forSequential(n -> {
      snodes.get(module.get(n)).add(n);
      snodeMod.set(module.get(n), module.get(n));
      snodeRank.reduceAdd(module.get(n), rank.get(n));
      snodeExitPr.set(module.get(n), qi.get(module.get(n)));
      snode.set(n, module.get(n));
      n.getOutNeighbors().forSequential(nNbr -> {
        PgxEdge e = nNbr.edge();
        if (module.get(n) != module.get(nNbr)) {
          long idx = (g.getNumVertices() * module.get(n)) + module.get(nNbr);

          if (!allSuperEdges.containsKey(idx)) {
            superNbrs.get(module.get(n)).add(nNbr);
            inSuperNbrs.get(module.get(nNbr)).add(n);
          }
          allSuperEdges.reduceAdd(idx, normWeight.get(e));
          cntE.increment();
        }
      });
    });

    Scalar<Long> moved = Scalar.create(0L);
    int coarseCnt = 0;

    auxMap.set(0L, sigmaQI);
    auxMap.set(1L, codeDiff);

    do {
      moved.set(0L);
      long outSum = 0;
      long preOut = 0;

      snodes.keys().forSequential(sndID -> {
        long oldModule = snodeMod.get(sndID);
        VertexSet tmp = snodes.get(sndID).clone();
        double localSigmaQI = auxMap.get(0L);

        PgxMap<Long, Double> superOutFlowToMod = PgxMap.create();
        PgxMap<Long, Double> superInFlowFromMod = PgxMap.create();

        VertexSet outSn = superNbrs.get(sndID).clone();
        VertexSet inSn = inSuperNbrs.get(sndID).clone();

        outSn.forSequential(sn -> superOutFlowToMod
            .reduceAdd(module.get(sn), allSuperEdges.get((g.getNumVertices() * sndID) + snode.get(sn))));

        inSn.forSequential(sn -> superInFlowFromMod
            .reduceAdd(module.get(sn), allSuperEdges.get((g.getNumVertices() * snode.get(sn)) + sndID)));

        PgxMap<Integer, Double> mapOfBests = PgxMap.create();
        double locRank = snodeRank.get(sndID);
        double locExitPr = snodeExitPr.get(sndID);
        double ndTpWeight = tmp.size() / (double) g.getNumVertices();

        compareNbrModules(g, oldModule, tau, localSigmaQI, locRank, locExitPr, ndTpWeight, qi, modRank, modSize,
            superOutFlowToMod, superInFlowFromMod, mapOfBests, emptyMod);

        double bestDiffCodeLen = mapOfBests.get(0);
        long bestNewModule = (long) (double) mapOfBests.get(1);
        double bestRankOldModule = mapOfBests.get(2);
        double bestRankNewModule = mapOfBests.get(3);
        double bestExitPrOldModule = mapOfBests.get(4);
        double bestExitPrNewModule = mapOfBests.get(5);
        double bestNewSigmaQI = mapOfBests.get(6);

        if (bestDiffCodeLen < 0) {

          if (emptyMod.containsKey(bestNewModule)) {
            emptyMod.remove(bestNewModule);
          }

          tmp.forSequential(n -> module.set(n, bestNewModule));

          moved.reduceAdd((long) tmp.size());

          modSize.set(bestNewModule, modSize.get(bestNewModule) + tmp.size());
          qi.set(bestNewModule, bestExitPrNewModule);
          modRank.set(bestNewModule, bestRankNewModule);
          snodeMod.set(sndID, bestNewModule);

          modSize.set(oldModule, modSize.get(oldModule) - tmp.size());
          qi.set(oldModule, bestExitPrOldModule);
          modRank.set(oldModule, bestRankOldModule);
          if (modSize.get(oldModule) < 1) {
            modSize.remove(oldModule);
            modRank.remove(oldModule);
            qi.remove(oldModule);
            emptyMod.set(oldModule, oldModule);
          }

          auxMap.set(0L, bestNewSigmaQI);
          auxMap.reduceAdd(1L, bestDiffCodeLen / log(2.0));
        }
      });
      coarseCnt++;
    } while (coarseCnt < maxIter && moved.get() > 0);
  }
}

/*
 * Copyright (C) 2013 - 2020 Oracle and/or its affiliates. All rights reserved.
 */

procedure weighted_infomap(graph G, nodeProp<double> rank, edgeProp<double> weight, double tau,
    double tol, int max_iter; nodeProp<long> module) : long {

  nodeProp<double> exit_pr;
  edgeProp<double> norm_weight;

  //initialize modules (each vertex is a module)
  map<long, long> empty_mod;
  map<long, long> mod_size;
  map<long, double> mod_rank;
  map<long, double> q_i;

  double sigma_q_i = 0;
  double code_length = 0;
  double code_diff = 0;

  map<int, double> init_map;
  initialization(G, tau, rank, weight, module, exit_pr, norm_weight, mod_size, mod_rank, q_i, init_map);
  sigma_q_i = init_map[0];
  code_length = init_map[1];

  //outer loop
  int out_cnt = 0;
  bool converged;
  long total_sum = 0;
  long total_pre = 0;
  do {

    double old_code_length = code_length + code_diff;
    converged = false;

    //fine-grain loop
    map<long, double> aux_map;
    fine_grain_loop(G, max_iter, tau, sigma_q_i, code_diff, code_length, rank, norm_weight, module, exit_pr, empty_mod,
        mod_size, mod_rank, q_i, aux_map);
    sigma_q_i = aux_map[0];
    code_diff = aux_map[1];

    //coarse-grain loop
    aux_map.clear();
    coarse_grain_loop(G, max_iter, tau, sigma_q_i, code_diff, code_length, rank, norm_weight, module, exit_pr, empty_mod,
        mod_size, mod_rank, q_i, aux_map);
    sigma_q_i = aux_map[0];
    code_diff = aux_map[1];

    if (old_code_length - (code_length+code_diff) < tol) {
      converged = true;
    }

    out_cnt++;
  } while (out_cnt < max_iter && !converged);

  relabeling_modules(G, module);

  return mod_size.size();
}

local get_key(map<long, long> empty_mod) : long {
  for (key: empty_mod.keys) {
    return key;
  }
  return -1;
}

local plogp(double p) : double {
  if (p > 0) {
    return p * log(p);
  } else {
    return 0.0;
  }
}

local relabeling_modules(graph G; nodeProp<long> module) {
  long l = -1;
  long k = -1;
  for (nd: G.nodes order by nd.module) {
    if (k < nd.module) {
      l++;
    }
    if (nd.module >= l) {
      k = nd.module;
      nd.module = l;
    }
  }
}

local compare_nbr_modules(graph G, long old_module, double tau, double sigma_q_i, double loc_rank, double loc_exit_pr,
    double nd_tp_weight, map<long, double> q_i, map<long, double> mod_rank, map<long, long> mod_size;
    map<long, double> out_flow_to_mod, map<long, double> in_flow_from_mod, map<int, double> map_of_bests,
    map<long, long> empty_mod) {

  double old_exit_pr1 = q_i[old_module];
  double old_sum_pr1 = mod_rank[old_module];
  double old_mod_tp_weight = mod_size[old_module] * 1.0 / G.numNodes();

  double additional_teleport_out_flow = tau * loc_rank * (old_mod_tp_weight - nd_tp_weight);
  double additional_teleport_in_flow = tau * (old_sum_pr1 - loc_rank) * nd_tp_weight;

  for (new_module: out_flow_to_mod.keys) {
    if (new_module == old_module) {
      out_flow_to_mod[new_module] += additional_teleport_out_flow;
      in_flow_from_mod[new_module] += additional_teleport_in_flow;
    } else {
      out_flow_to_mod[new_module] += tau * loc_rank * mod_size[new_module] / G.numNodes();
      in_flow_from_mod[new_module] += tau * mod_rank[new_module] * nd_tp_weight;
    }
  }

  double out_flow_to_old_mod = additional_teleport_out_flow;
  double in_flow_from_old_mod = additional_teleport_in_flow;

  if (out_flow_to_mod.hasKey(old_module)) {
    out_flow_to_old_mod = out_flow_to_mod[old_module];
    in_flow_from_old_mod = in_flow_from_mod[old_module];
  }

  if (mod_rank[old_module] > loc_rank && empty_mod.size() > 0) {
    long empty_tag = get_key(empty_mod);
    out_flow_to_mod[empty_tag] = 0;
    in_flow_from_mod[empty_tag] = 0;
  }

  double new_exit_pr1 = old_exit_pr1 - loc_exit_pr + out_flow_to_old_mod + in_flow_from_old_mod;

  double best_diff_code_len = 0;

  double current_diff_code_len = 0;
  long current_new_module = 0;
  double current_rank_old_module = 0;
  double current_rank_new_module = 0;
  double current_exit_pr_old_module = 0;
  double current_exit_pr_new_module = 0;
  double current_new_sigma_q_i = 0;

  for (new_module: out_flow_to_mod.keys) {

    double out_flow_to_new_mod = out_flow_to_mod[new_module];
    double in_flow_from_new_mod = in_flow_from_mod[new_module];

    if (old_module != new_module) {

      double old_exit_pr2 = q_i[new_module];
      double old_sum_pr2 = mod_rank[new_module];

      current_new_module = new_module;
      current_rank_old_module = old_sum_pr1 - loc_rank;
      current_rank_new_module = old_sum_pr2 + loc_rank;
      current_exit_pr_old_module = new_exit_pr1;
      current_exit_pr_new_module = old_exit_pr2 + loc_exit_pr - out_flow_to_new_mod - in_flow_from_new_mod;
      current_new_sigma_q_i = sigma_q_i + new_exit_pr1 + current_exit_pr_new_module - old_exit_pr1 - old_exit_pr2;

      double plogp_old = plogp(sigma_q_i);
      double plogp_new = plogp(current_new_sigma_q_i);
      double plogp_exit_old = plogp(old_exit_pr1) + plogp(old_exit_pr2);
      double plogp_exit_new = plogp(current_exit_pr_old_module) + plogp(current_exit_pr_new_module);
      double plogp_stay_old = plogp(old_exit_pr1 + old_sum_pr1) + plogp(old_exit_pr2 + old_sum_pr2);
      double plogp_stay_new = plogp(current_exit_pr_old_module + current_rank_old_module) +
          plogp(current_exit_pr_new_module + current_rank_new_module);

      double delta_all_exit_log_all_exit = plogp_new - plogp_old;
      double delta_exit_log_exit = plogp_exit_new - plogp_exit_old;
      double delta_stay_log_stay = plogp_stay_new - plogp_stay_old;

      current_diff_code_len = delta_all_exit_log_all_exit - 2 * delta_exit_log_exit + delta_stay_log_stay;

      if (current_diff_code_len < best_diff_code_len) {
        best_diff_code_len = current_diff_code_len;
        map_of_bests[0] = current_diff_code_len;
        map_of_bests[1] = current_new_module;
        map_of_bests[2] = current_rank_old_module;
        map_of_bests[3] = current_rank_new_module;
        map_of_bests[4] = current_exit_pr_old_module;
        map_of_bests[5] = current_exit_pr_new_module;
        map_of_bests[6] = current_new_sigma_q_i;
      }
    }
  }
}

local initialization(graph G, double tau, nodeProp<double> rank; edgeProp<double> weight, nodeProp<long> module,
    nodeProp<double> exit_pr, edgeProp<double> norm_weight, map<long, long> mod_size, map<long, double> mod_rank,
    map<long, double> q_i, map<int, double> init_map) {

  double aux1 = 0;
  double aux2 = 0;
  double aux3 = 0;
  double aux4 = 0;
  double sigma_q_i = 0;
  long l = 0;

  //assuming equal tp weights (1/N):
  double init_tp_weight = (G.numNodes() - 1) / (double) G.numNodes();

  for (n: G.nodes) {

    n.module = l;
    double sum_weight = sum (out: n.outEdges) { out.weight };

    for (n_nbr: n.nbrs) {
      edge e = n_nbr.edge();
      e.norm_weight = (1 - tau) * n.rank * e.weight / sum_weight;
    }

    double tmp_q_i = (tau * init_tp_weight * n.rank) + ((1 - tau) * n.rank);
    q_i[l] = tmp_q_i;
    n.exit_pr = tmp_q_i;
    mod_rank[l] = n.rank;
    mod_size[l] = 1;

    sigma_q_i += tmp_q_i;
    aux2 += plogp(tmp_q_i);
    aux3 += plogp(tmp_q_i + n.rank);
    aux4 += plogp(n.rank);

    l++;
  }

  aux1 = plogp(sigma_q_i);
  init_map[0] = sigma_q_i;
  init_map[1] = (aux1 - 2 * aux2 + aux3 - aux4) / log(2.0);
}

local fine_grain_loop(graph G, int max_iter, double tau, double sigma_q_i, double code_diff, double code_length,
    nodeProp<double> rank, edgeProp<double> norm_weight; nodeProp<long> module, nodeProp<double> exit_pr,
    map<long, long> empty_mod, map<long, long> mod_size, map<long, double> mod_rank, map<long, double> q_i,
    map<long, double> aux_map) {

  long moved = 0;
  int cnt = 0;
  aux_map[0] = sigma_q_i;
  aux_map[1] = code_diff;

  do {

    moved = 0;
    long old_module = 0;

    for (nd: G.nodes order by uniform()) {
      old_module = nd.module;

      double local_sigma_q_i = aux_map[0];
      map<long, double> out_flow_to_mod;
      map<long, double> in_flow_from_mod;

      for (nd_nbr: nd.nbrs) {
        edge e = nd_nbr.edge();
        out_flow_to_mod[nd_nbr.module] += e.norm_weight;
      }

      for (nd_nbr: nd.inNbrs) {
        edge e = nd_nbr.edge();
        in_flow_from_mod[nd_nbr.module] += e.norm_weight;
      }

      map<int, double> map_of_bests;
      double loc_rank = nd.rank;
      double loc_exit_pr = nd.exit_pr;
      double nd_tp_weight = 1.0 / G.numNodes();

      compare_nbr_modules(G, old_module, tau, local_sigma_q_i, loc_rank, loc_exit_pr, nd_tp_weight,
          q_i, mod_rank, mod_size, out_flow_to_mod, in_flow_from_mod, map_of_bests, empty_mod);

      double best_diff_code_len = map_of_bests[0];
      long best_new_module = (long) map_of_bests[1];
      double best_rank_old_module = map_of_bests[2];
      double best_rank_new_module = map_of_bests[3];
      double best_exit_pr_old_module = map_of_bests[4];
      double best_exit_pr_new_module = map_of_bests[5];
      double best_new_sigma_q_i = map_of_bests[6];

      if (best_diff_code_len < 0) {

        if (empty_mod.hasKey(best_new_module)) {
          empty_mod.remove(best_new_module);
        }

        nd.module = best_new_module;
        mod_size[best_new_module]++;
        q_i[best_new_module] = best_exit_pr_new_module;
        mod_rank[best_new_module] = best_rank_new_module;

        mod_size[old_module]--;
        q_i[old_module] = best_exit_pr_old_module;
        mod_rank[old_module] = best_rank_old_module;
        if (mod_size[old_module] < 1) {
          mod_size.remove(old_module);
          mod_rank.remove(old_module);
          q_i.remove(old_module);
          empty_mod[old_module] = old_module;
        }
        moved++;
        aux_map[0] = best_new_sigma_q_i;
        aux_map[1] += best_diff_code_len/log(2.0);

      }
    }
    cnt++;
  } while (cnt < max_iter && moved > 0);
}

local coarse_grain_loop(graph G, int max_iter, double tau, double sigma_q_i, double code_diff, double code_length,
    nodeProp<double> rank, edgeProp<double> norm_weight; nodeProp<long> module, nodeProp<double> exit_pr,
    map<long, long> empty_mod, map<long, long> mod_size, map<long, double> mod_rank, map<long, double> q_i,
    map<long, double> aux_map) {

  // creating super-vertices and super-edges
  map<long, nodeSet> snodes;
  map<long, nodeSet> super_nbrs;
  map<long, nodeSet> in_super_nbrs;
  map<long, double> all_super_edges;

  nodeProp<long> snode;
  map<long, long> snode_mod;
  map<long, double> snode_rank;
  map<long, double> snode_exit_pr;

  int cnt_e = 1;
  for (n: G.nodes) {
    snodes[n.module].add(n);
    snode_mod[n.module] = n.module;
    snode_rank[n.module] += n.rank;
    snode_exit_pr[n.module] = q_i[n.module];
    n.snode = n.module;
    for (n_nbr: n.nbrs) {
      edge e = n_nbr.edge();
      if (n.module != n_nbr.module) {

        long idx = (G.numNodes() * n.module) + n_nbr.module;

        if (!all_super_edges.hasKey(idx)) {
          super_nbrs[n.module].add(n_nbr);
          in_super_nbrs[n_nbr.module].add(n);
        }
        all_super_edges[idx] += e.norm_weight;
        cnt_e++;
      }
    }
  }

  long moved = 0;
  int coarse_cnt = 0;

  aux_map[0] = sigma_q_i;
  aux_map[1] = code_diff;

  do {

    moved = 0;
    long out_sum = 0;
    long pre_out = 0;

    for (sndID: snodes.keys) {

      long old_module = snode_mod[sndID];
      nodeSet tmp = snodes[sndID];
      double local_sigma_q_i = aux_map[0];

      map<long, double> super_out_flow_to_mod;
      map<long, double> super_in_flow_from_mod;

      nodeSet out_sn = super_nbrs[sndID];
      nodeSet in_sn = in_super_nbrs[sndID];

      for (sn: out_sn.items) {
        super_out_flow_to_mod[sn.module] += all_super_edges[(G.numNodes() * sndID) + sn.snode];
      }
      for (sn: in_sn.items) {
        super_in_flow_from_mod[sn.module] += all_super_edges[(G.numNodes() * sn.snode) + sndID];
      }

      map<int, double> map_of_bests;
      double loc_rank = snode_rank[sndID];
      double loc_exit_pr = snode_exit_pr[sndID];
      double nd_tp_weight = tmp.size() / (double) G.numNodes();

      compare_nbr_modules(G, old_module, tau, local_sigma_q_i, loc_rank, loc_exit_pr, nd_tp_weight,
          q_i, mod_rank, mod_size, super_out_flow_to_mod, super_in_flow_from_mod, map_of_bests, empty_mod);

      double best_diff_code_len = map_of_bests[0];
      long best_new_module = (long) map_of_bests[1];
      double best_rank_old_module = map_of_bests[2];
      double best_rank_new_module = map_of_bests[3];
      double best_exit_pr_old_module = map_of_bests[4];
      double best_exit_pr_new_module = map_of_bests[5];
      double best_new_sigma_q_i = map_of_bests[6];

      if (best_diff_code_len < 0) {

        if (empty_mod.hasKey(best_new_module)) {
          empty_mod.remove(best_new_module);
        }

        for (n: tmp.items) {
          n.module = best_new_module;
        }

        moved += tmp.size();

        mod_size[best_new_module] = mod_size[best_new_module] + tmp.size();
        q_i[best_new_module] = best_exit_pr_new_module;
        mod_rank[best_new_module] = best_rank_new_module;
        snode_mod[sndID] = best_new_module;

        mod_size[old_module] = mod_size[old_module] - tmp.size();
        q_i[old_module] = best_exit_pr_old_module;
        mod_rank[old_module] = best_rank_old_module;
        if (mod_size[old_module] < 1) {
          mod_size.remove(old_module);
          mod_rank.remove(old_module);
          q_i.remove(old_module);
          empty_mod[old_module] = old_module;
        }

        aux_map[0] = best_new_sigma_q_i;
        aux_map[1] += best_diff_code_len/log(2.0);
      }
    }
    coarse_cnt++;
  } while (coarse_cnt < max_iter && moved > 0);
}