# Regular Equivalence for Social Networks
## 4 Results
### Experiments
#### 4.2.1 Random Barabasi-Albert Graphs
```
0:\(|V|\)
0:\(E|\)
1:\(|E|\)\(\leftarrow\)\(|V|\)
2:\(intervalSize\)\(\leftarrow\)\(|V|\)
3:while\(intervalSize\)\(>\) 0.01 \(*\)\(|V|\)
4:\(\_\)\(passed\)\(\leftarrow\) 0
5:for 1 to 100 do
6:\(G\)\(\leftarrow\)\(RandomBarabasiAlbert(|V|,|E|)\)
7:\(\_\)\(colorsRequired\)\(\leftarrow\)\(calcColors(G)\)
8:if\(colorsRequired\)\(\geq\)\(99\%*|V|\)then
9:\(\_\)\(passed\)\(\leftarrow\)\(\_\)\(\_\)\(1\)
10:endif
11:endfor
12:if\(passed\)\(<\)\(99\)then
13:\(|E|\)\(\leftarrow\)\(|E|+intervalSize\)
14:else
15:\(|E|\)\(\leftarrow\)\(|E|-intervalSize\)
16:endif
17:\(intervalSize\)\(\leftarrow\)\(intervalSize/2\)
18:endwhile
19:return\(|E|\)
```  
**Algorithm 2** Relation between \(|V|\) & \(|E|\) to have many colors  
In practice, the method has been parametrized by the number of experiments and the confidence-probability, and it moreover contains some shortcuts and optimizations for speed. Using this algorithm allows us to accurately estimate the relation between \(|V|\) and \(|E|\) to have a 99% chance upon a coloring with more than 99% \(*\)\(|V|\) colors. The algorithm has been executed 50 times, for various numbers of vertices up to \(10^{6}\). Results are shown in Figure 5.  
Strikingly, we obtain that the relation is linear, and careful investigation of the data reveals that the slope of the graph \(|E|=s|V|\) corresponds to about \(s\approx 1.89\). The above results were, as already mentioned, obtained using a Barabasi-Albert procedure that always generates random scale-free networks with scaling exponent \(\alpha=3\) (see Appendix A). However, these results can be generalized for other scaling exponents, through the use of the parameter \(c\) that is used in the Generalized Barabasi-Albert generator. This parameter \(c\) is related to the scaling exponent \(\alpha\) through the equation \(\alpha=2+\frac{1}{1+2c}\) and can be used to let \(\alpha\) range between 2 and 3 for the resulting generated network. Using different values for \(c\) with \(0\leq c\leq 5\), a number of experiments were run with corresponding values for \(\alpha\) such that \(2.09<\alpha\leq 3\). Most notably, the slope of the graph depicting the relation between  
Figure 5: The number of edges required to obtain almost all possible colors. \(|V|\) and \(|E|\) (when 99% of the colors is reached, cf. Figure 5) was recalculated for these different values of \(c\) and is plotted in Figure 6. Clearly, for \(c=0\), we obtain again the slope of Figure 5 itself, which was \(s\approx 1.89\). For larger values of \(c\), the value of the corresponding slope grows linearly. These results are striking and puzzling at first sight. However, they can be intuitively understood as follows (using the Barabasi-Albert algorithm from Appendix A). Both for \(c=0\) and \(c>0\), \"Step 2 edges\" are added to connect the new vertex to already existing vertices in the network growth process (see Step 2 in Appendix A). Moreover for \(c>0\), another \(c*m\) \"Step 3 edges\" are added to vertices that are already present in the network (see Step 3 in Appendix A). As these Step 3 edges are added proportionally to the product of the degrees of the vertices involved, they have a strong tendency to confirm the already existing vertex degree structures. Hence, if two vertices have similar roles in the growing network, this similarity tends to be more or less preserved while adding these \(c*m\) Step 3 edges (despite some random noise effects). This preservation effect is stronger for a Step 3 edge being added than for a Step 2 edge: in the latter case, only the degree weight of one vertex is taken into account, not the degree weight of the new vertex (all new vertices start with the same weight). Looking closely to Figure 6, we can derive from the slope of the graph that adding a single Step 3 edge has approximately the same disruptive effect as adding 0.67 Step 2 edges.