Action selection in growing state spaces: Control of Network Structure Growth
For researchers studying network growth and dynamics, this work provides a control framework to influence network topology, though it is demonstrated only on a specific application (conversation threads) and may be incremental.
The authors formulate network growth control as a stochastic optimal control problem and approximate it using probabilistic inference with adaptive importance sampling. They demonstrate that their method produces conversation threads with better structural properties than uncontrolled growth in a realistic model.
The dynamical processes taking place on a network depend on its topology. Influencing the growth process of a network therefore has important implications on such dynamical processes. We formulate the problem of influencing the growth of a network as a stochastic optimal control problem in which a structural cost function penalizes undesired topologies. We approximate this control problem with a restricted class of control problems that can be solved using probabilistic inference methods. To deal with the increasing problem dimensionality, we introduce an adaptive importance sampling method for approximating the optimal control. We illustrate this methodology in the context of formation of information cascades, considering the task of influencing the structure of a growing conversation thread, as in Internet forums. Using a realistic model of growing trees, we show that our approach can yield conversation threads with better structural properties than the ones observed without control.