ConnectedGraphSquaringProblem

MeatballWiki | RecentChanges | Random Page | Indices | Categories

Problem: In any system that can be represented by a connected graph, how do you minimize or overcome the O(N**2) cost of maintaining the network?

: -- or, how do you get societies to scale?

That is, if you have a connected graph of N vertices, and each vertex connects to the other vertices, you will have a total of (N-1)*N/2 = (N**2 - N)/2 edges = O(N**2) edges.

Usually, maintaining a network shaped in a connected graph is tied to the cost of the edges. Thus, the maintenance cost grows faster than linear (O(N)). This is a problem because you can only grow the amount of energy you put into the network linearly if the vertices acted independently.

One such example are societies where the vertices are people and the edges are relationships. The ConnectedGraphSquaringProblem in this context describes why "friendship" doesn't hold a large society together: Since maintaining friendship requires time and (emotional) energy, people cannot maintain an infinite number friendships. Therefore, as the society grows, the fraction of friends each person has decreases.

Clearly the solution is to maintain the network non-independently, thus taking advantage of the O(N**2) connectivity rate. Invert the problem, in other words. But what are good ways to build a maintenance network, especially in the context of CollaborativeHypermedia?

Also note that ReedsLaw takes this even further, into what could be called the "Power set exponentiation phenomenon."

Subnetting

What feature of the network is critical to you in this application?

Maintenance of the minimal spanning tree is computationally cheap, and keeps you connected, provided you don't have to generate all O(N**2) links and discard from that set. So look for a heuristic that gives you an O(N Log N) subset of the O(N**2) links containing "high scoring links" to build your subnet from. You may not find a perfect heuristic, but this is unlikely to matter. Your network is going to need to be resilient in any case. --JamesCrook

Really, you want the O(N^2) power of the graph helping you, and only the O(N) or O(NlgN?) power of subgraphs working against you. For instance, you want the bandwidth cost for broadcasting to be O(N), but once all the nodes have the message, you want that O(N^2) working to solve the problem.

: 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

In the case of Wiki, some links happen all on their own, in the form of AccidentalLinking. A good (maybe semantics-aware) AutoLink feature would push that phenomenon even further. -- MichaelSparks?

... O(N**2) cost of maintaining ... In real world systems you never have this situation. E.g. in molecular systems you have short range forces (only towards 3-6 neighbours) while long range forces only apply to special cases (and their calculation can be simplified). So this seems more a theoretical problem than a practical problem.

On Atoms...

The reason why atoms destabilize past 168 protons is unrelated to the ConnectedGraphSquaringProblem. It is, however, an example of something else: The attraction between vertices and the repulsion between vertices as a function of N behave differently: For higher numbers of N, the attraction drops and the nucelus becomes unstable.

Here's the physical background:

Such atoms are not unstable from electrical forces between protons and electrons (which are capable of holding large things together with no trouble, for the same reason that the huge number of interacting particles contribute together to the earth's gravity.) The problem with building an atom with more than 200 protons has nothing to do with there being too many proton-electron interactions. The problem is that the nucleus becomes unstable, and that not because of too many attractive forces, but because of too few. Protons repel each other from electrical repulsion. In addition, protons and neutrons all have an attractive force towards each other at sufficiently small scales. Finally, neutrons are inherently unstable; left alone, they decay, but if they are closely bound to other neutrons or protons, then the decay is staved off. So atoms tend to have roughly as many neutrons as protons. More than that, and the neutrons would decay (beta-decay). Fewer than that and the repulsive force between protons blows the nucleus apart (producing either alpha'''Problem: In decay or fission). If you try to get way too many protons in a nucleus, a new problem happens: because the strong nuclear force (which binds the protons and neutrons to each other) operates only at very small scales, and the electric repulsion operates over arbitrarily long distances, it becomes impossible to overcome the electric repulsion once the nucleus gets to big. --ThomasBushnellBSG

So, Protons = Fanatics, Neutrons = Followers, Electrons = Nay-sayers? --WilliamUnderwood

Compare http://en.wikipedia.org/wiki/Dunbar%27s_number

ConnectedGraphSquaringProblem

Discussion