Fractality in Complex Networks

First we need to know: What are fractals?

A fractal is an object or quantity that displays self-similarity, in a somewhat technical sense, on all scales. The object need not exhibit exactly the same structure at all scales, but the same "type" of structures must appear on all scales.

Fractals are a paradox. Amazingly simple, yet infinitely complex. New, but older than dirt. What are fractals? Where did they come from?

Unconventional 20th century mathematician Benoit Mandelbrot created the term fractal from the Latin word fractus (meaning irregular or fragmented) in 1975. These irregular and fragmented shapes are all around us. At their most basic, fractals are a visual expression of a repeating pattern or formula that starts out simple and gets progressively more complex.

No matter how close you get, you will 
always see a similarly detailed picture

One of the earliest applications of fractals came about well before the term was even used. Lewis Fry Richardson was an English mathematician in the early 20th century studying the length of the English coastline. He reasoned that the length of a coastline depends on the length of the measurement tool. Measure with a yardstick, you get one number, but measure with a more detailed foot-long ruler, which takes into account more of the coastline's irregularity, and you get a larger number, and so on.

Carry this to its logical conclusion and you end up with an infinitely long coastline containing a finite space, the same paradox put forward by Helge von Koch in the Koch Snowflake. This fractal involves taking a triangle and turning the central third of each segment into a triangular bump in a way that makes the fractal symmetric. Each bump is, of course, longer than the original segment, yet still contains the finite space within. Weird, but rather than converging on a particular number, the perimeter moves towards infinity. Mandelbrot saw this and used this example to explore the concept of fractal dimension, along the way proving that measuring a coastline is an exercise in approximation

A little about Fractal Terminology

Fractal art may initially appear random and disjointed,
 but closer inspection reveals a repeating structure

All fractals show a degree of what's called self-similarity. This means that as you look closer and closer into the details of a fractal, you can see a replica of the whole. A fern is a classic example. Look at the entire frond. See the branches coming out from the main stem? Each of those branches looks similar to the entire frond. They are self-similar to the original, just at a smaller scale.

These self-similar patterns are the result of a simple equation, or mathematical statement. Fractals are created by repeating this equation through a feedback loop in a process called iteration, where the results of one iteration form the input value for the next. For example, if you look at the interior of a nautilus shell, you'll see that each chamber of the shell is basically a carbon copy of the preceding chamber, just smaller as you trace them from the exterior to the interior.

Fractals are also recursive, regardless of scale. Ever go into a store's dressing room and find yourself surrounded by mirrors? For better or worse, you're looking at an infinitely recursive image of yourself.

Finally, a note about geometry. Most of us grew up being taught that length, width and height are the three dimensions, and that's that. Fractal geometry throws this concept a curve by creating irregular shapes infractal dimension; the fractal dimension of a shape is a way of measuring that shape's complexity.

Fractals in Complex Networks

While, these fascinating patterns are only geometric, new forms of topological fractality have been observed in complex networks, where the links rely on interactions between the participants. Examples of topological fractal networks include the hyperlinks in the WWW, physical interactions in protein interaction networks or biochemical reactions in metabolism.

Many complex networks are “small world” due to the very small average distance d between two randomly chosen nodes. Often d ∼ lnN, where N is the number of nodes. Thus, starting from a randomly chosen node following the shortest path, one can reach any other node in a very small number of steps. This phenomenon is called “six degrees of separation” in social networks. That is, for most pairs of randomly chosen people, the shortest “distance” between them is not more than six. Many random network models, such as Erd˝os-Renyi network (ER), Watts-Strogatz network (WS) [5] and scale-free network (SF) , as well as many real networks, have been shown to possess this small-world property.

We find theoretically and numerically that the nodes at the boundaries, which are of order N, exhibit similar fractal features for many types of networks, including ER and SF models as well as several real networks.

Fractal complex networks are characterized by the small-world property (as given by the logarithmic dependence of the average distance with the number of nodes) brought about by the “short-cuts” in the network, a very wide (power-law or ”scale-free”) distribution of connections, and a modular hierarchical structure.


References:


[1]Fractality in complex networks: Critical and supercritical skeletons - J. S. Kim, K.-I. Goh, G. Salvi, E. Oh, B. Kahng, and D. Kim

[2]What are Fractals, Why Important? - Hubpages.com

[3]Exploring Fractals - Mary Ann Connors

[4]http://classes.yale.edu/fractals/


[5]Origins of fractality in the growth of complex networks - Chaoming Song, Shlomo Havlin, Hernán A. Makse

[6] How Stuff Works - Fractals - Craig Haggit