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.     

Effects of Edge Directions on the Structural Controllability of Complex Networks

Recent advances indicate that assigning or reversing edge direction can significantly improve the structural controllability of complex networks. For directed networks, approaching the optimal structural controllability can be achieved by detecting and reversing certain “inappropriate” edge directions. However, the existence of multiple sets of “inappropriate” edge directions suggests that different edges have different effects on optimal controllability—that is, different combinations of edges can be reversed to achieve the same structural controllability. Therefore, we classify edges into three categories based on their direction: critical, redundant and intermittent. We then investigate the effects of changing these edge directions on network controllability, and demonstrate that the existence of more critical edge directions implies not only a lower cost of modifying inappropriate edges but also better controllability. Motivated by this finding, we present a simple edge orientation method aimed at producing more critical edge directions—utilizing only local information—which achieves near optimal controllability. Furthermore, we explore the effects of edge direction on the controllability of several real networks.     

Geographies of an Online Social Network

How is online social media activity structured in the geographical space? Recent studies have shown that in spite of earlier visions about the “death of distance”, physical proximity is still a major factor in social tie formation and maintenance in virtual social networks. Yet, it is unclear, what are the characteristics of the distance dependence in online social networks. In order to explore this issue the complete network of the former major Hungarian online social network is analyzed. We find that the distance dependence is weaker for the online social network ties than what was found earlier for phone communication networks. For a further analysis we introduced a coarser granularity: We identified the settlements with the nodes of a network and assigned two kinds of weights to the links between them. When the weights are proportional to the number of contacts we observed weakly formed, but spatially based modules resemble to the borders of macro-regions, the highest level of regional administration in the country. If the weights are defined relative to an uncorrelated null model, the next level of administrative regions, counties are reflected.     

Unification of the Globally Distributed Spindle-Shaped Viruses of the Archaea

Viruses with spindle-shaped virions are abundant in diverse environments. Over the years, such viruses have been isolated from a wide range of archaeal hosts. Evolutionary relationships between them remained enigmatic, however. Here, using structural proteins as markers, we define familial ties among these “dark horses” of the virosphere and segregate all spindle-shaped viruses into two distinct evolutionary lineages, corresponding to Bicaudaviridae and Fuselloviridae. Our results illuminate the utility of structure-based virus classification and bring additional order to the virosphere.     

Dense Percolation in Large-Scale Mean-Field Random Networks Is Provably “Explosive”

Recent reports suggest that evolving large-scale networks exhibit “explosive percolation”: a large fraction of nodes suddenly becomes connected when sufficiently many links have formed in a network. This phase transition has been shown to be continuous (second-order) for most random network formation processes, including classical mean-field random networks and their modifications. We study a related yet different phenomenon referred to as dense percolation, which occurs when a network is already connected, but a large group of nodes must be dense enough, i.e., have at least a certain minimum required percentage of possible links, to form a “highly connected” cluster. Such clusters have been considered in various contexts, including the recently introduced network modularity principle in biological networks. We prove that, contrary to the traditionally defined percolation transition, dense percolation transition is discontinuous (first-order) under the classical mean-field network formation process (with no modifications); therefore, there is not only quantitative, but also qualitative difference between regular and dense percolation transitions. Moreover, the size of the largest dense (highly connected) cluster in a mean-field random network is explicitly characterized by rigorously proven tight asymptotic bounds, which turn out to naturally extend the previously derived formula for the size of the largest clique (a cluster with all possible links) in such a network. We also briefly discuss possible implications of the obtained mathematical results on studying first-order phase transitions in real-world linked systems.     

Edge Principal Components and Squash Clustering: Using the Special Structure of Phylogenetic Placement Data for Sample Comparison

Principal components analysis (PCA) and hierarchical clustering are two of the most heavily used techniques for analyzing the differences between nucleic acid sequence samples taken from a given environment. They have led to many insights regarding the structure of microbial communities. We have developed two new complementary methods that leverage how this microbial community data sits on a phylogenetic tree. Edge principal components analysis enables the detection of important differences between samples that contain closely related taxa. Each principal component axis is a collection of signed weights on the edges of the phylogenetic tree, and these weights are easily visualized by a suitable thickening and coloring of the edges. Squash clustering outputs a (rooted) clustering tree in which each internal node corresponds to an appropriate “average” of the original samples at the leaves below the node. Moreover, the length of an edge is a suitably defined distance between the averaged samples associated with the two incident nodes, rather than the less interpretable average of distances produced by UPGMA, the most widely used hierarchical clustering method in this context. We present these methods and illustrate their use with data from the human microbiome.     

