Abstract:
|
In many real-world networks, it is often observed that subgraphs or higher order interactions of certain configurations (e.g. triangles and by-fans) are overly abundant. However, statistical models accounting for this phenomenon are limited, especially when community structure is of interest. There is also a lack of community detection methods that leverage subgraphs or higher order interactions. In this paper, we propose a novel community detection method that effectively uses higher order structures in a network. Further, we show that under an edge dependent network model that consists of both block and triangle structures, the proposed method is consistent, and the misclassification error rate is bounded by O(d^{-1/2}) with high probability, where d is the expectation of the triangle degree of a node. To the best of our knowledge, this is the first consistency result for community detection that considers a network model with dependent edges. We have also examined the proposed method in simulation studies and real-world networks, and demonstrated the benefit of using higher order interactions in community detection.
|