Complexity Digest

Gonzalo Manzano, Gülce Kardeş, Édgar Roldán, and David H. Wolpert
Phys. Rev. X 14, 021026

Developing a thermodynamic theory of computation is a challenging task at the interface of nonequilibrium thermodynamics and computer science. In particular, this task requires dealing with difficulties such as stochastic halting times, unidirectional (possibly deterministic) transitions, and restricted initial conditions, features common in real-world computers. Here, we present a framework which tackles all such difficulties by extending the martingale theory of nonequilibrium thermodynamics to generic nonstationary Markovian processes, including those with broken detailed balance and/or absolute irreversibility. We derive several universal fluctuation relations and second-law-like inequalities that provide both lower and upper bounds on the intrinsic dissipation (mismatch cost) associated with any periodic process—in particular, the periodic processes underlying all current digital computation. Crucially, these bounds apply even if the process has stochastic stopping times, as it does in many computational machines. We illustrate our results with exhaustive numerical simulations of deterministic finite automata processing bit strings, one of the fundamental models of computation from theoretical computer science. We also provide universal equalities and inequalities for the acceptance probability of words of a given length by a deterministic finite automaton in terms of thermodynamic quantities, and outline connections between computer science and stochastic resetting. Our results, while motivated from the computational context, are applicable far more broadly.

Read the full article at: link.aps.org

Manlio De Domenico, Luca Allegri, Guido Caldarelli, Valeria d’Andrea, Barbara Di Camillo, Luis M. Rocha, Jordan Rozum, Riccardo Sbarbati, Francesco Zambelli

The adoption of digital twins (DTs) in precision medicine is increasingly viable, propelled by extensive data collection and advancements in artificial intelligence (AI), alongside traditional biomedical methodologies. However, the reliance on black-box predictive models, which utilize large datasets, presents limitations that could impede the broader application of DTs in clinical settings. We argue that hypothesis-driven generative models, particularly multiscale modeling, are essential for boosting the clinical accuracy and relevance of DTs, thereby making a significant impact on healthcare innovation. This paper explores the transformative potential of DTs in healthcare, emphasizing their capability to simulate complex, interdependent biological processes across multiple scales. By integrating generative models with extensive datasets, we propose a scenario-based modeling approach that enables the exploration of diverse therapeutic strategies, thus supporting dynamic clinical decision-making. This method not only leverages advancements in data science and big data for improving disease treatment and prevention but also incorporates insights from complex systems and network science, quantitative biology, and digital medicine, promising substantial advancements in patient care.

Read the full article at: arxiv.org

Marta Ewa Lech, Sune Lehmann, Jonas L. Juul

Since the creation of the Billboard Hot 100 music chart in 1958, the chart has been a window into the music consumption of Americans. Which songs succeed on the chart is decided by consumption volumes, which can be affected by consumer music taste, and other factors such as advertisement budgets, airplay time, the specifics of ranking algorithms, and more. Since its introduction, the chart has documented music consumerism through eras of globalization, economic growth, and the emergence of new technologies for music listening. In recent years, musicians and other hitmakers have voiced their worry that the music world is changing: Many claim that it is getting harder to make a hit but until now, the claims have not been backed using chart data. Here we show that the dynamics of the Billboard Hot 100 chart have changed significantly since the chart’s founding in 1958, and in particular in the past 15 years. Whereas most songs spend less time on the chart now than songs did in the past, we show that top-1 songs have tripled their chart lifetime since the 1960s, the highest-ranked songs maintain their positions for far longer than previously, and the lowest-ranked songs are replaced more frequently than ever. At the same time, who occupies the chart has also changed over the years: In recent years, fewer new artists make it into the chart and more positions are occupied by established hit makers. Finally, investigating how song chart trajectories have changed over time, we show that historical song trajectories cluster into clear trajectory archetypes characteristic of the time period they were part of. The results are interesting in the context of collective attention: Whereas recent studies have documented that other cultural products such as books, news, and movies fade in popularity quicker in recent years, music hits seem to last longer now than in the past.

Read the full article at: arxiv.org

Louie Slocombe and Sara Imari Walker

​ACS Cent. Sci. 2024

