New PAC learning algorithm reveals network structure from opinion dynamics

A team from the University of Warwick (Dmitry Chistikov, Luisa Estrada, Mike Paterson, Paolo Turrini) has investigated the computational limits of inferring social network structures from observed opinion dynamics. In their paper submitted to arXiv on May 14, 2026, they consider agents that update opinions synchronously based on thresholds—switching only when a fixed number of neighbors disagree. The central question: can we efficiently learn the underlying network from samples of these updates?

The authors prove two key results. First, if the dynamics follow a ‘unanimity’ or ‘quasi-unanimity’ rule—where a predetermined number of neighbors must all agree to prevent change—then the network can be PAC-learned in polynomial time, provided each agent’s number of influencers is bounded. This opens the door to reconstructing real-world influence networks when decisions require near-consensus. Second, if agents simply follow the majority, they show there is no efficient PAC learning algorithm unless standard complexity assumptions (like P ≠ NP) fail. This negative result highlights the inherent difficulty of reverse-engineering networks driven by majoritarian behavior. To bridge theory and practice, the team also proposes a polynomial-time heuristic that recovers a consistent network in over 98% of random graph simulations, with zero failures under certain conditions on agent counts and sample sizes.