Cooperation prevails when individuals adjust their social ties

Conventional evolutionary game theory predicts that natural selection favours the selfish and strong even though cooperative interactions thrive at all levels of organization in living systems. Recent investigations demonstrated that a limiting factor for the evolution of cooperative interactions is the way in which they are organized, cooperators becoming evolutionarily competitive whenever individuals are constrained to interact with few others along the edges of networks with low average connectivity. Despite this insight, the conundrum of cooperation remains since recent empirical data shows that real networks exhibit typically high average connectivity and associated single-to-broad–scale heterogeneity. Here, a computational model is constructed in which individuals are able to self-organize both their strategy and their social ties throughout evolution, based exclusively on their self-interest. We show that the entangled evolution of individual strategy and network structure constitutes a key mechanism for the sustainability of cooperation in social networks. For a given average connectivity of the population, there is a critical value for the ratio W between the time scales associated with the evolution of strategy and of structure above which cooperators wipe out defectors. Moreover, the emerging social networks exhibit an overall heterogeneity that accounts very well for the diversity of patterns recently found in acquired data on social networks. Finally, heterogeneity is found to become maximal when W reaches its critical value. These results show that simple topological dynamics reflecting the individual capacity for self-organization of social ties can produce realistic networks of high average connectivity with associated single-to-broad–scale heterogeneity. On the other hand, they show that cooperation cannot evolve as a result of “social viscosity” alone in heterogeneous networks with high average connectivity, requiring the additional mechanism of topological co-evolution to ensure the survival of cooperative behaviour.     

Prediction and Testing of Biological Networks Underlying Intestinal Cancer

Colorectal cancer progresses through an accumulation of somatic mutations, some of which reside in so-called “driver” genes that provide a growth advantage to the tumor. To identify points of intersection between driver gene pathways, we implemented a network analysis framework using protein interactions to predict likely connections – both precedented and novel – between key driver genes in cancer. We applied the framework to find significant connections between two genes, Apc and Cdkn1a (p21), known to be synergistic in tumorigenesis in mouse models. We then assessed the functional coherence of the resulting Apc-Cdkn1a network by engineering in vivo single node perturbations of the network: mouse models mutated individually at Apc (Apc^1638N+/−) or Cdkn1a (Cdkn1a^−/−), followed by measurements of protein and gene expression changes in intestinal epithelial tissue. We hypothesized that if the predicted network is biologically coherent (functional), then the predicted nodes should associate more specifically with dysregulated genes and proteins than stochastically selected genes and proteins. The predicted Apc-Cdkn1a network was significantly perturbed at the mRNA-level by both single gene knockouts, and the predictions were also strongly supported based on physical proximity and mRNA coexpression of proteomic targets. These results support the functional coherence of the proposed Apc-Cdkn1a network and also demonstrate how network-based predictions can be statistically tested using high-throughput biological data.     

Quilt Plots: A Simple Tool for the Visualisation of Large Epidemiological Data

Background

Graphical representation of data is one of the most easily comprehended forms of explanation. The current study describes a simple visualization tool which may allow greater understanding of medical and epidemiological data.

Method

We propose a simple tool for visualization of data, known as a “quilt plot”, that provides an alternative to presenting large volumes of data as frequency tables. Data from the Australian Needle and Syringe Program survey are used to illustrate “quilt plots”.

Conclusion

Visualization of large volumes of data using “quilt plots” enhances interpretation of medical and epidemiological data. Such intuitive presentations are particularly useful for the rapid assessment of problems in the data which cannot be readily identified by manual review. We recommend that, where possible, “quilt plots” be used along with traditional quantitative assessments of the data as an explanatory data analysis tool.     

Global Analysis of the Human Pathophenotypic Similarity Gene Network Merges Disease Module Components

