Cascading phenomena in social networks happen when the adoption of some behaviour by initial adopters causes some of their immediate friends to adopt which again causes some of their friends’ friends to adopt, and so on. Who the initial adopters are, or rather how they are positioned in the network, is of crucial importance for the potential cascade. In this paper we look at the relative importance of different agents as initial adopters in a network, for a given cascading goal such as a complete cascade: which groups of agents are sufficient, which groups are necessary, and which agents are the most important to have as initial adopters in order for the goal to be achieved? For the latter question, we look to cooperative games and power measures to identify agents who are pivotal for a group of inital adopters with respect to the goal. We characterise the computational complexity of resulting decision and counting problems, when the goal is represented using a propositional logical formula. We also draw connections to abduction in logic programming.

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Cascading Power

  • Thomas Ågotnes,
  • Zoé Christoff

摘要

Cascading phenomena in social networks happen when the adoption of some behaviour by initial adopters causes some of their immediate friends to adopt which again causes some of their friends’ friends to adopt, and so on. Who the initial adopters are, or rather how they are positioned in the network, is of crucial importance for the potential cascade. In this paper we look at the relative importance of different agents as initial adopters in a network, for a given cascading goal such as a complete cascade: which groups of agents are sufficient, which groups are necessary, and which agents are the most important to have as initial adopters in order for the goal to be achieved? For the latter question, we look to cooperative games and power measures to identify agents who are pivotal for a group of inital adopters with respect to the goal. We characterise the computational complexity of resulting decision and counting problems, when the goal is represented using a propositional logical formula. We also draw connections to abduction in logic programming.