Small-World Networks: the bare essentialsNetworks and small-worldsThe world is full of networks. The internet, electric circuits, train connections, brains, they're all networks and they can all be drawn by a graph. But some graphs are different than others. Some of them are small-world networks. Being a small-world network means information spreads fast throughout the graph, as well locally as throughout the whole graph. To have such a fast spread of information, the graph must have two things:1. A high clustering coefficient 2. A low characteristic path length And we'll start by looking at the clustering coefficient. Clustering CoefficientTurkey is a large country with a wide-spread public transport network. In the diagram below, some of this network has been depicted. The nodes are major cities, the connections are direct bus connections. Turkey's capital is bold and underlined, the country's second city is in boldface only.
The clustering coefficient on a node is the interconnectedness of its neighbours. Look at Selcuk. Selcuk has three neighbours: Istanbul, Ankara and Marmaris. Between these three neighbours there could be three connections at most. If all three connections existed, the CC on our Selcuk-node would be 100%. But since only two out of three exist, the CC on Selcuk is 2/3 = 66.6%. Check the diagram below. 
Test yourself: 1a) How many neighbours does Istanbul have? 1b) How many connections could possibly exist between these neighbours? 1c) How many do actually exist? What percentage is that? ( = What is the Cluster Coefficient on Istanbul?) 2) What is the Cluster Coefficient on Marmaris? 3) What is the Cluster Coefficient on Trabzon? Answers on the bottom of the page. It might now become clear that every node has a clustering coefficient. An exception in this diagram is the city of Edirne. Edirne has only one neighbour, and every node with only one neighbour has (per defnition) a clustering coefficient of 0. Usually though, when speaking of clustering coefficients, we are speaking of the entire network. The clustering coefficient of the entire network is the average of all its nodes. Characteristic Path LengthLook at the diagram again:
There is a path between any nodes in the diagram, meaning you can reach any city from any other city by bus, though you might have to change. For instance, you can go from Selcuk to Gaziantep, by changing at Ankara, the whole tour becoming: * Selcuk - Ankara - Gaziantep (2 buses) Of course, you could take a detour by taking the longer route over Trabzon: * Selcuk - Ankara - Trabzon - Gaziantep (3 buses) But this is only useful if you have some special reason to take this detour, for instance seeing the country whcih is well worth it in the case of Turkey. But if you are just traveling from Selcuk to Gaziantep, you are only interested in taking the shortest route. There is a shortest route between any two cities in this diagram. Some examples: * Marmaris - Ankara (1 bus) * Gaziantep - Edirne (3 buses) * Ordu - Marmaris (2 buses) We could make a table of all the shortest paths in the graph: 
Now, if you take the average of all these lengths, you get the Characteristic Path Length (CPL). The value CPL means "the average distance between two nodes in the network". In the case of our graph, the CPL = 1.75. There is one important exception: as soon as one node of the network becomes detached, it has no paths to other nodes and the CPL of the network becomes -1 (by definition). Answers to questions:1) Istanbul has three neighbours. With three possible connections between these neighbours, and one existing, the cluster coefficient on Istanbul is 1/3 = 33.3%2) Marmaris has two neighbours. With one possible connection between these neighbours, and one existing, the cluster coefficient on Marmaris is 1/1 = 100% 3) Trabzon has three neighbours. With three possible connections between the neighbours, and two existing, the cluster coefficient on Trabzon is 2/3 = 66.6% To see another example of Small-World networks, get this short tutorial |