Structure matters: Assessing the statistical significance of network topologies

Abstract

Network analysis has found widespread utility in many research areas. However, assessing the statistical significance of observed relationships within networks remains a complex challenge. Traditional node permutation tests are often insufficient in capturing the effect of changing network topology by creating reliable null distributions. We propose two randomization alternatives to address this gap: random rewiring and controlled rewiring. These methods incorporate changes in the network topology through edge swaps. However, controlled rewiring allows for more nuanced alterations of the original network than random rewiring. In this sense, this paper introduces a novel evaluation tool, the Expanded Quadratic Assignment Procedure (EQAP), designed to calculate a specific p-value and interpret statistical tests with enhanced precision. The combination of EQAP and controlled rewiring provides a robust network comparison and statistical analysis framework. The methodology is exemplified through two real-world examples: the analysis of an organizational network structure, illustrated by the Enron-Email dataset, and a social network case, represented by the UK Faculty friendship network. The utility of these statistical tests is underscored by their capacity to safeguard researchers against Type I errors when exploring network metrics dependent on intricate topologies.

Fig 1. Limitations of the Quadratic Assignment Procedure scheme.

(a) Two nodes of the original network are permuted, while the edges’ structure remains unchanged. (b) The adjacency matrices of the original and the modified networks are calculated. (c) The objective function is calculated using the adjacency matrices. The optimal permutation that minimizes it is the original network. (d) For each simulation, the p-value equals 1. When all p-values for the different simulations are aggregated, the p-value decays by 1/n.

Fig 2. Randomization alternatives scheme.

In all examples, the thickness of an edge represents its betweenness centrality. (a) The random rewiring alternative swaps the edges by randomly selected pairs while nodes remain the same. The edges betweenness centrality is still altered. (b) Finally, in the controlled rewiring alternative, the edges to be rewired are selected according to a metric and the edge betweenness centrality is less altered.

Fig 3

(a) Average edge betweenness centrality of the Fig 2 network example for 100 simulations along three controlled rewirings (orange) and three random rewirings (dark blue). Means are plotted in lines, and the standard deviation in shadowed areas (b) p-value by performing the Expanded Quadratic Assignment Procedure of the Fig 2 network example for 100 simulations along different numbers of rewirings. Means are plotted in lines, and the standard deviation is in shadowed areas.

Fig 4. Average edge betweenness centrality of different random Power Law network for 100 simulations along different numbers of rewirings.

Means are plotted in lines, and the standard deviation is in shadowed areas.

Fig 5. Expanded Quadratic Assignment Procedure scheme.

The following pipeline is repeated for several simulations and modifications: (a) The first step is to modify the original network with the explained methods in Fig 2, i.e., random rewiring or controlled rewiring. In this scheme, we show the controlled rewiring example. (b) The second step is to build the adjacency matrices of the original and the modified networks. We will use them to calculate the objective function. (c) The third step is to measure the described topological metrics to assess the impact of the modifications and the objective function for both networks. (d) Finally, we can calculate the p-value by comparing the minimum of the objective function of the modified network to the value for the original one. All p-values for the different simulations are aggregated at last to build the results chart.

Fig 6. p-value by performing the Expanded Quadratic Assignment Procedure of different random Power Law networks for 100 simulations along different numbers of rewirings.

Means are plotted in lines, and the standard deviation is in shadowed areas.

Fig 7

p-value by performing the Expanded Quadratic Assignment Procedure for the Enron-Email network (a), the UK Faculty network (b) networks. For both graphs, the solid line represents the mean after 100 simulations, and the shadowed band shows the standard deviation.

Fig 8. Topological metrics of the Enron-Email network for 100 simulations along 1,500 controlled rewirings (orange), 1,500 random rewirings (dark blue).

Averages are plotted in lines and the standard deviation in shadowed areas.

Fig 9. Topological metrics of the UK Faculty network for 100 simulations along 400 controlled rewirings (orange), 400 random rewirings (dark blue).

Averages are plotted in lines and the standard deviation in shadowed areas.