Influence maximization in Boolean networks.
Ontology highlight
ABSTRACT:
SUBMITTER: Parmer T
PROVIDER: S-EPMC9203747 | biostudies-literature | 2022 Jun
REPOSITORIES: biostudies-literature
Publications
Influence maximization in Boolean networks.
Parmer Thomas T Rocha Luis M LM Radicchi Filippo F
Nature communications 20220616 1
The optimization problem aiming at the identification of minimal sets of nodes able to drive the dynamics of Boolean networks toward desired long-term behaviors is central for some applications, as for example the detection of key therapeutic targets to control pathways in models of biological signaling and regulatory networks. Here, we develop a method to solve such an optimization problem taking inspiration from the well-studied problem of influence maximization for spreading processes in soci ...[more]
Similar Datasets
Project description:Identifying a set of vital nodes to achieve influence maximization is a topic of general interest in network science. Many algorithms have been proposed to solve the influence maximization problem in complex networks. Most of them just use topology information of networks to measure the node influence. However, the node attribute is also an important factor for measuring node influence in attributed networks. To tackle this problem, we first propose an extension model of linear threshold (LT) propagation model to simulate the information propagation in attributed networks. Then, we propose a novel community-based method to identify a set of vital nodes for influence maximization in attributed networks. The proposed method considers both topology influence and attribute influence of nodes, which is more suitable for identifying vital nodes in attributed networks. A series of experiments are carried out on five real world networks and a large scale synthetic network. Compared with CELF, IMM, CoFIM, HGD, NCVoteRank and K-Shell methods, experimental results based on different propagation models show that the proposed method improves the influence spread by [Formula: see text], [Formula: see text], [Formula: see text], [Formula: see text], [Formula: see text] and [Formula: see text].
| S-EPMC9805466 | biostudies-literature
Project description:The influence maximization problem (IMP) as classically formulated is based on the strong assumption that "chosen" nodes always adopt the new product. In this paper we propose a new influence maximization problem, referred to as the "Link-based Influence Maximization Problem" (LIM), which differs from IMP in that the decision variable of the spreader has changed from choosing an optimal seed to selecting an optimal node to influence in order to maximize the spread. Based on our proof that LIM is NP-hard with a monotonic increasing and submodular target function, we propose a greedy algorithm, GLIM, for optimizing LIM and use numerical simulation to explore the performance in terms of spread and computation time in different network types. The results indicate that the performance of LIM varies across network types. We illustrate LIM by applying it in the context of a Dutch national health promotion program for prevention of youth obesity within a network of Dutch schools. GLIM is seen to outperform the other methods in all network types at the cost of a higher computation time. These results suggests that GLIM may be utilized to increase the effectiveness of health promotion programs.
| S-EPMC8386878 | biostudies-literature
Project description:Most current studies on information diffusion in online social networks focus on the deterministic aspects of social networks. However, the behavioral parameters of online social networks are uncertain, unpredictable, and time-varying. Thus, deterministic graphs for modeling information diffusion in online social networks are too restrictive to solve most real network problems, such as influence maximization. Recently, stochastic graphs have been proposed as a graph model for social network applications where the weights associated with links in the stochastic graph are random variables. In this paper, we first propose a diffusion model based on a stochastic graph, in which influence probabilities associated with its links are unknown random variables. Then we develop an approach using the set of learning automata residing in the proposed diffusion model to estimate the influence probabilities by sampling from the links of the stochastic graph. Numerical simulations conducted on real and artificial stochastic networks demonstrate the effectiveness of the proposed stochastic diffusion model for influence maximization.
| S-EPMC10104855 | biostudies-literature
Project description:This work deals with a generalization of the minimum Target Set Selection (TSS) problem, a key algorithmic question in information diffusion research due to its potential commercial value. Firstly proposed by Kempe et al., the TSS problem is based on a linear threshold diffusion model defined on an input graph with node thresholds, quantifying the hardness to influence each node. The goal is to find the smaller set of items that can influence the whole network according to the diffusion model defined. This study generalizes the TSS problem on networks characterized by many-to-many relationships modeled via hypergraphs. Specifically, we introduce a linear threshold diffusion process on such structures, which evolves as follows. Let H=(V,E) be a hypergraph. At the beginning of the process, the nodes in a given set S⊆V are influenced. Then, at each iteration, (i) the influenced hyperedges set is augmented by all edges having a sufficiently large number of influenced nodes; (ii) consequently, the set of influenced nodes is enlarged by all the nodes having a sufficiently large number of already influenced hyperedges. The process ends when no new nodes can be influenced. Exploiting this diffusion model, we define the minimum Target Set Selection problem on hypergraphs (TSSH). Being the problem NP-hard (as it generalizes the TSS problem), we introduce four heuristics and provide an extensive evaluation on real-world networks.
| S-EPMC8305154 | biostudies-literature
Project description:We investigate the sensitivity of Boolean Networks (BNs) to mutations. We are interested in Boolean Networks as a model of Gene Regulatory Networks (GRNs). We adopt Ribeiro and Kauffman's Ergodic Set and use it to study the long term dynamics of a BN. We define the sensitivity of a BN to be the mean change in its Ergodic Set structure under all possible loss of interaction mutations. In silico experiments were used to selectively evolve BNs for sensitivity to losing interactions. We find that maximum sensitivity was often achievable and resulted in the BNs becoming topologically balanced, i.e. they evolve towards network structures in which they have a similar number of inhibitory and excitatory interactions. In terms of the dynamics, the dominant sensitivity strategy that evolved was to build BNs with Ergodic Sets dominated by a single long limit cycle which is easily destabilised by mutations. We discuss the relevance of our findings in the context of Stem Cell Differentiation and propose a relationship between pluripotent stem cells and our evolved sensitive networks.
| S-EPMC3346810 | biostudies-literature
Project description:Influence Maximization is a NP-hard problem of selecting the optimal set of influencers in a network. Here, we propose two new approaches to influence maximization based on two very different metrics. The first metric, termed Balanced Index (BI), is fast to compute and assigns top values to two kinds of nodes: those with high resistance to adoption, and those with large out-degree. This is done by linearly combining three properties of a node: its degree, susceptibility to new opinions, and the impact its activation will have on its neighborhood. Controlling the weights between those three terms has a huge impact on performance. The second metric, termed Group Performance Index (GPI), measures performance of each node as an initiator when it is a part of randomly selected initiator set. In each such selection, the score assigned to each teammate is inversely proportional to the number of initiators causing the desired spread. These two metrics are applicable to various cascade models; here we test them on the Linear Threshold Model with fixed and known thresholds. Furthermore, we study the impact of network degree assortativity and threshold distribution on the cascade size for metrics including ours. The results demonstrate our two metrics deliver strong performance for influence maximization.
| S-EPMC6447584 | biostudies-literature
Project description:BackgroundBoolean networks (BNs) provide an effective modelling formalism for various complex biochemical phenomena. Their long term behaviour is represented by attractors-subsets of the state space towards which the BN eventually converges. These are then typically linked to different biological phenotypes. Depending on various logical parameters, the structure and quality of attractors can undergo a significant change, known as a bifurcation. We present a methodology for analysing bifurcations in asynchronous parametrised Boolean networks.ResultsIn this paper, we propose a computational framework employing advanced symbolic graph algorithms that enable the analysis of large networks with hundreds of Boolean variables. To visualise the results of this analysis, we developed a novel interactive presentation technique based on decision trees, allowing us to quickly uncover parameters crucial to the changes in the attractor landscape. As a whole, the methodology is implemented in our tool AEON. We evaluate the method's applicability on a complex human cell signalling network describing the activity of type-1 interferons and related molecules interacting with SARS-COV-2 virion. In particular, the analysis focuses on explaining the potential suppressive role of the recently proposed drug molecule GRL0617 on replication of the virus.ConclusionsThe proposed method creates a working analogy to the concept of bifurcation analysis widely used in kinetic modelling to reveal the impact of parameters on the system's stability. The important feature of our tool is its unique capability to work fast with large-scale networks with a relatively large extent of unknown information. The results obtained in the case study are in agreement with the recent biological findings.
| S-EPMC9092939 | biostudies-literature
Project description:Understanding the relationship between brain architecture and brain function is a central issue in neuroscience. We modeled realistic spatio-temporal patterns of brain activity on a human connectome with a Boolean networks model with the aim of computationally replicating certain cognitive functions as they emerge from the standardization of many fMRI studies, identified as patterns of human brain activity. Results from the analysis of simulation data, carried out for different parameters and initial conditions identified many possible paths in the space of parameters of these network models, with normal (ordered asymptotically constant patterns), chaotic (oscillating or disordered) but also highly organized configurations, with countless spatial-temporal patterns. We interpreted these results as routes to chaos, permanence of the systems in regimes of complexity, and ordered stationary behavior, associating these dynamics to cognitive processes. The most important result of this work is the study of emergent neural circuits, i.e., configurations of areas that synchronize over time, both locally and globally, determining the emergence of computational analogues of cognitive processes, which may or may not be similar to the functioning of biological brain. Furthermore, results put in evidence the creation of how the brain creates structures of remote communication. These structures have hierarchical organization, where each level allows for the emergence of brain organizations which behave at the next superior level. Taken together these results allow the interplay of dynamical and topological roots of the multifaceted brain dynamics to be understood.
| S-EPMC9529940 | biostudies-literature
Project description:BackgroundBoolean Networks (BNs) are a popular dynamical model in biology where the state of each component is represented by a variable taking binary values that express, for instance, activation/deactivation or high/low concentrations. Unfortunately, these models suffer from the state space explosion, i.e., there are exponentially many states in the number of BN variables, which hampers their analysis.ResultsWe present Boolean Backward Equivalence (BBE), a novel reduction technique for BNs which collapses system variables that, if initialized with same value, maintain matching values in all states. A large-scale validation on 86 models from two online model repositories reveals that BBE is effective, since it is able to reduce more than 90% of the models. Furthermore, on such models we also show that BBE brings notable analysis speed-ups, both in terms of state space generation and steady-state analysis. In several cases, BBE allowed the analysis of models that were originally intractable due to the complexity. On two selected case studies, we show how one can tune the reduction power of BBE using model-specific information to preserve all dynamics of interest, and selectively exclude behavior that does not have biological relevance.ConclusionsBBE complements existing reduction methods, preserving properties that other reduction methods fail to reproduce, and vice versa. BBE drops all and only the dynamics, including attractors, originating from states where BBE-equivalent variables have been initialized with different activation values The remaining part of the dynamics is preserved exactly, including the length of the preserved attractors, and their reachability from given initial conditions, without adding any spurious behaviours. Given that BBE is a model-to-model reduction technique, it can be combined with further reduction methods for BNs.
| S-EPMC10207686 | biostudies-literature
Project description:In this paper, we analyze the synchronization problem of master-slave probabilistic Boolean networks (PBNs). The master Boolean network (BN) is a deterministic BN, while the slave BN is determined by a series of possible logical functions with certain probability at each discrete time point. In this paper, we firstly define the synchronization of master-slave PBNs with probability one, and then we investigate synchronization with probability one. By resorting to new approach called semi-tensor product (STP), the master-slave PBNs are expressed in equivalent algebraic forms. Based on the algebraic form, some necessary and sufficient criteria are derived to guarantee synchronization with probability one. Further, we study the synchronization of master-slave PBNs in probability. Synchronization in probability implies that for any initial states, the master BN can be synchronized by the slave BN with certain probability, while synchronization with probability one implies that master BN can be synchronized by the slave BN with probability one. Based on the equivalent algebraic form, some efficient conditions are derived to guarantee synchronization in probability. Finally, several numerical examples are presented to show the effectiveness of the main results.
| S-EPMC4551960 | biostudies-other