A Family of Algorithms for Computing Consensus about Node State from Network Data

Biological and social networks are composed of heterogeneous nodes that contribute differentially to network structure and function. A number of algorithms have been developed to measure this variation. These algorithms have proven useful for applications that require assigning scores to individual nodes–from ranking websites to determining critical species in ecosystems–yet the mechanistic basis for why they produce good rankings remains poorly understood. We show that a unifying property of these algorithms is that they quantify consensus in the network about a node''s state or capacity to perform a function. The algorithms capture consensus by either taking into account the number of a target node''s direct connections, and, when the edges are weighted, the uniformity of its weighted in-degree distribution (breadth), or by measuring net flow into a target node (depth). Using data from communication, social, and biological networks we find that that how an algorithm measures consensus–through breadth or depth– impacts its ability to correctly score nodes. We also observe variation in sensitivity to source biases in interaction/adjacency matrices: errors arising from systematic error at the node level or direct manipulation of network connectivity by nodes. Our results indicate that the breadth algorithms, which are derived from information theory, correctly score nodes (assessed using independent data) and are robust to errors. However, in cases where nodes “form opinions” about other nodes using indirect information, like reputation, depth algorithms, like Eigenvector Centrality, are required. One caveat is that Eigenvector Centrality is not robust to error unless the network is transitive or assortative. In these cases the network structure allows the depth algorithms to effectively capture breadth as well as depth. Finally, we discuss the algorithms'' cognitive and computational demands. This is an important consideration in systems in which individuals use the collective opinions of others to make decisions.     

Implications of incomplete networks on estimation of landscape genetic connectivity

Understanding processes and landscape features governing connectivity among individuals and populations is fundamental to many ecological, evolutionary, and conservation questions. Network analyses based on graph theory are emerging as a prominent approach to quantify patterns of connectivity with more recent applications in landscape genetics aimed at understanding the influence of landscape features on gene flow. Despite the strong conceptual framework of graph theory, the effect of incomplete networks resulting from missing nodes (i.e. populations) and their genetic connectivity network interactions on landscape genetic inferences remains unknown. We tested the violation of this assumption by subsampling from a known complete network of breeding ponds of the Columbia Spotted Frog (Rana luteiventris) in the Bighorn Crags (Idaho, USA). Variation in the proportion of missing nodes strongly influenced node-level centrality indices, whereas indices describing network-level properties were more robust. Overall incomplete networks combined with network algorithm types used to link nodes appears to be critical to the rank-order sensitivity of centrality indices and to the Mantel-based inferences made regarding the role of landscape features on gene flow. Our findings stress the importance of sampling effort and topological network structure as they both affect the estimation of genetic connectivity. Given that failing to account for uncertainty on network outcomes can lead to quantitatively different conclusions, we recommend the routine application of sensitivity analyses to network inputs and assumptions.     

Social network structure and parasite infection patterns in a territorial reptile, the tuatara (Sphenodon punctatus)

We investigated whether the parasite load of an individual could be predicted by its position in a social network. Specifically, we derived social networks in a solitary, territorial reptile (the tuatara, Sphenodon punctatus), with links based on the sharing of space, not necessarily synchronously, in overlapping territories. Tuatara are infected by ectoparasitic ticks (Amblyomma sphenodonti), mites (Neotrombicula spp.) and a blood parasite (Hepatozoon tuatarae) which is transmitted by the tick. We recorded the location of individual tuatara in two study plots twice daily during the mating season (March) in 2 years (2006 and 2007) on Stephens Island, New Zealand. We constructed weighted, directed networks to represent pathways for parasite transmission, where nodes represented individual tuatara and edges connecting the nodes represented the extent of territory overlap among each pair of individuals. We considered a network-based hypothesis which predicted that the in-strength of individuals (the sum of edge weights directed towards a node) in the derived network would be positively related to their parasite load. Alternatively, if the derived social network did not reflect actual parasite transmission, we predicted other factors such as host sex, size or territory size may better explain variation in parasite infection patterns. We found clear positive relationships between the in-strength of tuatara and their tick loads, and infection patterns with tick-borne blood parasites. In particular, the extent that individuals were connected to males in the network consistently predicted tick loads of tuatara. However, mite loads of tuatara were significantly related to host sex, body size and territory size, and showed little association with network measures. The results suggest that the pathway of transmission of parasites through a population will depend on the transmission mechanism of the parasite, but that social networks provide a powerful predictive tool for some parasites.     

Weighting,scale dependence and indirect effects in ecological networks: A comparative study

We studied the importance of weighting in ecological interaction networks. Fifty-three weighted interaction networks were analyzed and compared to their unweighted alternatives, based on data taken from two standard databases. We used five network indices, each with weighting and unweighting options, to characterize the positional importance of nodes in these networks. For every network, we ranked the nodes according to their importance values, based on direct and indirect indices and then we compared the rank order of coefficients to reveal potential differences between network types and between indices. We found that (1) weighting affects node ordering very seriously, (2) food webs fundamentally differ from other network types in this respect, (3) direct and indirect indices provide fairly different results but indirect effects are similar if longer than two steps, and (4) the effect of weighting depends on the number of network nodes in case of direct interactions only. We concluded that the importance of interaction weights may depend on the evolutionary stability of interaction types.     

