论文标题
在图中的影响
Spread of Influence in Graphs
论文作者
论文摘要
考虑图$ g $和每个节点为黑色或白色的初始配置。假设在每个回合中，所有节点都会根据预定义的规则同时更新其颜色。人们可以将Graph $ g $视为一个社交网络，每个黑色/白色节点代表一个对特定主题持积极/负面看法的人。在$ r $ $ - 阈值（分别$α$ - 阈值）型号中，如果至少$ r $的邻居（分别是$α$ neighbors的$α$分数）是黑色的，则节点变为黑色，否则为白色。 $ r $ - 单酮（分别$α$ -Sonotone）型号与$ r $ threshold（分别为$ $α$ - 阈值）型号相同，只是一个黑色节点永远是黑色的。 该过程需要稳定的回合数是多少？最初必须有多少个节点是黑色的，以便黑色接管或生存？本文中我们的主要目标是解决这两个问题
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. $α$-threshold) model, a node becomes black if at least $r$ of its neighbors (resp. $α$ fraction of its neighbors) are black, and white otherwise. The $r$-monotone (resp. $α$-monotone) model is the same as the $r$-threshold (resp. $α$-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
