Semi-supervised learning in unbalanced and heterogeneous networks
This addresses the challenge of community detection in partially labeled networks with unbalanced and heterogeneous structures, representing an incremental improvement over traditional Laplacian methods.
The authors tackled the problem of semi-supervised label prediction in unbalanced and heterogeneous networks by proposing the weighted inverse Laplacian (WIL) algorithm, which achieves a misclassification rate of O(1/d) for networks with average degree d=Ω(log n) and outperforms state-of-the-art methods in simulations and real datasets.
Community detection was a hot topic on network analysis, where the main aim is to perform unsupervised learning or clustering in networks. Recently, semi-supervised learning has received increasing attention among researchers. In this paper, we propose a new algorithm, called weighted inverse Laplacian (WIL), for predicting labels in partially labeled networks. The idea comes from the first hitting time in random walk, and it also has nice explanations both in information propagation and the regularization framework. We propose a partially labeled degree-corrected block model (pDCBM) to describe the generation of partially labeled networks. We show that WIL ensures the misclassification rate is of order $O(\frac{1}{d})$ for the pDCBM with average degree $d=Ω(\log n),$ and that it can handle situations with greater unbalanced than traditional Laplacian methods. WIL outperforms other state-of-the-art methods in most of our simulations and real datasets, especially in unbalanced networks and heterogeneous networks.