# Regular Equivalence for Social Networks
## 3 Materials and Methods
### Graphs and Equivalence Relations  
In order to present our work unambiguously, we first need to introduce some classic concepts. This is necessary as, in literature, multiple (slightly different) definitions appear for these notions, sometimes leading to different conclusions which might turn out to be important to the discussion. Definition (Graph/Network): We define a graph \(G=(V,E)\) to consist of a set of vertices \(V\) and a set of edges \(E\). An edge \(e=\{u,v\}\) connects the vertices \(u\in V\) and \(v\in V\) and is undirected. Throughout this paper, the vertices will be divided in groups, following several definitions all related to the concept of an equivalence relation from set theory. Definition (Equivalence Relation): An equivalence relation \(R:V\times V\to BOOL\) is a binary relation that is reflexive, symmetric, and transitive. As is commonly known, an equivalence relation in \(V\) always induces a partition of \(V\), which puts the vertices together in subsets of \(V\) such that every vertex is included in exactly one such subset. We write \(uRv\) for two vertices \(u\) and \(v\) that are related to each other through \(R\); they will be contained in the same subset of \(V\) in the partition of \(V\) induced by \(R\). In literature investigating the roles and relations of vertices in graphs or networks, one often encounters three specific equivalence relations, namely structural equivalence, automorphic equivalence, and regular equivalence, the latter having slightly differing definitions depending on the source [2, 21, 22, 36]. Definition (Structural Equivalence): Two vertices \(u\) and \(v\) are structurally equivalent (notation: \(seq(u,v)\)) if and only if  
\[\forall(w\in V-\{u,v\}):\{u,w\}\in E\iff\{v,w\}\in E.\]  
That is, \(seq(u,v)\) holds if and only if \(u\) and \(v\) have exactly the same set of neighbors, not counting the vertices \(u\) and \(v\) themselves. It is necessary to exclude \(u\) and \(v\) because otherwise two connected vertices could never be structurally equivalent. To define automorphic equivalence, we first need to define the concept of an automorphism. Definition (Automorphism): An automorphism of a graph is a permutation of vertices \(A:V\to V\) (notation: \(aut(A)\)) such that edges are mapped to edges:  
\[\forall(u,v\in V):\{u,v\}\in E\iff\{A(u),A(v)\}\in E.\]  
Thus, an automorphism of a graph is a (possibly trivial) isomorphism of the graph and itself, hence the name. Definition (Automorphic Equivalence): Two vertices \(u\) and \(v\) are automorphically equivalent (notation: \(aeq(u,v)\)) if and only if  
\[\exists(A:V\to V):aut(A)\wedge A(u)=v.\]  
Thus, \(aeq(u,v)\) holds if and only if there exists an automorphism \(A\) that maps \(u\) to \(v\). The third type of equivalence relation will play an important role in this paper and is called regular equivalence. In contrast with the other two equivalence relations that were discussed above, there is no single definition of regular equivalence agreed upon in the literature. In order to define our interpretation of regular equivalence exactly, we first need to introduce additional concepts. Firstly, we have the concept of a coloring function \(c:V\to\mathbb{N}\) that attaches a color (natural number) to every vertex of the graph. Coloring functions are used throughout graph theory in various contexts, like the chromatic number of a graph. Secondly, we also need the concept of a spectrum. Definition (Spectrum): The spectrum of a vertex \(u\) under the coloring function \(c\) is the function  
\[s_{u}:\mathbb{N}\to\mathbb{N}:n\mapsto|\{v\in V|\{u,v\}\in E\wedge c(v)=n\}|.\]Thus, the spectrum of a vertex is a function that takes a color (natural number) as argument and returns the number of neighbors of the vertex with that color. Thirdly, we are now ready to define a regular coloring function.