Constrained Voting Consensus Method Enhances Community Detection Across Complex Networks

In an unsupervised learning study published in Applied Network Science, researchers The-Anh Vu-Le, Minhyuk Park, Ian Chen, João Alfredo Cardoso Lamy, Tomás Alessi, Elfarouk Harb, George Chacko, and Tandy Warnow introduced Constrained Voting Consensus, abbreviated as CVC, a cluster ensemble framework designed to aggregate multiple distinct graph partitions into a unified and more accurate community structure. Community detection remains a foundational challenge across network science, where the objective is to partition the vertex set of an observed graph into disjoint subsets whose internal wiring displays high edge density, robust internal connectivity, and clean separation from the remainder of the network. While conventional consensus clustering architectures typically evaluate all input partitions uniformly across every edge, CVC introduces an eligibility requirement that permits an input clustering to vote on an edge only when both adjacent vertices are placed into non-singleton clusters. By integrating multiple dense subgraph extraction techniques with established community detection algorithms, the investigators established that CVC achieves higher clustering accuracy than its individual constituent algorithms and prior aggregation approaches, including the median consensus method, while scaling effectively to large empirical networks comprising millions of vertices.

The study contextualizes community detection against the established landscape of optimization-based formulations and heuristic graph searches. In standard graph partitioning formulations, algorithms seek to optimize specific objective functions across the entire graph, but because these formulations are typically NP-hard, practitioners rely on heuristic search strategies that do not guarantee globally optimal configurations. Modularity optimization, frequently implemented through the Louvain algorithm or the Leiden framework, represents one of the most prominent formulations in literature; however, optimal modularity clustering is mathematically constrained by a well-documented resolution limit that frequently prevents the detection of communities below a characteristic size and tends to group vertices into excessively large, sparse partitions. To mitigate these deficiencies, the Constant Potts Model, or CPM, incorporates a user-defined resolution parameter that guarantees optimal partitions will be resolution-limit-free and satisfy explicit edge-cut thresholds that ensure communities remain well-connected. Nevertheless, because both modularity and CPM optimization depend on heuristic procedures to navigate combinatorial search spaces, alternative methodologies based on iterative extraction have increasingly gained attention as complementary mechanisms for isolating network structure.

Iterative extraction approaches pursue community detection through a sequential peeling strategy: an algorithm isolates a high-quality subgraph from the network, designates that subgraph as a community, removes its constituent vertices and incident edges, and iteratively repeats the extraction process on the remaining graph until no subgraphs satisfy the extraction criteria. Historical implementations of this paradigm include the Iterative k-core algorithm, or IKC, which identifies the maximum value of k such that every vertex in a connected subgraph maintains at least k internal neighbors, extracting that k-core iteratively until no cores meet a pre-specified threshold B. Another iterative formulation is RTRex, which extracts subgraphs displaying the highest density of triangles, or 3-cliques. Dense subgraph discovery more broadly seeks subgraphs maximizing the ratio of edge count to vertex count, a problem solvable in polynomial time that has also been extended into dense subgraph decomposition. Solvers developed for this decomposition include quadratic programming via the Frank-Wolfe algorithm, multiplicative weight updates via Greedy++, convex relaxations solved through the Fast Iterative Shrinkage-Thresholding Algorithm known as FISTA, and max-flow formulations solved via push-relabel algorithms, referred to as Flow, each assigning intermediate density metrics to graph vertices.

Building on dense subgraph decomposition formulations, the authors evaluated five dense subgraph clustering, or DSC, techniques: DSC-FISTA(int), DSC-Flow, DSC-FISTA-Iter, DSC-Flow-Iter, and an iterative rounding variant termed DSC-FISTA(int)-Iter. In the non-iterative variants, vertices are partitioned directly based on their calculated decomposition values, with integer rounding applied to FISTA outputs to smooth granular, staircase-like approximations, while Flow values provide coarser plateaus that can be grouped directly. In the iterative variants, the algorithms serve as subroutines to extract only the single densest subgraph at each step before repeating the process on the residual graph. Across the first experimental benchmark conducted on seventy-four synthetic benchmark networks generated via the EC-SBM model, the newly evaluated DSC-FISTA(int)-Iter method achieved an average Adjusted Mutual Information, or AMI, of 0.309, surpassing both the non-iterative DSC-FISTA(int) average of 0.285 and the fractional peeling variant DSC-FISTA-Iter at 0.123. However, DSC-Flow-Iter demonstrated the strongest overall performance among all density-based algorithms, attaining the highest average AMI of 0.370 and an Adjusted Rand Index, or ARI, of 0.121, ranking best on forty-six and forty-five networks, respectively, thereby establishing DSC-Flow-Iter as the primary dense subgraph representative.