Multi-Scale Analysis of the European Airspace Using Network Community Detection

We show that the European airspace can be represented as a multi-scale traffic network whose nodes are airports, sectors, or navigation points and links are defined and weighted according to the traffic of flights between the nodes. By using a unique database of the air traffic in the European airspace, we investigate the architecture of these networks with a special emphasis on their community structure. We propose that unsupervised network community detection algorithms can be used to monitor the current use of the airspace and improve it by guiding the design of new ones. Specifically, we compare the performance of several community detection algorithms, both with fixed and variable resolution, and also by using a null model which takes into account the spatial distance between nodes, and we discuss their ability to find communities that could be used to define new control units of the airspace.     

The Rücker–Markov invariants of complex Bio-Systems: Applications in Parasitology and Neuroinformatics

Rücker's walk count (WC) indices are well-known topological indices (TIs) used in Chemoinformatics to quantify the molecular structure of drugs represented by a graph in Quantitative structure–activity/property relationship (QSAR/QSPR) studies. In this work, we introduce for the first time the higher-order (kth order) analogues (WC_k) of these indices using Markov chains. In addition, we report new QSPR models for large complex networks of different Bio-Systems useful in Parasitology and Neuroinformatics. The new type of QSPR models can be used for model checking to calculate numerical scores S(L_ij) for links L_ij (checking or re-evaluation of network connectivity) in large networks of all these fields. The method may be summarized as follows: (i) first, the WC_k(j) values are calculated for all jth nodes in a complex network already created; (ii) A linear discriminant analysis (LDA) is used to seek a linear equation that discriminates connected or linked (L_ij = 1) pairs of nodes experimentally confirmed from non-linked ones (L_ij = 0); (iii) The new model is validated with external series of pairs of nodes; (iv) The equation obtained is used to re-evaluate the connectivity quality of the network, connecting/disconnecting nodes based on the quality scores calculated with the new connectivity function. The linear QSPR models obtained yielded the following results in terms of overall test accuracy for re-construction of complex networks of different Bio-Systems: parasite–host networks (93.14%), NW Spain fasciolosis spreading networks (71.42/70.18%) and CoCoMac Brain Cortex co-activation network (86.40%). Thus, this work can contribute to the computational re-evaluation or model checking of connectivity (collation) in complex systems of any science field.     

Harmonic analysis of Boolean networks: determinative power and perturbations

Consider a large Boolean network with a feed forward structure. Given a probability distribution on the inputs, can one find, possibly small, collections of input nodes that determine the states of most other nodes in the network? To answer this question, a notion that quantifies the determinative power of an input over the states of the nodes in the network is needed. We argue that the mutual information (MI) between a given subset of the inputs X={X₁,...,X_n} of some node i and its associated function f_i(X) quantifies the determinative power of this set of inputs over node i. We compare the determinative power of a set of inputs to the sensitivity to perturbations to these inputs, and find that, maybe surprisingly, an input that has large sensitivity to perturbations does not necessarily have large determinative power. However, for unate functions, which play an important role in genetic regulatory networks, we find a direct relation between MI and sensitivity to perturbations. As an application of our results, we analyze the large-scale regulatory network of Escherichia coli. We identify the most determinative nodes and show that a small subset of those reduces the overall uncertainty of the network state significantly. Furthermore, the network is found to be tolerant to perturbations of its inputs.     

A waterfowl seed-dispersal network from the Neotropical region is nested and modular

Seed dispersal by vertebrates is fundamental for the persistence of plant species, forming networks of interactions that are often nested and modular. Networks involving angiosperms and frugivorous birds are relatively well-studied in the Neotropical region, but there are no previous studies of networks involving waterbirds. Here, we describe the structure of a Neotropical waterfowl seed-dispersal network and identify the species that have an important role for the network structure. We used information on 40 plant taxa found in fecal samples of five common waterfowl species to calculate the nestedness (NODF), weighted nestedness (WNODF), modularity, and weighted modularity of the network. We found that the network was nested, with yellow-billed teal showing the highest contribution both to nestedness and weighted nestedness. Twenty-four plant species contributed positively to weighted nestedness, with Salzmann's mille graines presenting the highest influence both to nestedness and weighted nestedness. The network was modular, but the weighted modularity was not significant. These results need to be considered with caution due to incomplete interaction sampling for two species. Ringed teal, Brazilian teal, and yellow-billed teal were considered hub modular species. Among plants, beak sedges and water snowflake were considered modular hub species, while Salzmann's mille graines and spikerush were network connectors. The structure of this Neotropical waterbird seed-dispersal network differed from the only previous waterfowl network study, from Europe, which found similar level of nestedness but no significant modularity. We include several possible explanations for this discrepancy and identified priorities for future research into waterbird–plant interaction networks. Abstract in Portuguese is available with online material.