Embedding complex networks in a low dimensional Euclidean space based on vertex dissimilarities

作者：Lee Chang Yong^*

来源：Physica A: Statistical Mechanics and Its Applications , 2012, 391(20): 5018-5030.

DOI：10.1016/j.physa.2012.05.021

• Complex networks
• Dissimilarity
• Euclidean space
• Non-metric multidimensional scaling

We propose a method for representing vertices of a complex network as points in a Euclidean space of an appropriate dimension. To this end, we first adopt two widely used quantities as the measures for the dissimilarity between vertices. The dissimilarity is then transformed into its corresponding distance in a Euclidean space via the non-metric multidimensional scaling. We applied the proposed method to real-world as well as models of complex networks. We empirically found that real-world complex networks were embedded in a Euclidean space of relatively lower dimensions and the configuration of vertices in the space was mostly characterized by the self-similarity of a multifractal. In contrast, by applying the same scheme to the network models, we found that, in general, higher dimensions were needed to embed the networks into a Euclidean space and the embedding results usually did not exhibit the self-similar property. From the analysis, we learn that the proposed method serves a way not only to visualize the complex networks in a Euclidean space but to characterize the complex networks in a different manner from conventional ways.

• 出版日期2012-10-15