In their second experiment, the researchers evaluated DSC-Flow-Iter against established standalone community detection methods, specifically Leiden optimizing modularity, Leiden optimizing the Constant Potts Model across varying resolution values, Infomap, IKC across parameter thresholds, and RTRex across seventy-four synthetic networks with known ground-truth structure. In these baseline assessments, Leiden optimizing CPM at a resolution of 0.01 achieved the highest standalone AMI and ARI scores among all individual methods, while DSC-Flow-Iter ranked second in both criteria. Conversely, RTRex exhibited a sharp divergence across evaluation metrics, recording the lowest AMI score of 0.099 and ARI score of 0.039, yet achieving the highest Normalized Mutual Information, or NMI, ranking best in fifty-two of the seventy-four networks. The authors demonstrated that this apparent discrepancy stems from the known structural bias of NMI toward clusterings containing very high numbers of clusters: RTRex placed approximately 93 percent of network vertices into isolated singleton clusters, yielding an exceptionally low node coverage that artificially inflated its NMI performance while compromising overall partition quality.

To design an optimized cluster ensemble pipeline, the investigators conducted a three-part investigation using a training corpus of fifty-one synthetic networks, beginning with the selection of the final clustering algorithm to be applied after voting. Comparing multiple methods with and without post-processing using the Well-Connected Clusters, or WCC, technique—which recursively removes small edge cuts from clusters failing connectivity thresholds—the authors determined that Leiden optimizing CPM at a resolution of 0.01 followed by WCC post-processing produced the highest performance, achieving an average AMI of 0.465 and ARI of 0.234, substantially outperforming Leiden-Mod with WCC, which reached an AMI of 0.424 and an ARI of 0.126. The empirical results further revealed that WCC post-processing provided meaningful improvements for optimization methods that generate weak edge cuts, but exerted negligible influence on methods designed to extract inherently dense subgraphs, including DSC-Flow-Iter, RTRex, and IKC at higher parameter thresholds such as 5, 10, or 20, because subgraphs possessing high edge density rarely contain small internal edge cuts.

The ensemble architecture was further structured by selecting base clustering algorithms that exhibited complementary trade-offs between precision and recall across classification metrics, where pairs of vertices are evaluated based on whether they are correctly assigned to the same community. For high recall, the authors selected Leiden-Mod, which demonstrated a near-perfect average recall of 0.927 and 100 percent node coverage on the training data, capturing the vast majority of true co-clustered pairs at the expense of a low precision of 0.034. To counterbalance this expansive coverage, the team incorporated three precision-oriented methods: RTRex, which exhibited the highest precision in the benchmark at 0.612 but negligible recall of 0.020 and node coverage under 20 percent; IKC with parameter B set to 5, providing a precision of 0.087, recall of 0.201, and coverage below 20 percent; and DSC-Flow-Iter, which bridged these algorithmic extremes by achieving a precision between 0.052 and 0.087, a moderate recall of 0.374, and a node coverage of 61.7 percent.

Using these four base clusterings—abbreviated as F for DSC-Flow-Iter, M for Leiden-Mod, R for RTRex, and K for IKC(5)—the researchers evaluated multiple ensemble variants on the training dataset to determine how edges should be preserved and weighted before final clustering with Leiden-CPM(0.01)+WCC, denoted as C. They compared free voting schemes, where every base clustering casts a vote on every edge, against constrained voting schemes, where a base clustering only votes if both incident vertices are placed into non-singleton clusters. Among evaluated voting rules, which included fully weighted networks, strict consensus, and majority rules, the configuration employing constrained voting under majority rule on unweighted edges, designated as FMRKC-Constrained-Majority(U) or FMRKC-CVC, achieved the highest performance across the training suite, tying for the top average AMI of 0.486 and securing the uniquely highest average ARI of 0.301. The formal protocol executes across four sequential stages: Stage 1 computes DSC-Flow-Iter; Stage 2 executes Leiden-Mod, RTRex, and IKC(5); Stage 3 builds an unweighted consensus network retaining edges supported by at least 50 percent of eligible voters; and Stage 4 executes Leiden-CPM(0.01) with WCC post-processing on the resulting consensus graph.

