On irreversible spread of influence in edge-weighted graphs

DOI10.11575/CDM.V15I2.68115MaRDI QIDQ3303530zbMATH OpenOpenAlexFDO

Authors Manouchehr Zaker

Publication date 12 August 2020

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

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)

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.

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

Cites work

• scientific article; zbMATH DE number 6474901 (Why is no real title available?)
• scientific article; zbMATH DE number 2203240 (Why is no real title available?)
• Bootstrap percolation in living neural networks
• Combinatorial model and bounds for target set selection
• Irreversible \(k\)-threshold processes: Graph-theoretical threshold models of the spread of disease and of opinion
• Irreversible conversion of graphs
• On dynamic monopolies of graphs: the average and strict majority thresholds
• On the approximability of influence in social networks
• On time versus size for monotone dynamic monopolies in regular topologies
• On tractable cases of target set selection
• Treewidth governs the complexity of target set selection

Cited in

(3)

• The effect of reverse edges on convergence rate of directed weighted chain network
• Spread of influence in weighted networks under time and budget constraints
• 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)