Random graph models of social networks

doi:10.1073/pnas.012582999

Random graph models of social networks

^*Santa Fe Institute, 1399 Hyde Park Road, Santa Fe, NM 87501;^‡ Department of Sociology, Columbia University, 1180 Amsterdam Avenue, New York, NY 10027; and ^§Department of Theoretical and Applied Mechanics, Cornell University, Ithaca, NY 14853-1503

Abstract

We describe some new exactly solvable models of the structure of social networks, based on random graphs with arbitrary degree distributions. We give models both for simple unipartite networks, such as acquaintance networks, and bipartite networks, such as affiliation networks. We compare the predictions of our models to data for a number of real-world social networks and find that in some cases, the models are in remarkable agreement with the data, whereas in others the agreement is poorer, perhaps indicating the presence of additional social structure in the network that is not captured by the random graph.

Footnotes

↵ † To whom reprint requests should be addressed. E-mail: mark{at}santafe.edu.
This paper results from the Arthur M. Sackler Colloquium of the National Academy of Sciences, “Self-Organized Complexity in the Physical, Biological, and Social Sciences,” held March 23–24, 2001, at the Arnold and Mabel Beckman Center of the National Academies of Science and Engineering in Irvine, CA.