Heterogeneous multidimensional scaling for complex networks

Many real-world networks are essentially heterogeneous, where the nodes have different abilities to gain connections. Such networks are difficult to be embedded into low-dimensional Euclidean space if we ignore the heterogeneity and treat all the nodes equally. In this paper, based on a newly defined heterogeneous distance and a generalized network distance under the constraints of network and triangle inequalities, respectively, we propose a new heterogeneous multidimensional scaling method (HMDS) to embed different networks into proper Euclidean spaces. We find that HMDS behaves much better than the traditional multidimensional scaling method (MDS) in embedding different artificial and real-world networks into Euclidean spaces. Besides, we also propose a method to estimate the appropriate dimensions of Euclidean spaces for different networks, and find that the estimated dimensions are quite close to the real dimensions for those geometrical networks under study. These methods thus can help to better understand the evolution of real-world networks, and have practical importance in network visualization, community detection, link prediction and localization of wireless sensors.