Helcio Felippe, Federico Battiston & Alec Kirkley 

Communications Physics volume 7, Article number: 335 (2024)

A wide range of tasks in network analysis, such as clustering network populations or identifying anomalies in temporal graph streams, require a measure of the similarity between two graphs. To provide a meaningful data summary for downstream scientific analyses, the graph similarity measures used for these tasks must be principled, interpretable, and capable of distinguishing meaningful overlapping network structure from statistical noise at different scales of interest. Here we derive a family of graph mutual information measures that satisfy these criteria and are constructed using only fundamental information theoretic principles. Our measures capture the information shared among networks according to different encodings of their structural information, with our mesoscale mutual information measure allowing for network comparison under any specified network coarse-graining. We test our measures in a range of applications on real and synthetic network data, finding that they effectively highlight intuitive aspects of network similarity across scales in a variety of systems.

Read the full article at: www.nature.com

Ariel Flint Ashery, Luca Maria Aiello, Andrea Baronchelli

Social conventions are the foundation for social and economic life. As legions of AI agents increasingly interact with each other and with humans, their ability to form shared conventions will determine how effectively they will coordinate behaviors, integrate into society and influence it. Here, we investigate the dynamics of conventions within populations of Large Language Model (LLM) agents using simulated interactions. First, we show that globally accepted social conventions can spontaneously arise from local interactions between communicating LLMs. Second, we demonstrate how strong collective biases can emerge during this process, even when individual agents appear to be unbiased. Third, we examine how minority groups of committed LLMs can drive social change by establishing new social conventions. We show that once these minority groups reach a critical size, they can consistently overturn established behaviors. In all cases, contrasting the experimental results with predictions from a minimal multi-agent model allows us to isolate the specific role of LLM agents. Our results clarify how AI systems can autonomously develop norms without explicit programming and have implications for designing AI systems that align with human values and societal goals.

Read the full article at: arxiv.org

What does it mean for a complex system to “compute” or perform “computations”? Intuitively, we can understand complex “computation” as occurring when a system’s state is a function of multiple inputs (potentially including its own past state). Here, we discuss how computational processes in complex systems can be generally studied using the concept of statistical synergy, which is information about an output that can only be learned when the joint state of all inputs is known. Building on prior work, we show that this approach naturally leads to a link between multivariate information theory and topics in causal inference, specifically, the phenomenon of causal colliders. We begin by showing how Berkson’s paradox implies a higher-order, synergistic interaction between multidimensional inputs and outputs. We then discuss how causal structure learning can refine and orient analyses of synergies in empirical data, and when empirical synergies meaningfully reflect computation versus when they may be spurious. We end by proposing that this conceptual link between synergy, causal colliders, and computation can serve as a foundation on which to build a mathematically rich general theory of computation in complex systems.

Thomas F. Varley
Entropy 2024, 26(10), 883

Read the full article at: www.mdpi.com

L. K. Eraso-Hernandez and A. P. Riascos

Phys. Rev. E 110, 044309

A system is called antifragile when damage acts as a constructive element improving the performance of a global function. In this paper, we analyze the emergence of antifragility in the movement of random walkers on networks with modular structures or communities. The random walker hops considering the capacity of transport of each link, whereas the links are susceptible to random damage that accumulates over time. We show that in networks with communities and high modularity, the localization of damage in specific groups of nodes leads to a global antifragile response of the system improving the capacity of stochastic transport to more easily reach the nodes of a network. Our findings give evidence of the mechanisms behind antifragile response in complex systems and pave the way for their quantitative exploration in different fields.

Read the full article at: link.aps.org

Ian Seet, Keith Y. Patarroyo, Gage Siebert, Sara I. Walker, Leroy Cronin

Determining the assembly index of a molecule, which aims to find the least number of steps required to make its molecular graph by recursively using previously made structures, is a novel problem seeking to quantify the minimum number of constraints required to build a given molecular graph which has wide applications from biosignature detection to cheminformatics including drug discovery. In this article, we consider this problem from an algorithmic perspective and propose an exact algorithm to efficiently find assembly indexes of large molecules including some natural products. To achieve this, we start by identifying the largest possible duplicate sub-graphs during the sub-graph enumeration process and subsequently implement a dynamic programming strategy with a branch and bound heuristic to exploit already used duplicates and reject impossible states in the enumeration. To do so efficiently, we introduce the assembly state data-structure as an array of edge-lists that keeps track of the graph fragmentation, by keeping the last fragmented sub-graph as its first element. By a precise manipulation of this data-structure we can efficiently perform each fragmentation step and reconstruct an exact minimal pathway construction for the molecular graph. These techniques are shown to compute assembly indices of many large molecules with speed and memory efficiency. Finally, we demonstrate the strength of our approach with different benchmarks, including calculating assembly indices of hundreds of thousands molecules from the COCONUT natural product database.

Read the full article at: arxiv.org