Tag Archives: self-similar

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: Fractals in Nature and Fractal Measurement

8 Replies

This post continues Wednesday’s post about fractals and the Mandelbrot set. Fractals are a branch of mathematics that we can observe in our daily life. Something is said to be fractal when a small piece of an object resembles a larger part of itself. The featured image is of romanesco broccoli; as you can see, each small cone on the broccoli resembles the overall structure of the vegetable. For this reason, the mathematical terms “fractal” and “self-similar” are closely related.

Examples of fractals in nature abound. The heartbeat of a healthy person is fractal when plotted in time; interestingly, people with various health problems show less fractal character to their heart rate. For a great slide show with images of fractal-ness in nature, check out this Wired article. Fractals have been observed in ocean waves, mountain structures, fern, lightning, city layout, seashell, trees, and many others. Many computer graphics of natural phenomena are generated using fractal processes.

Koch Snowflake (Wikipedia)

The Koch snowflake (above), is a fractal generated from a line. As the fractal pattern is repeated, the length of the curve grows infinite. A line segment does not have infinite length, and yet the Koch Snowflake clearly does not fill space. So what is the dimension of this object? Through a method called the “box counting method“, we can determine the dimensionality of a fractal object. The box counting method is used to estimate area and coastal length from satellite pictures, as demonstrated below.

Using the box counting method to estimate the area of Great Britain (Wikipedia).

In short, we can see how the number of boxes needed to define a length or space changes as the box size changes. For a line, the number of boxes needed grows as 1n. For a space, the number of boxes grows as 2n. The method is explained in more detail here. Intuitively, we can tell the Koch Snowflake has a dimension between 1 and 2. It turns out that, using the Box Counting method, we can determine that the Koch Snowflake has a fractal dimension of log(4)/log(3), or about 1.26.

Lorenz attractor from Wikipedia

Fractal dimensions turn up in strange places. For example, chaotic attractors have fractal dimension. The Lorenz attractor, above, has a fractal dimension of 2.06. In the future I will discuss chaos and chaotic attractors. Check out my previous science posts on synchrony and art resembling science.