In a scientific era focused on big data, it is easy to lose sight of the critical role of metrology─the science of measurement─in advancing fundamental science. However, most major scientific advances have been driven by progress in what we measure and how we measure it. An example is the invention of temperature, (1) where before it, we could say one thing was hotter than another but without a standardized, empirical measure we could not say how much hotter. This is not unlike the current state in discussing complexity in chemistry, (2,3) where we can say molecules are complex but lack an empirically validated standardization to confirm that one is more complex than another. In this issue of ACS Central Science, (4) a set of experiments by Leroy Cronin and co-workers conducted at the University of Glasgow aim to change this by providing a new kind of measurement with a well-defined scale, a significant step toward a metrology of complexity in chemistry. Although the concept of quantifying molecular complexity is not new itself, (3) the team leveraged principles from the recently developed theory of molecular assembly (MA) and related ideas (5) to define a rigorous concept of a scale for complexity, connected to a theory for how evolution builds complex molecules. (6,7) They show how the complexity of molecules on this scale can be inferred from standard laboratory spectroscopic techniques, including nuclear magnetic resonance (NMR), infrared (IR) spectroscopy, and tandem mass spectrometry (MS/MS). The robust validation of the inferred complexity across a multimodal suite of techniques instills confidence in the objectivity of the complexity scale proposed and the reliability of its resultant measurement.

Read the full article at: pubs.acs.org

Claudio Gnoli

Volume 29, pages 543–551, (2024)

Emergence can be described as a relationship between entities at different levels of organization, that looks especially puzzling at the transitions between the major levels of matter, life, cognition and culture. Indeed, each major level is dependent on the lower one not just for its constituents, but in some more formal way. A passage by François Jacob suggests that all such evolutionary transitions are associated with the appearance of some form of memory–genetic, neural or linguistic respectively. This implies that they have an informational nature. Based on this idea, we propose a general model of informational systems understood as combinations of modules taken from a limited inventory. Some informational systems are “semantic” models, that is reproduce features of their environment. Among these, some are also “informed”, that is have a pattern derived from a memory subsystem. The levels and components of informed systems can be listed to provide a general framework for knowledge organization, of relevance in both philosophical ontology and applied information services.

Read the full article at: link.springer.com

Roberto Casadei, Lukas Esterle, Rose Gamble, Paul Harvey, and Elizabeth F. Wanner

Front. Robot. AI, 06 May 2024

Cyber-physical collectives (CPCs) are systems consisting of groups of interactive computational devices situated in physical space. Their emergence is fostered by recent techno-scientific trends like the Internet of Things (IoT), cyber-physical systems (CPSs), pervasive computing, and swarm robotics. Such systems feature networks of devices that are capable of computation and communication with other devices, as well as sensing, actuation, and physical interaction with their environment. This distributed sensing, processing, and action enables them to address spatially situated problems and provide environment-wide services through their collective intelligence (CI) in a wide range of domains including smart homes, buildings, factories, cities, forests, oceans, and so on. However, the inherent complexity of such systems in terms of heterogeneity, scale, non-linear interaction, and emergent behaviour calls for scientific and engineering ideas, methods, and tools (cf. Wirsing et al. (2023); Dorigo et al. (2021); Brambilla et al. (2013); Casadei (2023a; b)). This Research Topic gathers contributions related to understanding and engineering cyber-physical collectives.

Read the full article at: www.frontiersin.org

Siddharth Patwardhan, Marc Barthelemy, Şirag Erkol, Santo Fortunato & Filippo Radicchi
Nature Communications volume 15, Article number: 3758 (2024)

Engineering multilayer networks that efficiently connect sets of points in space is a crucial task in all practical applications that concern the transport of people or the delivery of goods. Unfortunately, our current theoretical understanding of the shape of such optimal transport networks is quite limited. Not much is known about how the topology of the optimal network changes as a function of its size, the relative efficiency of its layers, and the cost of switching between layers. Here, we show that optimal networks undergo sharp transitions from symmetric to asymmetric shapes, indicating that it is sometimes better to avoid serving a whole area to save on switching costs. Also, we analyze the real transportation networks of the cities of Atlanta, Boston, and Toronto using our theoretical framework and find that they are farther away from their optimal shapes as traffic congestion increases.

