Measuring Network Features under Uncertainty

We propose a new methodological framework for data-based network reconstruction, which accounts for the uncertainty about the connectivity [1]. The nodes of the networks considered in our study represent interacting dynamical systems which are the components of a complex system. The network reconstruction problem is to derive the topological structure of the interactions between the components, relying on temporal data produced by each component. A wealth of methods has been developed to reconstruct the network connectivity using observations about the component’s dynamic (see e.g. [2]). Generally, the presence of a link between components is evaluated using a connectivity metric (e.g. correlation, mutual information) which results in a functional network structure. Typically, a threshold on the connectivity level is used to filter the unlikely links, obtaining a particular structure. The choice of the threshold is usually guided by an arbitrary heuristic. Preferably, using more sophisticated statistical analysis, a set of p-value are computed to evaluate the significance of the connectivity with respect to null-models. However, this process still incurs in the problem of multiple testing [3]. We discuss the impact of these issues on some important network analysis.
In this work, we propose an alternative probabilistic approach which overcomes these limitations and offers a different perspective on structural connectivity. The fundamental topological descriptors are replaced, even at the level of single nodes, with appropriate probability distributions. Employing a Bayesian procedure we derive for every i and j the posterior probability pij that the node i is linked to the node j, given the p-value from the traditional analysis. The probabilities pij can be arranged in the adjacency matrix A of the network. Although this matrix appears as a weighted adjacency matrix with values in the interval [0, 1], the entries are not weights, but they represent the existence probability of the corresponding edge. The result is a complete graph whose edges might exist with a certain probability. Therefore, the observed complex network is an actual realization of the possible configurations described by the “fuzzy network” model. Under this probabilistic perspective, also the network descriptors must be redefined as random variables. A natural way to recover the descriptive information is to consider the whole distribution or a suitable statistic. For example, it doesn’t make sense to ask for the degree of a node, because each node can have all possible degrees at the same time, with a certain probability. Consequently, we have defined the “fuzzy” counterpart of some structural descriptors such as the node degree and the network degree distribution, the distance, the clustering coefficient, and the connectivity. For each of them, we present the analytical probability distribution and the main statistics (see Figure 1 for an example). We applied this framework to various well-known real and synthetic networks and compared the results with the before mentioned reconstruction techniques.
The method proposed, is able to reveal the structural features of a complex network from time-series data, without the explicit reconstruction of the network and accounting for the uncertainty in the connectivity.