Testing for higher-order clustering in networks

Paper Title:

Testing Higher-order Clusterability on graphs

Published on:

6 October 2023

Primary Category:

Data Structures and Algorithms

Paper Authors:

Yifei Li,

Donghua Yang,

Jianzhong Li

Bullets

Key Details

•

Proposes method to test for clusterability based on network motifs

•

Defines 'good cluster' for higher-order clustering

•

Proves lower bound on testing higher-order clusterability

•

Develops optimal algorithm for testing triangle-based clusterability

Explore the topics in this paper

algorithm

connectedness

graph clustering

motifs

network analysis

AI generated summary

Testing for higher-order clustering in networks

This paper proposes a method to test whether a network can be partitioned into highly interconnected groups based on connected subgraphs called motifs. It defines a 'good cluster' for higher-order clustering, and poses the problem of testing if such a cluster exists in a network. A lower bound is proved, and an optimal algorithm is developed that can identify triangle-based clusterability in sublinear time.