Skip to content

NSGA-III-CCM

Re-implemented baseline Multi-objective

NSGA-III-CCM, from Shaik, Ravi and Deb (2021) (doi:10.1007/s42979-020-00382-x), maximizes three objectives together: Community Score and Community Fitness, the objective pair of MOGA-Net, and Newman's modularity \(Q\). Its three letters name those three objectives. The search is the reference-point-based NSGA-III of Deb and Jain (2014) (doi:10.1109/TEVC.2013.2281535), run over a locus-based genome in which every genome decodes to a valid partition, so no repair step is needed. ccm returns the member of the final rank-1 Pareto front with the highest modularity, and ccm_fronts returns the whole front. The same paper also defines NSGA-III-KRM, which keeps the engine and the modularity objective but replaces Community Score and Community Fitness with kernel k-means and ratio cut.
Entry points ccm, ccm_fronts
Objectives Community Score \(\mathrm{CS}\), Community Fitness \(\mathrm{CF}\) and modularity \(Q\), all three maximized
Search NSGA-III (Deb and Jain, 2014) over a locus-based genome, in a private, sequential engine
Selection rule Highest modularity \(Q\) on the rank-1 front
Front accessor ccm_fronts, a list[dict[int, int]]
Deterministic No. The engine draws from an OS-seeded generator and the API has no seed parameter (module README)
Original code None released (module README)
Paper Shaik, Ravi and Deb (2021), SN Computer Science 2(1):1 — doi:10.1007/s42979-020-00382-x

Objectives

Community Score, Community Fitness and the genome come from Pizzuti (2012), doi:10.1109/TEVC.2011.2161090, the paper behind MOGA-Net. Let \(S\) range over the communities of a partition, \(|S|\) be the number of nodes in \(S\), \(k_{\mathrm{in}}(i)\) the number of neighbors of node \(i\) that lie in \(i\)'s own community, \(\deg(i)\) the degree of \(i\), \(m\) the number of edges, \(l_c\) the number of edges inside community \(c\) (each counted once) and \(d_c\) the sum of the degrees of the nodes of \(c\).

\[ \mu_i = \frac{k_{\mathrm{in}}(i)}{|S|}, \qquad M(S) = \frac{1}{|S|} \sum_{i \in S} \mu_i^{\,r}, \qquad v_S = \sum_{i \in S} k_{\mathrm{in}}(i) \]
\[ \mathrm{CS} = \sum_{S} M(S)\, v_S, \qquad \mathrm{CF} = \sum_{S} \sum_{i \in S} \frac{k_{\mathrm{in}}(i)}{\deg(i)^{\alpha}}, \qquad Q = \sum_{c} \left[ \frac{l_c}{m} - \left( \frac{d_c}{2m} \right)^{2} \right] \]
  • \(v_S\) is twice the number of edges inside \(S\).
  • \(M(S)\) is the plain mean of \(\mu_i^{\,r}\), with no outer \(1/r\) root. This follows Pizzuti's definition. At the default \(r = 1\) the two readings coincide.
  • A node of degree 0 contributes 0 to \(\mathrm{CF}\).
  • \(\mathrm{CF}\) is largest when no edge leaves a community, which on a connected graph happens only for the single-community partition, so maximizing it favors partitions with few edges between communities.
  • \(Q\) is the modularity of Newman and Girvan (2004), doi:10.1103/PhysRevE.69.026113.
  • The exponents \(r\) and \(\alpha\) are the parameters r and alpha. The module README states that the paper fixes \(r = 1\), which weights all nodes equally, and \(\alpha = 1\), following MOGA-Net.

The paper maximizes all three objectives. The engine minimizes, so the vector it receives is \((-\mathrm{CS}, -\mathrm{CF}, -Q)\), and every rank, dominance test and reference-point distance is computed in that sign-flipped space.

Representation. The genome is Pizzuti's locus-based encoding. It has one cell per node, in the graph's stable node order. Cell \(u\) holds either \(u\) itself or the position of one of \(u\)'s neighbors. Decoding is a union-find over the cells: each connected component is one community. Every genome that an operator can produce is valid, so the module has no repair step. Initialization draws each cell uniformly from \(\{u\} \cup N(u)\), where \(N(u)\) is the set of neighbors of \(u\). Isolated nodes decode to singletons and are reported as community -1.

