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 challenge is that in different applications we may need different measurements that manifest different meanings of similarity. Furthermore, we often want to make trade-offs between specificity of neighborhood matching and efficiency. 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 trade-offs 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.
Abstract In this paper we present two algorithms for computing the extent of regular equivalence among pairs of nodes in a network. The first algorithm, REGE, is well known, but has not previously been described in the literature. The second algorithm, CATREGE, is new. Whereas REGE is applicable to quantitative data, CATREGE is used for categorical data. For binary data, either algorithm may be used, though the CATREGE algorithm is significantly faster and its output similarity coefficients have better metric properties. The CATREGE algorithm is also useful pedagogically, because it is easier to grasp. Abstract An efficient method for computing role (automorphic) equivalences in large networks is described. Numerical signatures (real numbers) are generated for each node. Role-identical nodes share common numerical signatures. The decomposition of the node set into classes by reference to the numerical signatures helps determine the automorphic equivalence classes of a network. The technique is applicable to symmetric and directed networks, and to graphs with multiple link types. The algorithm is linear with respect to the number of links in the network. Its theoretical foundation exploits properties of transcendental numbers. The aim of this paper is to understand the interrelations among relations within concrete social groups. Social structure is sought, not ideal types, although the latter are relevant to interrelations among relations. From a detailed social network, patterns of global relations can be extracted, within which classes of equivalently positioned individuals are delineated. The global patterns are derived algebraically through a ‘functorial’ mapping of the original pattern. Such a mapping (essentially a generalized homomorphism) allows systematically for concatenation of effects through the network. The notion of functorial mapping is of central importance in the ‘theory of categories,’ a branch of modern algebra with numerous applications to algebra, topology, logic. The paper contains analyses of two social networks, exemplifying this approach.