• Parallel Session 1 - Monday 23, 11:50-12:50

    Economics / Social systems 1 / Complex Method 1

Complex Method 1

Auditorium

Chair : Laura Hernandez

Authors: Gaspard Abel, Argyris Kalogeratos, Julien Randon-Furling and Jean-Pierre Nadal

Online social platforms have drastically affected the way people apprehend the information flows to which they are exposed, and the spread of multiple pieces of information or beliefs in a networked population is rarely uncorrelated. In this work we introduce here the Mixture of Interacting Cascades (MIC) model, which is based on marked Multidimensional Hawkes processes. MIC models jointly non-trivial interactions between users and cascades. Moreover, we show how derivative layered visualizations can reveal the coupling between social network structure and topic alignments, and hence can highlight the clusters of users and cascades that are closely related in terms of content.

Alexis Bénichou, Jean-Baptiste Masson and Christian Vestergaard

Physical and functional constraints on networks lead to complex topological patterns across multiple scales in their organization. A particular type of higher-order network feature that has received considerable interest is network motifs, defined as statistically regular subgraphs. These are referred to as “building blocks of complex networks” and may, in biological networks in particular, implement fundamental logical and computational circuits. Their well-defined structures and small sizes also enable the testing of their functions in synthetic and natural experiments. Here, we develop a framework for motif mining based on lossless network compression using subgraph contractions. This provides an alternative definition of motif significance which allows us to compare different motifs and select the collectively most significant set of motifs as well as other prominent network features in terms of their combined compression of the network. Our approach inherently accounts for multiple testing and correlations between subgraphs and does not rely on a priori specification of an appropriate null model. It thus overcomes common problems in hypothesis testing-based motif analysis and guarantees robust statistical inference. We validate our methodology on numerical data and then apply it on synaptic-resolution biological neural networks, as a medium for comparative connectomics, by evaluating their respective compressibility and characterize their inferred circuit motifs.

Building on recent work defining motif significance using information theoretic measures, we conceive a generic methodology for multi-motif mining in graphical data. Statistical significance is defined by the codelength required to describe a graph in a particular model framework; here a collection of candidate circuit motifs (termed graphlets) and a base code, corresponding to a random graph model. We leverage the minimum description length (MDL) principle, which relies on the equivalence between codelengths of universal codes and probabilities, to provide a principled model selection method by choosing the model that achieves the lowest codelength. We devised a stochastic greedy algorithm to infer the optimal encoding of a graph (i.e., its most significant features). This allows us to evaluate both the overall compressibility of a network by comparison with an encoding without any regularities and the significance of individual features by comparison to an encoding without the specific features in question. We apply our method to a range of whole-CNS neural connectomes and find that they are all significantly compressible and that they share common circuit motifs.

An additional advantage of our approach over hypothesis-testing based methods is that inferred circuit motifs are localized in the network, facilitating empirical testing of their biological relevance, e.g., by (opto)genetic activation or inactivation of neurons in live animals. Finally, our algorithm defines a generative model that can be used to generate more realistic null models for network structure and to test the functional importance of given circuit structures in synthetic experiments.

Sergio Magalhães Contente, Christian Vestergaard and Alexis Bénichou

The characterization of real-world networks calls for investigating distinct organization rules, at multiple scales. Across biological applications, from genetics to neuroscience, the relevant interaction range to describe connectivity goes beyond the distribution of node degrees or the detection of large modular structures. An in-between lens emerges as a central focus, both within the theoretical and experimental literatures, and which aims at answering the general question: what are the so-called “building blocks”—the topological patterns—of complex networks? The discovery of these small hypothetically fundamental components requires a flexible approach that is the least constraining and the least biased in terms of the sub-structures’ detectability. Historically, the standard approach has been the mining of “network motifs”, which consists in finding statistically significant classes of subgraphs. Recent generalizations based on information theory and statistical inference allow for a more precise assessment, by inquiring whether a localized motif occurrence, i.e., one particular subgraph, may be of importance.

