Addressing disconnected communities for edge deletions

[wolfram77]

Think of edge deletions within a community. These may cause a community to be internally-disconnected. Accordingly, we should mark the community to be refined.

But the issue I am currently facing is not related to this ...

[wolfram77]

I have pinpointed the error to the partial resetting of communities (to sub-communities) before the refinement phase. Simply resetting all communities makes this error go away, but doing a selecting resetting causes the disconnected communities issue --- a large number of disconnected communities are created.

I was assuming this issue might be due to out-of-community IDs, i.e., none of the vertices in the community have the same ID as the community ID. This might happen if a vertex leaves its community during the local-moving phase. But it appears this is not the issue.

[wolfram77]

So, here are the details.

• Simply forcing all the vertices to refine eliminated the issue.

Below is output dump from a small graph.

2024-06-19 23:32:12 OMP_NUM_THREADS=64
2024-06-19 23:32:12 Loading graph /home/graphwork/Data/sx-stackoverflow-30.txt ...
2024-06-19 23:32:12 order: 100 size: 43 [directed] {} (90%)
2024-06-19 23:32:12 order: 100 size: 43 [directed] {} (symmetrize)
{-0.000e+00/+0.000e+00 batchf, 064 threads} -> {0000000.8ms, 0000000.0ms mark, 0000000.0ms init, 0000000.4ms firstpass, 0000000.1ms locmove, 0000000.0ms refine, 0000000.3ms aggr, 0.000e+00 aff, 0006 iters, 003 passes, 0.724716063 modularity, 0/83 disconnected} louvainStaticOmpOriginal
{-0.000e+00/+0.000e+00 batchf, 064 threads} -> {0000000.9ms, 0000000.0ms mark, 0000000.0ms init, 0000000.4ms firstpass, 0000000.1ms locmove, 0000000.1ms refine, 0000000.3ms aggr, 0.000e+00 aff, 0006 iters, 003 passes, 0.724716063 modularity, 0/83 disconnected} leidenStaticOmpOriginal
2024-06-19 23:32:12 order: 100 size: 49 [directed] {} (insertions=6)
{-0.000e+00/+1.000e-01 batchf, 064 threads} -> {0000000.9ms, 0000000.0ms mark, 0000000.0ms init, 0000000.4ms firstpass, 0000000.1ms locmove, 0000000.1ms refine, 0000000.3ms aggr, 0.000e+00 aff, 0006 iters, 003 passes, 0.740524781 modularity, 0/80 disconnected} leidenStaticOmp
LM-1: 0 / 83 disconnected communities
LM-1: Community 00 has 01 vertices: 3
LM-1: Community 01 has 01 vertices: 4
LM-1: Community 02 has 01 vertices: 5
LM-1: Community 03 has 01 vertices: 6
LM-1: Community 04 has 01 vertices: 7
LM-1: Community 05 has 01 vertices: 10
LM-1: Community 06 has 01 vertices: 12
LM-1: Community 07 has 04 vertices: 11 13 23 49
LM-1: Community 08 has 01 vertices: 14
LM-1: Community 09 has 01 vertices: 15
LM-1: Community 10 has 01 vertices: 16
LM-1: Community 11 has 01 vertices: 18
LM-1: Community 12 has 01 vertices: 20
LM-1: Community 13 has 01 vertices: 21
LM-1: Community 14 has 01 vertices: 24
LM-1: Community 15 has 01 vertices: 25
LM-1: Community 16 has 01 vertices: 26
LM-1: Community 17 has 01 vertices: 27
LM-1: Community 18 has 01 vertices: 28
LM-1: Community 19 has 01 vertices: 29
LM-1: Community 20 has 01 vertices: 30
LM-1: Community 21 has 01 vertices: 31
LM-1: Community 22 has 01 vertices: 34
LM-1: Community 23 has 01 vertices: 36
LM-1: Community 24 has 01 vertices: 38
LM-1: Community 25 has 06 vertices: 33 35 37 39 40 50
LM-1: Community 26 has 01 vertices: 41
LM-1: Community 27 has 01 vertices: 42
LM-1: Community 28 has 02 vertices: 22 43
LM-1: Community 29 has 01 vertices: 44
LM-1: Community 30 has 01 vertices: 45
LM-1: Community 31 has 01 vertices: 46
LM-1: Community 32 has 01 vertices: 47
LM-1: Community 33 has 03 vertices: 2 48 60
LM-1: Community 34 has 04 vertices: 1 17 32 51
LM-1: Community 35 has 01 vertices: 52
LM-1: Community 36 has 01 vertices: 53
LM-1: Community 37 has 01 vertices: 54
LM-1: Community 38 has 04 vertices: 8 9 19 55
LM-1: Community 39 has 01 vertices: 56
LM-1: Community 40 has 01 vertices: 57
LM-1: Community 41 has 01 vertices: 58
LM-1: Community 42 has 01 vertices: 59
LM-1: Community 43 has 01 vertices: 61
LM-1: Community 44 has 01 vertices: 62
LM-1: Community 45 has 01 vertices: 63
LM-1: Community 46 has 01 vertices: 64
LM-1: Community 47 has 01 vertices: 65
LM-1: Community 48 has 01 vertices: 66
LM-1: Community 49 has 01 vertices: 67
LM-1: Community 50 has 01 vertices: 68
LM-1: Community 51 has 01 vertices: 69
LM-1: Community 52 has 01 vertices: 70
LM-1: Community 53 has 01 vertices: 71
LM-1: Community 54 has 01 vertices: 72
LM-1: Community 55 has 01 vertices: 73
LM-1: Community 56 has 01 vertices: 74
LM-1: Community 57 has 01 vertices: 75
LM-1: Community 58 has 01 vertices: 76
LM-1: Community 59 has 01 vertices: 77
LM-1: Community 60 has 01 vertices: 78
LM-1: Community 61 has 01 vertices: 79
LM-1: Community 62 has 01 vertices: 80
LM-1: Community 63 has 01 vertices: 81
LM-1: Community 64 has 01 vertices: 82
LM-1: Community 65 has 01 vertices: 83
LM-1: Community 66 has 01 vertices: 84
LM-1: Community 67 has 01 vertices: 85
LM-1: Community 68 has 01 vertices: 86
LM-1: Community 69 has 01 vertices: 87
LM-1: Community 70 has 01 vertices: 88
LM-1: Community 71 has 01 vertices: 89
LM-1: Community 72 has 01 vertices: 90
LM-1: Community 73 has 01 vertices: 91
LM-1: Community 74 has 01 vertices: 92
LM-1: Community 75 has 01 vertices: 93
LM-1: Community 76 has 01 vertices: 94
LM-1: Community 77 has 01 vertices: 95
LM-1: Community 78 has 01 vertices: 96
LM-1: Community 79 has 01 vertices: 97
LM-1: Community 80 has 01 vertices: 98
LM-1: Community 81 has 01 vertices: 99
LM-1: Community 82 has 01 vertices: 100
LM-2: 0 / 80 disconnected communities
LM-2: Community 15 has changed
LM-2: Community 25 has changed
LM-2: Community 41 has changed
LM-2: Community 42 has changed
LM-2: Community 43 has changed
LM-2: 5 communities have changed
LM-2: Community 00 has 01 vertices: 3
LM-2: Community 01 has 01 vertices: 4
LM-2: Community 02 has 01 vertices: 5
LM-2: Community 03 has 01 vertices: 6
LM-2: Community 04 has 01 vertices: 7
LM-2: Community 05 has 01 vertices: 10
LM-2: Community 06 has 01 vertices: 12
LM-2: Community 07 has 04 vertices: 11 13 23 49
LM-2: Community 08 has 01 vertices: 14
LM-2: Community 09 has 01 vertices: 15
LM-2: Community 10 has 01 vertices: 16
LM-2: Community 11 has 01 vertices: 18
LM-2: Community 12 has 01 vertices: 20
LM-2: Community 13 has 01 vertices: 21
LM-2: Community 14 has 01 vertices: 24
LM-2: Community 16 has 01 vertices: 26
LM-2: Community 17 has 01 vertices: 27
LM-2: Community 18 has 01 vertices: 28
LM-2: Community 19 has 01 vertices: 29
LM-2: Community 20 has 01 vertices: 30
LM-2: Community 21 has 01 vertices: 31
LM-2: Community 22 has 01 vertices: 34
LM-2: Community 23 has 01 vertices: 36
LM-2: Community 24 has 01 vertices: 38
LM-2: Community 25 has 07 vertices: 33 35 37 39 40 50 59
LM-2: Community 26 has 01 vertices: 41
LM-2: Community 27 has 01 vertices: 42
LM-2: Community 28 has 02 vertices: 22 43
LM-2: Community 29 has 01 vertices: 44
LM-2: Community 30 has 01 vertices: 45
LM-2: Community 31 has 01 vertices: 46
LM-2: Community 32 has 01 vertices: 47
LM-2: Community 33 has 03 vertices: 2 48 60
LM-2: Community 34 has 04 vertices: 1 17 32 51
LM-2: Community 35 has 01 vertices: 52
LM-2: Community 36 has 01 vertices: 53
LM-2: Community 37 has 01 vertices: 54
LM-2: Community 38 has 04 vertices: 8 9 19 55
LM-2: Community 39 has 01 vertices: 56
LM-2: Community 40 has 01 vertices: 57
LM-2: Community 43 has 03 vertices: 25 58 61
LM-2: Community 44 has 01 vertices: 62
LM-2: Community 45 has 01 vertices: 63
LM-2: Community 46 has 01 vertices: 64
LM-2: Community 47 has 01 vertices: 65
LM-2: Community 48 has 01 vertices: 66
LM-2: Community 49 has 01 vertices: 67
LM-2: Community 50 has 01 vertices: 68
LM-2: Community 51 has 01 vertices: 69
LM-2: Community 52 has 01 vertices: 70
LM-2: Community 53 has 01 vertices: 71
LM-2: Community 54 has 01 vertices: 72
LM-2: Community 55 has 01 vertices: 73
LM-2: Community 56 has 01 vertices: 74
LM-2: Community 57 has 01 vertices: 75
LM-2: Community 58 has 01 vertices: 76
LM-2: Community 59 has 01 vertices: 77
LM-2: Community 60 has 01 vertices: 78
LM-2: Community 61 has 01 vertices: 79
LM-2: Community 62 has 01 vertices: 80
LM-2: Community 63 has 01 vertices: 81
LM-2: Community 64 has 01 vertices: 82
LM-2: Community 65 has 01 vertices: 83
LM-2: Community 66 has 01 vertices: 84
LM-2: Community 67 has 01 vertices: 85
LM-2: Community 68 has 01 vertices: 86
LM-2: Community 69 has 01 vertices: 87
LM-2: Community 70 has 01 vertices: 88
LM-2: Community 71 has 01 vertices: 89
LM-2: Community 72 has 01 vertices: 90
LM-2: Community 73 has 01 vertices: 91
LM-2: Community 74 has 01 vertices: 92
LM-2: Community 75 has 01 vertices: 93
LM-2: Community 76 has 01 vertices: 94
LM-2: Community 77 has 01 vertices: 95
LM-2: Community 78 has 01 vertices: 96
LM-2: Community 79 has 01 vertices: 97
LM-2: Community 80 has 01 vertices: 98
LM-2: Community 81 has 01 vertices: 99
LM-2: Community 82 has 01 vertices: 100
RE-2: 1 / 80 disconnected communities [at u=25, d=43]
RE-2: 2 / 80 disconnected communities [at u=33, d=25]
RE-2: 3 / 80 disconnected communities [at u=35, d=25]
RE-2: 4 / 80 disconnected communities [at u=37, d=25]
RE-2: 5 / 80 disconnected communities [at u=39, d=25]
RE-2: 6 / 80 disconnected communities [at u=40, d=25]
RE-2: 7 / 80 disconnected communities [at u=50, d=25]
RE-2: 8 / 80 disconnected communities [at u=58, d=43]
RE-2: 8 / 80 disconnected communities [at u=59, d=25]
RE-2: 9 / 79 disconnected communities [at u=61, d=43]
RE-1: 9 / 79 disconnected communities
{-0.000e+00/+1.000e-01 batchf, 064 threads} -> {0000003.6ms, 0000000.0ms mark, 0000000.0ms init, 0000003.1ms firstpass, 0000000.1ms locmove, 0000000.4ms refine, 0000000.3ms aggr, 0.000e+00 aff, 0005 iters, 003 passes, 0.740524781 modularity, 2/76 disconnected} leidenNaiveDynamicOmp

