TY - GEN
T1 - Testing Higher-Order Clusterability on Graphs
AU - Li, Yifei
AU - Yang, Donghua
AU - Li, Jianzhong
N1 - Publisher Copyright:
© The Author(s), under exclusive license to Springer Nature Switzerland AG 2024.
PY - 2024
Y1 - 2024
N2 - Analysis of higher-order organizations, usually small connected subgraphs called motifs, is a fundamental task on complex networks. This paper studies a new problem of testing higher-order clusterability: given query access to an undirected graph, can we judge whether this graph can be partitioned into a few clusters of highly-connected motifs? 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, a good graph cluster on high dimensions is first defined for higher-order clustering. Then, query lower bound is given for testing whether this kind of good cluster exists. Finally, an optimal sublinear-time algorithm is developed for testing clusterability based on triangles.
AB - Analysis of higher-order organizations, usually small connected subgraphs called motifs, is a fundamental task on complex networks. This paper studies a new problem of testing higher-order clusterability: given query access to an undirected graph, can we judge whether this graph can be partitioned into a few clusters of highly-connected motifs? 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, a good graph cluster on high dimensions is first defined for higher-order clustering. Then, query lower bound is given for testing whether this kind of good cluster exists. Finally, an optimal sublinear-time algorithm is developed for testing clusterability based on triangles.
KW - High Dimensional Expander
KW - Higher-order Clustering
KW - Property Testing
KW - Spectral Graph Theory
UR - https://www.scopus.com/pages/publications/85180625481
U2 - 10.1007/978-3-031-49614-1_15
DO - 10.1007/978-3-031-49614-1_15
M3 - 会议稿件
AN - SCOPUS:85180625481
SN - 9783031496134
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 203
EP - 214
BT - Combinatorial Optimization and Applications - 16th International Conference, COCOA 2023, Proceedings
A2 - Wu, Weili
A2 - Guo, Jianxiong
PB - Springer Science and Business Media Deutschland GmbH
T2 - 16th Annual International Conference on Combinatorial Optimization and Applications, COCOA 2023
Y2 - 15 December 2023 through 17 December 2023
ER -