Complexity Digest

How hard is it to prove that problems are hard to solve? Meta-complexity theorists have been asking questions like this for decades. A string of recent results has started to deliver answers.

Read the full article at: www.quantamagazine.org

David Sloan Wilson, Guru Madhavan, Michele J. Gelfand, Steven C. Hayes, Paul W. B. Atkins, and Rita R. Colwell

PNAS 120 (16) e2218222120

Evolutionary science has led to many practical applications of genetic evolution but few practical uses of cultural evolution. This is because the entire study of evolution was gene centric for most of the 20th century, relegating the study and application of human cultural change to other disciplines. The formal study of human cultural evolution began in the 1970s and has matured to the point of deriving practical applications. We provide an overview of these developments and examples for the topic areas of complex systems science and engineering, economics and business, mental health and well-being, and global change efforts.

Read the full article at: www.pnas.org

John Meluso and Laurent Hébert-Dufresne

PNAS 120 (34) e2303568120

Like chefs at a fast-moving restaurant or engineers in a multidisciplinary project, team members often complete separate, interrelated subsets of larger tasks with limited insight into the work of others. These contexts make it difficult for individuals to assess the value of their own contribution to the collective work. Our work shows that despite this obstacle, individuals can still learn from their neighbors when neighbors’ actions influence collective outcomes. Though the effects are modest, we found that teams with more interactions between members perform better when refining their work while teams with fewer interactions perform better when innovating. We also found that across 34 tasks with diverse qualities, teams that decentralize coordination responsibilities outperform those that do not.

Read the full article at: www.pnas.org

Subhash Kak 

Theory in Biosciences volume 142, pages 205–210 (2023)

This paper addresses the relationship between information and structure of the genetic code. The code has two puzzling anomalies: First, when viewed as 64 sub-cubes of a 4×4×4 cube, the codons for serine (S) are not contiguous, and there are amino acid codons with zero redundancy, which goes counter to the objective of error correction. To make sense of this, the paper shows that the genetic code must be viewed not only on stereochemical, co-evolution, and error-correction considerations, but also on two additional factors of significance to natural systems, that of an information-theoretic dimensionality of the code data, and the principle of maximum entropy. One implication of non-integer dimensionality associated with data dimensions is self-similarity to different scales, and it is shown that the genetic code does satisfy this property, and it is further shown that the maximum entropy principle operates through the scrambling of the elements in the sense of maximum algorithmic information complexity, generated by an appropriate exponentiation mapping. It is shown that the new considerations and the use of maximum entropy transformation create new constraints that are likely the reasons for the non-uniform codon groups and codons with no redundancy.

Read the full article at: link.springer.com

Why did mammals, grasses and some other groups of organisms explode in diversity only after millions of years? The evolutionary biologist Andreas Wagner plumbs the secrets of those “sleeping beauties.”

Read the full article at: www.quantamagazine.org

The Center for the Study of Complex Systems (CSCS) at the University of Michigan seeks applicants for a tenure-track faculty position in complex systems science. The Center is a broad, interdisciplinary unit whose faculty use and develop tools from applied mathematics, computation, physics, statistics, engineering, and network theory to understand questions in the social, biological, and physical sciences. This is a University-year appointment at the Assistant Professor level. The expected start date is August 26, 2024.

More at: lsa.umich.edu

Jelena Joksimović , Matjaž Perc and Zoran Levnajić

Roy. Soc. Open Science August 2023 Volume 10 Issue 8

Private businesses are often entrusted with public contracts, wherein public money is allocated to a private company. This process raises concerns about transparency, even in the most developed democracies. But are there any regularities guiding this process? Do all private companies benefit equally from the state budgets? Here, we tackle these questions focusing on the case of Slovenia, which keeps excellent records of this kind of public spending. We examine a dataset detailing every transfer of public money to the private sector from January 2003 to May 2020. During this time, Slovenia has conducted business with no less than 248 989 private companies. We find that the cumulative distribution of money received per company can be reasonably well explained by a power-law or lognormal fit. We also show evidence for the first-mover advantage, and determine that companies receive new funding in a way that is roughly linear over time. These results indicate that, despite all human factors involved, Slovenian public spending is at least to some extent regulated by emergent self-organizing principles.

