Self-organisation lies at the core of fundamental but still unresolved scientific questions, and holds the promise of de-centralised paradigms crucial for future technological developments. While self-organising processes have been traditionally explained by the tendency of dynamical systems to evolve towards specific configurations, or attractors, we see self-organisation as a consequence of the interdependencies that those attractors induce. Building on this intuition, in this work we develop a theoretical framework for understanding and quantifying self-organisation based on coupled dynamical systems and multivariate information theory. We propose a metric of global structural strength that identifies when self-organisation appears, and a multi-layered decomposition that explains the emergent structure in terms of redundant and synergistic interdependencies. We illustrate our framework on elementary cellular automata, showing how it can detect and characterise the emergence of complex structures.

 

An Information-Theoretic Approach to Self-Organisation: Emergence of Complex Interdependencies in Coupled Dynamical Systems
Fernando Rosas, Pedro A.M. Mediano, Martín Ugarte and Henrik J. Jensen

Entropy 2018, 20(10), 793; https://doi.org/10.3390/e20100793

Source: www.mdpi.com

Urban transformations within large and growing metropolitan areas often generate critical dynamics affecting social interactions, transport connectivity and income flow distribution. We develop a statistical–mechanical model of urban transformations, exemplified for Greater Sydney, and derive a thermodynamic description highlighting critical regimes. We consider urban dynamics at two time scales: fast dynamics for the distribution of population and income, modelled via the maximum entropy principle, and slower dynamics evolving the urban structure under spatially distributed competition. We identify phase transitions between dispersed and polycentric phases, induced by varying the social disposition—a factor balancing the suburbs’ attractiveness—in contrast with the travel impedance. Using the Fisher information, we identify critical thresholds and quantify the thermodynamic cost of urban transformation, as the minimal work required to vary the underlying parameter. Finally, we introduce the notion of thermodynamic efficiency of urban transformation, as the ratio of the order gained during a change to the amount of required work, showing that this measure is maximized at criticality.

 

On critical dynamics and thermodynamic efficiency of urban transformations
Emanuele Crosato, Ramil Nigmatullin, Mikhail Prokopenko

Open Society

Published 17 October 2018.DOI: 10.1098/rsos.180863

Source: rsos.royalsocietypublishing.org

Community detection is often used to understand the structure of large and complex networks. One of the most popular algorithms for uncovering community structure is the so-called Louvain algorithm. We show that this algorithm has a major defect that largely went unnoticed until now: the Louvain algorithm may yield arbitrarily badly connected communities. In the worst case, communities may even be disconnected, especially when running the algorithm iteratively. In our experimental analysis, we observe that up to 25% of the communities are badly connected and up to 16% are disconnected. This may present serious issues in subsequent analyses. To address this problem, we introduce the Leiden algorithm. We prove that the Leiden algorithm yields communities that are guaranteed to be connected. In addition, we prove that, when the Leiden algorithm is applied iteratively, it converges to a partition in which all subsets of all communities are locally optimally assigned. Furthermore, by relying on a fast local move approach, the Leiden algorithm runs faster than the Louvain algorithm. We demonstrate the performance of the Leiden algorithm for several benchmark and real-world networks. We find that the Leiden algorithm is faster than the Louvain algorithm and uncovers better partitions, in addition to providing explicit guarantees. Based on our results, we conclude that the Leiden algorithm is preferable to the Louvain algorithm.

 

From Louvain to Leiden: guaranteeing well-connected communities
Vincent Traag, Ludo Waltman, Nees Jan van Eck

Source: arxiv.org