Network Global Testing by Counting Graphlets


Jiashun Jin, Zheng Ke, Shengming Luo ;
Proceedings of the 35th International Conference on Machine Learning, PMLR 80:2333-2341, 2018.


Consider a large social network with possibly severe degree heterogeneity and mixed-memberships. We are interested in testing whether the network has only one community or there are more than one communities. The problem is known to be non-trivial, partially due to the presence of severe degree heterogeneity. We construct a class of test statistics using the numbers of short paths and short cycles, and the key to our approach is a general framework for canceling the effects of degree heterogeneity. The tests compare favorably with existing methods. We support our methods with careful analysis and numerical study with simulated data and a real data example.

Related Material