The molecular complexity of genetic diseases requires novel approaches to break it down into coherent biological modules. For this purpose, many disease network models have been created and analyzed. We highlight two of them, “the human diseases networks” (HDN) and “the orphan disease networks” (ODN). However, in these models, each single node represents one disease or an ambiguous group of diseases. In these cases, the notion of diseases as unique entities reduces the usefulness of network-based methods. We hypothesize that using the clinical features (pathophenotypes) to define pathophenotypic connections between disease-causing genes improve our understanding of the molecular events originated by genetic disturbances. For this, we have built a pathophenotypic similarity gene network (PSGN) and compared it with the unipartite projections (based on gene-to-gene edges) similar to those used in previous network models (HDN and ODN). Unlike these disease network models, the PSGN uses semantic similarities. This pathophenotypic similarity has been calculated by comparing pathophenotypic annotations of genes (human abnormalities of HPO terms) in the “Human Phenotype Ontology”. The resulting network contains 1075 genes (nodes) and 26197 significant pathophenotypic similarities (edges). A global analysis of this network reveals: unnoticed pairs of genes showing significant pathophenotypic similarity, a biological meaningful re-arrangement of the pathological relationships between genes, correlations of biochemical interactions with higher similarity scores and functional biases in metabolic and essential genes toward the pathophenotypic specificity and the pleiotropy, respectively. Additionally, pathophenotypic similarities and metabolic interactions of genes associated with maple syrup urine disease (MSUD) have been used to merge into a coherent pathological module.Our results indicate that pathophenotypes contribute to identify underlying co-dependencies among disease-causing genes that are useful to describe disease modularity.     

Ethylene Production and Respiratory Behavior of the rin Tomato Mutant

Little or no change in ethylene or CO₂ production occurred in rin tomato mutant fruits monitored for up to 120 days after harvest. Of the abnormally ripening tomatoes investigated, including “Never ripe” (Nr Y a h, Nr c l₂ r), “Evergreen” (gf r) and “Green Flesh” (gf), only rin did not show a typical climacteric and ethylene rise.     

Wasp-waist interactions in the North Sea ecosystem

Background

In a “wasp-waist” ecosystem, an intermediate trophic level is expected to control the abundance of predators through a bottom-up interaction and the abundance of prey through a top-down interaction. Previous studies suggest that the North Sea is mainly governed by bottom-up interactions driven by climate perturbations. However, few studies have investigated the importance of the intermediate trophic level occupied by small pelagic fishes.

Methodology/Principal Findings

We investigated the numeric interactions among 10 species of seabirds, two species of pelagic fish and four groups of zooplankton in the North Sea using decadal-scale databases. Linear models were used to relate the time series of zooplankton and seabirds to the time series of pelagic fish. Seabirds were positively related to herring (Clupea harengus), suggesting a bottom-up interaction. Two groups of zooplankton; Calanus helgolandicus and krill were negatively related to sprat (Sprattus sprattus) and herring respectively, suggesting top-down interactions. In addition, we found positive relationships among the zooplankton groups. Para/pseudocalanus was positively related to C. helgolandicus and C. finmarchicus was positively related to krill.

Conclusion/Significance

Our results indicate that herring was important in regulating the abundance of seabirds through a bottom-up interaction and that herring and sprat were important in regulating zooplankton through top-down interactions. We suggest that the positive relationships among zooplankton groups were due to selective foraging and switching in the two clupeid fishes. Our results suggest that “wasp-waist” interactions might be more important in the North Sea than previously anticipated. Fluctuations in the populations of pelagic fish due to harvesting and depletion of their predators might accordingly have profound consequences for ecosystem dynamics through trophic cascades.     

Discovering protein complexes in protein interaction networks via exploring the weak ties effect

Background

Studying protein complexes is very important in biological processes since it helps reveal the structure-functionality relationships in biological networks and much attention has been paid to accurately predict protein complexes from the increasing amount of protein-protein interaction (PPI) data. Most of the available algorithms are based on the assumption that dense subgraphs correspond to complexes, failing to take into account the inherence organization within protein complex and the roles of edges. Thus, there is a critical need to investigate the possibility of discovering protein complexes using the topological information hidden in edges.

Results

To provide an investigation of the roles of edges in PPI networks, we show that the edges connecting less similar vertices in topology are more significant in maintaining the global connectivity, indicating the weak ties phenomenon in PPI networks. We further demonstrate that there is a negative relation between the weak tie strength and the topological similarity. By using the bridges, a reliable virtual network is constructed, in which each maximal clique corresponds to the core of a complex. By this notion, the detection of the protein complexes is transformed into a classic all-clique problem. A novel core-attachment based method is developed, which detects the cores and attachments, respectively. A comprehensive comparison among the existing algorithms and our algorithm has been made by comparing the predicted complexes against benchmark complexes.

Conclusions

We proved that the weak tie effect exists in the PPI network and demonstrated that the density is insufficient to characterize the topological structure of protein complexes. Furthermore, the experimental results on the yeast PPI network show that the proposed method outperforms the state-of-the-art algorithms. The analysis of detected modules by the present algorithm suggests that most of these modules have well biological significance in context of complexes, suggesting that the roles of edges are critical in discovering protein complexes.

     

Cluster Analysis of Weighted Bipartite Networks: A New Copula-Based Approach

