# Regular Equivalence for Social Networks
## 4 Results
### Experiments
#### 4.2.2 Real-Life Social Networks  
The previous section contained experiments on the behavior of randomly generated networks w.r.t. regular equivalence. We now look at regular equivalence for real-life social networks. To that aim, we downloaded some large networks from the Stanford SNAP data collection [40], which is maintained for the Stanford Network Analysis Project. It is a collection of more than 50 large network datasets with sizes up to tens of millions of vertices and edges. Social networks, web graphs, road networks, internet networks, citation networks, collaboration networks, and communication networks are all represented. We downloaded the following networks for use in our experiments, in order of increasing number of vertices. * CA-AstroPh: This graph represents a collaboration network on astrophysics obtained from arXiv. It covers scientific collaborations between authors that submitted papers within the Astrophysics category. If two authors \(u\) and \(v\) co-authored a paper, the graph will contain an (undirected) edge \(\{u,v\}\). It will thus contain a small complete subgraph for every paper in the database, as all authors on a single paper always induce a complete graph for these authors. * CA-CondMat: This dataset corresponds to the collaboration network obtained from arXiv within the Condense Matter Physics category. It was derived in a similar way as the CA-AstroPh network. It has about 23% more vertices than CA-AstroPh but only about half the number of edges. * Email-Enron: This is an email-communication network, covering email communication within the company Enron, and consisting of about half a million emails. It was disclosed to the public by the  
Figure 6: Relation between scaling parameter \(c\) and the slope \(s\). Federal Energy Regulatory Commission during the investigation into the Enron scandal in 2001. Vertices represent email-addresses, and an undirected edge \(\{u,v\}\) is added to the graph if either \(u\) or \(v\) sent at least one email to \(v\) or \(u\), respectively. Thus, the original direction of communication is not available in the dataset. * Slashdot0811: This dataset represents a social network derived from the website Slashdot, which is a news website focusing on technology-related subjects. Users can post messages and tag each other as friend or foe. They are represented by vertices and the tags are represented as undirected edges. No distinction is made between friend-tags and foe-tags, so an edge \(\{u,v\}\) can have four different meanings. This explains the reduction in \(|E|\) compared to the original dataset. * DBLP: The DBLP-dataset is derived from the DBLP-database maintained by the University of Trier, which contains a computer science bibliography with a comprehensive list of academic research papers in different subjects all related to computer science. The dataset represents a collaboration network where two authors (vertices) are connected through an (undirected) edge if and only if they co-authored at least one paper. * LiveJournal: This dataset was derived from LiveJournal, a website community allowing free blogs. People can befriend each other and form groups together. We consider being friends/foes a symmetric relation, and represent users as vertices and their friendships as undirected edges. The networks were processed in order to prepare them for analysis by our software. This involved, among other things, ensuring edges are undirected, removing double edges, and checking for inconsistencies. The resulting networks that were used for the rest of the analysis are listed in Table 1.  
After calculation of the actual number of colors required in the minimal regular coloring of these real-life social networks, it was obtained that they required only a relatively small fraction of colors. Results are shown in Table 2. In this table, we will denote the number of colors used in the minimal regular coloring as \(|C|\).