On Wednesday, March 27, 2002, at 01:08 PM, [EMAIL PROTECTED] wrote: > I've been thinking a little lately about network topologies > and peer-to-peer. What reading I've done seems to indicate that > most networks either have no organizational structure to them > at all or have some sort of dictated hierarchy. But it's > possible to have quite a lot of organization without anything like > a hierarchy. > ... > Of course, this kind of structure could be made with any number of > "levels" of clustering. > > I don't recall ever having read of this type of structure before, > but it seems so obvious that I'm sure it's been discussed before. > So is there a name for it? Does anyone use it? has it been > shown to be utterly worthless? >
Imagine a million people standing in a line, each communicating with his nearest neighbor. The average "distance" between any two people picked at random is half a million, and the maximum distance is a million. Now imagine those million people in a 1000 x 1000 array. Each communicating with 4 neighbors (8 if diagonals are considered, a very slight modification to the math). The average distance is much less than a million, and in fact can be no longer than the diagonal, 1414. (Left as a fun exercise to calculate the average separation as a function of the dimension d.) Next, put those million people into a skyscraper, e.g., 100 x 100 x 100 floors, with each person communicating with 6 nearest neighbors (again, more if diagonals are considered). Given the well-known empirical "six degrees of separation," America is basically a 9-dimensional system. (In some sense.) The math on this is pretty simple, but also illuminating. (No, it's of course not a precise model. Some people are very well connected, a la the example of the "The degrees of Kevin Bacon." Some semi-hermits may know only a few people on their roads, who know only a few in a village, etc. So the actual empirical results will be skewed. One thing it implies is that a well-mixed system, e.g. an America in which people move around and work at different companies and serve in the Army and all, becomes a higher dimensional system: more hypervolume for the same "average separation." A poorly-mixed system has less hypervolume per separation, or more separation between randomly picked members. The "clustering" you talk about is the same way corporations work. When someone in Intel's California headquarters wants to communicate with someone in Intel's Arizona operations, they don't need to "go up the ladder" to their boss, his boss, his boss, his boss, then over to Arizona, then down, and down, and down. Odds are they _know_ how to directly contact others, or can "tunnel" directly be sending e-mail or picking up a phone. "Mixers" are even formally arranged to do just this mixing of people at one site with people in another. Higher-dimensionality systems are the key. And this is well-known in computer architecture as well. Soon after joining Intel in 1974 I was involved with some folks at IMSAI (who later produced a famous early PC) on their "Hypercube": like other hypercubes, including famous ones from Caltech and Intel, increasing the connectivity between nodes effectively increased dimensionality and reduced the average latency/distance between nodes. Lastly, the whole focus of "distintermediating" and things like "everyone a mint" has been to increase the dimensionality of systems. Arguably, this is what the Agora of Athens (not the first, just one of the most famous) did: it increased point to point contacts and thus raised the dimensionalty. And it also reduced the "need" for hierarchy. More "point to point" connections (e-mail addresses, for example) up the number of near neighbors, and hence the dimensionality of the space. --Tim May "Stupidity is not a sin, the victim can't help being stupid. But stupidity is the only universal crime; the sentence is death, there is no appeal, and execution is carried out automatically and without pity." --Robert A. Heinlein