Loop. With pop_size \(= N\):

  1. Draw \(N\) random genomes, decode and evaluate them, and sort them into non-dominated fronts.
  2. Build the structured reference points of Das and Dennis (1998), doi:10.1137/S1052623496307510, for \(M = 3\) objectives and \(p\) = divisions subdivisions: \(H = \binom{M + p - 1}{p}\) points, which is 91 at the default \(p = 12\).
  3. For each of num_gens generations:
    1. Breed \(N\) offspring. Two parents are drawn uniformly at random, with no fitness-based mating selection. With probability cross_rate the child is their uniform crossover; otherwise it is a clone of one of the two, chosen with probability 1/2 each. Every gene of the child is then independently resampled from \(\{u\} \cup N(u)\) with probability mut_rate.
    2. Run NSGA-III environmental selection over the \(2N\) parents and offspring (Deb and Jain, 2014, Algorithms 1 to 4). Whole non-dominated fronts are kept while they fit. The remaining places go to members of the first front that does not fit: the kept members and that front together (\(S_t\)) are normalized onto a hyperplane, each is associated with its nearest reference line, and niching picks the survivors from that front. The least crowded reference point wins, with ties broken uniformly at random; an empty niche takes its closest member and a non-empty one takes a random member.
    3. Apply the paper's two customizations (Sec. 4), in this order: any individual whose canonical labeling repeats one already seen is replaced by a fresh random genome, and then so is any individual that puts every node in one community. Replacements are evaluated at once.
    4. Re-rank the population, because the customizations replaced members after selection had ranked them.
  4. Sort the final population once more. Its rank-1 members are the result.

The engine is that of Deb and Jain (2014), doi:10.1109/TEVC.2013.2281535, with the fast non-dominated sort of Deb et al. (2002), doi:10.1109/4235.996017.

Randomness

NSGA-III-CCM is not deterministic: two consecutive calls can return different results. The engine draws from the thread-local generator, which is seeded from the operating system, and no seed parameter is exposed, so the initial population, both parent picks, every crossover, clone and mutation draw, the replacement genomes of the two customizations and the random tie-breaks inside niching change from run to run. The search is sequential, so the thread count is not a further source of variation.

On Zachary's karate club the runs do not spread. ccm was run 30 times with its defaults on nx.karate_club_graph() (pymocd 6.1.0 from PyPI, Python 3.10, on a shared Linux server with 48 hardware threads), and all 30 calls returned the same 4-community partition, with modularity \(Q = 0.4198\) counted on edges (weight=None). Scored with ami against the two karate ground-truth conventions, its AMI is 0.5667 ± 0.0000 against NetworkX's club attribute and 0.6712 ± 0.0000 against the convention that puts node 8 with the Officer faction; its nmi is 0.5878 and 0.6873. The module README attributes the absence of spread to that graph being degenerate, and reports a rank-1 front of roughly 110 ± 30 members on a 250-node LFR graph. See Performance and reproducibility for how to handle nondeterministic detectors in experiments.

Selecting a partition

ccm returns the rank-1 member with the highest modularity \(Q\). The docstring calls this the paper's recommended decision rule when no ground truth is available.

ccm_fronts returns every rank-1 member as a list of partitions. The paper reports both the best-NMI and the best-modularity member of the front (its Tables 1 and 2), and reproducing that protocol needs the whole candidate set; score each member against the ground truth with nmi.

Each call runs its own search. Because the search is not deterministic, the partition returned by ccm need not be a member of the front returned by a separate ccm_fronts call. To obtain a front and its selected member from the same run, call ccm_fronts and apply the max-modularity rule yourself, as the example below does. See Working with Pareto fronts for more on fronts.

Parameters

