# Regular Equivalence for Social Networks
## 2 Background and Context  
Random networks have a long history, starting with [PERSON] in the late 1950s [1]. The basic idea is to generate graphs with a fixed number of vertices and afterwards adding edges, with each possible edge effectively added to the graph with fixed probability \(p\). This approach immediately gives rise to interesting mathematical results but is inapt in modeling real-life networks [2]. Indeed, in many social networks, vertices can be grouped in relatively small clusters, a fact not observed in Erdos-Renyi random graphs. [PERSON] and [PERSON] [3] proposed a new model, which does exhibit this clustering property well and generates so-called small-world networks with weak links [4]. This model also sparked a large body of research and is successfully applied in many different contexts. However, networks generated through the procedure by [PERSON] and [PERSON] are not scale-free, a property that is sometimes observed in real-life networks: the distribution of vertex degrees in real-life networks might follow a power law [5; 6; 7], such that the probability that an arbitrary vertex has degree \(k\) is inversely proportional to \(k^{\alpha}\) for some \(\alpha>1\) called the scaling exponent. This behavior is modeled by the scale-free random network generator proposed by [PERSON] and [PERSON] [8], which applies an iterative growth process combined with edge addition through preferential attachment [9; 10]. Up to this date, the Barabasi-Albert generator, together with its many variations, is used throughout the literature as it is the most realistic scale-free network generator available [11; 12; 13].  
Equivalence relations, defined on the vertices of a graph, allow thorough network analysis through attaching positions or roles to vertices: the role of a vertex summarizes in some sense the structure of its neighborhood [14; 15]. Attaching roles is, in effect, nothing less than identifying similarity between vertices based on the structure of surrounding subnetworks. Structural equivalence [16] and automorphic equivalence [17] are thoroughly studied in the literature, but are mathematically oriented, being defined in terms of purely graph-related definitions like automorphisms. From a practical point of view, it is more interesting to investigate looser definitions of equivalence, such as regular equivalence [18; 19], which defines the role of a vertex not based on the set of its neighbors, but instead on the _roles_ of its neighbors. This circular definition allows for a more functional approach to attaching roles to vertices and is a practical way to match the common concept of a vertex having a role in a social context.  
In recent years, work has focused on theoretical investigations of social networks and the accompanying equivalences, focusing on axioms and logical characterizations [20; 21; 22], spectral methods [23], blocks/blockmodeling [24; 25; 26], and general analysis [27]. These approaches are in general much more mathematically oriented than ours, focusing on strict and rigorous scientific analysis. They have been generalized in many directions, e.g., fuzzy graphs [28], applying data-driven [29], and unsupervised role learning methods [30], some of these building upon massive amounts of data in contrast to our approach. New methods extend the ideas of equivalence through the use of additional measures when defining roles, like geodesic distance, modularity, community structure, and cliques [31; 32; 33], which make use of complimentary concepts beyond our definitions. Computationally, both theoretical considerations [34] as well as practical implementations have been presented [35; 36; 37; 38].