Identifying Influential Nodes in Large-Scale Directed Networks: The Role of Clustering

Identifying influential nodes in very large-scale directed networks is a big challenge relevant to disparate applications, such as accelerating information propagation, controlling rumors and diseases, designing search engines, and understanding hierarchical organization of social and biological networks. Known methods range from node centralities, such as degree, closeness and betweenness, to diffusion-based processes, like PageRank and LeaderRank. Some of these methods already take into account the influences of a node’s neighbors but do not directly make use of the interactions among it’s neighbors. Local clustering is known to have negative impacts on the information spreading. We further show empirically that it also plays a negative role in generating local connections. Inspired by these facts, we propose a local ranking algorithm named ClusterRank, which takes into account not only the number of neighbors and the neighbors’ influences, but also the clustering coefficient. Subject to the susceptible-infected-recovered (SIR) spreading model with constant infectivity, experimental results on two directed networks, a social network extracted from delicious.com and a large-scale short-message communication network, demonstrate that the ClusterRank outperforms some benchmark algorithms such as PageRank and LeaderRank. Furthermore, ClusterRank can also be applied to undirected networks where the superiority of ClusterRank is significant compared with degree centrality and k-core decomposition. In addition, ClusterRank, only making use of local information, is much more efficient than global methods: It takes only 191 seconds for a network with about nodes, more than 15 times faster than PageRank.     

CytoKavosh: A Cytoscape Plug-In for Finding Network Motifs in Large Biological Networks

Network motifs are small connected sub-graphs that have recently gathered much attention to discover structural behaviors of large and complex networks. Finding motifs with any size is one of the most important problems in complex and large networks. It needs fast and reliable algorithms and tools for achieving this purpose. CytoKavosh is one of the best choices for finding motifs with any given size in any complex network. It relies on a fast algorithm, Kavosh, which makes it faster than other existing tools. Kavosh algorithm applies some well known algorithmic features and includes tricky aspects, which make it an efficient algorithm in this field. CytoKavosh is a Cytoscape plug-in which supports us in finding motifs of given size in a network that is formerly loaded into the Cytoscape work-space (directed or undirected). High performance of CytoKavosh is achieved by dynamically linking highly optimized functions of Kavosh's C++ to the Cytoscape Java program, which makes this plug-in suitable for analyzing large biological networks. Some significant attributes of CytoKavosh is efficiency in time usage and memory and having no limitation related to the implementation in motif size. CytoKavosh is implemented in a visual environment Cytoscape that is convenient for the users to interact and create visual options to analyze the structural behavior of a network. This plug-in can work on any given network and is very simple to use and generates graphical results of discovered motifs with any required details. There is no specific Cytoscape plug-in, specific for finding the network motifs, based on original concept. So, we have introduced for the first time, CytoKavosh as the first plug-in, and we hope that this plug-in can be improved to cover other options to make it the best motif-analyzing tool.     

A Kalman-Filter Based Approach to Identification of Time-Varying Gene Regulatory Networks

Motivation

Conventional identification methods for gene regulatory networks (GRNs) have overwhelmingly adopted static topology models, which remains unchanged over time to represent the underlying molecular interactions of a biological system. However, GRNs are dynamic in response to physiological and environmental changes. Although there is a rich literature in modeling static or temporally invariant networks, how to systematically recover these temporally changing networks remains a major and significant pressing challenge. The purpose of this study is to suggest a two-step strategy that recovers time-varying GRNs.

Results

It is suggested in this paper to utilize a switching auto-regressive model to describe the dynamics of time-varying GRNs, and a two-step strategy is proposed to recover the structure of time-varying GRNs. In the first step, the change points are detected by a Kalman-filter based method. The observed time series are divided into several segments using these detection results; and each time series segment belonging to two successive demarcating change points is associated with an individual static regulatory network. In the second step, conditional network structure identification methods are used to reconstruct the topology for each time interval. This two-step strategy efficiently decouples the change point detection problem and the topology inference problem. Simulation results show that the proposed strategy can detect the change points precisely and recover each individual topology structure effectively. Moreover, computation results with the developmental data of Drosophila Melanogaster show that the proposed change point detection procedure is also able to work effectively in real world applications and the change point estimation accuracy exceeds other existing approaches, which means the suggested strategy may also be helpful in solving actual GRN reconstruction problem.     

A Bio-Inspired Methodology of Identifying Influential Nodes in Complex Networks