Read the full article at: www.nature.com

Abramson, J., Adler, J., Dunger, J. et al.

Nature (2024).

The introduction of AlphaFold 2 has spurred a revolution in modelling the structure of proteins and their interactions, enabling a huge range of applications in protein modelling and design. In this paper, we describe our AlphaFold 3 model with a substantially updated diffusion-based architecture, which is capable of joint structure prediction of complexes including proteins, nucleic acids, small molecules, ions, and modified residues. The new AlphaFold model demonstrates significantly improved accuracy over many previous specialised tools: far greater accuracy on protein-ligand interactions than state of the art docking tools, much higher accuracy on protein-nucleic acid interactions than nucleic-acid-specific predictors, and significantly higher antibody-antigen prediction accuracy than AlphaFold-Multimer v2.3. Together these results show that high accuracy modelling across biomolecular space is possible within a single unified deep learning framework.

Read the full article at: www.nature.com

Tiago P. Peixoto

A fundamental problem associated with the task of network reconstruction from dynamical or behavioral data consists in determining the most appropriate model complexity in a manner that prevents overfitting, and produces an inferred network with a statistically justifiable number of edges. The status quo in this context is based on L1 regularization combined with cross-validation. However, besides its high computational cost, this commonplace approach unnecessarily ties the promotion of sparsity with weight “shrinkage”. This combination forces a trade-off between the bias introduced by shrinkage and the network sparsity, which often results in substantial overfitting even after cross-validation. In this work, we propose an alternative nonparametric regularization scheme based on hierarchical Bayesian inference and weight quantization, which does not rely on weight shrinkage to promote sparsity. Our approach follows the minimum description length (MDL) principle, and uncovers the weight distribution that allows for the most compression of the data, thus avoiding overfitting without requiring cross-validation. The latter property renders our approach substantially faster to employ, as it requires a single fit to the complete data. As a result, we have a principled and efficient inference scheme that can be used with a large variety of generative models, without requiring the number of edges to be known in advance. We also demonstrate that our scheme yields systematically increased accuracy in the reconstruction of both artificial and empirical networks. We highlight the use of our method with the reconstruction of interaction networks between microbial communities from large-scale abundance samples involving in the order of 104 to 105 species, and demonstrate how the inferred model can be used to predict the outcome of interventions in the system.

Read the full article at: arxiv.org

Rafael Prieto-Curiel, Gian Maria Campedelli

El Salvador, once one of the most violent countries in the world, has, in recent years, experienced a huge drop in homicides. The massive reduction is the result of Nayib Bukele’s anti-gang policies, which brought widespread domestic and international popularity to the President and its government. Other countries suffering high levels of violence are praising Bukele’s actions, electing El Salvador as a model to be followed despite the blatant violations of human, civil and political rights suffered by its citizens. While concurring that this aspect represents the most concerning facet of El Salvador’s strategy, we reflect on whether other countries should follow Bukele’s policies, elaborating on issues that have been largely overlooked. First, the policy scalability, adaptability and external validity. Second, the long-term vision of the prison population and the demographic and economic costs. As a result of our reflections, we conclude that other countries should not follow El Salvador’s strategy: beyond the likely erosion of citizens’ rights, the exportation of the policy may entail an array of additional unbearable costs, making Latin American democracies weaker.

Read the full article at: papers.ssrn.com

Andreagiovanni Reina, Thierry Njougouo, Elio Tuci, and Timoteo Carletti
Phys. Rev. E 109, 054307

To succeed in their objectives, groups of individuals must be able to make quick and accurate collective decisions on the best option among a set of alternatives with different qualities. Group-living animals aim to do that all the time. Plants and fungi are thought to do so too. Swarms of autonomous robots can also be programed to make best-of-n decisions for solving tasks collaboratively. Ultimately, humans critically need it and so many times they should be better at it! Thanks to their mathematical tractability, simple models like the voter model and the local majority rule model have proven useful to describe the dynamics of such collective decision-making processes. To reach a consensus, individuals change their opinion by interacting with neighbors in their social network. At least among animals and robots, options with a better quality are exchanged more often and therefore spread faster than lower-quality options, leading to the collective selection of the best option. With our work, we study the impact of individuals making errors in pooling others’ opinions caused, for example, by the need to reduce the cognitive load. Our analysis is grounded on the introduction of a model that generalizes the two existing models (local majority rule and voter model), showing a speed-accuracy trade-off regulated by the cognitive effort of individuals. We also investigate the impact of the interaction network topology on the collective dynamics. To do so, we extend our model and, by using the heterogeneous mean-field approach, we show the presence of another speed-accuracy trade-off regulated by network connectivity. An interesting result is that reduced network connectivity corresponds to an increase in collective decision accuracy.

