Search

Network controllability is unifying the traditional control theory with the structural network information rooted in many large-scale biological systems of interest, from intracellular networks in molecular biology to brain neuronal networks. In controllability approaches, the set of minimum driver nodes is not unique, and critical nodes are the most important control elements because they appear in all possible solution sets. On the other hand, a common but largely unexplored feature in network control approaches is the probabilistic failure of edges or the uncertainty in the determination of interactions between molecules. This is particularly true when directed probabilistic interactions are considered. Until now, no efficient algorithm existed to determine critical nodes in probabilistic directed networks. Here we present a probabilistic control model based on a minimum dominating set framework that integrates the probabilistic nature of directed edges between molecules and determines the critical control nodes that drive the entire network functionality. The proposed algorithm, combined with the developed mathematical tools, offers practical efficiency in determining critical control nodes in large probabilistic networks. The method is then applied to the human intracellular signal transduction network revealing that critical control nodes are associated with important biological features and perturbed sets of genes in human diseases, including SARS-CoV-2 target proteins and rare disorders. We believe that the proposed methodology can be useful to investigate multiple biological systems in which directed edges are probabilistic in nature, both in natural systems or when determined with large uncertainties in-silico. [ABSTRACT FROM AUTHOR]

Securing complete control of complex systems comprised of tens of thousands of interconnected nodes holds immense significance across various fields, spanning from cell biology and brain science to human-engineered systems. However, depending on specific functional requirements, it can be more practical and efficient to focus on a pre-defined subset of nodes for control, a concept known as target control. While some methods have been proposed to find the smallest driver node set for target control, they either rely on heuristic approaches based on k-walk theory, lacking a guarantee of optimal solutions, or they are overly complex and challenging to implement in real-world networks. To address this challenge, we introduce a simple and elegant algorithm, inspired by the path cover problem, which efficiently identifies the nodes required to control a target node set within polynomial time. To practically apply the algorithm in real-world systems, we have selected several networks in which a specific set of nodes with functional significance can be designated as a target control set. The analysed systems include the complete connectome of the nematode worm C. elegans, the recently disclosed connectome of the Drosophila larval brain, as well as dozens of genome-wide metabolic networks spanning major plant lineages. The target control analysis shed light on distinctions between neural systems in nematode worms and larval brain insects, particularly concerning the number of nodes necessary to regulate specific functional systems. Furthermore, our analysis uncovers evolutionary trends within plant lineages, notably when examining the proportion of nodes required to control functional pathways. [ABSTRACT FROM AUTHOR]

Recent studies have drawn attention to the problem of how complex networks can be controlled through a small number of controller nodes. Here, we develop an algorithmic procedure and mathematical tools to compute and evaluate the critical and redundant nodes in controlling directed and undirected scale-free networks using the minimum dominating set (MDS) approach. Because there are multiple MDS configurations that control the entire network, we can classify the nodes depending on the condition whether a node is part of all (critical), some but not all (intermittent), or does not participate in any (redundant) possible MDS. The presented mathematical analysis predicts the probability of finding a critical node in undirected scale-free networks with $k^{-\gamma }$, where $k$ is a node degree, as a function of the scaling exponent $\gamma $ and its node degree. Critical nodes tend to have high degree and are more abundant in undirected scale-free networks with high $\gamma $. In addition, analytical expressions of lower bounds for the number of critical nodes for both undirected and directed networks are also derived. By applying the MDS control model, we find that undirected networks can be controlled with relatively fewer nodes than those engaged in controlling directed networks. On the other hand, our computational experiments also show that the MDS is unimodal with varying the average degree $\langle k \rangle $ in both directed and undirected networks. In particular, by increasing $\langle k \rangle $, the fraction of nodes engaged in control becomes smaller, which highlights a centralized control mode. The analysis of a set of undirected and directed real-world networks confirms the findings shown in theoretical analysis and simulation experiments. [ABSTRACT FROM AUTHOR]