Local Roles from Random Walks

Any structural approach begins with a definition of social relations and, as a corollary, positions. In the social networks tradition, positions have been defined in terms of equivalences. In this paper, we relax the automorphic equivalence criterion not by weakening the criterion itself but by restricting its scope to each node's local surrounding. We define two nodes as locally---or random-walk---equivalent when the distributions of anonymous random walks (ARWs) launched from them coincide. Building on recent work in the anonymous-walk literature, we characterize what local structure these distributions encode and propose a two-step approach to detect nodes embedded in isomorphic local structures. Applications to Krackhardt's kite and Padgett's Florentine marriage network show that the proposed method recovers substantively meaningful positions---coinciding with automorphic classes when such classes exist, and yielding sensible groupings when no two nodes are exactly equivalent.