Read the full article at: royalsocietypublishing.org

Calvo Martín M, Rodriguez Palacio E, Deneubourg J-L, Nicolis SC

PLoS ONE 18(7): e0287845

The stability of collective decisions-making in social systems is crucial as it can lead to counterintuitive phenomena such as collective memories, where an initial choice is challenged by environmental changes. Many social species face the challenge to perform collective decisions under variable conditions. In this study, we focused on situations where isolated individuals and groups of the American cockroach (Periplaneta americana) had to choose between two shelters with different luminosities that were inverted during the experiment. The darker shelter was initially preferred, but only groups that reached a consensus within that shelter maintain their choice after the light inversion, while isolated individuals and small groups lacked site fidelity. Our mathematical model, incorporating deterministic and probabilistic elements, sheds light on the significance interactions and their stochasticity in the emergence and retention of a collective memory.

Read the full article at: journals.plos.org

Pratissoli, F., Reina, A., Kaszubowski Lopes, Y. et al.

Nature Communications 14, 4063 (2023).

We investigate how reliable movement can emerge in aggregates of highly error-prone individuals. The individuals—robotic modules—move stochastically using vibration motors. By coupling them via elastic links, soft-bodied aggregates can be created. We present distributed algorithms that enable the aggregates to move and deform reliably. The concept and algorithms are validated through formal analysis of the elastic couplings and experiments with aggregates comprising up to 49 physical modules—among the biggest soft-bodied aggregates to date made of autonomous modules. The experiments show that aggregates with elastic couplings can shrink and stretch their bodies, move with a precision that increases with the number of modules, and outperform aggregates with no, or rigid, couplings. Our findings demonstrate that mechanical couplings can play a vital role in reaching coherent motion among individuals with exceedingly limited and error-prone abilities, and may pave the way for low-power, stretchable robots for high-resolution monitoring and manipulation. In biology, individuals are known to achieve higher navigation accuracy when moving in a group compared to single animals. The authors show that simple self-propelled robotic modules that are incapable of accurate motion as individuals can achieve accurate group navigation once coupled via deformable elastic links.

Read the full article at: www.nature.com

The International Conference on Complex Networks (CompleNet) brings together researchers and practitioners from diverse disciplines working on areas related to complex networks. CompleNet has been an active conference since 2009. In its 15th year, we are very enthusiastic to bring it back to Exeter after the 2020 event had to be cancelled due to COVID. It will be hosted by the University of Exeter in late April.

​Over the past two decades, we have witnessed an exponential increase in the number of publications and research centres dedicated to this field of Complex Networks (aka Network Science). From biological systems to computer science, from technical to informational networks, and from economic to social systems, complex networks are becoming pervasive for dozens of applications. It is the interdisciplinary nature of complex networks that CompleNet aims to capture and celebrate.

The CompleNet conference is one of the most cherished events by scientists in our field. Maybe it is because of its motivating format, consisting of plenary sessions (no parallel sessions); or perhaps the reason is that it finds the perfect balance between young and senior participation, a balance in the demographics of the presenters, or perhaps it is just the quality of the work presented. Whatever your reason is, we hope that you will join us at the 2024 event. Welcome to CompleNet 2024!

More at: complenet.weebly.com

Conor Heins, Beren Millidge, Lancelot da Costa, Richard Mann, Karl Friston, Iain Couzin
Collective motion is ubiquitous in nature; groups of animals, such as fish, birds, and ungulates appear to move as a whole, exhibiting a rich behavioral repertoire that ranges from directed movement to milling to disordered swarming. Typically, such macroscopic patterns arise from decentralized, local interactions among constituent components (e.g., individual fish in a school). Preeminent models of this process describe individuals as self-propelled particles, subject to self-generated motion and ‘social forces’ such as short-range repulsion and long-range attraction or alignment. However, organisms are not particles; they are probabilistic decision-makers. Here, we introduce an approach to modelling collective behavior based on active inference. This cognitive framework casts behavior as the consequence of a single imperative: to minimize surprise. We demonstrate that many empirically-observed collective phenomena, including cohesion, milling and directed motion, emerge naturally when considering behavior as driven by active Bayesian inference — without explicitly building behavioral rules or goals into individual agents. Furthermore, we show that active inference can recover and generalize the classical notion of social forces as agents attempt to suppress prediction errors that conflict with their expectations. By exploring the parameter space of the belief-based model, we reveal non-trivial relationships between the individual beliefs and group properties like polarization and the tendency to visit different collective states. We also explore how individual beliefs about uncertainty determine collective decision-making accuracy. Finally, we show how agents can update their generative model over time, resulting in groups that are collectively more sensitive to external fluctuations and encode information more robustly.

