On irreversible spread of influence in edge-weighted graphs

DOI10.11575/CDM.V15I2.68115zbMATH Open1445.05080arXiv1912.01243OpenAlexW3138011811MaRDI QIDQ3303530FDOQ3303530

Manouchehr Zaker

Publication date: 12 August 2020

Abstract: Various kinds of spread of influence occur in real world social and virtual networks. These phenomena are formulated by activation processes and irreversible dynamic monopolies in combinatorial graphs representing the topology of the networks. In most cases the nature of influence is weighted and the spread of influence depends on the weight of edges. The ordinary formulation and results for dynamic monopolies do not work for such models. In this paper we present a graph theoretical analysis for spread of weighted influence and mention a real world example realizing the activation model with weighted influence. Then we obtain some extremal bounds and algorithmic results for activation process and dynamic monopolies in directed and undirected graphs with weighted edges.

Full work available at URL: https://arxiv.org/abs/1912.01243

Recommendations

• Dynamic monopolies in directed graphs: the spread of unilateral influence in social networks
• Weak dynamic monopolies in social graphs
• Spread of influence in weighted networks under time and budget constraints
• A polyhedral study of dynamic monopolies
• On the spread of influence in graphs

zbMATH Keywords

irreversible dynamic monopoliesspread of influence in graphsedge weighted graphs

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Social networks; opinion dynamics (91D30) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Signed and weighted graphs (05C22)

Cites Work

• On time versus size for monotone dynamic monopolies in regular topologies
• On the approximability of influence in social networks
• Combinatorial model and bounds for target set selection
• On dynamic monopolies of graphs: the average and strict majority thresholds
• Treewidth governs the complexity of target set selection
• Title not available (Why is that?)
• Title not available (Why is that?)
• Irreversible \(k\)-threshold processes: Graph-theoretical threshold models of the spread of disease and of opinion
• Irreversible conversion of graphs
• Bootstrap percolation in living neural networks
• On Tractable Cases of Target Set Selection

Cited In (2)

• The effect of reverse edges on convergence rate of directed weighted chain network
• Spread of influence with incentives in edge-weighted graphs with emphasis on some families of graphs

This page was built for publication: On irreversible spread of influence in edge-weighted graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3303530)