Scaling in Biological and Social Networks - Abstract - Moore

Workshop Navigation Home Agenda Abstracts Attendees Speakers Travel Information

The Power of Choice in Social Networks

Cristopher Moore, University of New Mexico and the Santa Fe Institute

The "power of choice" is a familiar tool in computer science, where it can be used to distribute jobs over a set of processors in a way which is much more uniform than a random distribution. I will report on some recent work with Raissa D'Souza and Paul Krapivsky, in which have looked at the power of choice in social networks. For instance, consider the following model: there is a growing tree. At each step, a new node is added. It has k contacts chosen randomly from the existing nodes, where k is a constant, and it connects to whichever one is closest to the root. I will show that this results in a distribution of depths given by a differential equation with a traveling-wave solution. Another application is to have a generate a peer-to-peer network with a nearly-uniform degree distribution, where the maximum degree is O(log log n).