How to identify influential nodes is a key issue in complex networks. The degree centrality is simple, but is incapable to reflect the global characteristics of networks. Betweenness centrality and closeness centrality do not consider the location of nodes in the networks, and semi-local centrality, leaderRank and pageRank approaches can be only applied in unweighted networks. In this paper, a bio-inspired centrality measure model is proposed, which combines the Physarum centrality with the K-shell index obtained by K-shell decomposition analysis, to identify influential nodes in weighted networks. Then, we use the Susceptible-Infected (SI) model to evaluate the performance. Examples and applications are given to demonstrate the adaptivity and efficiency of the proposed method. In addition, the results are compared with existing methods.     

Robustness in Regulatory Networks: A Multi-Disciplinary Approach

We give in this paper indications about the dynamical impact (as phenotypic changes) coming from the main sources of perturbation in biological regulatory networks. First, we define the boundary of the interaction graph expressing the regulations between the main elements of the network (genes, proteins, metabolites, ...). Then, we search what changes in the state values on the boundary could cause some changes of states in the core of the system (robustness to boundary conditions). After, we analyse the role of the mode of updating (sequential, block sequential or parallel) on the asymptotics of the network, essentially on the occurrence of limit cycles (robustness to updating methods). Finally, we show the influence of some topological changes (e.g. suppression or addition of interactions) on the dynamical behaviour of the system (robustness to topology perturbations).     

NetMODE: Network Motif Detection without Nauty

A motif in a network is a connected graph that occurs significantly more frequently as an induced subgraph than would be expected in a similar randomized network. By virtue of being atypical, it is thought that motifs might play a more important role than arbitrary subgraphs. Recently, a flurry of advances in the study of network motifs has created demand for faster computational means for identifying motifs in increasingly larger networks. Motif detection is typically performed by enumerating subgraphs in an input network and in an ensemble of comparison networks; this poses a significant computational problem. Classifying the subgraphs encountered, for instance, is typically performed using a graph canonical labeling package, such as Nauty, and will typically be called billions of times. In this article, we describe an implementation of a network motif detection package, which we call NetMODE. NetMODE can only perform motif detection for -node subgraphs when , but does so without the use of Nauty. To avoid using Nauty, NetMODE has an initial pretreatment phase, where -node graph data is stored in memory (). For we take a novel approach, which relates to the Reconstruction Conjecture for directed graphs. We find that NetMODE can perform up to around times faster than its predecessors when and up to around times faster when (the exact improvement varies considerably). NetMODE also (a) includes a method for generating comparison graphs uniformly at random, (b) can interface with external packages (e.g. R), and (c) can utilize multi-core architectures. NetMODE is available from netmode.sf.net.     

A Bridge Role Metric Model for Nodes in Software Networks

A bridge role metric model is put forward in this paper. Compared with previous metric models, our solution of a large-scale object-oriented software system as a complex network is inherently more realistic. To acquire nodes and links in an undirected network, a new model that presents the crucial connectivity of a module or the hub instead of only centrality as in previous metric models is presented. Two previous metric models are described for comparison. In addition, it is obvious that the fitting curve between the results and degrees can well be fitted by a power law. The model represents many realistic characteristics of actual software structures, and a hydropower simulation system is taken as an example. This paper makes additional contributions to an accurate understanding of module design of software systems and is expected to be beneficial to software engineering practices.     

Degree Correlations in Directed Scale-Free Networks

Scale-free networks, in which the distribution of the degrees obeys a power-law, are ubiquitous in the study of complex systems. One basic network property that relates to the structure of the links found is the degree assortativity, which is a measure of the correlation between the degrees of the nodes at the end of the links. Degree correlations are known to affect both the structure of a network and the dynamics of the processes supported thereon, including the resilience to damage, the spread of information and epidemics, and the efficiency of defence mechanisms. Nonetheless, while many studies focus on undirected scale-free networks, the interactions in real-world systems often have a directionality. Here, we investigate the dependence of the degree correlations on the power-law exponents in directed scale-free networks. To perform our study, we consider the problem of building directed networks with a prescribed degree distribution, providing a method for proper generation of power-law-distributed directed degree sequences. Applying this new method, we perform extensive numerical simulations, generating ensembles of directed scale-free networks with exponents between 2 and 3, and measuring ensemble averages of the Pearson correlation coefficients. Our results show that scale-free networks are on average uncorrelated across directed links for three of the four possible degree-degree correlations, namely in-degree to in-degree, in-degree to out-degree, and out-degree to out-degree. However, they exhibit anticorrelation between the number of outgoing connections and the number of incoming ones. The findings are consistent with an entropic origin for the observed disassortativity in biological and technological networks.     

Community Structures in Bipartite Networks: A Dual-Projection Approach

