Browse
Submit Data
Databases
API
Help

Dataset Information

25 Views

0 Connections

0 Citations

0 Reanalyses

0 Downloads

Omics score: 0

Social Influence Maximization in Hypergraphs.

ABSTRACT: 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.

SUBMITTER: Antelmi A

PROVIDER: S-EPMC8305154 | biostudies-literature |

REPOSITORIES: biostudies-literature

ACCESS DATA

Json Xml

Similar Datasets

Influence maximization in Boolean networks.

Project description: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 social networks. We validate the method on small gene regulatory networks whose dynamical landscapes are known by means of brute-force analysis. We then systematically study a large collection of gene regulatory networks. We find that for about 65% of the analyzed networks, the minimal driver sets contain less than 20% of their nodes.

| S-EPMC9203747 | biostudies-literature

Multistability, intermittency, and hybrid transitions in social contagion models on hypergraphs.

Project description:Although ubiquitous, interactions in groups of individuals are not yet thoroughly studied. Frequently, single groups are modeled as critical-mass dynamics, which is a widespread concept used not only by academics but also by politicians and the media. However, less explored questions are how a collection of groups will behave and how their intersection might change the dynamics. Here, we formulate this process as binary-state dynamics on hypergraphs. We showed that our model has a rich behavior beyond discontinuous transitions. Notably, we have multistability and intermittency. We demonstrated that this phenomenology could be associated with community structures, where we might have multistability or intermittency by controlling the number or size of bridges between communities. Furthermore, we provided evidence that the observed transitions are hybrid. Our findings open new paths for research, ranging from physics, on the formal calculation of quantities of interest, to social sciences, where new experiments can be designed.

| S-EPMC10011415 | biostudies-literature

Influence Maximization for Fixed Heterogeneous Thresholds.

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

Reverse engineering molecular hypergraphs.

Project description:Analysis of molecular interaction networks is pervasive in systems biology. This research relies almost entirely on graphs for modeling interactions. However, edges in graphs cannot represent multiway interactions among molecules, which occur very often within cells. Hypergraphs may be better representations for networks having such interactions, since hyperedges can naturally represent relationships among multiple molecules. Here, we propose using hypergraphs to capture the uncertainty inherent in reverse engineering gene-gene networks. Some subsets of nodes may induce highly varying subgraphs across an ensemble of networks inferred by a reverse engineering algorithm. We provide a novel formulation of hyperedges to capture this uncertainty in network topology. We propose a clustering-based approach to discover hyperedges. We show that our approach can recover hyperedges planted in synthetic data sets with high precision and recall, even for moderate amount of noise. We apply our techniques to a data set of pathways inferred from genetic interaction data in S. cerevisiae related to the unfolded protein response. Our approach discovers several hyperedges that capture the uncertain connectivity of genes in relevant protein complexes, suggesting that further experiments may be required to precisely discern their interaction patterns. We also show that these complexes are not discovered by an algorithm that computes frequent and dense subgraphs.

| S-EPMC4051496 | biostudies-literature

Fixation dynamics on hypergraphs.

Project description:Hypergraphs have been a useful tool for analyzing population dynamics such as opinion formation and the public goods game occurring in overlapping groups of individuals. In the present study, we propose and analyze evolutionary dynamics on hypergraphs, in which each node takes one of the two types of different but constant fitness values. For the corresponding dynamics on conventional networks, under the birth-death process and uniform initial conditions, most networks are known to be amplifiers of natural selection; amplifiers by definition enhance the difference in the strength of the two competing types in terms of the probability that the mutant type fixates in the population. In contrast, we provide strong computational evidence that a majority of hypergraphs are suppressors of selection under the same conditions by combining theoretical and numerical analyses. We also show that this suppressing effect is not explained by one-mode projection, which is a standard method for expressing hypergraph data as a conventional network. Our results suggest that the modeling framework for structured populations in addition to the specific network structure is an important determinant of evolutionary dynamics, paving a way to studying fixation dynamics on higher-order networks including hypergraphs.

| S-EPMC10558078 | biostudies-literature

Identifying vital nodes for influence maximization in attributed networks

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

| S-EPMC9805466 | biostudies-literature

