A little about complexity metrics

Over time, the world around us becomes more and more complex, and the number of ways to measure this very complexity is growing even faster. It is believed that the increase in the number of metrics may indicate some degree of confusion in the area of ​​complex systems. In fact, many complexity metrics are variations on several basic ideas. This article presents an (incomplete) listing and categorization of complexity metrics.

A historical analogy can be drawn between the problem of measuring complexity and the problem of describing electromagnetism, which was relevant before the appearance of Maxwell’s equations. In the case of electromagnetism, quantities such as electric and magnetic forces, arising under different experimental conditions, were initially viewed as fundamentally different. Eventually it became clear that electricity and magnetism are in fact closely related aspects of the same fundamental quantity – the electromagnetic field. Likewise, modern researchers in architecture, biology, computer science, dynamical systems, engineering, finance, game theory, and a long line of other fields have developed different complexity metrics for each of their industries. These researchers asked similar questions about measuring the complexity of various subjects of study, and in fact their answers have a lot in common.

Here are the three questions that most often arise when trying to quantify the complexity of a research subject (home, bacteria, problem, process, investment scheme):

1) How difficult is it to describe?

2) How difficult is it to create?

3) What is his level of organization?

Using these questions, I divided the complexity metrics into groups. Metrics within a group are often related quantities.

Complexity of description

Usually, the complexity of a system is directly related to the degree of complexity of describing the system in its entirety. Notable examples of this group of metrics (usually measured in bits) are the following:

• Information (Information);

• Entropy;

• Algorithmic complexity or algorithmic information content

• Minimum description length;

• Fisher information;

• Renyi entropy;

• Code length (prefix-free, Huffman, Shannon-Fano, error-correcting, Hamming);

• Chernoff information;

• Dimension;

• Fractal dimension;

• Lempel-Ziv complexity.

Complexity of creation

Alternatively, the complexity metric can be based on the degree of complexity associated with building or duplicating a system. In this case, units of time, energy, money, etc. are usually used. Metrics of this group can be as follows:

• Computational complexity;

• Time computational complexity;

• Space computational complexity;

• Information complexity (information-based complexity);

• Logical depth;

• Thermodynamic depth;

• Cost (Cost);

• Crypticity.

Complexity of the organization

Complexity is also often related to organizational aspects. The metrics of this group can be further divided into two subclasses.

a) The complexity of describing the organizational structure, be it corporate, chemical, network, etc .:

• Effective complexity;

• Metric entropy;

• Fractal dimension;

• Excess entropy;

• Stochastic complexity;

• Sophistication

• Effective measure complexity;

• True measure complexity;

• Topological epsilon-machine size;

• Conditional information;

• Conditional algorithmic information content;

• Schema length;

• Ideal complexity;

• Hierarchical complexity;

• Tree subgraph diversity;

• Homogeneous complexity;

• Grammatical complexity

b) Based on the amount of information distributed among the parts of the system, which is the result of the organizational structure:

• Mutual information;

• Algorithmic mutual information;

• Channel capacity;

• Correlation

• Stored information;

• Organization

Related concepts

In addition to the metrics listed above, there are a number of related concepts that are not quantitative metrics of complexity but are closely related. These concepts include:

• Long-range order;

• Self-organization;

• Complex adaptive systems;

• Edge of chaos.

Please supplement this list with your examples, regardless of whether they fall into the classification scheme adopted here.

Product Information – www.ieee.org/magazines/DirectAccess

---

Material prepared as part of the course “Architecture and Design Patterns”… If you are interested in learning more about the training format and program, to get acquainted with the course teacher, we invite you to the online open day. registration here.