-
Decomposing force fields as flows on graphs reconstructed from stochastic trajectories
Authors:
Ramón Nartallo-Kaluarachchi,
Paul Expert,
David Beers,
Alexander Strang,
Morten L. Kringelbach,
Renaud Lambiotte,
Alain Goriely
Abstract:
Disentangling irreversible and reversible forces from random fluctuations is a challenging problem in the analysis of stochastic trajectories measured from real-world dynamical systems. We present an approach to approximate the dynamics of a stationary Langevin process as a discrete-state Markov process evolving over a graph-representation of phase-space, reconstructed from stochastic trajectories…
▽ More
Disentangling irreversible and reversible forces from random fluctuations is a challenging problem in the analysis of stochastic trajectories measured from real-world dynamical systems. We present an approach to approximate the dynamics of a stationary Langevin process as a discrete-state Markov process evolving over a graph-representation of phase-space, reconstructed from stochastic trajectories. Next, we utilise the analogy of the Helmholtz-Hodge decomposition of an edge-flow on a contractible simplicial complex with the associated decomposition of a stochastic process into its irreversible and reversible parts. This allows us to decompose our reconstructed flow and to differentiate between the irreversible currents and reversible gradient flows underlying the stochastic trajectories. We validate our approach on a range of solvable and nonlinear systems and apply it to derive insight into the dynamics of flickering red-blood cells and healthy and arrhythmic heartbeats. In particular, we capture the difference in irreversible circulating currents between healthy and passive cells and healthy and arrhythmic heartbeats. Our method breaks new ground at the interface of data-driven approaches to stochastic dynamics and graph signal processing, with the potential for further applications in the analysis of biological experiments and physiological recordings. Finally, it prompts future analysis of the convergence of the Helmholtz-Hodge decomposition in discrete and continuous spaces.
△ Less
Submitted 20 November, 2024; v1 submitted 2 September, 2024;
originally announced September 2024.
-
A unified framework for Simplicial Kuramoto models
Authors:
Marco Nurisso,
Alexis Arnaudon,
Maxime Lucas,
Robert L. Peach,
Paul Expert,
Francesco Vaccarino,
Giovanni Petri
Abstract:
Simplicial Kuramoto models have emerged as a diverse and intriguing class of models describing oscillators on simplices rather than nodes. In this paper, we present a unified framework to describe different variants of these models, categorized into three main groups: "simple" models, "Hodge-coupled" models, and "order-coupled" (Dirac) models. Our framework is based on topology, discrete different…
▽ More
Simplicial Kuramoto models have emerged as a diverse and intriguing class of models describing oscillators on simplices rather than nodes. In this paper, we present a unified framework to describe different variants of these models, categorized into three main groups: "simple" models, "Hodge-coupled" models, and "order-coupled" (Dirac) models. Our framework is based on topology, discrete differential geometry as well as gradient flows and frustrations, and permits a systematic analysis of their properties. We establish an equivalence between the simple simplicial Kuramoto model and the standard Kuramoto model on pairwise networks under the condition of manifoldness of the simplicial complex. Then, starting from simple models, we describe the notion of simplicial synchronization and derive bounds on the coupling strength necessary or sufficient for achieving it. For some variants, we generalize these results and provide new ones, such as the controllability of equilibrium solutions. Finally, we explore a potential application in the reconstruction of brain functional connectivity from structural connectomes and find that simple edge-based Kuramoto models perform competitively or even outperform complex extensions of node-based models.
△ Less
Submitted 29 May, 2023;
originally announced May 2023.
-
Local dominance unveils clusters in networks
Authors:
Dingyi Shi,
Fan Shang,
Bingsheng Chen,
Paul Expert,
Linyuan Lü,
H. Eugene Stanley,
Renaud Lambiotte,
Tim S. Evans,
Ruiqi Li
Abstract:
Clusters or communities can provide a coarse-grained description of complex systems at multiple scales, but their detection remains challenging in practice. Community detection methods often define communities as dense subgraphs, or subgraphs with few connections in-between, via concepts such as the cut, conductance, or modularity. Here we consider another perspective built on the notion of local…
▽ More
Clusters or communities can provide a coarse-grained description of complex systems at multiple scales, but their detection remains challenging in practice. Community detection methods often define communities as dense subgraphs, or subgraphs with few connections in-between, via concepts such as the cut, conductance, or modularity. Here we consider another perspective built on the notion of local dominance, where low-degree nodes are assigned to the basin of influence of high-degree nodes, and design an efficient algorithm based on local information. Local dominance gives rises to community centers, and uncovers local hierarchies in the network. Community centers have a larger degree than their neighbors and are sufficiently distant from other centers. The strength of our framework is demonstrated on synthesized and empirical networks with ground-truth community labels. The notion of local dominance and the associated asymmetric relations between nodes are not restricted to community detection, and can be utilised in clustering problems, as we illustrate on networks derived from vector data.
△ Less
Submitted 29 March, 2024; v1 submitted 30 September, 2022;
originally announced September 2022.
-
Cycle Analysis of Directed Acyclic Graphs
Authors:
Vaiva Vasiliauskaite,
Tim S. Evans,
Paul Expert
Abstract:
In this paper, we employ the decomposition of a directed network as an undirected graph plus its associated node metadata to characterise the cyclic structure found in directed networks by finding a Minimal Cycle Basis of the undirected graph and augment its components with direction information. We show that only four classes of directed cycles exist, and that they can be fully distinguished by t…
▽ More
In this paper, we employ the decomposition of a directed network as an undirected graph plus its associated node metadata to characterise the cyclic structure found in directed networks by finding a Minimal Cycle Basis of the undirected graph and augment its components with direction information. We show that only four classes of directed cycles exist, and that they can be fully distinguished by the organisation and number of source-sink node pairs and their antichain structure. We are particularly interested in Directed Acyclic Graphs and introduce a set of metrics that characterise the Minimal Cycle Basis using the Directed Acyclic Graphs metadata information. In particular, we numerically show that Transitive Reduction stabilises the properties of Minimal Cycle Bases measured by the metrics we introduced while retaining key properties of the Directed Acyclic Graph. This makes the metrics consistent characterisation of Directed Acyclic Graphs and the systems they represent. We measure the characteristics of the Minimal Cycle Bases of four models of Transitively Reduced Directed Acyclic Graphs and show that the metrics introduced are able to distinguish the models and are sensitive to their generating mechanisms.
△ Less
Submitted 5 August, 2021;
originally announced August 2021.
-
Modelling the Spread of Covid-19 on Malaysian Contact Networks for Practical Reopening Strategies in an Institutional Setting
Authors:
Fatimah Abdul Razak,
Paul Expert
Abstract:
Reopening strategies are crucial to balance efforts of economic revitalization and bringing back a sense of normalcy while mitigating outbreaks and effectively flattening the infection curve. This paper proposes practical reopening, monitoring and testing strategies for institutions to reintroduce physical meetings based on SIR simulations run on a student friendship network collected pre-Covid-19…
▽ More
Reopening strategies are crucial to balance efforts of economic revitalization and bringing back a sense of normalcy while mitigating outbreaks and effectively flattening the infection curve. This paper proposes practical reopening, monitoring and testing strategies for institutions to reintroduce physical meetings based on SIR simulations run on a student friendship network collected pre-Covid-19. These serve as benchmarks to assess several testing strategies that can be applied in physical classes. Our simulations show that the best outbreak mitigation results are obtained with full knowledge of contact, but are also robust to non-compliance of students to new social interaction guidelines, simulated by partial knowledge of the interactions. These results are not only applicable to institutions but also for any organization or company wanting to navigate the Covid-19 ravaged world.
△ Less
Submitted 7 April, 2021;
originally announced April 2021.
-
Geometric graphs from data to aid classification tasks with graph convolutional networks
Authors:
Yifan Qian,
Paul Expert,
Pietro Panzarasa,
Mauricio Barahona
Abstract:
Traditional classification tasks learn to assign samples to given classes based solely on sample features. This paradigm is evolving to include other sources of information, such as known relations between samples. Here we show that, even if additional relational information is not available in the data set, one can improve classification by constructing geometric graphs from the features themselv…
▽ More
Traditional classification tasks learn to assign samples to given classes based solely on sample features. This paradigm is evolving to include other sources of information, such as known relations between samples. Here we show that, even if additional relational information is not available in the data set, one can improve classification by constructing geometric graphs from the features themselves, and using them within a Graph Convolutional Network. The improvement in classification accuracy is maximized by graphs that capture sample similarity with relatively low edge density. We show that such feature-derived graphs increase the alignment of the data to the ground truth while improving class separation. We also demonstrate that the graphs can be made more efficient using spectral sparsification, which reduces the number of edges while still improving classification performance. We illustrate our findings using synthetic and real-world data sets from various scientific domains.
△ Less
Submitted 13 April, 2021; v1 submitted 8 May, 2020;
originally announced May 2020.
-
Quantifying the Alignment of Graph and Features in Deep Learning
Authors:
Yifan Qian,
Paul Expert,
Tom Rieu,
Pietro Panzarasa,
Mauricio Barahona
Abstract:
We show that the classification performance of graph convolutional networks (GCNs) is related to the alignment between features, graph, and ground truth, which we quantify using a subspace alignment measure (SAM) corresponding to the Frobenius norm of the matrix of pairwise chordal distances between three subspaces associated with features, graph, and ground truth. The proposed measure is based on…
▽ More
We show that the classification performance of graph convolutional networks (GCNs) is related to the alignment between features, graph, and ground truth, which we quantify using a subspace alignment measure (SAM) corresponding to the Frobenius norm of the matrix of pairwise chordal distances between three subspaces associated with features, graph, and ground truth. The proposed measure is based on the principal angles between subspaces and has both spectral and geometrical interpretations. We showcase the relationship between the SAM and the classification performance through the study of limiting cases of GCNs and systematic randomizations of both features and graph structure applied to a constructive example and several examples of citation networks of different origins. The analysis also reveals the relative importance of the graph and features for classification purposes.
△ Less
Submitted 26 January, 2021; v1 submitted 30 May, 2019;
originally announced May 2019.
-
Graph spectral characterisation of the XY model on complex networks
Authors:
Paul Expert,
Sarah de Nigris,
Taro Takaguchi,
Renaud Lambiotte
Abstract:
There is recent evidence that the $XY$ spin model on complex networks can display three different macroscopic states in response to the topology of the network underpinning the interactions of the spins. In this work, we present a novel way to characterise the macroscopic states of the $XY$ spin model based on the spectral decomposition of time series using topological information about the underl…
▽ More
There is recent evidence that the $XY$ spin model on complex networks can display three different macroscopic states in response to the topology of the network underpinning the interactions of the spins. In this work, we present a novel way to characterise the macroscopic states of the $XY$ spin model based on the spectral decomposition of time series using topological information about the underlying networks. We use three different classes of networks to generate time series of the spins for the three possible macroscopic states. We then use the temporal Graph Signal Transform technique to decompose the time series of the spins on the eigenbasis of the Laplacian. From this decomposition, we produce spatial power spectra, which summarise the activation of structural modes by the non-linear dynamics, and thus coherent patterns of activity of the spins. These signatures of the macroscopic states are independent of the underlying networks and can thus be used as universal signatures for the macroscopic states. This work opens new avenues to analyse and characterise dynamics on complex networks using temporal Graph Signal Analysis.
△ Less
Submitted 8 June, 2017; v1 submitted 4 November, 2016;
originally announced November 2016.
-
Temporal stability of network partitions
Authors:
Giovanni Petri,
Paul Expert
Abstract:
We present a method to find the best temporal partition at any time-scale and rank the relevance of partitions found at different time-scales. This method is based on random walkers coevolving with the network and as such constitutes a generalization of partition stability to the case of temporal networks. We show that, when applied to a toy model and real datasets, temporal stability uncovers str…
▽ More
We present a method to find the best temporal partition at any time-scale and rank the relevance of partitions found at different time-scales. This method is based on random walkers coevolving with the network and as such constitutes a generalization of partition stability to the case of temporal networks. We show that, when applied to a toy model and real datasets, temporal stability uncovers structures that are persistent over meaningful time-scales as well as important isolated events, making it an effective tool to study both abrupt changes and gradual evolution of a network mesoscopic structures.
△ Less
Submitted 7 August, 2014; v1 submitted 28 April, 2014;
originally announced April 2014.
-
Uncovering space-independent communities in spatial networks
Authors:
Paul Expert,
Tim Evans,
Vincent D. Blondel,
Renaud Lambiotte
Abstract:
Many complex systems are organized in the form of a network embedded in space. Important examples include the physical Internet infrastucture, road networks, flight connections, brain functional networks and social networks. The effect of space on network topology has recently come under the spotlight because of the emergence of pervasive technologies based on geo-localization, which constantly fi…
▽ More
Many complex systems are organized in the form of a network embedded in space. Important examples include the physical Internet infrastucture, road networks, flight connections, brain functional networks and social networks. The effect of space on network topology has recently come under the spotlight because of the emergence of pervasive technologies based on geo-localization, which constantly fill databases with people's movements and thus reveal their trajectories and spatial behaviour. Extracting patterns and regularities from the resulting massive amount of human mobility data requires the development of appropriate tools for uncovering information in spatially-embedded networks. In contrast with most works that tend to apply standard network metrics to any type of network, we argue in this paper for a careful treatment of the constraints imposed by space on network topology. In particular, we focus on the problem of community detection and propose a modularity function adapted to spatial networks. We show that it is possible to factor out the effect of space in order to reveal more clearly hidden structural similarities between the nodes. Methods are tested on a large mobile phone network and computer-generated benchmarks where the effect of space has been incorporated.
△ Less
Submitted 3 January, 2012; v1 submitted 15 December, 2010;
originally announced December 2010.