Slashdot Mirror
Web: 19 Clicks Wide
InitZero writes "The journal Nature reports that the web is only 19 clicks wide. What it fails to mention is that a least one of those must be through Kevin Bacon. " The graphic at the beginning of the article is gorgeous in a Mandelbrot style-now if I could just have it in a 24 x 30 print.
Let us not forget the story of the statistician who drowned while fording a very wide river with an average depth of 6 inches...
"...they may harpoon us, but they ain't gonna pick us up on no radar screen!"
Northern Light, as I recall. I don't know that that claim is verified in any credible way, however.
Mind the Gap
Start: www.microsoft.com
- Click on MSN Home
- Click on Computing
- Click on Operating Systems
- Click on Linux
- Click on Linux vs NT Server 4.0
- Click on FreeBSD and Linux Resources
- Click on Slashdot
So microsoft is at most seven clicks from slashdot. Can anyone do better?Stochastic (random) functions can be characterized by a range of power-law functions and other spectral shapes. The randomness of the power-law function is given by the randomness (e.g., mean and variance) of the individual components of the spectral function. For instance, draw a x-y plot consisting of a straight line that has a negative slope. The y-axis is the amplitude while the x-axis is the frequency (or the inverse wavelength). Now suppose that this straight line represents the "average" value as random fluctuations about this line exists. This is power-law random function.
Sorry if this is over simplified. BTW, fractals are characterized by a power-law function. OTOH, true fractal functions have constraints on what the power-law slope can be (Haussdorf dimension).
Now for something silly. What is the degree of freedom from Gore (Father of the Internet) to Slashot (the bastard child of the Internet)?
But on a more serious note (yeah, right), I once thought about the following. It is too bad that this site is not more pro Microsoft (boy, does this company's name have Freudian meaning, right Billy boy?). Then Rod can put up a link to assembler info. It would be:
http://slashdot.org/asm
One of the interesting applications they have at caida is the graphical traceroute that plots the physical location of the hop on a map. www.caida.org/Tools/GTrace
People who want to express themselves, and know how to do it, will always get websites.
Those who don't care to do so, well, won't.
The real limit is on the number of people willing to be creative.
I don't think it has anything to do with "cool" technologies - whether I have JavaScript rollovers on my site or not doesn't affect the quality of the content itself.
D
----
that you are never more than two clicks from a porn site.
The WWW *will* become self limiting. Yes, geeks like us will be building more and more web pages. But more and more normal people (you didn't think you were normal, did you?) will not. Also, as resources start getting tight, some of those wonderful "calling cards" will get wiped. You may no longer need them. Somebody may be willing to pay you for the domain name (okay, that would cause more sites). The admin may decide one day that since the site got no hits in six months, it's gone (think GeoCities).
:).
Using the tree analogy:
- Yes, the tree will get a *lot* bigger.
- Yes, the tree can only get so big.
- Yes, leaves (pages) and branches (sites) will fall off and hit the WWG (world-wide ground).
- Yes, there is a gardener, but he's only interested in a branch or two.
- No, I haven't gotten much sleep lately
The Lord DebtAngel
Lord and Sacred Prince of all you owe
Is this post not nifty? Sluggy Freelance. Worshi
"To figure a shape to the web I would think you would first have to decide how many dimensions it has."
If you want to know geometrical shape that would be true. But topological shape is a little different. Topologically, a coffee cup and a donut both have the same shape. The shape in common is that they each have one hole.
Similarly, their power law reference means that the web is fractal in dimension, which is not the usual 1-2-3-4 dimensionality commonly meant. I would imagine this dimension is somewhere between 1 and 2. It's a set of lines (one dimensional) that are almost dense enough to fill an area (two dimensional.)
"But even if you only assume two or three dimensions, why 'clicks wide'? "
It sounds like they are looking at the web as a graph, a series of points (web pages) connected by edges (links). The width of a graph might be found like this:
For each pair of points in the graph, find the shortest path along edges between the points (in terms of number of edges.) The maximum length among all these shortest paths is the width of the graph.
What sort of analysis can be done with points which there is no connecting path? How many of these are there? Why is there no path? How did that affect that average?
Just like the '6 degrees of seperation' game, I fail to see how this could be useful. Finding the shortest path between two websites is nice when you're stuck on a machine that can't go to random URLs (secured lynx, some web kiosks, browse slashdot from anywhere, yeah!), but the 19-click average sounds like a curiousity.
And, ooh, the web exhibits properties of exponential growth, with some sites that have many more links to other sites. Like I couldn't figure *that* one out. Some people post their bookmarks, and lists of links, and other people only link within their interests. A graph of this might look interesting if done correctly, but I still don't see how this would be that useful.
The graph at the top was pretty, though, it looked like an IFS fractal. They look like stuff found in nature too, so I guess that gives this article a context to exist...
pb Reply or e-mail; don't vaguely moderate.
There's an additional study in Scientific American awhile back that shows evidence of that. The premise of the study was to create a search engine that refines the quality of web sites by giving them a "hub" and a "target" rating (I believe that was the terminology used). The "hub" rating was determined by the number and quality of the target sites the page linked to (quality being determined by the "target" score), and the "target" rating was determined by the number and quality of the "hubs" that linked to it. (again, quality determined by "hub" score) So they'd run the list of sites through several time using these, and each time the hub and target scores were refined by each other. Eventually stabilized scores are obtained by running this evaluation scheme enough. To relate it to the topic at hand in this thread, though, when they studied the web using these, individual communities of targets and hubs could be discerned by an above-average rate of linkage within the group.
For you Van Vogt fans...
I agree with many here that the analysis in the article described is not much to talk about, and yeah not much use except for generating some cool fractalized images, but the basic precept behind their development may be the only real way of performing a true mapping of the Net's shape and growth, something that will be important in the years to come.
You can't build a useful map of the Internet's structure in the way you map the streets that wind through your town. Future search tools will require a fair amount of intelligence not in the way they go about a search, but in they way they 'think' about a search (there is a difference). Topographical mapping -- not index cataloging -- will help developers figure out these ways of thinking.
"It's alive! It's alive!!!"
Seriously, though, that's very interesting, but it's actually obvious when you think about it. The reason why galaxies are not distributed randomly is that there are centres of attraction that begin as random fluctuations in an evenly-distributed environment; but as matter condenses, these types of patterns emerge.
Now, replace "gravity" with "number of hits". A site with a lot of hits, of course, represents a centre of interest, where people congregate. And naturally, they will either link to the site, or try to get linked from it.
And so, the same patterns emerge.
Hey, that means Slashdot is kinda like a black hole generator! Once it aims its beam at a site, it submerges it with hits until the site reaches critical mass and implodes, dropping out of the known Uiverse!
"There is no surer way to ruin a good discussion than to contaminate it with the facts."
Hypersearching The Web is that SA article. Google is different as it primarily tries to find authorities based on links, while the Clever method in the article is more like finding authorities within communities. The Clever algorithm looks at text around a link to estimate importance and relevance of a link.
You had to create a rather special example, although a real world worst case would probably involve anthropologist->?>anthropologist replaced by merchant->city resident->city resident->merchant, which is just a little longer.
I think an example of the real-life short circuits is my wife's friend of a friend. My wife is from another country. We quickly found a friend of a friend of hers five miles from our home in this country. It seems unlikely, but the real math is something like this:
That is only an average... And the minimum and maximum is wide apart. The web is not really a web I think, but a set of (nearly) independent webs. An example of this is the set of x86 protected mode programming sites. Nearly all of them are linked with the others, but not with anything else.
--The knowledge that you are an idiot, is what distinguishes you from one.
I am not sure that the web is even that wide. Maybe the scientists did not factor in enough search sites; but I am quite sure that search engines cover at least 150 million web pages total. I don't think that the distance will be that long, except to some hard-to-reach or foreign sites that almost nobody links to. What would be more revelaing is the frequency distribution of distances.
The map of the Internet reminded me of a map of an airline's routing table, which, unless you fly Southwest Airlines, usually runs through a series of hubs. I'm sure that the 'Net has it's own hubs (hell, you have Yahoo and Slashdot already), but I wonder if it has many Southwests. Webrings are the only real analogy I can think of, so I wonder if anyone else could throw any more of those out.
FYI: Southwest Airlines doesn't use a hub-based system of flights, but does direct flights between cities. Many flights are thus 'direct' but not 'non-stop'. They're also pretty cheap. Don't factor the cheapness into your analogies.
But to me, the most important part was the last paragraph:
:-)
"I think that we might end up in an era where, just as
people today have their own e-mail addresses, people will
have their own Web sites," he said. "But eventually it will
taper off. Eventually it has to be self-limiting."
That last sentance makes me think he isn't too sure of the Web's self-limiting qualities. I personally don't think it will ever taper off. Just about the time it starts to get stale, the Netizins will get a new toy (ala JS rolovers, Java applets, Flash, Shockwave, whatever). There will always be too much excitement and new technology.
And, just as it seems weve run out of things to do, we might actually have a moon base with a couple hundred-thousand miles of 100BaseT. Voila, brand new web to play with.
censorship is a form of noise, which actively seeks to drown out content with silence - Crash Culligan
The Source code for that mandelbrot set is available at Caida. My friend has been working on the project for quite some time, ever since graduating at UCSD. Most of the work is done by him in the San Diego Super Computer Center. Take a look at the software, it's java and Brad put a lot of cross platform testing into it. So it should run fine everywhere. (Java claim). It has a lot of really nice features to it.
Joseph Elwell.
Hmmm...
To figure a shape to the web I would think you would first have to decide how many dimensions it has. Perhaps by assigning a dimension to each method of getting to a page, or perhaps by counting each hyperlink into a page as a separate dimension. Either way it could get pretty hairy pretty quick.
For example, is a hyperlink on a search engine different in some way from a hyperlink on a personal page? How about a web directory? Bookmarks?
But even if you only assume two or three dimensions, why 'clicks wide'? Seems more like 'clicks deep' to me. I always think of clicking on a hyperlink as 'drilling down'. Showing my age again I guess...
Jack
- -
Are you an SF Fan? Are you a Tru-Fan?
I think the idea behind this article of a "click" would define "click" to be a mouse click. Which would rule out all typing. It's a fair assumption that the web would be considerably smaller if search engines were lumped together, because you could type in the addresses of the two places you wanted to find the distance of into altavista as +url:www.math.com +url:www.slashdot.org . Placing all sites that are logged by altavista much closer.
But then do you calculate width by starting at point A and continuing to point B? Because if that were true then the search engine argument would still be relatively benign. As you would still have to reach a search engine from page A in less "clicks" than it would take you to go straight.
If the "true" diameter is required one could measure in any fashion as long as we agree on a definition of "click" (which I define - for myself - as only mouse presses). So such sites as yahoo might bring unrelated pages closer. But without typing would many be relatively fewer than 19 clicks away? Yahoo is still categorically sorted so sites that are unrelated would need to traverse up the Yahoo category tree after first leaving the first site.
Joseph Elwell.
What would be superb in a graphical representation is a combination of this data (the supposed "distance" from point to point) combined with last week's graphic on /geographic/ location or top-end domain (.com, .org, .etc).
It would be interesting to see if, for example, internet traffic patterns show any kind of focus or foci about certain domains or sites or even specific boxen, and how those machines are distributed in real space. . . where, essentially, are our eyeballs and electrons going?
As for "dimensions," a 3D rendering would be the easiest to comprehend. Perhaps a sphere representing the globe, with an atmosphere of satellite link channels, and a substrata of bandwidth pipes and routers. Or a flat geometric field with peaks to represent the Big Iron, fractal spires twisting off as homepages and smaller sites. And isolated islands or floating moons of self-contained networks, or pages that go nowhere.
Don't mind me, I just finished reading Snow Crash, Diamond Age, and Idoru, and would enjoy a virtual walk through the data we're all accumulating.
Rafe
V^^^^V
Rafe
Opinions expressed by the author may not actually exist in the wild.
If you remove search engines, you're removing a major part of the natural growth of the Net itself.
This was touched on by this Scientific American article a few months back. It covers another project looking for useful ways to index the Web. They came up with a similar hub/cluster topology based on authorities, which are sites that a lot of other sites link to, and hubs, which have large collections of links to authorities. Unfortunately, the cool illustration that was in the print version didn't make it online. (You can pretty much skip the first two sections of the article unless you want to read the authors' grossly incorrect definition of spamming; it doesn't get interesting until the "Searching With Hyperlinks" subhed.)
1- sure, everybody can get their own web page, probably will, but how many "here's my dog, check out my car" web pages does the world need. I think we (humanity) are finding out the hard way that we aren't as individual as we'd like to think. This is why I haven't made my own web page about my own boring life. 2- the other thing that's said, the real imporant thing in this article, has some pretty chilling implications - which have already proven true. The major portals are the main targets of the search engine, the "fringe" sites are not. Only a small fraction of sites are even scanned by search engines, and this will become a limiting logic for them. Thus, only mainstream sites will be found by search engines (in general), and the rest of the sites, the covert sites, the underground, the fringe, will not be reachable by the vast majority of people, and this has all the Orwellian implications you think it does. All this time, the netizens have been thinking, this internet empowers the individual, it frees information. BUZZZT! wrong, try again please. It empowers the rich, the mainstream media, the corporate establishment. Now how much do you think it matters that we wire the ghettos and set up internet access for cambodian rice farmers? It's not going to be a channel that connects everybody with everybody else, it's going to be just another orifice for greedy corporations to rape us with. Sorry about the class-warfare tone, and the oblique anti-Microsoft slam, but at least I didn't say anything about Beowolf clusters, though a Beowolf cluster of internets would be cool.
And with this link, you're but a click away 8^)
http://visualroute.datametrics.com/How do you suppose they account for dynamically-generated (i.e. database- or object-driven) web pages that typically don't register with search engines?
What about sites with logins, where hundreds of pages are hidden from public view?
It seems to me that most of what's interesting about the emerging behaviour of the web is buried within one of those two types of sites... discuss?!
The really cool thing would be if someone were to write a program (probably a cgi script) that would use a search engine that list pages that link to a site to let you type in two web sites and see the hyperlink path. I wonder how far slashdot.org is from www.microsoft.com?
Mean hop distance is relatively easy to measure, as IP addresses are nicely arranged. Measuring clicks takes a bit more work, I feel. A somewhat cryptic document by another guy at caida.org puts the average hop at 14-15. A great link with more info is the
Internet Distance Maps Project.
For more pretty pictures, check out the Internet Mapping Project.
--
Make mine methylphenidate.
The article says the WWW is 9 years old, not the Internet. The average consumer doesn't know, but the two are not the same.
Actually, the article says the WWW is 9 years old. I had the same reaction at first, then I quickly double checked myself, and discovered they did say WWW, and not the Internet.
*Life is too serious to be taken too seriously.*
http://www.caida.org/Tools/Plankton
:)
It was on that badass little graphic. There are links to info about LOC records in Bind8 that hold longitude and latitude info. You can then be plotted on the map. Or something like that. I just went for more of the purtty pictures.
The other comment that mentioned topology I think was rather off-course on the dimensions of the web. Topology is the study of geometry on surfaces; donuts and teacups are similar because primitive shapes behave in similar ways on them.
A second factor is that you must consider what you are calling dimensions. A representative graph may be made in any number of dimenstions - flattened to two, or made in 3d. But the dimension in the fractal since is a different animal. No matter what dimension you draw it in, the fractal dimension stays the same. Yes, the dimension would be between 1 and 2 because as the number of links -> infinity, the 'perimeter' does too, but the lines certainly don't have an area!
The shape of the web, however, is not about fractal dimensions. It's about summarizing and arranging the points and connections in such a way that clustering and localization phenomena begin to emerge. With 800 million+ nodes, this task is nearly impossible - however, an analogous structure of fewer nodes and clusters can be made that will have visible patterns.
One thing, perhaps, we can agree on...
... DirectHit, which bases its analysis on "what people are clicking on" ... and Inktomi, which is "looking at what people are actually viewing."
Google, which ranks its results by link "importance"
Hmmm, follow the herd or go for something "immportant" (perhaps the perfect word for a search, a clue if you will) seems like a pretty simple decision. I suggested it to the folks in my company (along with www.m-w.com and babelfish) and they love it. I'm feeling lucky.....
(Get Andover to buy it, or maybe the other way around...)
+&x
Yeah, but at least she's only one hop away from you. She's at least two hops away from most of us, so I would have to say that the best person around here to ask is .. um .. you.
---
Have a Sloppy day!
As copyright owner of this comment, I authorize everyone to defeat any technological measure which limits access to it.
At first I was amazed at the claim that
the web is only 19 clicks wide.
To me, this means the maximum distance between any two sites is 19 clicks. Sort of the way that people claim that only six degrees separate us from any other person in the world. This would be an impressive display of the "web" aspect of the world wide web.
But this isn't the claim at all. If you read the article, it says that
there's an average of 19 clicks separating random Internet sites.
Different story altogether.
heck, maybe this is out of line...
... Sure the second foundation was a lot more then that but the mathematical aspect was what I loved most about the concept.
Every time I see an article about a statistical study of something created by man, I get a flash back to Asimov's second foundation : how mathematics can generally describe man, events, history,
This study has some distant similarities to it. Statisticians studying the average distance between two ramdomly chosen internet site. The catch is that the entire structure is created by man, there really isn't much ramdomness in it : Compared to the Bacon thing were you may have met someone, that knew someone, at one point or another walking down the street; having a link from your web page to another web page is a completely conscious action.
Which brings me to the counter-argument that news site such has slashdot or c|net have their content (and thus their links) influenced by random events of the outside world such has tornadoes or floods.
Which now brings me to a conclusion before I back home, how long will it be before someone attemps to make a measure of the amount of randomness in the web, that is the influence of events that cannot be predicted (to some extent or other, to be determined later) by man. Is the web something that could over time become completely predictable?
I really should reread these Asimov books.