  In many applications, we need to measure similarity between nodes in a large
network based on features of their neighborhoods. Although in-network node
similarity based on proximity has been well investigated, surprisingly,
measuring in-network node similarity based on neighborhoods remains a largely
untouched problem in literature. One grand challenge is that in different
applications we may need different measurements that manifest different
meanings of similarity. In this paper, we investigate the problem in a
principled and systematic manner. We develop a unified parametric model and a
series of four instance measures. Those instance similarity measures not only
address a spectrum of various meanings of similarity, but also present a series
of tradeoffs between computational cost and strictness of matching between
neighborhoods of nodes being compared. By extensive experiments and case
studies, we demonstrate the effectiveness of the proposed model and its
instances.

Social and Information Networks