ConnectedGraphSquaringProblem

We can envision a social network as a graph where the nodes are people and the edges are relationships.

For small social groups the graph can be almost "complete", i.e. each person can maintain a personal relationship with also every other person in the group.

For large groups, such as an entire nation, this is impossible; there are too many other people for any person to have a relationship with even a significant fraction of them. So things become impersonal, which causes trouble.

Technically, if there are n people in the network, then for the graph to be "complete", that is, for every person to know everyone else, each person must maintain n - 1 relationships, and the network as a whole will have on the order of n^2 edges. This is impossible since each person only has so much time and energy to maintain personal relationships; we can imagine that each edge "costs something", and so while the network as a whole may be able to afford a lot of edges, it probably can't afford n^2 when n is large.

This is why the problem of scaling a social network is sometimes called an instance of the ConnectedGraphSquaringProblem.


Discussion

Please see MeatBall:ConnectedGraphSquaringProblem for the rest of the discussion.

One person suggested the use of minimal spanning trees to provide a connected graph wile minimizing edges. So, in terms of a social network, we construct minimal spanning tree subnets… interesting… instead of social clubs that connect "similar" members, and which contain subsets of nodes (people), we want to find a subset of edges (friendships) between all of the people on Earth.

I guess "edge costs" could be the reciprocal of the "natural affinity" of people to be connected (i.e. there is a "cost" to connecting to someone you know but don't like too much). Then we could use Prim's algorithm to construct a minimal spanning tree. Effectively, we ask, in sequence, every person on Earth to connect to their best friend, except that anyone already in the subnet is ruled out.

Then we tell them all that if they want, they don't need to bother communicating with anyone else they know, they can just route messages through their one or two connections, and everything will be fine as the net is still connected.

An interesting idea, and one which does indeed show how to get a scalable society. However, I think the more pressing difficulty with a large society is not simply to ensure connectedness, but rather is how to bring collegiality/a greater sense of personal friendship into large social networks. In graph terms, a min spanning tree minimizes edges, which is good, but increases the average number of hops between nodes, which increases the social "distance" felt by the participants. We want to do the opposite; we want not only to preserve connectivity, but also to minimize the social distance (while also, perhaps, minimizing required edges, as these represent "maintanence expense").

BayleShanks


Given some group of people, more connections are often better. The "telephone game" illustrates the problems with "only 2 connections".

Unfortunately, it's impossible for anyone to have a direct connection to everyone on the planet – it's a ConnectedGraphSquaringProblem .

So we're going to have to have indirect connections – and because of the "telephone game" issues, we want to minimize the number of steps of indirection.

Imagine that the human brain was tuned to deal with about 10 other people. (I'm just making this number up to make the math to work out nicely – I'd be very interested in actual research trying to quantify this).

Then we could build groups of 11 people, each of which knew every other person in the group, but each group would be isolated.

Or we could build a linear band 3 people wide of indefinite length, where each person knows the 10 people nearest him.

Or we could build hierarchies of indefinite size, where each member of "middle management" talks up to his boss, and down to about 10 employees. Since there's less than than 10^9 people in the US at the moment, the entire population of the U.S. would only be 9 degrees of separation from the root person. Since there's less than than 10^10 people on Earth at the moment, the entire population of the earth would only be 10 degrees of separation from the root person.

This is related to the famous "six degrees of separation".

What other things do we need to keep in consideration ?

See HiveMind.

DavidCary


Here's some research:

"The Dunbar Number as a Limit to Group Sizes" http://www.lifewithalacrity.com/2004/03/the_dunbar_numb.html

Is this "150" number the number of people a single person can directly have 2-way interactions with ? Or have indirect links already formed ?


See also SmallGroupDiscussionSizeLimit. See also CommunityMayNotScale.

Translations / Traductions

Cette page a été traduite en français vers : ProblèmeGrapheCarréConnexions – speaking of n^2-n connexions ?

Languages:

The same page elsewhere:
MeatBall:ConnectedGraphSquaringProblem