# Regular Equivalence for Social Networks
## 3 Materials and Methods
### Graphs and Equivalence Relations
Definition (Regular Coloring Function): A coloring function \(c\) is called regular (notation: \(reg(c)\)) if and only if  
\[\forall(u,v\in V):c(u)=c(v)\]  
\[\Longleftrightarrow\]  
\[\forall(n\in\mathbb{N}):|\{w\in V|\{u,w\}\in E\wedge c(w)=n\}|=|\{w\in V|\{v, w\}\in E\wedge c(w)=n\}|.\]  
Thus, a regular coloring function attaches the same color to two vertices if and only if they have exactly the same distribution of colors among their respective neighbors, which can also be written using spectra as \(\forall(u,v\in V):c(u)=c(v)\iff s_{u}=s_{v}\). Note that such a coloring always exists by giving each vertex a distinct color, which trivially fulfills the condition. We thus want to minimize the number of colors used in a regular coloring function, which gives rise to the fourth auxiliary definition. Definition (Minimal Regular Coloring Function): A regular coloring function \(c\) is called minimal (notation: \(minreg(c)\)) if and only if  
\[\forall(f:V\rightarrow\mathbb{N}):reg(f)\implies|\{n\in\mathbb{N}|\exists(u \in V):c(u)=n\}|\leq|\{n\in\mathbb{N}|\exists(u\in V):f(u)=n\}|.\]  
Thus, a minimal regular coloring function uses the minimal amount of colors among all regular coloring functions. Finally, we can now define regular equivalence. Definition (Regular Equivalence): Two vertices \(u\) and \(v\) are regular equivalent (notation: \(req(u,v)\)) if and only if  
\[\forall(c:V\rightarrow\mathbb{N}):minreg(c)\implies c(u)=c(v).\]  
Thus, \(u\) and \(v\) need to have the same color for all minimal regular coloring functions. The algorithm that is presented in this paper will prove that the minimal regular coloring is uniquely defined for a graph, and thus an equivalent definition could have been that two vertices are regular equivalent if and only if \(\exists(c:V\rightarrow\mathbb{N}):minreg(c)\wedge c(u)=c(v)\). We are aware that other definitions of regular equivalence are used throughout the literature, but for the entirety of this paper we will adhere to the one defined above. As we have seen, multiple equivalence relations can be defined upon a graph. These different relations have interdependencies to each other, in the sense that some equivalence relations are more strict than others. Definition (Strictness): For two equivalence relations \(R_{1}\) and \(R_{2}\), we say that \(R_{1}\) is more strict than \(R_{2}\) (notation: \(R_{1}\prec R_{2}\)) if and only if  
\[\forall(u,v\in V):uR_{1}v\implies uR_{2}v.\]  
It is now possible to prove that structurally equivalent vertices are also automorphically equivalent, but not necessarily vice versa. Additionally, automorphically equivalent vertices are regularly equivalent, but not necessarily vice versa. Stated otherwise, there is a clear ordering between the 3 equivalence definitions, which we now demonstrate through the following two proofs. We start by proving the relation between structural and automorphic equivalence. Theorem 1: _Structural equivalence is more strict than automorphic equivalence_  
Proof: Consider a structural equivalence relation \(R\). It is sufficient to demonstrate that an automorphism of the graph exists with \(A(u)=v\) and \(A(v)=u\), given \(uRv\). Given that the neighbors of \(u\) and \(v\) are the same, possibly excepting \(u\) and \(v\) themselves, it is trivial to take the automorphism \(A:V\to V\) such that  
\[A(w)= \begin{cases}v&\text{if }w=u,\\ u&\text{if }w=v,\\ w&\text{otherwise}.\end{cases} \]  
In order to demonstrate that structural equivalence and automorphic equivalence are different concepts, we need to provide a counterexample: a graph containing two vertices \(u\) and \(v\) that are automorphically equivalent but not structurally equivalent. This can be done easily. A graph with four vertices which are linearly connected to each other in a single chain is sufficient, as the two outer vertices have different neighbors but are still automorphically equivalent. We continue by proving the relation between automorphic and regular equivalence. **Theorem 2**.