Tag Archives: networks

Fun science: scale-free networks

Leave a reply

A scale-free network is a network with self-similar structure. As you zoom in on parts of the network, the sub-network resembles the overall network. In this way, scale-free networks are the network analogy of fractals. (Read previous posts about fractals, or fractals in nature.) Fractals arise in many natural systems like coastlines, snowflakes, and topology; likewise many naturally arising networks are self-similar. Examples include links on the internet, social networks, and protein interaction networks. Understanding the structure of a network helps us to understand the types of behavior that can occur on the network. Some network structures are more prone to failure or instability, or different types of failure or instability.

Scale-free networks have a sort of hub arrangement. Some elements connect to a bunch of other elements, while most connect to just a few. Going back to the social network analogy, the hubs are those people with 1500 friends on Facebook, while most people have 100 or so. In the picture below, a random network is shown on the left, and a scale-free network is shown on the right (hubs shown in grey). In the random network, all the elements have roughly the same number of connections, with some slightly more, some slightly less. The scale-free there has more variation in number of connections amongst elements.

From Wikipedia page on scale-free networks.

Getting more mathematical, the number of connections an element has gives its degree. An element with 3 connections has a degree of 3. We can say, hypothetically, that element 1 has a degree of 2, element 2 has a degree of 6, element 3 has a degree of 2, etc. We have degrees for all of the elements of the network. If we organize this set of degrees into a histogram (where we bin by degree value– in our example, we had counted two of degree 2, and one of degree 6) we get a degree distribution.

If something is distributed normally, the histogram has a bell-shape to it, like the first picture below. If you did a histogram of the height of all the people in your city, it would be a normal distribution. If it is distributed in a scale-free fashion, there are a few high value elements (high degree in our case), and a lot of low value elements. This gives the bottom picture, with a peak at a low value and a long tail into the higher values. The wealth distribution in your city probably looks like the scale-free distribution. If you take the log of the values on the scale-free distribution, you will get a straight line. This is because the logarithm is the inverse of the function 10^x; if you take the log of something, you can see its behavior on the 10^x scale, which gives you insight into how it behaves across multiple powers of 10, or its “scaling free” behavior.

From Wikipedia article on normal distribution

From Wikipedia article on power-law distribution

If you are interested in other basic explanations of more advanced science, also check out my posts on synchrony, chaos, network theory, and small-world networks.

Advertisement

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!

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.