Read the full article at: arxiv.org

Rebecca Katz, Kate Toole, Hailey Robertson, Alaina Case, Justin Kerr, Siobhan Robinson-Marshall, Jordan Schermerhorn, Sarah Orsborn, Michael Van Maele, Ryan Zimmerman, Tess Stevens, COVID AMP Coding Team, Alexandra Phelan, Colin Carlson & Ellie Graeden
Scientific Data volume 10, Article number: 491 (2023)

As the COVID-19 pandemic unfolded in the spring of 2020, governments around the world began to implement policies to mitigate and manage the outbreak. Significant research efforts were deployed to track and analyse these policies in real-time to better inform the response. While much of the policy analysis focused narrowly on social distancing measures designed to slow the spread of disease, here, we present a dataset focused on capturing the breadth of policy types implemented by jurisdictions globally across the whole-of-government. COVID Analysis and Mapping of Policies (COVID AMP) includes nearly 50,000 policy measures from 150 countries, 124 intermediate areas, and 235 local areas between January 2020 and June 2022. With up to 40 structured and unstructured characteristics encoded per policy, as well as the original source and policy text, this dataset provides a uniquely broad capture of the governance strategies for pandemic response, serving as a critical data source for future work in legal epidemiology and political science.

Read the full article at: www.nature.com

JOSEPH L.-H. TSUI, et al.

SCIENCE 20 Jul 2023 Vol 381, Issue 6655 pp. 336-343

Severe acute respiratory syndrome coronavirus 2 (SARS-CoV-2) variants of concern (VOCs) now arise in the context of heterogeneous human connectivity and population immunity. Through a large-scale phylodynamic analysis of 115,622 Omicron BA.1 genomes, we identified >6,000 introductions of the antigenically distinct VOC into England and analyzed their local transmission and dispersal history. We find that six of the eight largest English Omicron lineages were already transmitting when Omicron was first reported in southern Africa (22 November 2021). Multiple datasets show that importation of Omicron continued despite subsequent restrictions on travel from southern Africa as a result of export from well-connected secondary locations. Initiation and dispersal of Omicron transmission lineages in England was a two-stage process that can be explained by models of the country’s human geography and hierarchical travel network. Our results enable a comparison of the processes that drive the invasion of Omicron and other VOCs across multiple spatial scales.

Read the full article at: www.science.org

For over a century, biologists have had to contend with a complicated picture of genetics, which they’ve only recently begun to understand.

Read the full article at: www.quantamagazine.org

The proof establishes new conditions that cause connected oscillators to sway in sync.

Read the full article at: www.quantamagazine.org

A. Reina, T. Bose, V. Srivastava, J.A.R. Marshall

Royal Society Open Science 10: 230175, 2023.

It is usually assumed that information cascades are most likely to occur when an early but incorrect opinion spreads through the group. Here, we analyse models of confidence-sharing in groups and reveal the opposite result: simple but plausible models of naive-Bayesian decision-making exhibit information cascades when group decisions are synchronous; however, when group decisions are asynchronous, the early decisions reached by Bayesian decision-makers tend to be correct and dominate the group consensus dynamics. Thus early decisions actually rescue the group from making errors, rather than contribute to it. We explore the likely realism of our assumed decision-making rule with reference to the evolution of mechanisms for aggregating social information, and known psychological and neuroscientific mechanisms.

Read the full article at: royalsocietypublishing.org

Cristobal Pais, Jose Ramon Gonzalez-Olabarria, Pelagie Elimbi Moudio, Jordi Garcia-Gonzalo, Marta C. González & Zuo-Jun Max Shen
Communications Earth & Environment volume 4, Article number: 267 (2023)

