Testing Higher-order Clusterability on Graphs

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 Ω(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 O~(n)-time algorithm is developed for testing clusterability based on triangles.