Read the full article at: link.aps.org

School on Water: From the Anomalies to the Biological and Technological Applications Date: September 2 – 7, 2024 Venue: IFT-UNESP, São Paulo, Brazil We can all agree that a liquid that occupies 70 percent of Earth’s surface and two-thirds of our body is very important. Do we already know everything about water? Water has more than 70 thermodynamic, dynamic and structural anomalies and also shows new strange behavior upon analysis of the biological or material nanostructures. For instance, at nanoconfinement, water violates the hydrodynamic equations. Since water is present everywhere, understanding how the anomalies affect different systems is relevant. In this school, we explore the water anomalies starting from the basic ideas of phase transitions and critical phenomena, and show how they can be measured from scattering experiments and simulations of the nanoscale results.

There is no registration fee and limited funds are available for travel and local expenses.

Lecturers:

• Gustavo Appignanesi (Universidad Nacional del Sur, Argentina): Hydrophobic and Hydrophilic Surfaces and Interfaces
• Marcia Barbosa (UFRGS, Brazil): Nanoconfined Water
• Paola Gallo (Roma Tre University, Italy): Dynamics and Supercooled Water
• Enrique Lomba (CSIC, Spain): Scattering and Structural Factor

Application deadline: June 22, 2024 More information: https://www.ictp-saifr.org/sw2024/

We are organizing an international Conference on Complex Systems and Stochastic Processes to be held from the 1st to the 5th of July 2024, hosted by the Universidad de Guadalajara at the University Center for Exact and Engineering Sciences (CUCEI) in Guadalajara, Jalisco, Mexico. The scope of the Meeting is to discuss recent exciting developments in critical dynamics, quantum thermodynamics, classical and quantum walks, sociophysics and opinion dynamics, search and optimization, econophysics, networks, fractals, among others.

See: https://sites.google.com/view/meetingcomplexsystems 

Foundational Papers in Complexity Science maps the development of complex-systems science through eighty-eight revolutionary works originally published between 1922 and 2000. Curated by SFI President David C. Krakauer, each seminal paper is introduced and placed into its historical context, with enduring insights discussed by leading contemporary complexity scientists.

These four volumes are a product of collective intelligence. More than a compilation, Foundational Papers represents large-scale collaboration within the SFI community—brilliant thinkers who have contextualized the work that shaped their own research, resulting in a sparkling demonstration of how complexity shatters the usual scientific divisions and a look back at the path we’ve followed in order to gain a clearer view of what lies ahead.

Read the full article at: www.foundationalpapersincomplexityscience.org

Adam Rupe, James P. Crutchfield

Physics Reports

Volume 1071, 13 June 2024, Pages 1-47

After more than a century of concerted effort, physics still lacks basic principles of spontaneous self-organization. To appreciate why, we first state the problem, outline historical approaches, and survey the present state of the physics of self-organization. This frames the particular challenges arising from mathematical intractability and the resulting need for computational approaches, as well as those arising from a chronic failure to define structure. Then, an overview of two modern mathematical formulations of organization—intrinsic computation and evolution operators—lays out a way to overcome these challenges. Additionally, we show how intrinsic computation and evolution operators combine to produce a general framework showing physical consistency between emergent behaviors and their underlying physics. This statistical mechanics of emergence provides a theoretical foundation for data-driven approaches to organization necessitated by analytic intractability. Taken all together, the result is a constructive path towards principles of organization that builds on the mathematical identification of structure.

Read the full article at: www.sciencedirect.com

Hiroki Sayama

