Science Fair Project Encyclopedia
The reason for this is that the number of possible sub-groups of network participants is , 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, (which follows Metcalfe's law)
so that even if the utility of groups being available to be joined is very small on a per-group basis, eventually the network effect of potential group membership can dominate the overall economics of the system.
Derivation of the number of possible subgroups
Given a set A which represents a group of people, and whose members are persons, then the number of people in the group is the cardinality of set A.
The set of all subsets of A is the power set of A, denoted as :
It is known in set theory that the cardinality of is equal to 2 to the power of the cardinality of A, i.e.
This is not difficult to see, since we can form each possible subgroup by simply choosing for each element of A one of two possibilities: whether to include that element, or not.
However, A itself belongs to its own power set but if A is considered as a group of people, then A is not a proper "subgroup" of itself:
Then, any members of which are singletons are not considered "groups of people". Since each individual in a group can form a singleton, then the number of singletons in A is equal to the cardinality of A:
But notice that — using Big O notation — the function is as , so that it is exponential.
The contents of this article is licensed from www.wikipedia.org under the GNU Free Documentation License. Click here to see the transparent copy and copyright details