Efficient target control of complex networks based on preferential matching.
Ontology highlight
ABSTRACT:
SUBMITTER: Zhang X
PROVIDER: S-EPMC5383299 | biostudies-literature | 2017
REPOSITORIES: biostudies-literature
Publications
Efficient target control of complex networks based on preferential matching.
Zhang Xizhe X Wang Huaizhen H Lv Tianyang T
PloS one 20170406 4
Controlling a complex network towards a desired state is of great importance in many applications. Existing works present an approximate algorithm to find the input nodes used to control partial nodes of the network. However, the input nodes obtained by this algorithm depend on the node matching order and cannot achieve optimum results. Here we present a novel algorithm to find the input nodes for target control based on preferential matching. The algorithm elaborately arranges the matching orde ...[more]
Similar Datasets
Project description:Controlling large natural and technological networks is an outstanding challenge. It is typically neither feasible nor necessary to control the entire network, prompting us to explore target control: the efficient control of a preselected subset of nodes. We show that the structural controllability approach used for full control overestimates the minimum number of driver nodes needed for target control. Here we develop an alternate 'k-walk' theory for directed tree networks, and we rigorously prove that one node can control a set of target nodes if the path length to each target node is unique. For more general cases, we develop a greedy algorithm to approximate the minimum set of driver nodes sufficient for target control. We find that degree heterogeneous networks are target controllable with higher efficiency than homogeneous networks and that the structure of many real-world networks are suitable for efficient target control.
| S-EPMC4243219 | biostudies-literature
Project description:In spite of its relevance to the origin of complex networks, the interplay between form and function and its role during network formation remains largely unexplored. While recent studies introduce dynamics by considering rewiring processes of a pre-existent network, we study network growth and formation by proposing an evolutionary preferential attachment model, its main feature being that the capacity of a node to attract new links depends on a dynamical variable governed in turn by the node interactions. As a specific example, we focus on the problem of the emergence of cooperation by analyzing the formation of a social network with interactions given by the Prisoner's Dilemma. The resulting networks show many features of real systems, such as scale-free degree distributions, cooperative behavior and hierarchical clustering. Interestingly, results such as the cooperators being located mostly on nodes of intermediate degree are very different from the observations of cooperative behavior on static networks. The evolutionary preferential attachment mechanism points to an evolutionary origin of scale-free networks and may help understand similar feedback problems in the dynamics of complex networks by appropriately choosing the game describing the interaction of nodes.
| S-EPMC2413409 | biostudies-literature
Project description:The energy needed in controlling a complex network is a problem of practical importance. Recent works have focused on the reduction of control energy either via strategic placement of driver nodes, or by decreasing the cardinality of nodes to be controlled. However, optimizing control energy with respect to target nodes selection has yet been considered. In this work, we propose an iterative method based on Stiefel manifold optimization of selectable target node matrix to reduce control energy. We derive the matrix derivative gradient needed for the search algorithm in a general way, and search for target nodes which result in reduced control energy, assuming that driver nodes placement is fixed. Our findings reveal that the control energy is optimal when the path distances from driver nodes to target nodes are minimized. We corroborate our algorithm with extensive simulations on elementary network topologies, random and scale-free networks, as well as various real networks. The simulation results show that the control energy found using our algorithm outperforms heuristic selection strategies for choosing target nodes by a few orders of magnitude. Our work may be applicable to opinion networks, where one is interested in identifying the optimal group of individuals that the driver nodes can influence.
| S-EPMC7581767 | biostudies-literature
Project description:What can we learn about controlling a system solely from its underlying network structure? Here we adapt a recently developed framework for control of networks governed by a broad class of nonlinear dynamics that includes the major dynamic models of biological, technological, and social processes. This feedback-based framework provides realizable node overrides that steer a system toward any of its natural long-term dynamic behaviors, regardless of the specific functional forms and system parameters. We use this framework on several real networks, identify the topological characteristics that underlie the predicted node overrides, and compare its predictions to those of structural controllability in control theory. Finally, we demonstrate this framework's applicability in dynamic models of gene regulatory networks and identify nodes whose override is necessary for control in the general case but not in specific model instances.
| S-EPMC5514702 | biostudies-literature
Project description:BackgroundNetworks have been widely used to model the structures of various biological systems. The ultimate aim of research on biological networks is to steer biological system structures to desired states by manipulating signals. Despite great advances in the linear control of single-layer networks, it has been observed that many complex biological systems have a multilayer networked structure and extremely complicated nonlinear processes.ResultIn this study, we propose a general framework for controlling nonlinear dynamical systems with multilayer networked structures by formulating the problem as a minimum union optimization problem. In particular, we offer a novel approach for identifying the minimal driver nodes that can steer a multilayered nonlinear dynamical system toward any desired dynamical attractor. Three disease-related biology multilayer networks are used to demonstrate the effectiveness of our approaches. Moreover, in the set of minimum driver nodes identified by the algorithm we proposed, we confirmed that some nodes can act as drug targets in the biological experiments. Other nodes have not been reported as drug targets; however, they are also involved in important biological processes from existing literature.ConclusionsThe proposed method could be a promising tool for determining higher drug target enrichment or more meaningful steering nodes for studying complex diseases.
| S-EPMC6540418 | biostudies-literature
Project description:Complex network growth across diverse fields of science is hypothesized to be driven in the main by a combination of preferential attachment and node fitness processes. For measuring the respective influences of these processes, previous approaches make strong and untested assumptions on the functional forms of either the preferential attachment function or fitness function or both. We introduce a Bayesian statistical method called PAFit to estimate preferential attachment and node fitness without imposing such functional constraints that works by maximizing a log-likelihood function with suitably added regularization terms. We use PAFit to investigate the interplay between preferential attachment and node fitness processes in a Facebook wall-post network. While we uncover evidence for both preferential attachment and node fitness, thus validating the hypothesis that these processes together drive complex network evolution, we also find that node fitness plays the bigger role in determining the degree of a node. This is the first validation of its kind on real-world network data. But surprisingly the rate of preferential attachment is found to deviate from the conventional log-linear form when node fitness is taken into account. The proposed method is implemented in the R package PAFit.
| S-EPMC5013469 | biostudies-literature
Project description:Preferential attachment is a stochastic process that has been proposed to explain certain topological features characteristic of complex networks from diverse domains. The systematic investigation of preferential attachment is an important area of research in network science, not only for the theoretical matter of verifying whether this hypothesized process is operative in real-world networks, but also for the practical insights that follow from knowledge of its functional form. Here we describe a maximum likelihood based estimation method for the measurement of preferential attachment in temporal complex networks. We call the method PAFit, and implement it in an R package of the same name. PAFit constitutes an advance over previous methods primarily because we based it on a nonparametric statistical framework that enables attachment kernel estimation free of any assumptions about its functional form. We show this results in PAFit outperforming the popular methods of Jeong and Newman in Monte Carlo simulations. What is more, we found that the application of PAFit to a publically available Flickr social network dataset yielded clear evidence for a deviation of the attachment kernel from the popularly assumed log-linear form. Independent of our main work, we provide a correction to a consequential error in Newman's original method which had evidently gone unnoticed since its publication over a decade ago.
| S-EPMC4574777 | biostudies-literature
Project description:Controlling complex networks has become a forefront research area in network science and engineering. Recent efforts have led to theoretical frameworks of controllability to fully control a network through steering a minimum set of driver nodes. However, in realistic situations not every node is accessible or can be externally driven, raising the fundamental issue of control efficacy: if driving signals are applied to an arbitrary subset of nodes, how many other nodes can be controlled? We develop a framework to determine the control efficacy for undirected networks of arbitrary topology. Mathematically, based on non-singular transformation, we prove a theorem to determine rigorously the control efficacy of the network and to identify the nodes that can be controlled for any given driver nodes. Physically, we develop the picture of diffusion that views the control process as a signal diffused from input signals to the set of controllable nodes. The combination of mathematical theory and physical reasoning allows us not only to determine the control efficacy for model complex networks and a large number of empirical networks, but also to uncover phenomena in network control, e.g., hub nodes in general possess lower control centrality than an average node in undirected networks.
| S-EPMC4914948 | biostudies-literature
Project description:Viral infection exerts selection pressure on marine microbes, as virus-induced cell lysis causes 20 to 50% of cell mortality, resulting in fluxes of biomass into oceanic dissolved organic matter. Archaeal and bacterial populations can defend against viral infection using the clustered regularly interspaced short palindromic repeat (CRISPR)-associated (Cas) system, which relies on specific matching between a spacer sequence and a viral gene. If a CRISPR spacer match to any gene within a viral genome is equally effective in preventing lysis, no viral genes should be preferentially matched by CRISPR spacers. However, if there are differences in effectiveness, certain viral genes may demonstrate a greater frequency of CRISPR spacer matches. Indeed, homology search analyses of bacterioplankton CRISPR spacer sequences against virioplankton sequences revealed preferential matching of replication proteins, nucleic acid binding proteins, and viral structural proteins. Positive selection pressure for effective viral defense is one parsimonious explanation for these observations. CRISPR spacers from virioplankton metagenomes preferentially matched methyltransferase and phage integrase genes within virioplankton sequences. These virioplankton CRISPR spacers may assist infected host cells in defending against competing phage. Analyses also revealed that half of the spacer-matched viral genes were unknown, some genes matched several spacers, and some spacers matched multiple genes, a many-to-many relationship. Thus, CRISPR spacer matching may be an evolutionary algorithm, agnostically identifying those genes under stringent selection pressure for sustaining viral infection and lysis. Investigating this subset of viral genes could reveal those genetic mechanisms essential to virus-host interactions and provide new technologies for optimizing CRISPR defense in beneficial microbes.IMPORTANCE The CRISPR-Cas system is one means by which bacterial and archaeal populations defend against viral infection which causes 20 to 50% of cell mortality in the ocean. We tested the hypothesis that certain viral genes are preferentially targeted for the initial attack of the CRISPR-Cas system on a viral genome. Using CASC, a pipeline for CRISPR spacer discovery, and metagenome data from oceanic microbes and viruses, we found a clear subset of viral genes with high match frequencies to CRISPR spacers. Moreover, we observed a many-to-many relationship of spacers and viral genes. These high-match viral genes were involved in nucleotide metabolism, DNA methylation, and viral structure. It is possible that CRISPR spacer matching is an evolutionary algorithm pointing to those viral genes most important to sustaining infection and lysis. Studying these genes may advance the understanding of virus-host interactions in nature and provide new technologies for leveraging CRISPR-Cas systems in beneficial microbes.
| S-EPMC6401485 | biostudies-literature
Project description:The aim of this paper is to shed light on the problem of controlling a complex network with minimal control energy. We show first that the control energy depends on the time constant of the modes of the network, and that the closer the eigenvalues are to the imaginary axis of the complex plane, the less energy is required for complete controllability. In the limit case of networks having all purely imaginary eigenvalues (e.g. networks of coupled harmonic oscillators), several constructive algorithms for minimum control energy driver node selection are developed. A general heuristic principle valid for any directed network is also proposed: the overall cost of controlling a network is reduced when the controls are concentrated on the nodes with highest ratio of weighted outdegree vs indegree.
| S-EPMC5816648 | biostudies-literature