There is an increasing level of interest in open-endedness in the recent literature of Artificial Life and Artificial Intelligence. We previously proposed the cardinality leap of possibility spaces as a promising mechanism to facilitate open-endedness in artificial evolutionary systems, and demonstrated its effectiveness using Hash Chemistry, an artificial chemistry model that used a hash function as a universal fitness evaluator. However, the spatial nature of Hash Chemistry came with extensive computational costs involved in its simulation, and the particle density limit imposed to prevent explosion of computational costs prevented unbounded growth in complexity of higher-order entities. To address these limitations, here we propose a simpler non-spatial variant of Hash Chemistry in which spatial proximity of particles are represented explicitly in the form of multisets. This model modification achieved a significant reduction of computational costs in simulating the model. Results of numerical simulations showed much more significant unbounded growth in both maximal and average sizes of replicating higher-order entities than the original model, demonstrating the effectiveness of this non-spatial model as a minimalistic example of open-ended evolutionary systems.

Read the full article at: arxiv.org

We live in an age of increasing complexity, where accelerating technology and global interconnection hold more promise – and more peril – than any other time in human history. As well as financial crises, issues around climate change, automation, growing inequality and polarization are all rooted in the economy, yet standard economic predictions fail us.

Many books have been written about Doyne Farmer and his pioneering work in chaos and complexity theory. Making Sense of Chaos is the first in his own words, presenting a manifesto for doing economics better. In a tale of science and ideas, Farmer fuses his profound knowledge with stories from his life to explain how to harness a scientific revolution to address the economic conundrums facing society.

Using big data and ever more powerful computers, we can for the first time apply complex systems science to economic activity, building realistic models of the global economy. The resulting simulations and the emergent behaviour we observe form the cornerstone of complexity economics. This new science, Farmer shows, will allow us to test ideas and make significantly better economic predictions – and, ultimately, create a better world.

More at: www.penguin.co.uk

Advances in computational power and statistical algorithms, in conjunction with the increasing availability of large datasets, have led to a Cambrian explosion of machine learning (ML) methods. For population researchers, these methods are useful not only for predicting population dynamics but also as tools to improve causal inference tasks. However, the rapid evolution of this literature, coupled with terminological disparities from conventional approaches, renders these methods enigmatic and arduous for many population researchers to grasp.

This workshop on November 5 to 6, 2024 at the Max Planck Intsitute for Demographic Research (MPIDR) in Rostock, Germany, clarifies the goals, techniques, and applications of machine learning methods for population research. The workshop covers

• an introduction to ML methods for population researchers,
• showcases of ML applications to answer causal questions,
• discussions of the current developments of ML for population health, fertility and family dynamics, and
• fosters critical discussions about the shortfalls of these techniques.

The main focus of this workshop is on ML techniques using quantitative population data and research questions, not on ML language models. The workshop consists of keynotes, contributed sessions, and a tutorial.

More at: www.demogr.mpg.de

Beyond is a Socratic love story, a Platonic dialogue, a Bhagavad Gita of our times: a philosophical quest folded into an epic exploration of the world. Imagine an encounter with unconfused human existence. What does it mean to fall in love with God? Can the Good only adopt the role of a servant, or can it rise to provide a beacon of light ruling us?

How often we are caught in the myopic perspective that the material world is all there is! And yet, mathematics and science themselves point to a greater, all-embracing, unchanging reality. This insight suffices to move past selfishness and advance humanity to the next level. Beyond dismantles the artificial borders that have for too long separated genres: here, science confronts philosophy, mathematics engages religion, poetry brings nonfiction to life, time meets infinity. Beyond is sui generis.

Read the full article at: angelicopress.com

Carlos Gershenson

The scientific fields of complexity, artificial life (ALife), and artificial intelligence (A.I.) share several commonalities: historic, conceptual, methodological, and philosophical. It was possible to develop them only because of information technology, while their origins can be traced back to cybernetics. In this perspective, I’ll revise the expectations and limitations of these fields, some of which have their roots in the limits of formal systems. I will use interactions, self-organization, emergence, and balance to compare different aspects of complexity, ALife, and A.I. The paper poses more questions than answers, but hopefully it will be useful to align efforts in these fields towards overcoming — or accepting — their limits.

Read the full article at: www.preprints.org