Parameter Default Description
pop_size 200 Population size \(N\). The module README requires it to stay above the number of reference points, \(H = 91\) at the default divisions; the code does not check this. The README notes that Sec. 8.1 of the paper says 20 for karate, while the paper's Table 3 grid and its Fig. S.22 use 200.
num_gens 100 Number of generations. The paper's best-reported combination on Zachary's karate club.
cross_rate 0.8 Probability that a child is the uniform crossover of its two parents rather than a clone of one of them. The paper's best combination.
mut_rate 1/68 Per-gene probability of resampling a cell from \(\{u\} \cup N(u)\). The paper's best combination on the 34-node karate graph.
r 1.0 Exponent \(r\) applied to each \(\mu_i\) in \(M(S)\) (there is no outer \(1/r\) root, so \(M(S)\) is not a power mean). Fixed by the paper at \(r = 1\).
alpha 1.0 Exponent \(\alpha\) of the degree in Community Fitness. Fixed by the paper at \(\alpha = 1\), following MOGA-Net.
divisions 12 Das and Dennis subdivisions \(p\); \(H = \binom{p + 2}{2}\) reference points for the three objectives, 91 at \(p = 12\). The paper does not state a value; the module README takes 12 from pymoo's convention for three objectives.

Every parameter after graph is optional, and ccm and ccm_fronts take the same ones with the same defaults.

The mut_rate default is tuned to a 34-node graph

The default is the constant \(1/68 \approx 0.0147\) (the stub prints it as 0.014705882352941176). It is not rescaled for other graphs. Because mutation acts on each gene independently, a child of an \(n\)-node graph has on average \(n \cdot\) mut_rate resampled genes, which is \(0.5\) on karate. To use another rate, pass mut_rate explicitly.

The paper ties the rates it tries to \(n\) but picks no single rule. Its Table 3 is the sensitivity grid, one row per dataset and shared by both variants: D1 is karate (\(n = 34\)), D2 the dolphins (62), D3 college football (115) and D4 the political books (105). Each row tries 100 generations, crossover rates 0.8, 0.85 and 0.9, and mutation rates \(1/n\), \(2/n\) and \(1/(2n)\). The best NSGA-III-CCM settings are given in the text of Sec. 8.1, not in Table 3: population sizes 20, 200, 450 and 500 and mutation rates \(1/68\), \(1/62\), \(1/230\) and \(2/105\) for D1 to D4, which are \(1/(2n)\), \(1/n\), \(1/(2n)\) and \(2/n\). The same sentence lists only three crossover rates, 0.8, 0.85 and 0.9, for the four datasets, so the crossover rate of each dataset cannot be read from it. The default is the D1 rate. These numbers were read from the arXiv preprint (see Reference).

Internal constants

These are fixed in src/core/algorithms/ccm/nsga3/normalize.rs and are not exposed: NEAR_ZERO = 1e-10 is the threshold below which a pivot, an intercept or a fallback scale counts as zero; MIN_INTERCEPT = 1e-6 is the smallest accepted hyperplane intercept, below which a fallback scaling is used; and ASF_OFF_AXIS_WEIGHT = 1e-6 is the off-axis weight of the achievement scalarizing function that picks the extreme points. In nsga3/niching.rs, a reference direction whose squared norm is below 1e-30 is treated as the origin.

Degenerate inputs

The budget arguments are not validated. Every row was checked against the current package.

Input Result
pop_size=0 ccm panics with "empty Pareto front"; ccm_fronts returns [].
cross_rate or mut_rate outside \([0, 1]\) Both functions panic with p=… is outside range [0.0, 1.0].
An empty graph ccm returns {}; ccm_fronts returns pop_size empty dicts.
A graph with no edges ccm maps every node to -1; ccm_fronts returns pop_size copies of that partition.

A panic reaches Python as pyo3_runtime.PanicException, which derives from BaseException, so except Exception does not catch it.

Complexity

Neither the module README nor the paper states a bound: the arXiv preprint (arXiv:2005.03181v1) has no complexity analysis. The bounds below are derived from the source of this implementation. Write \(N\) for pop_size, \(G\) for num_gens, \(H\) for the number of reference points (\(\binom{p + 2}{2}\) for divisions \(= p\), so 91 at the default), and \(n\) and \(m\) for the numbers of nodes and edges.

