Spread of Influence in Graphs

MaRDI QIDQ6342186FDOQ6342186

Authors: Ahad N. Zehmakan 

Publication date: 3 June 2020

Abstract: Consider a graph $G$ and an initial configuration where each node is black or white. Assume that in each round all nodes simultaneously update their color based on a predefined rule. One can think of graph $G$ as a social network, where each black/white node represents an individual who holds a positive/negative opinion regarding a particular topic. In the $r$-threshold (resp. $alpha$-threshold) model, a node becomes black if at least $r$ of its neighbors (resp. $alpha$ fraction of its neighbors) are black, and white otherwise. The $r$-monotone (resp. $alpha$-monotone) model is the same as the $r$-threshold (resp. $alpha$-threshold) model, except that a black node remains black forever. What is the number of rounds that the process needs to stabilize? How many nodes must be black initially so that black color takes over or survives? Our main goal in the present paper is to address these two questions

This page was built for publication: Spread of Influence in Graphs

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