Tag Archives: six degrees

Fun Science: Small World Networks

1 Reply

The small-world phenomenon refers to the fact that even in a very large population, it takes relatively few connections to go from any element 1 to another random element. Amongst people, we know this concept as the “six degrees of separation” game. Any population of objects with connections can be conceptualized this way. Examples include crickets communicating by audible chirps, websites with links, electrical elements with wiring, board members with common members, or authors on mutual scientific papers. All of the examples I list have been examined in various scientific studies.

In a small-world network, elements are first connected in a regular lattice; for example, each element is connected to one or two nearby neighbors on each side. The leftmost picture below shows a regular lattice of elements. A connection between element i and element j is then removed. Then we add a connection between element i and any other element x, like the middle picture below. If x is across the network from i, then the number of steps between i and x has been reduced from some large number to 1. All of the elements connected to i are now 2 steps from element x. This reduces the diameter of the network, which is the maximum number of steps between any two elements, although the number of connections remains constant. In the six-degrees of separation game, the diameter would be 6. As we replace more of the lattice connections with random ones, the network becomes more and more random. We quantify a small-world network by its randomness, as in the picture below.

The small-world network has been explored as a means of sending information efficiently through a population. As the diameter reduces, the time it takes information to spread through the entire network reduces. Neurons in the brain have been explored as small-world networks; certain regions of the brain are highly interconnected with a few long distance connections to other regions of the brain. Protein networks and gene transcription networks have also been described with the small-world model. Further information with scholarly references is available on the scholarpedia page (which is generally a great resource for complex systems problems).

 

Here you can read a good scientific paper by Steven Strogatz, one of the premier scientists in the area. This is a paper published in Nature, one of the highest scientific publications. There are some equations, but the figures are also excellent if you are uncomfortable with the math. The paper models the power grid, boards of directors, and coauthorship using network ideas. I mention this paper specifically because I find Strogatz a very relatable and clear writer. Also consider reading his recent nontechnical book about math, The Joy of X, for more math fun.

Check out my other science posts on graph theory, chaos, fractals, the mandelbrot set, and synchrony. And drop a note with any questions!

Advertisement

Fun Science: Network Theory and Graphs

3 Replies

If you have a set of items and you can connect or sequence them in many ways, you probably have a graph or network. Clearly if you have these objects, some connection arrangements might be preferable to others. Heart cells are connected in patterns that contract the heart in the proper pattern. If you must deliver items to ten different locations, different paths may be more efficient (the traveling salesman problem).

Euler’s 1735 Koenigsberg bridge problem is considered the first graph theory problem. At the time, the city of Koenigsberg had seven bridges (shown above). Euler wished to find a path which crossed each bridge exactly once. He showed mathematically that no path satisfied those constraints.

The famous game “six degrees of Kevin Bacon” is a network theory problem. This game says that with six steps, any actor can be linked to Kevin Bacon through films pairs of actors appeared in. This idea was originally introduced at the Erdös number. Paul Erdös was a brilliant and highly published mathematician (over 1500 papers!) who worked in graph theory and combinatorics. The Erdös number was how many papers it took by coauthoring to connect you to Erdös. He was also wonderfully eccentric. Once, visiting a friend, he woke in the night to get some juice. In the morning, his friend found red liquid all over the floor. Erdös, puzzled by the juice carton, had simply stabbed a hole in the side to drink from. His biography is a fascinating glimpse into a nearly alien mind.

In my own research, I look at how oscillators synchronize in small networks, such as rings. Even in a simple ring, many new types of synchrony occur, compared to all-to-all connections. It is easy to believe that the structure of the brain, and how various regions and subregions connect, might greatly influence human thinking. On a more science fiction note, I suspect that artificial intelligence will not exist in machines without complex networks of elements.

This was just a very quick overview of a huge field. In the future, I plan to write on topics like small-world networks, scale-free networks, and synchrony on networks. Check out my other science posts on synchrony, fractals, the Mandelbrot set, and chaos.