Make it or break it, games and opinions on social networks

We are interested in the problem of Probably Approximately Correct (PAC) learning the structure of a social network by observing its threshold-based opinion dynamics. Using the PAC-learning framework, we aim to retrieve the edges of a directed graph whose nodes represent the agents in the social network. The agents are coloured based on their opinions and update according to a given update function. We have results for unanimity, all-but-k, and majority opinion dynamics. In these models, agents increasingly require more of their influencers to disagree with them in order to prompt an opinion change.