Venue: Madhava Lecture Hall
Workshop on Complex Networks held from 26 - 30 June, 2018
Day:
Since most of the existing real-world networks are evolving, hence, the study of traffic dynamics is a challenging task. Avoidance of traffic congestion, system utility maximization, enhancement of network capacity are prominent issues. In this context, we focus on the design of a time-varying network model and propose an algorithm to find efficient user's route in this network. Centrality plays a very important role in finding congestion-free routes especially, betweenness, closeness and Eigen vector centralities. If the nodes appearing in user's route are most betweenness central then that route will be highly congested. Eigen vector centrality is used to find the influence of a node to others. If a node is most influential then it will be highly congested and considered as least reputed. For that reason, classically, routes are chosen such that the sum of the centrality of the nodes appearing in user's route is minimum. Closeness centrality outperforms betweenness centrality in the case of community structured time-varying networks.
Persistent homology is a recently developed tool to extract qualitative features from data that persist through multiple scales. We employ persistent homology analysis to investigate the dynamics of a well-known system, the Duffing oscillator. To evaluate and correlate the homology characterizers better with the dynamical behaviour of this system, we use statistical methods to obtain signal-to-noise like quantifiers.
"We study dynamic phase transitions on small world and other nonlocal networks. We find that they are not necessarily in a mean-field universality class. We investigate persistence and its generalization for the study of chaotic synchronization in such systems.
Talk 1: Theory of inferring bifurcations and non-smooth behaviours from time series analyses
Talk 2: Real world applications to ecological datasets and financial market time series analyses
TBA
Using networks to detect dynamical regime change in time series
Various techniques have been proposed, and are now fairly widely used, to construct networks from time series which are in turn the output of a deterministic dynamical system. The basic idea behind all these methods is that the network provides insight into some aspect of the dynamics of the underlying system. We will review these methods and demonstrate their efficacy. In particularly we will show that such methods can be used to provide measures which act as a proxy for the largest Lyapunov exponent. From this we are able to follow an emerging bifurcation from a sequence of time series. To demonstrate why these methods work we will draw on some results that have been obtained for the invert process - recovering the time series from the complex network. Finally, we will turn our attention to the harder problem of detecting imminent regime change in a dynamical system from a single measurement function.
Prediction of Indian summer monsoon: from Complex Network to Tipping elements approach
Prediction of the onset and withdrawal of the Indian summer monsoon is crucial for India's economy, social welfare, and environment. The forecasting of monsoon is a challenge mostly because of spatial and temporal variability, and there is no recent historical precedent for such changing in the climate system. Applying climate network approach to a spatial distribution of extreme precipitation over the Indian subcontinent, we revealed regions on the Indian subcontinent, which exhibit anomalous behavior prior to monsoon onset. We have found the evidence in observational data that we can consider the onset of monsoon as a critical transition – a sudden transition to the monsoon when critical thresholds (in particular, in near-surface air temperature, relative humidity) are reached. This finding allows us using the critical transition theory for developing the Tipping elements approach for prediction of onset and withdrawal dates of the summer monsoon. Our prediction relies on observations of near-surface air temperature and relative humidity from both the ERA-40 and NCEP/NCAR re-analyses. Our results show that our method allows predicting the monsoon as retrospectively (over the period 1951-2015) as well in the future. In 2016 and 2017 both of our forecasts were successful. Hence, we proved that such early prediction of the monsoon timing is possible. The proposed approach is applicable for different kind of season, which exhibits properties of critical transition. Our prediction is based on observational data only when the model cannot accurately anticipate the transition or does not exist yet. The author would like to acknowledge the support of the EPICC project (18_II_149_Global_A_Risikovorhersage) funded by BMUB.
References:
- V. Stolbova, P. Martin, B. Bookhagen, N. Marwan and J. Kurths (2014) - Topology and seasonal evolution of the network of extreme precipitation over the Indian subcontinent and Sri Lanka. Nonlinear Processes in Geophysics, 21, 901–917 [doi:10.5194/npg-21-901-2014]
- Stolbova, V., E. Surovyatkina, B. Bookhagen, and J. Kurths (2016): Tipping elements of the Indian monsoon: Prediction of onset and withdrawal. GRL 43, 1–9 [doi:10.1002/2016GL068392]
- https://www.pik-potsdam.de/services/infodesk/forecasting-indian-monsoon
Transport or flux of particles on complex networks can be modelled as random walks. This has many applications such as search and foraging problems on networks, recommender systems and ranking algorithms. For instance, popular algorithms for web search engines are based on some variant of random walks. In the first part of this talk, an overview of the basic ideas and applications will be given. In the second part of the talk, some recent results related to the extent of the network covered by the random walkers and extreme events on networks will be discussed. For applications to realistic dynamics, variants of standard random walks will also be considered. The implications of some of these results for network resilience will be discussed.
Vaccination is a core component of public health initiatives for preventing/containing epidemics of vaccine-preventable diseases. Apart from protecting the individual receiving the vaccine from getting infected, large-scale vaccination also provides herd immunity to the population and is thus a public good. A major factor underlying the success of such an immunization program is the public perception about the benefits and costs associated with vaccination, especially when the decision to get vaccinated is a voluntary one (i.e., in the absence of coercion). Specifically, when the prevalence of a disease is low, the perceived risk of getting infected can be much lower than the perceived cost of getting vaccinated (in terms of side-effects or effort involved, apart from monetary), making the latter course of action less lucrative. With increasing prevalence, the perceived benefit of vaccination may eventually exceed the perceived cost, and as a result individuals will be more likely to opt for vaccination. From the point of view of a rational individual or agent, the best outcome will be one where everybody else gets vaccinated so that she enjoys the benefit of herd immunity, while not incurring any cost associated with getting vaccinated herself. However, if every individual argues in this manner, the vaccination drive will be unsuccessful and the population will be vulnerable to a large-scale epidemic. It is thus equivalent to the ``free-rider'' problem in game theory, where a choice that appears to be optimal for an individual will be sub-optimal if everyone adopts it. This problem lies at the heart of the phenomena of social dilemmas, such as the prisoners' dilemma, which provides a natural framework for understanding voluntary vaccination behavior in a population of rational agents. In this talk we will show how integrating a dynamic compartmental model of epidemic spreading in a social network of rational agents who take strategic decisions to get vaccinated (or not) results in novel insights about the conditions under which voluntary vaccination becomes successful. The implications of our results point towards important role of the different modes of information spreading in society that govern the efficacy of public health intervention schemes.
(This work is done in collaboration with Anupama Sharma (IMSc), Shakti N. Menon (IMSc) and V. Sasidevan (IMSc))
We will show how spatio-temporal chaos in networks with strongly chaotic nodal dynamics can be tamed by dynamically changing links. Specifically, we will illustrate the results in examples ranging from neuronal networks to disease spreading models. Further we will show how random links can prevent blow-ups in coupled nonlinear systems suffering from unbounded growth.
TBA
The traditional monoplex network framework offers only a limited representation of complex systems having different layers of interactions. Recent years have witnessed the emergence of the multiplex network (MN) framework, which provides more accurate insights into the behaviors of complex systems possessing multiple types of relations among the same units. For example, an individual or collective behavior of a society, that is modeled by individuals interacting through the Facebook and Twitter social networks, can be better understood by considering an MN consisting of layers representing the network of connections of people in each social media. The interactions within a layer (intra-layer connection) for this particular network model of a social system encode friendship relations between pairs of two people within each social media, whereas the interactions between the layers (inter-layer connection) represent the impact of interactions in one layer on the other (for example, when two people actively interacting by Facebook increase their Twitter activity because of their Facebook activity), or the probability of a relation switching its existence between the layers. The last 20 years have witnessed a development of methods and techniques to characterize various structural properties and functional activities of networks representing complex systems. Particularly, it has been reported that the eigenvector corresponding to the largest eigenvalue, the so-called principal eigenvector (PEV) of the network’s adjacency matrices, provides information about both the structural and dynamical properties of the underlying systems. For various dynamical processes on networks, for instance, in disease spreading, steady-state vector has been shown to be approximated using PEV of the underlying adjacency matrix. One key factor of our interest is to understand properties of multilayer networks which may help in spreading or restricting perturbation in networks captured by the PEV localization. For a network, an eigenvector is said to be localized when most of its components are near to zero, with few taking very high values.
We develop randomized algorithms considering the inverse participation ratio (IPR) as an objective function and demonstrate that PEV localization is not a consequence of a single network property and rather requires collective impact of several structural features. Moreover, the optimized structure contains a special set of edges, rewiring any one of them leads to a complete delocalization of the PEV from a highly localized state. This sensitivity of the PEV at the most localized state turns out to be related to the behavior of the largest and the second largest eigenvalue of the network. Precisely when the network becomes most localized, the second largest eigenvalue of the adjacency matrix become very close to the largest eigenvalue and there exists evidence of the level crossing. Our analytical calculations match well with the numerical results to a certain extent and deviate in the sensitive region marked by the level crossing. Furthermore, by constructing multiplex network using real-world social and biological data, we show that our simulation results for model multiplex networks are in good agreement with the properties of these real-world multiplex network.
Today, social media and online social networks constantly bombard users with informations. In presence of such a heavy information overload, it becomes critical to understand which pieces of information are getting through and which are ignored. The dynamics of these users’ activities in general, is a complex evolving process and encompasses a spectrum of subprocesses. For example, in Twitter, when a user receives a tweet, she may simply re-tweet the message, or modify its content, or gain information and form opinion about a particular topic. However, the dynamics of all these processes can be naturally encapsulated by a potent mathematical devise called ‘temporal point process’, which models the rate of arrival of messages using different functional forms characterizing various phenomenons of interest. In this talk, we would discuss two key dynamical processes in Twitter, opinion dynamics of the users and hashtag propagation.
In this first part, we aim to learn a data-driven model of opinion dynamics that is able to accurately forecast opinions of any user in future. We introduce SLANT, a probabilistic modeling framework of opinion dynamics, which represents users opinions over time by means of marked jump diffusion stochastic differential equations, and allows for efficient model simulation and parameter estimation from historical fine grained event data. We then leverage our framework to derive a set of efficient predictive formulas for opinion forecasting and identify conditions under which opinions converge to a steady state.
The second part of the talk is more about the complex temporal dynamics that jointly models hashtag reinforcement and hashtag competition. While the existing works have mainly focused on modeling the popularity of individual tweets rather than the popularity of the underlying hashtags, we propose Large Margin Point Process (LMPP), a novel probabilistic framework that integrates hashtag-tweet influence and hashtag-hashtag competitions, the two factors which play important roles in hashtag propagation. Furthermore, while considering the hashtag competitions, LMPP looks into the variations of popularity rankings of the competing hashtags across time.
Complex networks are ubiquitous in biology; cellular function is a result of the web of interplay between different types of complex networks within the cell, spanning from metabolism to signalling and gene regulation. In a series of two talks, we will study metabolic networks from two different perspectiv es. In the first talk, we will look at how reaction patterns/rules can be learnt from metabolic networks to infer and predict novel pathways. The ability to predict pathways for biosynthesis of metabolites is very important in metabolic engineering. It is possible to mine the repertoire of biochemical transformations from reaction databases, and apply the knowledge to predict reactions to synthesise new molecules. However, this usually involves a careful understanding of the mechanism and the knowledge of the exact bonds being created and broken. There is clearly a need for a method to rapidly predict reactions for synthesising new molecules, which relies only on the structures of the molecules, without demanding additional information such as thermodynamics or hand-curated reactant mapping, which are often hard to obtain accurately. In this talk, I will describe a robust method based on graph mining, to predict a series of biochemical transformations, which can convert between two (even previously unseen) molecules. We mine the reaction database and store reaction centres and signatures in a reaction rule network. Such a novel representation enables us to rapidly predict pathways. We also propose a heuristic that predominantly recovers natural biosynthetic pathways from amongst hundreds of alternatives, through a directed search of the reaction rule network, enabling us to provide a reliable ranking of pathways. Our approach scales well, even to databases with >100,000 reactions. Our tool, ReactionMiner, is available from Link.
In the second talk, we look at efficient ways to exhaustively identify all p ossible alternate pathways that exist in metabolic networks, which can provide valuable insights into cellular metabolism. With the growing number of metabolic reconstructions, there is a need for an efficient method to enumerate pathways, which can also scale well to large metabolic networks, such as those corresponding to microbial communities. We developed MetQuest, an efficient graph-theoretic algorithm to enumerate all possible pathways of a particular size between a given set of source and target molecules. Our algorithm employs a guided breadth-first search to identify all feasible reactions based on the availability of the precursor molecules, followed by a novel dynamic-programming based enumeration, which assembles these reactions into pathways of a specified size producing the target from the source. We demonstrate several interesting applications of our algorithm, ranging from identifying amino acid biosynthesis pathways to identifying the most diverse pathways involved in degradation of complex molecules. We also illustrate the scalability of our algorithm, by studying large graphs such as those corresponding to microbial communities, and identify several metabolic interactions happening therein. MetQuest is available as a Python package and the source codes can be found at this link.
Cardiac Arrhythmias: What can we learn from Mathematical Models for Cardiac Tissue?
"Mammalian hearts are among the most efficient electro-mechanical pumps in the biological world. They sustain pulmonary and systemic circulation by pumping, rhythmically, roughly 4.5-5 L/min of blood in normal human adults. Aberrations in the normal cardiac rhythm are called cardiac arrhythmias; the most serious ones, ventricular tachycardia and ventricular fibrillation, are a leading cause of death in the industrialised world (approximately 1 out of every 6 deaths). These arrhythmias arise primarily because of the formation, and breaking, of spiral or scroll waves of electrical activation in cardiac tissue. Thus, the development of a detailed understanding of the propagation of such waves of electrical activation through cardiac tissue is an interdisciplinary problem of central importance in the biological, physical, mathematical, and computational sciences, in which in vivo, in vitro, and in silico studies play equally important and complementary roles. This lecture provides a concise overview of the initiation, propagation, break-up, and control (the mathematical analogue of defibrillation) of spiral and scroll waves in mathematical models for cardiac tissue.
My work in this area has been carried out with several students and postdoctoral fellows (A. Pande, S. Sinha, A. Sen, T.K. Shajahan, A.R. Nayak, R. Majumder, K.V. Rajany, S. Zimik, and M.K. Mulimani)
Light-cone spreading of perturbations and the butterfly effect in classical spin chains
The talk will discuss the chaotic growth and spread of perturbations in many body classical systems with Hamiltonian dynamics. In particular, we will consider the example of the Heisenberg spin chain and show that chaos propagation can be characterised by a velocity dependent Lyapunov exponent. The perturbation spreads ballistically and we comment on some interesting properties of the propagation front.
Chimera states in mechanical oscillator networks
TBA
Decimated Navier-Stokes turbulence
We give an overview of recent advances in the study of small-scale and high- frequency turbulent fluctuations in turbulent flows under Fourier-mode reduction. The Navier–Stokes equations are evolved on a restricted set of modes, obtained as a projection on a fractal or homogeneous Fourier set. In the first part of the talk, we will describe how such a system allows us to obtain a non-integer critical dimension where the Kolmogorov spectrum coincides with the equilibrium distribution. We then show a strong sensitivity (reduction) of the high-frequency variability of the Lagrangian velocity fluctuations on the degree of mode decimation. This is quantified by a tendency towards a quasi-Gaussian statistics, i.e., to a reduction of intermittency, at all scales and frequencies. This can be attributed to a strong depletion of vortex filaments and of the vortex stretching mechanism. Nevertheless, we found that Eulerian and Lagrangian ensembles are still connected by a dimensional bridge-relation which is independent of the degree of Fourier- mode decimation. Finally we discuss the implications of such an approach for intermittency, chaos and irreversibility in turbulence.
Dynamics of non-spherical particles and chains
We discuss the dynamics of non-spherical particles and chains in a turbulent flow. We show that very complex dynamics can evolve when we go beyond the point, spherical particle approximation and consider other degrees of freedom. We will then end, time permitting, with a discussion of how these may be used to model the collective behaviour of microorganisms in non-trivial flows.
1. Complex Networks to Study Dynamical Transitions in Thermoacoustic Systems
We investigate the scale invariance of combustion noise generated from turbulent reacting flows in a confined environment using complex networks. The time series data of unsteady pressure, which is the indicative of spatio-temporal changes happening in the combustor, is converted into complex networks using the visibility algorithm. We show that the complex networks obtained from the low-amplitude, aperiodic pressure fluctuations during combustion noise have scale-free structure. The power law distributions of connections in the scale-free network are related to the scale invariance of combustion noise. We also show that the scale-free feature of combustion noise disappears and order emerges in the complex network topology during the transition from combustion noise to combustion instability. The use of complex networks enables us to formalize the identification of the pattern (i.e. scale-free to order) during the transition from combustion noise to thermoacoustic instability as a structural change in topology of the network. Further, we construct recurrence networks from the same data, which also lead to similar conclusions.
2. Spatio-temporal analysis of thermoacoustic systems
We use complex network theory to investigate the dynamical transition from stable operation to thermoacoustic instability via intermittency in a turbulent combustor with a bluff body stabilized flame. A spatial network is constructed, representing each of these three dynamical regimes of combustor operation, based on the correlation between time series of local velocity obtained from particle image velocimetry (PIV). Network centrality measures enable us to identify critical regions of the field during combustion noise, intermittency and thermoacoustic instability. We find that during combustion noise, the bluff body wake turns out to be the critical region that determines the dynamics of the combustor. As the turbulent combustor transitions to thermoacoustic instability, during intermittency, the wake of the bluff body loses its significance in determining the flow dynamics and the region on top of the bluff body emerges as the most critical region in determining the flow dynamics during thermoacoustic instability. The knowledge about this critical region of the reactive flow field can help us devise optimal control strategies to evade thermoacoustic instability.
We discuss two different dynamical phenomena on complex networks; namely, the ordering dynamics of spin systems and infectious disease spreading. In the first, we have considered the dynamics on several different types of networks while the second problem is mainly considered on a Euclidean network. For ordering dynamics of spin systems, the nonequilibrium behaviour and phase transitions are studied in detail. For infectious diseases on networks, we discuss a model and its application in a real case. For both phenomena, we discuss open problems and possibilities.
In this talk, we discuss the behaviour of a ring of identical Stuart-Landau oscillators with symmetry breaking coupling by playing with the choice of initial conditions. These network of oscillators exhibits a variety of asymptotic states, namely, multicluster oscillation death, chimera states, traveling waves, and chimera death. Increasing asymmetry in the initial cluster size favours complete synchronization state for a broad range of coupling parameters. We also show that the network model can also be reduced using the mean-field approximation that reproduces the dynamical features of the original network.
An abrupt transition from an oscillatory state to a death one in coupled oscillators is termed as explosive death transition. The occurrence of explosive oscillation quenching in a system of coupled Stuart-Landau oscillators is studied by Bi et al. where three typical scenarios with distinct microscopic mechanism of occurrence, i.e., ordinary, hierarchical, and cluster explosive oscillation death, corresponding to different frequency distributions of oscillators are observed [1]. In another study, an explosive death transition in an ensemble of identical limit cycle and chaotic oscillators coupled via mean–field diffusion is studied. Here, the variation of the normalized amplitude with the coupling strength exhibits an abrupt and irreversible transition to death state from an oscillatory state and this first order phase transition to death state is independent of the size of the system. This transition is quite general and has been found in all the coupled systems where in–phase oscillations co–exist with a coupling dependent homogeneous steady state [2]. This transition is also studied in environmentally coupled oscillators as well as a network of oscillators with nonlocal coupling and indirect coupling [3, 4].
References:
1. H. Bi, X. Hu, X. Zhang, Y. Zou, Z. Liu and S. Guan, Explosive oscillation death in coupled Stuart-Landau oscillators. Europhysics Letters, 108, 50003 (2014).
2. Explosive death induced by mean–field diffusion in identical oscillators, U K Verma, A Sharma, N K Kamal, J Kurths, and Manish Dev Shrimali, Scientific Reports, 7, 7936 (2017).
3. First order transition to oscillation death through an environment, Umesh Kumar Verma, Amit Sharma, Neeraj Kumar, Kamal, Manish Dev Shrimali, Physics Letters A, in press (2018).
4. Explosive death in complex network, preprint (2018).
We propose a method to construct weighted recurrence networks from a time series, where the weight of each link is defined in terms of the degrees of connecting nodes. We show that such networks, when generated from chaotic time series, form a new class of complex networks characterized by a node strength distribution that follows a power law, with an exponential tail. The scaling index of power law is found to be characteristic to the fractal structure of the underlying attractor. We generalize the definition of the two other network measures, viz. clustering coefficient and characteristic path length, and they are found useful in discriminating chaotic dynamics from noise.
Collaborators:
Rinku Jacob and K. P. Harikrishnan Department of Physics, The Cochin College, Cochin-682 002, India
R. Misra, Inter University Centre for Astronomy and Astrophysics, Pune-411 007, India
In this Discussion topic we wish to initiate a dialogue between complexity scientists on what has recently been termed the "Systems approach to public health". There is a growing recognition that many public health concerns are a multiscale problem. Consider the example of obesity, its systematic growth to epidemic proportions in the population. One the one hand obesity is an individual's concern (with managing overnutrition); this is the microscopic scale in the system. On the other hand, there is an exquisite coupling to factors that function at the population - macroscopic - scale. Many such factors have been identified; please see the Obesity System Influence diagram for a network representation of the myriad interdependencies at http://www.shiftn.com/obesity/Full-Map.html [2]. A particularly fruitful area of application for network science seems to be non-communicable diseases (NCDs). A recent WHO report ("Time to deliver", 2018) identifies five key themes as the reduction of: Premature death, alchohol and tobacco (ab)use), physical inactivity and unhealthy diets. Can complexity systems scientists show the way forward for such initiatives? Are there actionable insights from networks science that can shape future policy? Is data collection a central question, or limitation? What is the relationship between modelling and data-driven approaches in the systems view of public health? In other words, how can specialists from networks and systems science help construct the conceptual frameworks that can crystallize the amorphous goals of ameliorating chronic disease, and creating effective public health systems.
Network representations are one of the emerging paradigms for analysis, control and monitoring of complex systems. A particular class of networks, namely, causal dynamical networks has attracted widespread attention across the broad fields of science, engineering, social science and econometrics. This talk is concerned with reconstructing causal networks from observed data with focus on a sub-class, known as the Granger-causal networks. Frequency-domain methods of reconstructions for linear stochastic processes with extensions to handle missing data and non-linear processes are presented. We take this opportunity to provide an overview of causality analysis and challenges ahead. Applications to topology reconstruction, analysis of interactions in multivariable control systems shall be briefly discussed.
The idea of Robust Chaos was introduced by Banerjee, Grebogi and Yorke in the 1990s to describe systems with chaotic attractors on intervals of parameter values. I shall look at the various methods and results -- both theoretical and numerical -- available to investigate this phenomenon in piecewise smooth dynamical systems.
Obtaining a sparse representation of high dimensional data is importan t since it provides an efficient representation of the data and facilitates its further analysis. Conventional Vector Autoregressive (VAR) modeling methods applied to such data result in non-sparse solutions with a large number of spurious coefficients. We propose two sparse VAR modelling methods that work well for high dimensional time series data, even when the number of time points is relatively low, by incorporating only statistically significant coefficients. In numerical experiments, our methods show consistently higher accuracy compared to other contemporary methods in recovering the true sparse model. The relative absence of spurious coefficients in our models permits more accurate, stable and efficient evaluation of derived quantities such as power spectrum, coherence and Granger causality. Using our models, sparse functional connectivity networks can be computed, in a reasonable time, from data comprising tens of thousands of channels/voxels. This far exceeds the capabilit ies of existing methods and enables simultaneous analysis of both local and global functional connectivity patterns and community structures in such large networks. When computed for fMRI data, these network and community structures are consistent over independent recording sessions and they show good spatial correspondence with known functional and anatomical regions of the brain. Our methods, when used to analyze ADHD fMRI data, provide new ways of differentiating between ADHD and typically developing children using global and node-level network measures.
I will describe a representation of the Indian summer monsoon rainfall in terms of a probabilistic model based on a Markov Random Field, consisting of discrete state variables representing low and high rainfall at grid-scale and daily rainfall patterns across space and in time. These discrete states are conditioned on observed daily gridded rainfall data from the period 2000-2007. The model gives us a set of 10 spatial patterns of daily monsoon rainfall over India, which are robust over a range of user-chosen parameters as well as coherent in space and time. Each day in the monsoon season is assigned precisely one of the spatial patterns, that approximates the spatial distribution of rainfall on that day. Such approximations are quite accurate for nearly 95% of the days. Remarkably, these patterns are representative (with similar accuracy) of the monsoon seasons from 1901 to 2000 as well.