Reed's law

related topics
{math, number, function}
{group, member, jewish}
{rate, high, increase}
{system, computer, user}
{law, state, case}
{@card@, make, design}

Reed's law is the assertion of David P. Reed that the utility of large networks, particularly social networks, can scale exponentially with the size of the network.

The reason for this is that the number of possible sub-groups of network participants is 2^N - N - 1 \, , where N is the number of participants. This grows much more rapidly than either

  • the number of participants, N, or
  • the number of possible pair connections, \frac{N(N-1)}{2} (which follows Metcalfe's law).

so that even if the utility of groups available to be joined is very small on a peer-group basis, eventually the network effect of potential group membership can dominate the overall economics of the system.



Given a set A of N people, it has 2N possible subsets. This is not difficult to see, since we can form each possible subset by simply choosing for each element of A one of two possibilities: whether to include that element, or not.

However, this includes the (one) empty set, and N Singletons, which are not properly subgroups. So 2NN − 1 subsets remain, which is exponential, like 2N.


From David P. Reed's, "The Law of the Pack" (Harvard Business Review, February 2001, pp 23-4):

See also


External links

Full article ▸

related documents
Centralizer and normalizer
Liouville function
Euler's sum of powers conjecture
Tomaž Pisanski
Canonical Encoding Rules
Cypherpunk anonymous remailer
Face (geometry)
FIPS county code
Wilhelm Ackermann
Vladimir Voevodsky
List of basic mathematics topics
Gauss–Markov process
Code word
Mrs. Miniver's problem
Mathematical constants (sorted by continued fraction representation)
Simple module
Super-Poulet number
Spaced repetition
Type 1 encryption
Binary symmetric channel
Pedal triangle
Elementary event
Sample space