Time. This implementation takes \(O(N(n + m) + N^2 + NH)\) time per generation and \(O(G\,[N(n + m) + N^2 + NH])\) per run. With pop_size above \(H\), as the module README asks, \(NH < N^2\) and the bound per run is \(O(G\,[N(n + m) + N^2])\). The search runs on one thread. Three steps make up a generation:

  • Evaluation, \(O(N(n + m))\). new_individual (nsga3/individual.rs) decodes a genome with locus::decode (locus.rs), a union-find with path compression and union by size, which costs \(O(n\,\alpha(n))\); the inverse Ackermann factor \(\alpha(n)\) is treated as a constant here. evaluate (objectives.rs) then calls community_objectives and modularity_labels, each of which walks every node's neighbor list once. A generation evaluates its \(N\) offspring and every individual the two customizations replace (apply_customizations in nsga3/engine.rs), at most \(2N - 1\) more: up to \(N - 1\) duplicates, then up to \(N\) single-community members. Breeding (breed, with locus::uniform_crossover and locus::mutate, which draws once per gene whatever mut_rate is), the canonical labelings the duplicate filter hashes, and the single-community test add \(O(Nn)\).
  • Non-dominated sorting, \(\Theta(N^2)\). fast_non_dominated_sort (nsga3/individual.rs) tests every ordered pair of individuals for dominance. It runs on the \(2N\) parents and offspring inside environmental_selection (nsga3/survival.rs), and again on the \(N\) survivors after the customizations.
  • Niching, \(O(NH)\). niche_select (nsga3/niching.rs) measures the distance from each of the at most \(2N\) members of \(S_t\) to all \(H\) reference lines, and each of its at most \(N\) picks scans all \(H\) niche counts. The normalization in nsga3/normalize.rs is linear in the size of \(S_t\) for three objectives.

Outside the loop, locus::neighbor_positions costs \(O(n + m)\), the initial population \(N\) evaluations and one sort, and api.rs sorts the final population once more. ccm then computes the modularity of every rank-1 member, at most \(O(N(n + m))\), and converts one partition in \(O(n)\); ccm_fronts converts every rank-1 member, up to \(O(Nn)\).

Memory. \(O(Nn + m + N^2 + H)\). Each individual stores its genome (\(n\) usize) and its labels (\(n\) i32), 12 bytes per node on a 64-bit build, and the \(2N\) parents and offspring are alive together during breeding and environmental selection: about \(24Nn\) bytes. The neighbor table holds the \(2m\) neighbor positions. The domination lists of the sort hold at most one entry per pair of individuals, under \(2N^2\) for the \(2N\)-member pool, and the duplicate filter's hash set holds up to \(N\) canonical labelings (\(4Nn\) bytes) after the pool is cut back to \(N\). Nothing accumulates across generations.

Measured scaling. ccm was timed on a shared Linux server with 48 hardware threads (pymocd 6.1.0 from PyPI, Python 3.10), three runs per setting, each run in a fresh process. The table gives the median wall time of the ccm call, the ratio to the previous row, and the added peak memory: the median peak resident memory of the three runs minus the median size of the process just before the call. The LFR rows use pymocd.lfr_graph(n, 2.5, 1.5, 0.3, average_degree=10, max_degree=50, min_community=20, max_community=100, seed=1); every parameter not named in the table is at its default.

Varied Graph Setting Median time Ratio Added peak memory
\(n\) LFR, \(N = 200\), \(G = 100\) \(n\) = 500 (\(m\) = 2,393) 0.884 s 2.6 MiB
\(n\) = 1,000 (\(m\) = 4,887) 1.54 s 1.75 5.2 MiB
\(n\) = 2,000 (\(m\) = 9,795) 3.37 s 2.18 10.5 MiB
\(n\) = 4,000 (\(m\) = 19,667) 6.31 s 1.87 20.6 MiB
\(n\) = 8,000 (\(m\) = 40,227) 13.7 s 2.17 41.4 MiB
\(G\) LFR \(n\) = 1,000, \(N = 200\) \(G\) = 25 0.433 s 5.2 MiB
\(G\) = 50 0.907 s 2.09 4.9 MiB
\(G\) = 100 1.87 s 2.06 5.6 MiB
\(G\) = 200 3.50 s 1.87 4.9 MiB
\(N\) LFR \(n\) = 2,000, \(G = 100\) \(N\) = 100 1.68 s 6.0 MiB
\(N\) = 200 3.46 s 2.07 10.1 MiB
\(N\) = 400 7.36 s 2.13 20.6 MiB
\(N\) = 800 15.0 s 2.04 42.8 MiB
\(N\) karate, \(G = 100\) \(N\) = 100 0.063 s 0.8 MiB
\(N\) = 200 0.179 s 2.84 1.5 MiB
\(N\) = 400 0.734 s 4.10 3.0 MiB
\(N\) = 800 2.29 s 3.12 9.8 MiB
\(N\) = 1,600 8.28 s 3.62 33.4 MiB

