CS Paper Radar

Scaled Null-Adjusted Persistence: A Multiscale Bridge between Modularity and Persistence

Alessandro Avellone, Paolo Bartesaghi, Stefano Benati, Rosanna Grassi

cs.SI math.OC ·submitted 2026-08-31 15:07 UTC · v1

Abstract

Community detection methods must balance two competing objectives: identifying small, cohesive groups while avoiding excessive fragmentation. Modularity, the most widely adopted optimization criterion, typically merges small communities in large networks due to its resolution limit. In contrast, a persistence-based criterion promotes more granular partitions. We introduce Scaled Null-Adjusted Persistence (Scaled-NAP), a parametric family of quality functions that incorporates both these criteria. The definition exploits the exact identity between a cluster's modularity contribution and its Null-Adjusted Persistence (NAP) multiplied by its relative volume. Raising this volume factor to a parameter $α\in[0,1]$ yields NAP at $α=0$ and modularity at $α=1$, while intermediate values control the scale of the detected partition. We derive conditions under which merging two communities improves the objective function and characterize the emergence of scale dependence, including resolution-limit behaviour on Caveman graphs. We develop the Milano algorithm, a multilevel Louvain-style heuristic for optimizing Scaled-NAP on large networks. Experiments on weighted and unweighted Lancichinetti-Fortunato-Radicchi benchmarks show that Scaled-NAP achieves the highest or tied-highest recovery wherever the ground truth structure is detectable, with its advantage increasing under community-size heterogeneity. Tests on three real networks with up to 1.1 million nodes confirm its capability to identify fine-grained ground-truth communities. The Milano algorithm also turned out to be the fastest method evaluated on large networks. These results show that Scaled-NAP provides an effective and scalable bridge between modularity-based and persistence-based community detection methodologies.

Closest papers

Nearest neighbours by meaning across the whole index.

Constrained Enumeration Reveals Hidden Optima and Precision-Dependent Degeneracy in Modularity-Based Community Detection

cs.SI ·2026-09-29 ·Fabio Morea
benchmark similarity 0.70
Abstract · 11 pages, 7 figures

Modularity landscapes are often flat near the top: many distinct partitions achieve indistinguishable scores, and repeated runs of heuristic algorithms can still miss accessible optima. We introduce a two-phase workflow that (i) samples partitions until novelty saturates, then (ii) localises instability to a small subset of nodes and enumerates only that residual ambiguity under a locked stable core. Across a simple 50-nodes benchmark network, and a real weighted collaboration network, constrained enumeration systematically expands plateau coverage and can improve modularity beyond extensive Louvain restarts. Finally, we show that edge-weight rounding qualitatively reshapes plateau structure, making precision sensitivity an essential part of solution-space reporting.

0.26

Representation-Aware Modularity with a Distance-Calibrated Null Model

cs.SI ·2026-10-05 ·Taejoon Han, Dahee Kim, Junghoon Kim, Taeho Ha
top venue similarity 0.67
Abstract

Modularity is a standard objective for community detection, comparing observed intra-community connectivity with its null-model expectation. Modern node embeddings capture structural and semantic proximity beyond raw topology, but replacing adjacency with representation-induced affinity while retaining the classical degree-based null model makes the observed term geometry-dependent and the expected term geometry-agnostic. This creates a null-model mismatch: the objective may reward affinity already expected from representation proximity. This paper introduces RAM, a representation-aware modularity objective with a distance-calibrated null model. RAM preserves the observed-minus-expected principle by calibrating expected affinity with both degree heterogeneity and representation distance. We analyse its relation to classical modularity and develop divisive and multi-level greedy optimisers. Experiments on seven real-world datasets and synthetic scalability tests show that RAM improves over topology-only, direct embedding-clustering, and deep learning-based baselines, remains competitive under classical modularity while improving community quality on large graphs, and scales efficiently. Ablations confirm that both degree correction and distance calibration are essential.

0.37

Explicit objective functions in modularity-based community detection on multiplex networks

cs.SI ·2026-09-29 ·Elizaveta Evmenova, Petr Chunaev
code/data similarity 0.65
Abstract · Revised exposition of the fusion-objective relationships; added label-free Cora external validation, fixed-weight baselines, and a reproduci…