Competition between Homophily and Information Entropy Maximization in Social Networks.

Project description:In social networks, it is conventionally thought that two individuals with more overlapped friends tend to establish a new friendship, which could be stated as homophily breeding new connections. While the recent hypothesis of maximum information entropy is presented as the possible origin of effective navigation in small-world networks. We find there exists a competition between information entropy maximization and homophily in local structure through both theoretical and experimental analysis. This competition suggests that a newly built relationship between two individuals with more common friends would lead to less information entropy gain for them. We demonstrate that in the evolution of the social network, both of the two assumptions coexist. The rule of maximum information entropy produces weak ties in the network, while the law of homophily makes the network highly clustered locally and the individuals would obtain strong and trust ties. A toy model is also presented to demonstrate the competition and evaluate the roles of different rules in the evolution of real networks. Our findings could shed light on the social network modeling from a new perspective.

| S-EPMC4559466 | biostudies-literature

Link-based influence maximization in networks of health promotion professionals.

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

Data-Driven Engineering of Social Dynamics: Pattern Matching and Profit Maximization.

Project description:In this paper, we define a new problem related to social media, namely, the data-driven engineering of social dynamics. More precisely, given a set of observations from the past, we aim at finding the best short-term intervention that can lead to predefined long-term outcomes. Toward this end, we propose a general formulation that covers two useful engineering tasks as special cases, namely, pattern matching and profit maximization. By incorporating a deep learning model, we derive a solution using convex relaxation and quadratic-programming transformation. Moreover, we propose a data-driven evaluation method in place of the expensive field experiments. Using a Twitter dataset, we demonstrate the effectiveness of our dynamics engineering approach for both pattern matching and profit maximization, and study the multifaceted interplay among several important factors of dynamics engineering, such as solution validity, pattern-matching accuracy, and intervention cost. Finally, the method we propose is general enough to work with multi-dimensional time series, so it can potentially be used in many other applications.

| S-EPMC4714878 | biostudies-literature

Influence maximization in time bounded network identifies transcription factors regulating perturbed pathways.

Project description:MotivationTo understand the dynamic nature of the biological process, it is crucial to identify perturbed pathways in an altered environment and also to infer regulators that trigger the response. Current time-series analysis methods, however, are not powerful enough to identify perturbed pathways and regulators simultaneously. Widely used methods include methods to determine gene sets such as differentially expressed genes or gene clusters and these genes sets need to be further interpreted in terms of biological pathways using other tools. Most pathway analysis methods are not designed for time series data and they do not consider gene-gene influence on the time dimension.ResultsIn this article, we propose a novel time-series analysis method TimeTP for determining transcription factors (TFs) regulating pathway perturbation, which narrows the focus to perturbed sub-pathways and utilizes the gene regulatory network and protein-protein interaction network to locate TFs triggering the perturbation. TimeTP first identifies perturbed sub-pathways that propagate the expression changes along the time. Starting points of the perturbed sub-pathways are mapped into the network and the most influential TFs are determined by influence maximization technique. The analysis result is visually summarized in TF-PATHWAY MAP IN TIME CLOCK: TimeTP was applied to PIK3CA knock-in dataset and found significant sub-pathways and their regulators relevant to the PIP3 signaling pathway.Availability and implementationTimeTP is implemented in Python and available at http://biohealth.snu.ac.kr/software/TimeTP/Supplementary information: Supplementary data are available at Bioinformatics online.Contactsunkim.bioinfo@snu.ac.kr.

| S-EPMC4908359 | biostudies-literature

OmicsDI is part of the ELIXIR infrastructure

OmicsDI is an Elixir interoperability service. Learn more ›

Tweets

OmicsDI Databases

PRIDE
PeptideAtlas
MassIVE
JPOST Repository
Physiome Model Repository

EGA
EVA
ENA
LINCS
PAXDB
Cell Collective

MetaboLights
Metabolomics Workbench
MetabolomeExpress
GNPS
BioModels
FAIRDOMHub

ArrayExpress
dbGaP
ExpressionAtlas
GEO
NODE

Information

Databases
Help
API
Contact us
Code on GitHub
Terms of use
Submit Data