The measurements agree with the bound. Doubling \(n\), which also doubles \(m\) on these graphs, multiplied the time by 1.75 to 2.18; the time per unit of \(G\,N\,(n + m)\) stayed between 13.1 and 15.3 ns with no trend from \(n\) = 500 to 8,000. Memory grew by about 5.3 KiB per node at \(N = 200\), close to the \(24N = 4{,}800\) bytes (4.7 KiB) per node the population accounts for. Time was linear in \(G\), and memory did not depend on it. At \(n\) = 2,000, where \(n + m\) is about 11,800, doubling \(N\) multiplied the time by 2.04 to 2.13 and the memory by 1.68 to 2.08: the \(N(n + m)\) term dominates and the \(N^2\) term is not visible up to \(N = 800\). On karate, where \(n + m = 112\), doubling \(N\) multiplied the time by 2.8 to 4.1, the \(N^2\) term of non-dominated sorting, and memory grew faster than linearly from \(N = 400\) on, as the \(O(N^2)\) domination lists predict. The server was shared, so repeated timings vary: the setting \(n\) = 1,000, \(N = 200\), \(G = 100\) took 1.54 s in the \(n\) sweep and 1.87 s in the \(G\) sweep, run at a different time.

When to use it

  • Reproducing or comparing with Shaik, Ravi and Deb (2021). The num_gens, cross_rate and mut_rate defaults are the paper's best-reported combination on Zachary's karate club, and ccm_fronts exposes the front for the paper's best-NMI and best-modularity protocol.
  • Comparing with MOGA-Net. CCM keeps MOGA-Net's two objectives, adds modularity as a third, and replaces MOGA-Net's NSGA-II-ranked genetic algorithm with NSGA-III. Both detectors return the max-modularity member of their rank-1 front. Note that moga_net defaults to r=2.0 while ccm defaults to r=1.0.
  • As a baseline, not as a default. NSGA-III-CCM is one of the library's re-implemented baselines, which exist for papers and benchmarks. For general use, start from Choosing a detector; RIMPSO is the library's recommended default.

Divergences from the paper

The module README lists these deliberate differences:

  • The NSGA-III engine is private to the module and sequential, instead of a shared engine, and uses no thread parallelism, so that the baseline's cost and behavior track the paper's rather than this library's infrastructure.
  • Mating draws two parents uniformly at random, with no fitness-based selection. The README identifies this as pymoo's NSGA-III for unconstrained problems, which the paper adapted; there is no binary tournament.
  • \(M(S)\) is the plain mean of \(\mu_i^{\,r}\) with no outer \(1/r\) root, following Pizzuti's definition. This is not a dropped operation.
  • pop_size = 200 resolves a contradiction in the paper and divisions = 12 an omission; see Parameters.
  • Modularity is computed inside the module rather than by the library's shared modularity function, so the inner loop never builds a partition object. A test asserts that the two agree to within \(10^{-12}\).
  • The public functions return normalized partitions in which isolated nodes are community -1; the paper leaves them as singletons.
  • The duplicate filter compares canonical labelings, so it also removes partitions that differ only by a permutation of community labels.

The code has one more difference that the CCM README does not list but the KRM README records for the same engine design (see NSGA-III-KRM): the ideal point and the extreme points are recomputed from \(S_t\) at every normalization (nsga3/normalize.rs), whereas pymoo carries them across generations.

Example

The block below runs ccm and ccm_fronts on Zachary's karate club, then applies the max-modularity rule to the front by hand. The two calls are independent runs. The modularity is computed with weight=None because nx.karate_club_graph() carries edge weights, while the modularity inside CCM counts edges.

import networkx as nx
import pymocd

G = nx.karate_club_graph()

part = pymocd.ccm(G)        # max-Q member of one run's rank-1 front
print("ccm:", len(set(part.values())), "communities")