A practical limitation, which is common to all methods, follows from the sheer number of subgraphs in most natural networks. Given a subgraph of size k, listing all of them is often well beyond our modern computational means, even for moderately small networks. Thus, we must resort to approximate methods that typically rely on subgraph sampling. To avoid biasing downstream analyses and inferences, this sampling should be unbiased, that is, each relevant subgraph should be sampled with equal probability, It turns out that the uniform subgraph sampling is also a non-trivial computational problem. Recently, an efficient stochastic algorithm has however been proposed for undirected networks.

Here, we report our progress on extending this algorithm to directed networks and to sampling targeted subgraph patterns corresponding to a restricted set of subgraphs corresponding to predefined isomorphism classes (graphlets). Our subgraph sampling scheme, which incorporates a suffix tree data structure that has already proved its worth in network motif census, allows for targeting a subset of graphlet types, to be delimited by the user, among all k-sized subgraphs (see Fig. 1 for an application to sample 4-node motifs in a small synthetic network). We apply this new implementation to the standard and inferential motif mining methodologies in multiple biological networks, including all complete publically available neural wiring diagrams.

Economics

Conference room

Chair: Jean-Pierre Nadal

Trade credit in B2B systems, provided through deferred supplier payments, is essential for short-term financing but can create complex networks of unpaid invoices. When late payments accumulate, companies often become both creditors and debtors, resulting in a chain of interlinked obligations that heightens liquidity risks. Failure to collect credits on time can trigger a domino effect of non-payments, potentially leading to widespread financial stress or defaults across interconnected firms. Integral debt netting is a method to mitigate these risks. However, the underlying problem is NP-Complete, posing significant computational challenges for large, real-world graphs. Consequently, we apply a divide-and-conquer strategy onto our initial algorithm, significantly reducing computation time while maintaining result quality. This methodology offers a viable avenue for mitigating systemic financial risks in extensive B2B networks.

Bitcoin, originally conceived as a decentralised, trustless system to challenge traditional financial apparatus, has increasingly exhibited structural properties akin to those of conventional financial markets, such as centralisation, concentration of power, and herd behavior. This study investigates whether Bitcoin adapts to exogenous shocks in a manner similar to financial markets and if so, whether these adaptations are reflected in the reconfiguration of its network structures.
We analyse Bitcoin’s structural dynamics by examining the temporal occurrence of network edges under varying market conditions, focusing on transactions patterns of repetition, reciprocation, and cyclic and transitive closures. Our analysis spans different time horizons, including market crises like the Mt. Gox collapse and the COVID-19 flash crash. Using network analysis and survival analysis, we employ Kaplan-Meier curves to assess the temporal dynamics within the Bitcoin transaction network.
Our findings indicate that Bitcoin network adapts to crises in ways that resemble the behavior of traditional financial markets under stress. By tracing the temporal dynamics of transactions and observing network reconfigurations, we investigate endogenous mechanisms that drive Bitcoin’s response to external shocks, challenging the notion that it operates fundamentally differently from conventional financial systems. Moreover, this study provides a novel perspective on the temporal dynamics of financial networks to avoid reducing network events to static representations and lays the groundwork for future, more causally-oriented analyses.

Bastien Fernandez and Ali Ellouze

Nous introduisons un modèle pour la dynamique de populations d’acheteurs dans des marchés de produits frais tel que le M.I.N. de Rungis, et nous présenterons les résultats de son étude mathématique. Les acheteurs sont mus à la fois par une loyauté envers leurs vendeurs habituels et par une recherche de meilleure opportunité. Les vendeurs, eux, modifient leurs prix selon les volumes de clientèle, de sorte à générer une rétroaction négative sur les acheteurs. Source d’instabilité, cette rétroaction favorise des comportements oscillatoires. Il s’agit donc de déterminer si ces oscillations perdurent indéfiniment ou si les volumes de populations se stabilisent asymptotiquement. Nous verrons en particulier que cette alternative dépend de l’inertie des acheteurs et de la sensibilité intrinsèque des vendeurs dans leur réaction
aux variations de clientèle.