Tag Archives: self-similarity

Fun science: scale-free networks

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, chaosnetwork theory, and small-world networks.

Advertisements

Fun Science: Fractals and the Mandelbrot Set

Fractals are often immediately visually appealing, even if the underlying equation is harder to understand. For this reason, fractals have reached a wider audience than many branches of mathematics. Beyond their visual appeal, fractals give us a way to look at many natural systems that math was not previously able to examine. How long is a winding and convoluted coastline? How does a one-dimensional system like the circulatory system serve our three-dimensional bodies? How does lightning disburse its energy when it strikes? (The image below shows how electricity dissipated through a block of plexiglass, more details here.) These are all concepts related to fractals.

from Capturedlightning.com

One very famous fractal is the Mandelbrot set (pictured at the top of this entry), named after pioneer Benoit Mandelbrot. The Mandelbrot set is generated by the iterative equation zn+1 = zn2 + c. This equation indicates that at a specific value of c, we get to the next z (that is, zn+1), by squaring our current z and adding the constant c. Let’s say that c is 1. z0 is 0, so z1 is z0 squared plus 1, and z1=1. Then z2=z12+1=2, z3=z22+1=5, and so forth. A value c is in the Mandelbrot set if zn→∞ goes to a constant value (so that zn=large is roughly equal to zn=large+1). When c=1, each z keeps getting bigger and bigger, so clearly it is not a part of the Mandelbrot set. c is a complex number, so we generate a map in two dimensions of which values of c belong to the set. The video below shows the Mandelbrot set (color giving rate of divergence, black giving a member of the set) and continues to zoom in. Even at incredible zoom scales, fine and self repeating structure can be seen.

Fractals can also be generated in a more directly visual way. Below is a fractal called the Koch Snowflake. The Koch Snowflake is generated iteratively as well. The base unit is a triangle. The middle third of each leg of the triangle is replaced by a tent. For the next step, the middle segment of all the legs of the new structure are replaced by a tent, and so on. You can see in the graphic that the Koch Snowflake gets complicated quickly. Many other visual fractals have been explored. The java applet here has a few that you can play with.

Koch snowflake from Wikipedia

I will have another post about fractals on Friday, where I discuss more numerical properties and examples of fractals in nature. Food for thought: what is the perimeter length of the Koch Snowflake? Also check out my previous science posts on synchrony and art resembling science.