Identifying communities or clusters in networked systems has received much attention across the physical and social sciences. Most of this work focuses on single layer or one-mode networks, including social networks between people or hyperlinks between websites. Multilayer or multi-mode networks, such as affiliation networks linking people to organizations, receive much less attention in this literature. Common strategies for discovering the community structure of multi-mode networks identify the communities of each mode simultaneously. Here I show that this combined approach is ineffective at discovering community structures when there are an unequal number of communities between the modes of a multi-mode network. I propose a dual-projection alternative for detecting communities in multi-mode networks that overcomes this shortcoming. The evaluation of synthetic networks with known community structures reveals that the dual-projection approach outperforms the combined approach when there are a different number of communities in the various modes. At the same time, results show that the dual-projection approach is as effective as the combined strategy when the number of communities is the same between the modes.     

Species Invasiveness in Biological Invasions: A Modelling Approach

The study of invasiveness, the traits that enable a species to invade a habitat, and invasibility, the habitat characteristics that determine its susceptibility to the establishment and spread of an invasive species, provide a useful conceptual framework to formulate the biological invasion problem in a modelling context. Another important aspect is the complex interaction emerging among the invader species, the noninvader species already present in the habitat, and the habitat itself. Following a modelling approach to the biological invasion problem, we present a spatially explicit cellular automaton model (Interacting Multiple Cellular Automata (IMCA)). We use field parameters from the invader Gleditsia triacanthos and the native Lithraea ternifolia in montane forests of central Argentina as a case study to compare outputs and performance of different models. We use field parameters from another invader, Ligustrum lucidum, and the native Fagara coco from the same system to run the cellular automaton model. We compare model predictions with invasion values from aerial photographs. We discuss in detail the importance of factors affecting species invasiveness, and give some insights into habitat invasibility and the role of interactions between them. Finally, we discuss the relevance of mathematical modelling for studying and predicting biological invasions. The IMCA model provided a suitable context for integrating invasiveness, invasibility, and the interactions. In the invasion system studied, the presence of an invader's juvenile bank not only accelerated the rate of invasion but was essential to ensure invasion. Using the IMCA model, we were able to determine that not only adult survival but particularly longevity of the native species influenced the spread velocity of the invader, at least when a juvenile bank is present. Other factors determining velocity of invasion detected by the IMCA model were seed dispersal distance and age of reproductive maturity. We derived relationships between species' adult survival, fecundity and longevity of both theoretical and applied relevance for biological invasions. Invasion velocities calculated from the aerial photographs agreed well with predictions of the IMCA model.     

Effective Identification of Conserved Pathways in Biological Networks Using Hidden Markov Models

Background

The advent of various high-throughput experimental techniques for measuring molecular interactions has enabled the systematic study of biological interactions on a global scale. Since biological processes are carried out by elaborate collaborations of numerous molecules that give rise to a complex network of molecular interactions, comparative analysis of these biological networks can bring important insights into the functional organization and regulatory mechanisms of biological systems.

Methodology/Principal Findings

In this paper, we present an effective framework for identifying common interaction patterns in the biological networks of different organisms based on hidden Markov models (HMMs). Given two or more networks, our method efficiently finds the top matching paths in the respective networks, where the matching paths may contain a flexible number of consecutive insertions and deletions.

Conclusions/Significance

Based on several protein-protein interaction (PPI) networks obtained from the Database of Interacting Proteins (DIP) and other public databases, we demonstrate that our method is able to detect biologically significant pathways that are conserved across different organisms. Our algorithm has a polynomial complexity that grows linearly with the size of the aligned paths. This enables the search for very long paths with more than 10 nodes within a few minutes on a desktop computer. The software program that implements this algorithm is available upon request from the authors.     

A Framework of Algorithms: Computing the Bias and Prestige of Nodes in Trust Networks

A trust network is a social network in which edges represent the trust relationship between two nodes in the network. In a trust network, a fundamental question is how to assess and compute the bias and prestige of the nodes, where the bias of a node measures the trustworthiness of a node and the prestige of a node measures the importance of the node. The larger bias of a node implies the lower trustworthiness of the node, and the larger prestige of a node implies the higher importance of the node. In this paper, we define a vector-valued contractive function to characterize the bias vector which results in a rich family of bias measurements, and we propose a framework of algorithms for computing the bias and prestige of nodes in trust networks. Based on our framework, we develop four algorithms that can calculate the bias and prestige of nodes effectively and robustly. The time and space complexities of all our algorithms are linear with respect to the size of the graph, thus our algorithms are scalable to handle large datasets. We evaluate our algorithms using five real datasets. The experimental results demonstrate the effectiveness, robustness, and scalability of our algorithms.     