front = pymocd.ccm_fronts(G)  # the rank-1 front of a second, independent run
print("ccm_fronts:", len(front), "partitions on the front")


def communities(partition):
    groups = {}
    for node, label in partition.items():
        groups.setdefault(label, set()).add(node)
    return list(groups.values())


# ccm's decision rule, applied to this front
scored = [
    (nx.community.modularity(G, communities(p), weight=None), p) for p in front
]
q_best, best = max(scored, key=lambda item: item[0])
sizes = sorted(len(set(p.values())) for p in front)
print(f"communities per front member: {sizes[0]} to {sizes[-1]}")
print(f"max-Q member: {len(set(best.values()))} communities, Q = {q_best:.4f}")

ccm: 4 communities
ccm_fronts: 42 partitions on the front
communities per front member: 2 to 10
max-Q member: 4 communities, Q = 0.4198

The first line is the number of communities ccm selected. The last line is the member the same rule picks from the second run's front; the range above it shows how far the front spreads in the number of communities.

Reference

Tanveerulhuq Shaik, Vadlamani Ravi and Kalyanmoy Deb. "Evolutionary Multi-Objective Optimization Algorithm for Community Detection in Complex Social Networks." SN Computer Science 2(1), article 1, 2021 (published online 7 November 2020). doi:10.1007/s42979-020-00382-x.

The volume, issue, article number and dates follow the Crossref record of the DOI.

The published article is not open access. The paper's parameter grid and best settings quoted in the mut_rate note, and the absence of a complexity bound, were read from the open preprint instead: Shaik Tanveer ul Huq, Vadlamani Ravi and Kalyanmoy Deb, arXiv:2005.03181v1, 7 May 2020, arXiv:2005.03181v1. There, Sec. 8.1 is on p. 10 and Table 3 on p. 13. The "Sec. 4" cited for the two customizations under Search follows the module README; in the preprint, Sec. 4 lists the duplicate filter among the contributions and Sec. 6.5 describes both customizations.

@article{Shaik_2020,
  title     = {Evolutionary Multi-Objective Optimization Algorithm for Community Detection in Complex Social Networks},
  volume    = {2},
  ISSN      = {2661-8907},
  url       = {http://dx.doi.org/10.1007/s42979-020-00382-x},
  DOI       = {10.1007/s42979-020-00382-x},
  number    = {1},
  journal   = {SN Computer Science},
  publisher = {Springer Science and Business Media LLC},
  author    = {Shaik, Tanveerulhuq and Ravi, Vadlamani and Deb, Kalyanmoy},
  year      = {2020},
  month     = Nov,
  pages     = {1}
}

The entry is the publisher's record from doi.org, which dates the article by its online publication (2020); the journal issue is dated 2021. The pages field is added: it holds the article number 1 from Crossref, which the doi.org record leaves out.

Works the implementation builds on:

  • Clara Pizzuti. "A Multiobjective Genetic Algorithm to Find Communities in Complex Networks." IEEE Transactions on Evolutionary Computation 16(3): 418–430, 2012. doi:10.1109/TEVC.2011.2161090.
  • Kalyanmoy Deb and Himanshu Jain. "An Evolutionary Many-Objective Optimization Algorithm Using Reference-Point-Based Nondominated Sorting Approach, Part I: Solving Problems With Box Constraints." IEEE Transactions on Evolutionary Computation 18(4): 577–601, 2014. doi:10.1109/TEVC.2013.2281535.
  • Kalyanmoy Deb, Amrit Pratap, Sameer Agarwal and T. Meyarivan. "A fast and elitist multiobjective genetic algorithm: NSGA-II." IEEE Transactions on Evolutionary Computation 6(2): 182–197, 2002. doi:10.1109/4235.996017.
  • Indraneel Das and J. E. Dennis. "Normal-Boundary Intersection: A New Method for Generating the Pareto Surface in Nonlinear Multicriteria Optimization Problems." SIAM Journal on Optimization 8(3): 631–657, 1998. doi:10.1137/S1052623496307510.
  • M. E. J. Newman and M. Girvan. "Finding and evaluating community structure in networks." Physical Review E 69(2): 026113, 2004. doi:10.1103/PhysRevE.69.026113.

See also