Fractal Motifs and Iterated Function Systems

"Once we have an eye for fractals, discovery, analysis and interpretation can be rationalized in terms of the underlying motifs and IFS. This is a useful approach since apparently dissimilar objects and processes can be derived from slightly modified initiators."

Artificial and Natural Fractals

There are two classes of fractals: (a) artificial and (b) natural. There are also two types of fractals:

1. strictly self-similar; those that preserve their shapes at all length scales of observations.
2. statistically self-similar; those that preserve their shapes at limited length scales of observations.

Computer-generated fractals can be strictly self-similar or statistically self-similar. However, some man-made objects and patterns found in Nature are self-similar at limited length scales; i.e., they look the same when viewed within a limited scale range.

Also natural fractals can even possess dissimilar scaling behaviors in different directions, and therefore different local fractal dimensions may be required to characterize their complexity. These are classified as multifractals and possessing self-affinity. Self-affinity means that different sections of the multifractal shape exhibit different self-similar patterns (1). While the Mandelbrot Set is a deterministic, strict multifractal, many clustering materials, physical processes and time-dependent phenomena are only multifractals under limited length scales.

Motifs and Iterated Function Systems

A fractal is constructed by applying a set of transformations to an element called the generator. This yields a building block unit called the initiator or motif. Recursively replacing each portion of a motif by reduced copies of itself eventually generates a fractal. The mathematical transformations involved are called affine transformations. A two-dimensional affine transformation W takes points in the Euclidean plane into new points in the Euclidean plane. Figure 2 shows the motif and affine transformations for the Koch Curve, named after Helge von Koch.

Note that four affine transformations are applied to the generator, a straight line of length X = L, to produce a motif 4/3*L long.

• scaling by 1/3
• scaling by 1/3, followed by 60 degree rotation
• scaling by 1/3, followed by -60 degree rotation
• scaling by 1/3

This set of affine transformations are known as Iterated Function Systems or IFS. Invented by Michael Barnsley (2), IFS generate complex and Nature-like shapes. Combined with other techniques, IFS are excellent image compression tools. Instead of processing images, pixel by pixel, IFS addressable values are stored, processed and interpreted.

Creating a fractal can be accomplished with or without selection rules. For example, one selection rule could consist in recursively replacing some segments of a motif but not others. Once we have an eye for fractals (3), discovery, analysis and interpretation can be rationalized in terms of the underlying motifs and IFS. This is a useful approach since apparently dissimilar objects and processes can be derived from slightly modified initiators.

Fractal Patterns, Everywhere!

That we are surrounded by fractals and motifs is evident. These can be found, for example, in

• structures and processes that conform to binary decision trees.
• Web architectures such as themed sites/documents, categorized directories, search databases, etc.
• clustering techniques that require the use of dendrograms, multidimensional matrices, etc.
• electrodeposited ramified pattern.

Figure 3 shows several candidate motifs

Note

I derived the motif at the far right from the Koch Curve at the far left and iterated to produce tree-like patterns along its baseline. I did this for my doctoral work back in the early 90's and before search engines or SEO marketers were around the block. The idea was to conduct computer simulation studies and to compare the resultant shape with patterns we observed in crystal growth under electrical anisotropy conditions, where the incoming particle or "visitor" is not strictly a random walker but an induced or "guided walker".

Compare these conditions with a partial random visitor (not a pure markovian visitor), with no knowledge (or caring) about any cluster geodesic distance, moving through a link structure and being guided or influenced during its walk.

It turned out that even under electric anisotropy and low experimental conditions we still observed electrodeposited fractal patterns. This challenged the notion that fractal deposits were the result of the diffusion field alone, as proponent of the diffusion-limited agregation model (DLA) thought. When applied to electrodeposition, the model was not enough.

Figure 4 shows the output of a DLA computer simulation, generated with one of the early versions of Fractint.

Compare the figure with a growing link subgraph of the Web. Check both for self-similarity. Additional screen shots of simulated and real grown clusters can be found in my thesis. In those days the clusters were video filmed, documented and presented at several conferences on chaos and fractals. Back then I explained why the DLA model fell short in explaining their nature and complexity. Article 7 of this series, Fractal Clusters - Fractal Networks, features fractal growth under isotropic and anisotropic conditions.

Recent developments: At the Document Space Workshop I attended at IPAM -Institute for Pure and Applied Mathematics; University of California, Los Angeles, (UCLA); Jan 23 - 27, 2006 - diffusion geometries and the diffusion space emerged at the most obvious space for embedding documents and conducting clustering studies from large collections. Check briefings at SEWF.

To sum up, web fractals are real and can appear in large collections of clusters and link structures. Figure 5 shows a fractal architecture of a site map. Note its limited self-similarity, running only up to three length scales. Evidently, self-similar environments can be found in link "farms" and link structures, databases, themed sites, documents, passages, doc trees or even in a "bag of words".

Next: Overlapping Patterns

Prev: The Fractal Nature of Semantics

References

1. B. B. Mandelbrot, The Fractal Geometry of Nature, W. H. Freeman, New York (1983).
2. M. F. Barnsley, Fractals Everywhere, Academic Press, New York (1988).
3. M. McGuire, An Eye For Fractals, Addison-Wesley, California (1991).

Thank you for using this site.

Status of the Current Document 
  

Copyright © 2006 Mi Islita.com - ▲