[wolfram77]

handle disconnected communities

• Obtain any vertex from each community (no atomic ops needed).
• Rename communities based on the ID of any vertex within each community.
• Initialize a subset of communities such that each vertex is its own community (as usual).

template <bool DYNAMIC=false, bool SUBREFINE=false, bool RANDOM=false, bool USEPARENT=false, class FLAG=char, int CHUNK_SIZE=2048, class RND, class G, class FI, class FM, class FA>
...

...
auto fr = [&](auto u) { return SUBREFINE? cchg[vcob[u]] : B(1); };
if (SUBREFINE && isFirst) {
  swap(ctot, dtot); swap(vcob, ucom);
  leidenSubsetRenameCommunitiesW(ucom, ctot, bufc, x, vcob, dtot);
}

[wolfram77]

fix tracking of changed communities

This resulted in some disconnected communities.

// @param cchg communities that have changed (output)
// @param dchg old communities that have changed
template <class G, class K, class W, class B>
inline void leidenSubsetRenameCommunitiesW(vector<K>& vcom, vector<W>& ctot, vector<B>& cchg, vector<K>& cvtx, const G& x, const vector<K>& vdom, const vector<W>& dtot, const vector<B>& dchg) {
// ...

if (SUBREFINE && isFirst) {
  swap(ctot, dtot); swap(vcob, ucom); swap(vaff, cchg);
  leidenSubsetRenameCommunitiesOmpW(ucom, ctot, cchg, bufc, x, vcob, dtot, vaff);
}

[wolfram77]

handle data race while changing community

The data races in parallel code was doing this ...

/**
 * Move vertex to another community C.
 * @param vcom community each vertex belongs to (updated)
 * @param ctot total edge weight of each community (updated)
 * @param x original graph
 * @param u given vertex
 * @param c community to move to
 * @param vtot total edge weight of each vertex
 */
template <bool REFINE=false, class G, class K, class W>
inline bool leidenChangeCommunityOmpW(vector<K>& vcom, vector<W>& ctot, const G& x, K u, K c, const vector<W>& vtot) {
  K d = vcom[u];
  if (REFINE) {
    W ctotd = ctot[d];
    W ctotc = ctot[c];
    W btotd = ctotd - vtot[u];
    W btotc = ctotc + vtot[u];
    if (ctotd!=vtot[u] || !ctotc) return false;
    bool okLeave = __atomic_compare_exchange((int64_t*) &ctot[d], (int64_t*) &ctotd, (int64_t*) &btotd, false, __ATOMIC_SEQ_CST, __ATOMIC_SEQ_CST);
    if (!okLeave) return false;
    bool okJoin  = __atomic_compare_exchange((int64_t*) &ctot[c], (int64_t*) &ctotc, (int64_t*) &btotc, false, __ATOMIC_SEQ_CST, __ATOMIC_SEQ_CST);
    if (!okJoin) {
      #pragma omp atomic
      ctot[d] += vtot[u];
      return false;
    }
    vcom[u] = c;
  }
  else {
    #pragma omp atomic
    ctot[d] -= vtot[u];
    #pragma omp atomic
    ctot[c] += vtot[u];
    vcom[u] = c;
  }
  return true;
}