Learning Opinions in Social Networks

Vincent Conitzer · Debmalya Panigrahi · Hanrui Zhang


Keywords: [ Learning Theory ] [ Statistical Learning Theory ] [ Network Analysis ]

[ Abstract ]
[ Slides
Wed 15 Jul 5 a.m. PDT — 5:45 a.m. PDT
Wed 15 Jul 4 p.m. PDT — 4:45 p.m. PDT


We study the problem of learning opinions in social networks. The learner observes the states of some sample nodes from a social network, and tries to infer the states of other nodes, based on the structure of the network. We show that sample-efficient learning is impossible when the network exhibits strong noise, and give a polynomial-time algorithm for the problem with nearly optimal sample complexity when the network is sufficiently stable.

Chat is not available.