Approximate regular equivalence by partition refinement

Regular equivalence aims to identify nodes that have links to nodes that are themselves equivalent, and is considered to capture key relational properties in networks. Exact equivalences are notoriously difficult to emerge in real-world networks because of the rather stringent criteria required. This has motivated the development of approximate approaches, which, however, do not scale well to large networks. In this paper, we present a new method to compute approximate regular equivalences for weighted networks based on a partition refinement algorithm. This is parameterized by a tolerance that determines the extent to which two nodes may be deemed equivalent. We also show an asymptotic result for networks with power-law distribution that analytically provides a partition of approximately equivalent nodes. Using a number of benchmark networks, we show that our method outperforms the state of the art in terms of precision and running time. When the asymptotic partition is used to initialize the partition refinement algorithm for real-world networks, it avoids the problem of aggressive clustering that affects binary networks.