# Regular Equivalence for Social Networks
## 3 Materials and Methods
### Graphs and Equivalence Relations
: _Automorphic equivalence is more strict than regular equivalence_  
Proof. : We need to prove that \(\forall(u,v\in V):aut(u,v)\implies reg(u,v)\). Consider an automorphic equivalence relation \(R\) and consider any two vertices \(u,v\in V\) such that \(uRv\), that is, there exists an automorphism \(A:V\to V\) such that \(A(u)=v\). We now need to prove that the minimal regular coloring function attaches the same color to \(u\) and \(v\). We will first prove that the coloring corresponding to \(R\) is a regular coloring function. Consider the coloring function \(c:V\to V\) such that \(\forall(u,v\in V):uRv\iff c(u)=c(v)\). We will now prove that \(s_{u}=s_{v}\), that is, \(u\) and \(v\) have the same spectrum. Indeed, as \(A\) is an automorphism of the graph, every neighbor \(w_{u}\) of \(u\) will be mapped by \(A\) to some neighbor \(w_{v}\) of \(v\); formally, \(\forall(w_{u}\in V):\{u,w_{u}\}\in E\implies\exists(w_{v}\in V):A(w_{u})=w_{v }\wedge\{v,w_{v}\}\in E\). Thus, there exists an automorphism that maps \(w_{u}\) to \(w_{v}\), namely \(A\) itself; thus, \(w_{u}Rw_{v}\) and thus \(c(w_{u})=c(w_{v})\). We have thus proven that we can map any neighbor \(w_{u}\) of \(u\) to a neighbor \(w_{v}\) of \(v\) while preserving the color. This is tantamount to saying that the spectrum \(s_{u}\) is equal to the spectrum \(s_{v}\). Thus, the coloring function \(c\) is indeed a valid regular coloring function and \(c(u)=c(v)\). Now, although \(c\) is a valid regular coloring function, it still might be the case that it does not use the minimal number of colors; that is, it might not be a minimal regular coloring function. However, changing the regular coloring function \(c\) to a minimal regular coloring function \(c^{\prime}\) involves attaching the same color to vertices that previously had a different color, because their spectrum is the same (although no automorphism exists that maps them to each other). Thus, \(\forall(u,v\in V):reg(c)\wedge minreg(c^{\prime})\wedge(c(u)=c(v))\Rightarrow (c^{\prime}(u)=c^{\prime}(v))\). This concludes our proof, as we already demonstrated that \(c(u)=c(v)\). In order to demonstrate that automorphic equivalence and regular equivalence are different concepts, we need to provide a counterexample: a graph containing two vertices \(u\) and \(v\) that are regularly equivalent but not automorphically equivalent. Such a graph is more difficult to construct, and one example is given in Figure 1.  
As strictness is transitive, we immediately obtain that structural equivalence is more strict than regular equivalence. In practice, both structural equivalence and automorphic equivalence are very strict when applied to real-life social networks, having only very little vertices being equivalent to each other. Indeed, two vertices are structurally equivalent if and only if they have exactly the same set of neighbors (excluding themselves), which is something that rarely happens in real-life networks. Additionally, two vertices are automorphic equivalent if and only if the connections of the whole, global graph look exactly the same from their respective points of view, which is what automorphic equivalence expresses informally. Thus, little structure is discovered when investigating these networks using only structural equivalence and automorphic equivalence. In contrast, regular equivalence is much \"looser,\" allowing more structure to be discovered, with more vertieach other. Thus, regular equivalence is an important tool that allows us to gain additional insight in network structure. It does not require neighbors to be exactly the same vertices, as it is sufficient that neighbors have the same role. Additionally, it takes into account the local connection-structure of the vertices instead of the global structure, which is once more relaxing the condition for vertices to be equivalent. It is thus possible to investigate the structure without having to look at too fine-grained details, discovering meaningful relations or roles between the vertices.