Testing Higher-order Clusterability on Graphs

Yifei Li (), Donghua Yang () and Jianzhong Li ()
Additional contact information
Yifei Li: Harbin Institute of Technology
Donghua Yang: Harbin Institute of Technology
Jianzhong Li: Harbin Institute of Technology

Journal of Combinatorial Optimization, 2025, vol. 49, issue 3, No 16, 21 pages

Abstract: Abstract Analysis of higher-order organizations, represented as small connected subgraphs, is a fundamental task on complex networks. This paper studies a new problem of testing higher-order clusterability: given neighbor query access to an undirected graph, can we judge whether this graph can be partitioned into a few clusters of highly-connected cliques? This problem is an extension of the former work proposed by Czumaj et al. (STOC’ 15), who recognized cluster structure on graphs using the framework of property testing. In this paper, the problem of testing whether a well-defined higher-order cluster exists is first defined. Then, an $$\varOmega (\sqrt{n})$$ Ω ( n ) query lower bound of this problem is given. After that, a baseline algorithm is provided by an edge-cluster tester on k-clique dual graph. Finally, an optimized $$\tilde{O}(\sqrt{n})$$ O ~ ( n ) -time algorithm is developed for testing clusterability based on triangles.

Keywords: Higher-order clustering; Property testing; Dual graph; Spectral graph theory (search for similar items in EconPapers)
Date: 2025
References: Add references at CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10878-025-01262-x Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jcomop:v:49:y:2025:i:3:d:10.1007_s10878-025-01262-x

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10878

DOI: 10.1007/s10878-025-01262-x

Access Statistics for this article

Journal of Combinatorial Optimization is currently edited by Thai, My T.

More articles in Journal of Combinatorial Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().