behavior is often exhibited by real-world systems. If the system can be described as a network
, where nodes
represent an object
in the network (such as a person
, a web page
, or a city
) and links
represent the connection
s between nodes (relationships between individuals, hypertext
links, interstates), certain characteristics of the graph may indicate an ease of travel between nodes on the graph, even if the number of nodes is quite large. The world wide web
and social connections are two examples of such systems that exhibit the characteristics of small-world networks.
The first such characteristic is short average path length, meaning that the average distance for any two nodes in the graph chosen at random is shorter than would be expected in a randomly connected graph. Note the concept of six degrees of separation--though there are billions of people in the world, the average path length between persons, as determined by a 1967 study, is merely six. Note that this is average path length, not longest path length, which makes the "every person is connected to every other by at most six people" tagline incorrect. This figure was arrived at by giving a subject the name and address of a random person to which they were to send a parcel. If they did not know the person, then they were to send it to someone they knew that may be more likely to know that person, and the process would repeat itself until the parcel arrived. Also note that this was before the age of Google which could have assisted this task tremendously. Speaking of the world wide web, it too displays this characteristic--the average pathway between any two of its 8 * 10^8 web pages is 19 links long.
The second characteristic of a small-world network is clustering--in which a large number of nodes in the graph are linked to one particular node, making this central node a link in the pathways between many different nodes. A person who you are dating will know many people who you also know, forming a cluster of aquaintances. Researchers dealing with the same issues are likely to link to each other's pages, forming a cluster of links between them. In order for a system to be considered a small-world network, the clustering coefficient (a measure of the average amount of clustering in a graph) will be several orders of magnitude higher than a randomly linked graph of the same size.
Everything2 as a Small-world Network?
Everything2 is a subset of the small-world network discussed above, the world wide web, however, it is a node/link-based entity in itself. The estimated average path length L in a graph can be found by a formula using the number of nodes in the system and the average number of links per node (1). According to the stats nodelet to the right of my screen, at system time Tuesday, July 15, 2003 4:52:33, everything2 consists of 956,901 nodes with 7,658,945 links connecting them--or about 8 links per node. Using this formula, the average path length is about 7.6. The clustering coefficient of everything2 if it were randomly connected is predicted by the formula C = k/(N-1), or 1.044e-6 (2). Predicting the actual clustering coefficient is a lot more time intensive and requires computing the amount of actual clustering per node (or a random sample of nodes), then taking the average. If anyone would like to take a stab at it, let me know. So while I have not managed to decisively conclude whether or not e2 is small-world network, I have answered the question posed in six degrees of everything which is good enough for one night.
(1) Albert & Barabási (2003).
(2) Motter ,de Moura, Lai, & Dasgupta (2002).Topology of the
conceptual network of language.Physical Review E ,65.