TL;DR研究 Majority Model 和 Random Majority Model 在 social network 中的表现,证明了其稳定配置状态需要指数级的时间,以及稳定涂色方案的数量,对初态随机涂色的期望涂色数量进行了分析,并且研究了“获胜集合”大小的下界。
Abstract
Consider a graph G with n nodes and m edges, which represents a social network, and assume that initially each node is blue or white. In each round, all nodes simultaneously update their color to the most frequent color in their neighborhood. This is called the majority model (MM) if a