The null setting

First, we simulate random graphs with the function igraph::erdos.renyi.game. This function generates random graphs with a skewed degree distribution, so called Erdős-Rényi graphs. Such graphs have two parameters: the number of nodes \(n\) and the probability of connexion \(p\).

An Erdős-Rényi graph with parameters \(n=20\) and \(p=0.1\).

The distribution of the degrees of 100 Erdős-Rényi graphs with parameters \(n=20\) and \(p=0.1\).

More precisely, we simulate two sets of \(N = 30\) independent graphs, each graph being an Erdős-Rényi graph with parameters \(n=20\) and \(p=0.1\). Once these two sets are generated, we compute for each graph its adjacency matrix.11 The adjacency matrix of an unweighted graph is a square binary matrix where the 1s describes which nodes are connected to one another. Each adjacency matrix is then double centered.

In the end, we obtain from this process two sets of \(N=30\) square matrices, each one of this matrix describes the double-centered distance matrix of a sorting dataset. In this setting, any two sorting tasks are independent from one another.

Finally, we represent the RV matrix of the double-centered distances between the first set (rows) and the second set (columns).

Notice that the RV coefficients range from -0.186 to 0.31.

The non-null setting

For the non null setting, we begin by choosing two “structures”: one for the first set and one for the second set.

The two structures, noted \(\mathbf S_1\) and \(\mathbf S_2\) are shown on the right: \[ \mathbf S_1 = \left[ \begin{array}{cc} \mathbf B_1 & \mathbf 0 \\ \mathbf 0 & \mathbf B_1 \end{array}\right] \text{ and } \mathbf S_2 = \left[ \begin{array}{ccc} \mathbf B_2 & \mathbf 0 & \mathbf 0 \\ \mathbf 0 & \mathbf B_2 & \mathbf 0 \\ \mathbf 0 & \mathbf 0 & \mathbf B_2\end{array}\right], \] where \(\mathbf B_1\) and \(\mathbf B_2\) are “blocks”, here correlation matrices with the off-diagonal correlations being random positive values following a uniform law \(\mathcal U(0.5, 0.8)\).

These matrices are then transformed into adjacency matrices and into undirected graphs. The two sets of undirected graphs are displayed below (on the left the 30 graphs of set 1 and on the right the 30 graphs of set 2). Most graphs of each set share the same structure (here, the same connected components), with a certain variance. Two connected components of the second set of graphs are shared with the first set, while only one connected component is unique to the second set. The colors are used to highlight the connected components encoded by the “blocks” (\(\mathbf B_1\) and \(\mathbf B_2\)) in the original structure matrices.

Finally, we compute for this non-null setting the RV matrix between the double centered adjacency matrices of the two sets of graphs.