Pith. sign in

REVIEW 4 cited by

Maximizing Modularity is hard

Not yet reviewed by Pith; the record is open.

Re-run · record.json Download PDF Read on arXiv ↗

This paper has not been read by Pith yet. Machine review is queued; the pith claim, tier, and objections will appear here once it completes.

SPECIMEN: schema-true, not a live event

T0 review · schema-true

One-sentence machine reading of the paper's core claim.

pith:XXXXXXXX · record.json · timestamp

arxiv physics/0608255 v2 pith:U6CWXDBS submitted 2006-08-25 physics.data-an cond-mat.stat-mechphysics.soc-ph

U. Brandes , D. Delling , M. Gaertler , R. Goerke , M. Hoefer , Z. Nikoloski , D. Wagner This is my paper · ORCID
classification physics.data-ancond-mat.stat-mechphysics.soc-ph
keywords algorithmsmodularitypartitionsbeencomputeactuallyalgorithmcalled
verification ladder T0 review T1 audit T2 compute T3 formal

Signed reviews

No signed human review yet.

0 comments
read the original abstract

Several algorithms have been proposed to compute partitions of networks into communities that score high on a graph clustering index called modularity. While publications on these algorithms typically contain experimental evaluations to emphasize the plausibility of results, none of these algorithms has been shown to actually compute optimal partitions. We here settle the unknown complexity status of modularity maximization by showing that the corresponding decision version is NP-complete in the strong sense. As a consequence, any efficient, i.e. polynomial-time, algorithm is only heuristic and yields suboptimal partitions on many instances.

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 4 Pith papers

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

  1. Linear-Time Multilevel Graph Partitioning via Edge Sparsification

    cs.DS 2025-04 conditional novelty 7.0 of 10

    A multilevel graph partitioner with edge sparsification achieves proven linear expected work and a 1.49x average speedup in KaMinPar with only about 1% average cut increase.

  2. GraphHash: Graph Clustering Enables Parameter Efficiency in Recommender Systems

    cs.IR 2024-12 conditional novelty 6.0 of 10

    Using modularity clusters of the user-item graph as hash buckets sharply improves retrieval accuracy when embedding tables are compressed.

  3. Imputation-free and Alignment-free: Incomplete Multi-view Clustering Driven by Consensus Semantic Learning

    cs.CV 2025-05 conditional novelty 5.0 of 10

    FreeCSL performs incomplete multi-view clustering by learning shared semantic prototypes across views and enhancing them with within-view graph structure, avoiding explicit imputation and alignment.

  4. Flexible Online Representation Learning Based on Similarity Matching

    cs.LG 2026-06 unverdicted novelty 4.0 of 10

    Proposes a versatile online biologically plausible algorithm for learning sparse shift-invariant representations usable for clustering, manifold tiling, or sparse coding depending on data structure.

Pith tools