On the Limits of PAC Learning Opinion Dynamics

Agents in social networks with threshold-based dynamics change opinions when influenced by sufficiently many peers. Existing literature typically assumes that the network structure and dynamics are fully known, which is often unrealistic. In this work, we ask how to learn a network structure from samples of the agents' synchronous opinion updates. Firstly, if the opinion dynamics follow a threshold rule where a fixed number of influencers prevent opinion change (e.g., unanimity and quasi-unanimity), we give an efficient PAC learning algorithm provided that the number of influencers per agent is bounded. Secondly, under standard computational complexity assumptions, we prove that if the opinion of agents follows the majority of their influencers, then there is no efficient PAC learning algorithm. We propose a polynomial-time heuristic that successfully learns consistent networks in over 97% of our simulations on random graphs, with no failures for some specified conditions on the numbers of agents and opinion diffusion examples.