Partial embedding distance for networks

摘要

This paper presents methods to compare networks where relationships between pairs of nodes in a given network are defined. We define such network distance by searching for the optimal method to embed one network into another network, and prove that such distance is a valid metric in the space of networks modulo permutation isomorphisms. The network distance defined can be approximated via multi-dimensional scaling, however, the lack of structure in networks results in poor approximations. To alleviate such problem, we consider methods to define the interiors of networks. We show that comparing interiors induced from a pair of networks yields the same result as the actual network distance between the original networks. Practical implications are explored by showing the ability to discriminate networks generated by different models. This paper is eligible for the student paper award.