In this work we are interested in identifying clusters of “positional equivalent” actors, i.e. actors who play a similar role in a system. In particular, we analyze weighted bipartite networks that describes the relationships between actors on one side and features or traits on the other, together with the intensity level to which actors show their features. We develop a methodological approach that takes into account the underlying multivariate dependence among groups of actors. The idea is that positions in a network could be defined on the basis of the similar intensity levels that the actors exhibit in expressing some features, instead of just considering relationships that actors hold with each others. Moreover, we propose a new clustering procedure that exploits the potentiality of copula functions, a mathematical instrument for the modelization of the stochastic dependence structure. Our clustering algorithm can be applied both to binary and real-valued matrices. We validate it with simulations and applications to real-world data.     

NET: a new framework for the vectorization and examination of network data

Background

The analysis of complex networks both in general and in particular as pertaining to real biological systems has been the focus of intense scientific attention in the past and present. In this paper we introduce two tools that provide fast and efficient means for the processing and quantification of biological networks like Drosophila tracheoles or leaf venation patterns: the Network Extraction Tool (NET) to extract data and the Graph-edit-GUI (GeGUI) to visualize and modify networks.

Results

NET is especially designed for high-throughput semi-automated analysis of biological datasets containing digital images of networks. The framework starts with the segmentation of the image and then proceeds to vectorization using methodologies from optical character recognition. After a series of steps to clean and improve the quality of the extracted data the framework produces a graph in which the network is represented only by its nodes and neighborhood-relations. The final output contains information about the adjacency matrix of the graph, the width of the edges and the positions of the nodes in space. NET also provides tools for statistical analysis of the network properties, such as the number of nodes or total network length. Other, more complex metrics can be calculated by importing the vectorized network to specialized network analysis packages. GeGUI is designed to facilitate manual correction of non-planar networks as these may contain artifacts or spurious junctions due to branches crossing each other. It is tailored for but not limited to the processing of networks from microscopy images of Drosophila tracheoles.

Conclusion

The networks extracted by NET closely approximate the network depicted in the original image. NET is fast, yields reproducible results and is able to capture the full geometry of the network, including curved branches. Additionally GeGUI allows easy handling and visualization of the networks.

     

The Mesh of Civilizations in the Global Network of Digital Communication