The authors supported the constrained voting design with formal theoretical properties detailed in their supplementary findings. Specifically, Theorem 1 establishes that if all base clusterings used to construct the consensus network possess perfect precision—meaning no base method groups two vertices together unless they belong to the same ground-truth cluster—and the final clustering algorithm does not generate internally disconnected clusters, then constrained voting is guaranteed to maintain perfect precision. Furthermore, Theorem 2 proves that if these perfect precision conditions hold, the threshold for edge retention requires at least one supporting clustering, and every true co-clustered pair appears together in at least one input partition, the connected components of the resulting consensus network will correspond exactly to the ground-truth communities.

When evaluated on the held-out testing dataset comprising twenty-three EC-SBM synthetic networks, the proposed FMRKC-CVC pipeline demonstrated superior accuracy over alternative consensus models and individual clustering methods. Compared directly against Leiden-CPM(0.01)+WCC, which was the most accurate constituent method on standalone networks, FMRKC-CVC achieved higher average AMI (0.625 versus 0.583), higher ARI (0.439 versus 0.367), and higher NMI (0.906 versus 0.888), securing superior performance on twenty out of twenty-three individual test networks. Statistical analysis confirmed that the improvement in classification F1 score over Leiden-CPM(0.01)+WCC was statistically significant, with a p-value of 0.0010 under both Benjamini-Hochberg and Holm-Bonferroni corrections. FMRKC-CVC also outperformed the free voting variant FMRKC-FVC and the median consensus pipeline FMRKC-MedCon across all clustering and classification metrics, achieving a statistically significant F1 advantage over median consensus (p=0.0070 under Benjamini-Hochberg and p=0.0105 under Holm-Bonferroni adjustments).

An extensive ablation analysis revealed fundamental differences in how consensus algorithms handle inputs with uneven node coverage. Removing Leiden-Mod from CVC caused a substantial drop in AMI and ARI, confirming that the ensemble requires at least one base method with high recall and comprehensive node coverage to establish a global structural framework. However, removing low-coverage methods had varying effects: eliminating DSC-Flow-Iter reduced ARI, removing IKC(5) diminished both AMI and ARI, and excluding RTRex had a neutral impact. In sharp contrast, both Free Voting Consensus and Median Consensus suffered notable performance degradation when low-coverage, high-precision methods were included in their inputs; Median Consensus only approached the accuracy of CVC when its inputs were artificially restricted to the two high-coverage algorithms, Leiden-Mod and Leiden-CPM(0.01)+WCC. These findings confirm that CVC’s eligibility rule insulates the ensemble from low-coverage penalties, enabling it to leverage local, dense community signals without distorting global consensus.

To evaluate computational scalability, the team benchmarked the pipeline across seventy-eight real-world networks spanning from 906 vertices to nearly 14 million vertices in the CEN dataset. The authors resolved a memory leak that had caused out-of-memory errors in earlier implementations during repeated external function calls within DSC-Flow-Iter, allowing all seventy-eight networks to run successfully within a three-day execution window on Illinois Campus Cluster nodes with 256 gigabytes of RAM. Total runtime scaled within one minute for networks with up to 100,000 nodes, but reached 2,608 minutes—approximately 43.5 hours—on the livejournal network. Computational profiling across the largest networks showed that Stage 1 calculation of DSC-Flow-Iter exhibited a power-law relationship with network size and dominated execution time in five of the six largest datasets, while Stage 4 WCC post-processing accounted for more than 50 percent of runtime on the 14-million-node CEN graph. The authors concluded that while CVC enables robust, scalable ensemble community detection, optimizing push-relabel implementations and refining connectivity post-processing remain critical targets for accelerating execution in future graph mining applications.

Subject of Research: Constrained voting consensus clustering for network community detection

Article Title: Improving community detection with CVC, a new cluster ensemble method

Article References: Vu-Le, T.-A., Park, M., Chen, I., Lamy, J. A. C., Alessi, T., Harb, E., Chacko, G., & Warnow, T. (2026). Improving community detection with CVC, a new cluster ensemble method. Applied Network Science, 11(1), Article 53. https://doi.org/10.1007/s41109-026-00809-z

Image Credits: AI Generated

DOI: 10.1007/s41109-026-00809-z

Keywords: community detection, graph clustering, cluster ensembles, constrained voting consensus, dense subgraph discovery, network science, unsupervised learning, Applied Network Science, Improving, community, detection, cluster