Interpretation of Genomic Variants Using a Unified Biological Network Approach

The decreasing cost of sequencing is leading to a growing repertoire of personal genomes. However, we are lagging behind in understanding the functional consequences of the millions of variants obtained from sequencing. Global system-wide effects of variants in coding genes are particularly poorly understood. It is known that while variants in some genes can lead to diseases, complete disruption of other genes, called ‘loss-of-function tolerant’, is possible with no obvious effect. Here, we build a systems-based classifier to quantitatively estimate the global perturbation caused by deleterious mutations in each gene. We first survey the degree to which gene centrality in various individual networks and a unified ‘Multinet’ correlates with the tolerance to loss-of-function mutations and evolutionary conservation. We find that functionally significant and highly conserved genes tend to be more central in physical protein-protein and regulatory networks. However, this is not the case for metabolic pathways, where the highly central genes have more duplicated copies and are more tolerant to loss-of-function mutations. Integration of three-dimensional protein structures reveals that the correlation with centrality in the protein-protein interaction network is also seen in terms of the number of interaction interfaces used. Finally, combining all the network and evolutionary properties allows us to build a classifier distinguishing functionally essential and loss-of-function tolerant genes with higher accuracy (AUC = 0.91) than any individual property. Application of the classifier to the whole genome shows its strong potential for interpretation of variants involved in Mendelian diseases and in complex disorders probed by genome-wide association studies.     

Community Landscapes: An Integrative Approach to Determine Overlapping Network Module Hierarchy,Identify Key Nodes and Predict Network Dynamics

Background

Network communities help the functional organization and evolution of complex networks. However, the development of a method, which is both fast and accurate, provides modular overlaps and partitions of a heterogeneous network, has proven to be rather difficult.

Methodology/Principal Findings

Here we introduce the novel concept of ModuLand, an integrative method family determining overlapping network modules as hills of an influence function-based, centrality-type community landscape, and including several widely used modularization methods as special cases. As various adaptations of the method family, we developed several algorithms, which provide an efficient analysis of weighted and directed networks, and (1) determine pervasively overlapping modules with high resolution; (2) uncover a detailed hierarchical network structure allowing an efficient, zoom-in analysis of large networks; (3) allow the determination of key network nodes and (4) help to predict network dynamics.

Conclusions/Significance

The concept opens a wide range of possibilities to develop new approaches and applications including network routing, classification, comparison and prediction.     

Selectide Technology: Substrate Motif Identification for Post-translational Modifications

The random synthetic peptide library screening method based on the "one-bead one-peptide concept" (Selectide Process) can be used as a general method for the identification of peptide substrate motif for post-translational modifications. We applied this method to the cAMP-dependent protein kinase system and were able to rapidly identify a peptide motif (RRXS) that exactly matched that described for its natural substrates.     

Directed Evolution: An Approach to Engineer Enzymes

ABSTRACT

Directed evolution is being used increasingly in industrial and academic laboratories to modify and improve commercially important enzymes. Laboratory evolution is thought to make its biggest contribution in explorations of non-natural functions, by allowing us to distinguish the properties nurtured by evolution. In this review we report the significant advances achieved with respect to the methods of biocatalyst improvement and some critical properties and applications of the modified enzymes. The application of directed evolution has been elaborately demonstrated for protein solubility, stability and catalytic efficiency. Modification of certain enzymes for their application in enantioselective catalysis has also been elucidated. By providing a simple and reliable route to enzyme improvement, directed evolution has emerged as a key technology for enzyme engineering and biocatalysis.     

QuateXelero: An Accelerated Exact Network Motif Detection Algorithm

Finding motifs in biological, social, technological, and other types of networks has become a widespread method to gain more knowledge about these networks’ structure and function. However, this task is very computationally demanding, because it is highly associated with the graph isomorphism which is an NP problem (not known to belong to P or NP-complete subsets yet). Accordingly, this research is endeavoring to decrease the need to call NAUTY isomorphism detection method, which is the most time-consuming step in many existing algorithms. The work provides an extremely fast motif detection algorithm called QuateXelero, which has a Quaternary Tree data structure in the heart. The proposed algorithm is based on the well-known ESU (FANMOD) motif detection algorithm. The results of experiments on some standard model networks approve the overal superiority of the proposed algorithm, namely QuateXelero, compared with two of the fastest existing algorithms, G-Tries and Kavosh. QuateXelero is especially fastest in constructing the central data structure of the algorithm from scratch based on the input network.