Distribution-Free Models of Social Networks

Tim Roughgarden, C. Seshadhri

Abstract

The structure of large-scale social networks has predominantly been articulated using generative models, a form of average-case analysis. This chapter surveys recent proposals of more robust models of such networks. These models posit deterministic and empirically supported combinatorial structure rather than a specific probability distribution. We discuss the formal definitions of these models and how they relate to empirical observations in social networks, as well as the known structural and algorithmic results for the corresponding graph classes.
BibTeX
@inproceedings{roughgarden2020distribution,
  author = {Tim Roughgarden and C. Seshadhri},
  title = {{Distribution-Free Models of Social Networks}},
  booktitle = {Beyond the Worst-Case Analysis of Algorithms},
  year = {2020},
  url = {https://openreview.net/forum?id=JGKJXiK2b1},
}

Loading related content...

Figure