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.
arXivLabs is a framework that allows collaborators to develop and share new arXiv features directly on our website.
Both individuals and organizations that work with arXivLabs have embraced and accepted our values of openness, community, excellence, and user data privacy. arXiv is committed to these values and only works with partners that adhere to them.
Have an idea for a project that will add value for arXiv's community? Learn more about arXivLabs.
