Optimal strategies to influence network decisions with minimum effort
Intervention problems in the Linear Threshold Model: A general formulation and new results
Computer Science and Game TheoryMultiagent SystemsSocial and Information Networks
Summary
The paper looks at how to change people's choices in a network by adjusting the rules they follow for making decisions. In this model, each person decides based on how many of their friends have chosen a certain action, like turning on a light switch if enough neighbors do. The researchers study how a planner can increase individuals' thresholds, or resistance, to ensure that everyone eventually picks the same option, while spending the least amount of effort. They introduce a graph measure called the oriented path number, which helps calculate the least cost to achieve full agreement in the network under certain conditions.
What this means in practice
- •For marketing strategists: Design minimal-cost campaigns to ensure product adoption spreads widely in social networks by targeting key influence thresholds.
- •For social network analysts: Model and plan interventions to drive consensus or behavior change in online networks by adjusting user influence parameters efficiently.
Authors
Giacomo Como, Fabio Fagnani, Stephane Durand
Abstract
We study an optimal intervention problem for linear threshold models. This is a popular class of dynamical network systems whereby a number of agents, identified with the nodes of a graph, strategically change their binary action (0 or 1) according to a threshold rule. Specifically, an agent adopts action 1 if and only if the fraction of its neighbors in the interaction graph that do so is greater than or equal to a prescribed threshold. Assuming that a planner can modify the agents' thresholds at a cost equal to the aggregate threshold increase, we study the minimum intervention cost needed to ensure global convergence to the all-1 configuration. Our main contribution is the introduction of a new graph-theoretic quantity, called oriented path number, that is the minimum number of disjoint paths needed to cover the graph that can be oriented to form a directed acyclic graph. When thresholds are all equal to 1/2, the optimal cost is shown to coincide with the oriented path number, whereas, in the general case, it turns out to be the main ingredient of a bound on the optimal intervention cost.