Constrained Randomisation of Weighted Networks

Assessing the statistical significance of network patterns is crucial for understanding whether such patterns indicate the presence of interesting network phenomena, or whether they simply result from less interesting processes, such as nodal-heterogeneity. Typically, significance is computed with reference to a null model. While there has been extensive research into such null models for unweighted graphs, little has been done for the weighted case. This article suggests a n...

Graph randomization techniques play a crucial role in network analysis, allowing researchers to assess the statistical significance of observed network properties and distinguish meaningful patterns from random fluctuations. In this survey we provide an overview of the graph randomization methods available in the most popular software tools for network analysis. We propose a comparative analysis of popular software tools to highlight their functionalities and limitations. Thr...

The international trade network (ITN) has received renewed multidisciplinary interest due to recent advances in network theory. However, it is still unclear whether a network approach conveys additional, nontrivial information with respect to traditional international-economics analyses that describe world trade only in terms of local (first-order) properties. In this and in a companion paper, we employ a recently proposed randomization method to assess in detail the role tha...

Randomising networks using a naive `accept-all' edge-swap algorithm is generally biased. Building on recent results for nondirected graphs, we construct an ergodic detailed balance Markov chain with non-trivial acceptance probabilities for directed graphs, which converges to a strictly uniform measure and is based on edge swaps that conserve all in- and out-degrees. The acceptance probabilities can also be generalized to define Markov chains that target any alternative desire...

In statistical mechanical investigations on complex networks, it is useful to employ random graphs ensembles as null models, to compare with experimental realizations. Motivated by transcription networks, we present here a simple way to generate an ensemble of random directed graphs with, asymptotically, scale-free outdegree and compact indegree. Entries in each row of the adjacency matrix are set to be zero or one according to the toss of a biased coin, with a chosen probabi...

One of the most influential recent results in network analysis is that many natural networks exhibit a power-law or log-normal degree distribution. This has inspired numerous generative models that match this property. However, more recent work has shown that while these generative models do have the right degree distribution, they are not good models for real life networks due to their differences on other important metrics like conductance. We believe this is, in part, beca...

We develop a statistical theory to characterize correlations in weighted networks. We define the appropriate metrics quantifying correlations and show that strictly uncorrelated weighted networks do not exist due to the presence of structural constraints. We also introduce an algorithm for generating maximally random weighted networks with arbitrary $P(k,s)$ to be used as null models. The application of our measures to real networks reveals the importance of weights in a corr...

Networks are widely used in science and technology to represent relationships between entities, such as social or ecological links between organisms, enzymatic interactions in metabolic systems, or computer infrastructure. Statistical analyses of networks can provide critical insights into the structure, function, dynamics, and evolution of those systems. However, the structures of real-world networks are often not known completely, and they may exhibit considerable variation...

Represented as graphs, real networks are intricate combinations of order and disorder. Fixing some of the structural properties of network models to their values observed in real networks, many other properties appear as statistical consequences of these fixed observables, plus randomness in other respects. Here we employ the $dk$-series, a complete set of basic characteristics of the network structure, to study the statistical dependencies between different network propertie...

In the past two decades, significant advances have been made in understanding the structural and functional properties of biological networks, via graph-theoretic analysis. In general, most graph-theoretic studies are conducted in the presence of serious uncertainties, such as major undersampling of the experimental data. In the specific case of neural systems, however, a few moderately robust experimental reconstructions do exist, and these have long served as fundamental pr...