Different interpretations of the fire regime concept have limited the capacity to allocate specific fire regimes worldwide. To solve this limitation, in this study, we present a framework to frame contemporary fire regimes spatially on a global scale. We process historical wildfire records between 2000 and 2018 across the six continents. We uncover 15 global pyromes with clear differences in fire-related metrics, such as frequency and size. The pyromes were further divided into 62 regimes based on spatial aggregation patterns. This spatial framing of contemporary fire regimes allows for an interpretation of how a combination of driving factors such as vegetation, climate, and demographic features can result in a specific fire regime. To the best of our knowledge, this open source platform at unprecedented scale expands on existing classification efforts and bridges the gaps between global and regional fire studies. A framework to classify fire regimes spatially on a global scale based on historical records between 2000 and 2018 reveals 15 global pyromes with differences in fire-related metrics and indicates how factors such as vegetation, climate, and demographic features can result in a specific fire regime.

Read the full article at: www.nature.com

Niraj Kushwaha, Edward D Lee 
PNAS Nexus, Volume 2, Issue 7, July 2023, pgad228

Conflicts, like many social processes, are related events that span multiple scales in time, from the instantaneous to multi-year development, and in space, from one neighborhood to continents. Yet, there is little systematic work on connecting the multiple scales, formal treatment of causality between events, and measures of uncertainty for how events are related to one another. We develop a method for extracting causally related chains of events that addresses these limitations with armed conflict. Our method explicitly accounts for an adjustable spatial and temporal scale of interaction for clustering individual events from a detailed data set, the Armed Conflict Event & Location Data Project. With it, we discover a mesoscale ranging from a week to a few months and tens to hundreds of kilometers, where long-range correlations and nontrivial dynamics relating conflict events emerge. Importantly, clusters in the mesoscale, while extracted from conflict statistics, are identifiable with mechanism cited in field studies. We leverage our technique to identify zones of causal interaction around conflict hotspots that naturally incorporate uncertainties. Thus, we show how a systematic, data-driven, and scalable procedure extracts social objects for study, providing a scope for scrutinizing and predicting conflict and other processes.

Read the full article at: academic.oup.com

Milan Jović, Lovro Šubelj, Tea Golob, Matej Makarovič, Taha Yasseri, Danijela Boberić Krstićev, Srdjan Škrbić & Zoran Levnajić
Scientific Reports volume 13, Article number: 12451 (2023)

Terrorist attacks not only harm citizens but also shift their attention, which has long-lasting impacts on public opinion and government policies. Yet measuring the changes in public attention beyond media coverage has been methodologically challenging. Here we approach this problem by starting from Wikipedia’s répertoire of 5.8 million articles and a sample of 15 recent terrorist attacks. We deploy a complex exclusion procedure to identify topics and themes that consistently received a significant increase in attention due to these incidents. Examining their contents reveals a clear picture: terrorist attacks foster establishing a sharp boundary between “Us” (the target society) and “Them” (the terrorist as the enemy). In the midst of this, one seeks to construct identities of both sides. This triggers curiosity to learn more about “Them” and soul-search for a clearer understanding of “Us”. This systematic analysis of public reactions to disruptive events could help mitigate their societal consequences.

Read the full article at: www.nature.com

Large language models (LLMs) exhibit impressive capabilities in generating
realistic text across diverse subjects. Concerns have been raised that they
could be utilized to produce fake content with a deceptive intention, although
evidence thus far remains anecdotal. This paper presents a case study about a
Twitter botnet that appears to employ ChatGPT to generate human-like content.
Through heuristics, we identify 1,140 accounts and validate them via manual
annotation. These accounts form a dense cluster of fake personas that exhibit
similar behaviors, including posting machine-generated content and stolen
images, and engage with each other through replies and retweets.
ChatGPT-generated content promotes suspicious websites and spreads harmful
comments. While the accounts in the AI botnet can be detected through their
coordination patterns, current state-of-the-art LLM content classifiers fail to
discriminate between them and human accounts in the wild. These findings
highlight the threats posed by AI-enabled social bots.

Read the full article at: arxiv.org