Representation Learning for Scale-Free Networks

Network embedding aims to learn the low-dimensional representations of vertexes in a network, while structure and inherent properties of the network is preserved. Existing network embedding works primarily focus on preserving the microscopic structure, such as the first- and second-order proximity of vertexes, while the macroscopic scale-free property is largely ignored. Scale-free property depicts the fact that vertex degrees follow a heavy-tailed distribution (i. e. , only a few vertexes have high degrees) and is a critical property of realworld networks, such as social networks. In this paper, we study the problem of learning representations for scale-free networks. We first theoretically analyze the difficulty of embedding and reconstructing a scale-free network in the Euclidean space, by converting our problem to the sphere packing problem. Then, we propose the “degree penalty” principle for designing scale-free property preserving network embedding algorithm: punishing the proximity between high-degree vertexes. We introduce two implementations of our principle by utilizing the spectral techniques and a skip-gram model respectively. Extensive experiments on six datasets show that our algorithms are able to not only reconstruct heavy-tailed distributed degree distribution, but also outperform state-ofthe-art embedding models in various network mining tasks, such as vertex classification and link prediction.

Authors

• Rui Feng School of Computer Science, Shanghai Key Laboratory of Intelligent Information Processing, Fudan University Shanghai Collaborative Innovation Center of Intelligent Visual Computing
• Yang Yang
• Wenjie Hu
• Fei Wu Zhejiang University
• Yueting Zhang

Keywords

No keywords are indexed for this paper.