On the Limits of PAC Learning of Networks from Opinion Dynamics
Fuente:
arXiv
Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Preprint |
| Published: |
2026
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866916013248872448 |
|---|---|
| author | Chistikov, Dmitry Estrada, Luisa Paterson, Mike Turrini, Paolo |
| author_facet | Chistikov, Dmitry Estrada, Luisa Paterson, Mike Turrini, Paolo |
| contents | 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 in which a fixed number of influencers prevent opinion change (e.g., unanimity and quasi-unanimity), we provide 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 agents' opinions follow 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 $98\%$ of our simulations on random graphs, with no failures for some specified conditions on the numbers of agents and opinion diffusion examples. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2605_15033 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | On the Limits of PAC Learning of Networks from Opinion Dynamics Chistikov, Dmitry Estrada, Luisa Paterson, Mike Turrini, Paolo Social and Information Networks Computational Complexity 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 in which a fixed number of influencers prevent opinion change (e.g., unanimity and quasi-unanimity), we provide 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 agents' opinions follow 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 $98\%$ of our simulations on random graphs, with no failures for some specified conditions on the numbers of agents and opinion diffusion examples. |
| title | On the Limits of PAC Learning of Networks from Opinion Dynamics |
| topic | Social and Information Networks Computational Complexity |
| url | https://arxiv.org/abs/2605.15033 |