Network evolution and the emergence of structure
This publication defends the point of view according to which depending on the number of connections in a graph, entities may appear and these could be seen as modeling macroscopic quantities in complex systems.NEWLINENEWLINENEWLINEAn introduction illustrates that networks permeate our world.NEWLINENEWLINENEWLINEA first section settles the terminology (graphs, networks, cycles, trees) and states that graphs can be extracted from various types of models (matrix for linear ODEs, Markov processes, automata); the structure of the dependency graph (cycles, trees) influences the behaviour in state space and conversely, in the case of automata, cyclic trajectories may help classify the running system.NEWLINENEWLINENEWLINEA second section describes the qualitative behaviours which occur in a digraph when one adds connections (randomly). The main feature is the appearance of a sharp increase in connectivity after having added some connections (little less than half the number of nodes). A giant component is formed and various embedded cyclic structures manifest themselves afterwards until full connectedness is obtained. Then the author tries to illustrate that this type of ``phase change'' has analogs in various situations with abrupt change leading to ergodic type behaviour (cf. cellular automata which may be self-reproducing in suitable circumstances).NEWLINENEWLINENEWLINEAnother section presents a ``local point of view'' in the sense that one looks at the nodes connected to a particular one and circuits and forking structures are formed, duplicated, absorbed in a self-similar fashion which is reminiscent to the internal structure of fractals.NEWLINENEWLINENEWLINEFinally, the author considers examples (physiological, psychological, sociological, ecological, technological, management, computational).NEWLINENEWLINENEWLINEIn the conclusion, the author stresses that structural changes due to phase transitions, the birth of chaos and self-organization can have a paradigmatic extension in the sense that our way of thinking should change from hierarchical or dogmatic (``top-down'') to integrated (``down-top'') whereby local interactions of subsystems between themselves and the environment lead to global changes and increased intelligence.NEWLINENEWLINENEWLINEIt is stated that an analytical study to support the argumentation is not available and that the results are empirical, based on simulations.NEWLINENEWLINENEWLINEReviewer's comments: The author's point is often based on formal analogies and empirical behavioural comparisons (leading to a ``top-down'' way of thinking). By looking at bifurcation phenomena in ODEs for example one sees that the critical situation is described by the eigenstructure of the linearization; spectral quantities can be attached to a matrix in normal form whose off-diagonal components are irrelevant. Thus sharp changes arise through mechanisms different in nature. Also, the statements of the conclusion may be contested: The supercritical world (interaction dominated) may not necessarily represent an improvement over the subcritical one (elements dominated) as is seen for example in the text in the case of congestion in queueing networks.NEWLINENEWLINEFor the entire collection see [Zbl 0954.00019].
scientific article