Early, simultaneous, and late fusion combine network layers at different stages of community detection. Their modularity values consequently need not measure the same property of a partition. For normalized shared-node multiplexes, a unified comparison extends an existing two-layer identity: early fusion equals simultaneous fusion plus a weighted variance of community degree volumes. An elementary simplex argument explains simultaneous fusion's preference for single-layer weights. For a specified late-fusion construction, an additional transformation correction separates changes to the graph from changes to the objective. Exact small-network experiments and Louvain and Leiden experiments illustrate these distinctions. On label-free Cora, all objective-selected weights favor citations alone, while the fixed equal-weight mixtures achieve higher median adjusted Rand agreement with subject categories. The analysis provides a diagnostic for interpreting fusion objectives; higher objective values alone do not establish better recovery of externally defined communities.

0.38

Partition Space Maps for Community Detection: Visualizing Algorithmic Behaviour and Guiding Search

cs.SI ·2026-09-29 ·Fabio Morea
benchmark similarity 0.63
Abstract

Community-detection methods search over possible partitions of a network, but the structure of this partition space is rarely examined directly. This paper introduces two complementary tools that make~$\mathcal{P}$ analytically and visually accessible. First, a canonical labelling scheme based on the Restricted Growth Sequence~(RGS) is adopted, assigning each partition a unique, permutation-invariant identifier and eliminating the need for pairwise similarity measures such as the Normalized Mutual Information. Second, granularity~$Γ$ is defined and combined with modularity~$Q$ to produce a two-dimensional projection: the Partition Space Map~(PSM). Within the $(Γ,Q)$ plane, only a discrete set of integer values of~$Γ$ is attainable, and upper and lower bounds on~$Q$ are derived directly from the deviation matrix. These tools are demonstrated through complete enumeration of~$\mathcal{P}$ for small benchmark graphs, revealing the fine structure of modularity degeneracy and the combinatorial constraints that shape the feasible region. The framework provides an exact, assumption-free reference for evaluating heuristic community detection algorithms and lays the groundwork for geometry-aware exploration of partition space in larger networks.

0.31

Exact computation of the network modularity with branch-and-bound

cs.SI stat.CO ·2026-10-03 ·Emily Weng, Georg Hahn
publishedbenchmark similarity 0.62
Abstract

We consider the computation of the network modularity, a common measure of the structure of networks or graphs that quantifies the division of a network into modules or clusters. The computation of the network modularity is an NP-hard problem, thus making its exact computation often infeasible in practice. This has resulted in the development of several heuristics in the literature. In this work, we consider the exact computation of the network modularity with the help of a branch-and-bound algorithm. Our algorithm is guaranteed to find the optimal clustering that maximizes the network modularity, however it achieves this without a full exploration of the search space. This is accomplished by bounding partial solutions and discarding them if it can be foreseen that a partial solution will not yield an improvement over an existing solution. We assess our algorithm with respect to accuracy and runtime and compare it to a brute-force approach as well as two benchmark algorithms, simulated annealing and the Louvain method.

0.40

Parameterized Complexity of Connected Network Microaggregation: The Role of Cluster Size

cs.DS ·2026-08-28 ·Ajinkya Gaikwad, Dušan Knop, Tomáš Valla
theory similarity 0.61
Abstract

Network microaggregation is a fundamental technique in statistical disclosure control, where vertices of a graph are partitioned into clusters satisfying size constraints and admitting a center within bounded distance. We study the parameterized complexity of the \emph{unweighted Connected Network Microaggregation} problem, focusing on structural parameters and natural clustering parameters such as the distance bound $d$ and cluster size gap $u-\ell$. We show that, unlike the weighted variant, the unweighted connected problem is fixed-parameter tractable when parameterized by neighborhood diversity, and hence by vertex cover. In contrast, it remains $\mathrm{W[1]}$-hard for more general structural parameters, including vertex deletion to paths, stars, and cliques. These hardness results hold even for every $d\ge 2$ and any fixed gap $u-\ell$, showing that these clustering parameters do not overcome the structural hardness. We further show that adding the cluster size bound $u$ restores tractability for structural parameters such as treewidth and cluster vertex deletion. Moreover, $u$ is essential: the problem remains $\mathrm{W[1]}$-hard when these structural parameters are considered alone. For kernelization, we prove that the problem has no polynomial kernel parameterized by vertex cover unless $\mathrm{coNP}\subseteq\mathrm{NP/poly}$, even when the distance constraint is vacuous. Adding $u$ yields a polynomial kernel for vertex cover, while kernelization remains unlikely for more general structural parameters even when combined with $u$. Finally, we show that the problem is NP-hard on graphs of bounded clique-width.