Conflicts fueled by popular religious mobilization have rekindled the controversy surrounding Samuel Huntington’s theory of changing international alignments in the Post-Cold War era. In The Clash of Civilizations, Huntington challenged Fukuyama’s “end of history” thesis that liberal democracy had emerged victorious out of Post-war ideological and economic rivalries. Based on a top-down analysis of the alignments of nation states, Huntington famously concluded that the axes of international geo-political conflicts had reverted to the ancient cultural divisions that had characterized most of human history. Until recently, however, the debate has had to rely more on polemics than empirical evidence. Moreover, Huntington made this prediction in 1993, before social media connected the world’s population. Do digital communications attenuate or echo the cultural, religious, and ethnic “fault lines” posited by Huntington prior to the global diffusion of social media? We revisit Huntington''s thesis using hundreds of millions of anonymized email and Twitter communications among tens of millions of worldwide users to map the global alignment of interpersonal relations. Contrary to the supposedly borderless world of cyberspace, a bottom-up analysis confirms the persistence of the eight culturally differentiated civilizations posited by Huntington, with the divisions corresponding to differences in language, religion, economic development, and spatial distance.Have social media created a global village that spans cultural differences and traditional borders? For most of the postwar period, research on international alignments was informed by World Systems Theory, an approach that emphasized the influence of North-South economic divisions and East-West ideological divisions [1]. Following the collapse of the Soviet Union, Fukuyama [2] proposed that those divisions had culminated in the triumph of liberal democratic systems, signaling the “end of history.” In The Clash of Civilizations [3], Fukuyama’s mentor, Samuel Huntington, acknowledged that “the fundamental source of conflict in this new world will not be primarily ideological or primarily economic,” but he challenged Fukyama’s prediction of global consensus:The great divisions among humankind and the dominating source of conflict will be cultural. Nation states will remain the most powerful actors in world affairs, but the principal conflicts of global politics will occur between nations and groups of different civilizations. The clash of civilizations will dominate global politics. The fault lines between civilizations will be the battle lines of the future.The world has undergone substantial changes since Huntington made this prediction in 1993, including rapid economic growth in South Asia and South America and global diffusion of social media connecting the world’s population. Moreover, the evidence for Huntington''s theory of international global alignment was largely top-down, based on the political and economic relations among culturally differentiated nation states. The growing availability of digital traces of human communications now makes it possible to revisit Huntington''s thesis by taking a bottom-up view, based on interpersonal interactions among millions of individuals instead of the alignments of state actors. Have these online interactions created a global village that spans not only the old Cold War divisions but Huntington’s cultural fault lines as well?To find out, we used hundreds of millions of anonymized email and Twitter communications among tens of millions of worldwide users to map global patterns of transnational interpersonal communication. We measure the density, not the content, of interpersonal communication, and our findings do not address Huntington’s highly controversial warning of the potential for conflict between cultures. Nevertheless, the observed patterns provide a unique angle on changing global alignments in the Post-Cold War era.Our work builds on a study by Leskovec and Horvitz of the global flows of online Instant Messaging (IM) [4], extending that research in four important ways. First, we measure the density of social ties, not the density of message traffic. The “fault lines of civilizations” are indicated not by the number of messages two people exchange across borders but by the number of individuals in each country who exchange messages with one another. Second, we measure the density of social ties after taking into account differences in language, geo-location, Cold War alignment, economic development, and religion. (NB: In addition to analyzing communication densities between country pairs, Leskovec and Horvitz also measured global properties of the social network among pairs of individuals, but they did not use the latter to analyze social densities between country pairs. They also found that between-country communication densities were highly correlated with language and spatial distance, but they did not measure communication densities relative to the expected density given similarities of language and geo-location.) Third, we use multiple platforms (Yahoo! email and Twitter) to provide greater robustness and to avoid the possibility that our results are artifacts of the idiosyncrasies of a particular service. Twitter differs from email in two ways that are relevant to our study: most email exchanges are dyadic while Twitter messages are publicly visible, and the Twitter platform makes it much easier for users to discover one another, thereby reducing the tendency for online interactions to reflect pre-existing relationships. Fourth, we correct for internet access and market penetration, without which online traffic flows confound the strength of interpersonal ties with the popularity of a given communication medium. By taking into account differences in Internet access and market penetration, we are able to estimate the global network of social ties derived from the interpersonal flows of Internet communications.We measured communication density based on the number of observed bi-directed ties between users in two countries, relative to the maximum possible number of such ties, given the number of users in each country and the number of people with Internet access. (NB: The email analysis was based on anonymized geo-tagged edge lists. Prior to the analysis, the edge lists were anonymized as follows: Individual email accounts were assigned a random numeric identifier, after which the original email addresses were deleted. The email message content was not accessed or used for this study. Other than country, the edge lists we analyzed contained no individually identifiable information. The project was approved by the Cornell University IRB. The Twitter dataset was provided to us already anonymized by the team that collected it [5]. Scripts for the processing of that dataset are available from http://dx.doi.org/10.6084/m9.figshare.1304572.)A bi-directed email tie exists between two users if at least two messages are exchanged, one in each direction. A bi-directed Twitter tie exists if two users each follow the other. We defined pairwise communication density as the ratio between the observed number of bi-directed ties and the number of expected ties, given the number of subscribers and the number of Internet users.We obtained qualitatively similar results for email and Twitter communication densities and therefore report only the combined density measures for the two platforms. We also measured densities net of geographic proximity, shared language, population size, economic development, and colonial history.     

Potential Health Risk of Reused Creosote-Treated Old Railway Ties at Recreational Sites in Korea

Old creosote-treated railway ties reused at recreational sites in Korea are potential hazards, due to the presence of harmful substances in creosote, such as polycyclic aromatic hydrocarbons (PAHs). In such sites, PAHs in ties can be leached or emitted, and human exposure might then occur. In this study, the concentrations of 16 PAHs in soil, air, and tie surfaces in old creosote-treated railway ties reused in recreational sites were investigated, and the potential health risk of the ties was evaluated through two exposure scenarios: a recreational scenario (ingestion of and dermal contact with soil and inhalation of soil particles) and a playground scenario (ingestion after contact and dermal contact with ties). For the recreational scenario, the health risks of PAHs were safe; however, for the playground scenario, the carcinogenic risk of ingestion after contact, and dermal contact with benz(a)anthracene and benzo(a)pyrene on the tie surfaces, exceeded the acceptable risk level (10^–6). For the carcinogenic risks of ingestion after contact with ties, the probabilities of cancer development were 8 and 5 in one million people for benz(a)anthracene and benzo(a)pyrene, respectively. The carcinogenic risks for dermal contact with ties were 2.4 × 10^–6 and 1.4 × 10^–6 for benz(a)anthracene and benzo(a)pyrene, respectively.