0.24

Community Search under Member-Specific Tolerances

cs.SI cs.CCcs.DB ·2026-11-04 ·Yanghao Liu, Fangda Guo, Yuxuan Zhang, Xueqi Cheng
similarity 0.60
Abstract · 23 pages, 5 figures, 19 tables. Technical report. Results on the Yelp Open Dataset are omitted from this version pending the data provider's…

We study community search when each vertex has its own tolerance for differences in position. For positions such as opinions or homes, a latitude-consistent community (LCC) contains the query vertex, is connected, has minimum degree at least k, and bounds its diameter by the smallest member tolerance. Motivated by social judgment theory, the bound exactly characterizes persistent acceptance of every interaction in a closed group under bounded-confidence dynamics with arbitrary positive weights. It also prevents rejection under social-judgment dynamics, whereas natural relaxations preserve neither guarantee. Finding a maximum LCC is NP-hard even in the plane, and with unbounded dimension, deciding whether an LCC exists is NP-complete for every fixed k >= 2. LatSweep turns the coupled bound into a sweep over the smallest tolerance, yielding two feasible heuristics, a (1,2)-bicriteria approximation and an exact branch-and-bound algorithm. Across eight graphs with up to 1.8 billion edges, the exact algorithm proves optimality on all but 9 of 3,700 efficiency queries and usually certifies absence within microseconds when no LCC exists. Its branch-and-bound solver proves more queries than a reimplemented maximum-(k,r)-core algorithm, a mixed-integer program and CP-SAT. In simulations, uneven influence disrupts initially accepted interactions in pairwise groups. Outside ties invalidate the guarantee for many real groups. On two location-based networks, tolerance-agnostic groups often place another member's home beyond a member's estimated travel radius; comparisons with spatial communities of the same size detect no co-visit loss from enforcing every member's tolerance.

0.35

WCCS: Efficient Wedge Conductance Community Search over Large Temporal Bipartite Graphs (Full Paper)

cs.SI ·2026-09-15 ·Longlong Lin, Wei Chen, Pingpeng Yuan, Ruikun Luo, Qiangqiang Dai +1 more
similarity 0.60
Abstract

Bipartite graphs are ubiquitous for modeling complex interactions between two distinct entity types across numerous practical applications such as e-commerce, academic networks, and social systems. Despite significant progress in community search over bipartite graphs, most prior work is limited to static settings and ignores the rich temporal dynamics present in real-world networks. Moreover, existing methods typically adopt edge-centric measures and strict consecutivity constraints, failing to capture higher-order interactions and frequent yet non-consecutive activities. More importantly, they often neglect the crucial community-quality requirements of both internal cohesiveness and external sparsity, failing to identify critical nodes or including many irrelevant nodes. To address these dilemmas, we propose the novel problem of \emph{Wedge Conductance Community Search (WCCS)}, which aims to identify a query-dependent community that is not only structurally and temporally cohesive but also well-separated from the rest of the network over non-consecutive timestamps. We formalize WCCS by generalizing the classical $(α,β)$-core to a higher-order $(α,β,τ)$-wedge core, and by proposing a novel temporal wedge conductance metric that explicitly balances internal density and external sparsity. To solve WCCS efficiently, we first develop an online priority-driven filter-and-expand framework with several effective pruning techniques and a powerful geometric slope optimization for rapid temporal wedge conductance calculation. Subsequently, to further improve scalability, we propose an offline compressed index to accelerate search. Finally, comprehensive experiments on seven real-world datasets demonstrate the effectiveness, efficiency, and scalability of our solutions compared to eight competitors.

0.11