Search for: All records

Discrete dynamical systems serve as useful formal models to study diffusion phenomena in social networks. Several recent articles have studied the algorithmic and complexity aspects of some decision problems on synchronous Boolean networks, which are discrete dynamical systems whose underlying graphs are directed, and may contain directed cycles. Such problems can be regarded as reachability problems in the phase space of the corresponding dynamical system. Previous work has shown that some of these decision problems become efficiently solvable for systems on directed acyclic graphs (DAGs). Motivated by this line of work, we investigate a number of decision problems for dynamical systems whose underlying graphs are DAGs. We show that computational intractability (i.e.,PSPACE-completeness) results for reachability problems hold even for dynamical systems on DAGs. We also identify some restricted versions of dynamical systems on DAGs for which reachability problem can be solved efficiently. In addition, we show that a decision problem (namely, Convergence), which is efficiently solvable for dynamical systems on DAGs, becomesPSPACE-complete for Quasi-DAGs (i.e., graphs that become DAGs by the removal of asingleedge). In the process of establishing the above results, we also develop several structural properties of the phase spaces of dynamical systems on DAGs. 

Discrete dynamical systems are commonly used to model the spread of contagions on real-world networks. Under the PAC framework, existing research has studied the problem of learning the behavior of a system, assuming that the underlying network is known. In this work, we focus on a more challenging setting: to learn both the behavior and the underlying topology of a black-box system. We show that, in general, this learning problem is computationally intractable. On the positive side, we present efficient learning methods under the PAC model when the underlying graph of the dynamical system belongs to certain classes. Further, we examine a relaxed setting where the topology of an unknown system is partially observed. For this case, we develop an efficient PAC learner to infer the system and establish the sample complexity. Lastly, we present a formal analysis of the expressive power of the hypothesis class of dynamical systems where both the topology and behavior are unknown, using the well-known Natarajan dimension formalism. Our results provide a theoretical foundation for learning both the topology and behavior of discrete dynamical systems. 

Networks allow us to describe a wide range of interaction phenomena that occur in complex systems arising in such diverse fields of knowledge as neuroscience, engineering, ecology, finance, and social sciences. Until very recently, the primary focus of network models and tools has been on describing the pairwise relationships between system entities. However, increasingly more studies indicate that polyadic or higher-order group relationships among multiple network entities may be the key toward better understanding of the intrinsic mechanisms behind the functionality of complex systems. Such group interactions can be, in turn, described in a holistic manner by simplicial complexes of graphs. Inspired by these recently emerging results on the utility of the simplicial geometry of complex networks for contagion propagation and armed with a large-scale synthetic social contact network (also known as a digital twin) of the population in the U.S. state of Virginia, in this paper, we aim to glean insights into the role of higher-order social interactions and the associated varying social group determinants on COVID-19 propagation and mitigation measures. 

The SARS-CoV-2 pandemic has generated a considerable number of infections and associated morbidity and mortality across the world. Recovery from these infections, combined with the onset of large-scale vaccination, have led to rapidly-changing population-level immunological landscapes. In turn, these complexities have highlighted a number of important unknowns related to the breadth and strength of immunity following recovery or vaccination. Using simple mathematical models, we investigate the medium-term impacts of waning immunity against severe disease on immuno-epidemiological dynamics. We find that uncertainties in the duration of severity-blocking immunity (imparted by either infection or vaccination) can lead to a large range of medium-term population-level outcomes (i.e. infection characteristics and immune landscapes). Furthermore, we show that epidemiological dynamics are sensitive to the strength and duration of underlying host immune responses; this implies that determining infection levels from hospitalizations requires accurate estimates of these immune parameters. More durable vaccines both reduce these uncertainties and alleviate the burden of SARS-CoV-2 in pessimistic outcomes. However, heterogeneity in vaccine uptake drastically changes immune landscapes toward larger fractions of individuals with waned severity-blocking immunity. In particular, if hesitancy is substantial, more robust vaccines have almost no effects on population-level immuno-epidemiology, even if vaccination rates are compensatorily high among vaccine-adopters. This pessimistic scenario for vaccination heterogeneity arises because those few individuals that are vaccine-adopters are so readily re-vaccinated that the duration of vaccinal immunity has no appreciable consequences on their immune status. Furthermore, we find that this effect is heightened if vaccine-hesitants have increased transmissibility (e.g. due to riskier behavior). Overall, our results illustrate the necessity to characterize both transmission-blocking and severity-blocking immune time scales. Our findings also underline the importance of developing robust next-generation vaccines with equitable mass vaccine deployment. 

Large-scale population displacements arising from conflict-induced forced migration generate uncertainty and introduce several policy challenges. Addressing these concerns requires an interdisciplinary approach that integrates knowledge from both computational modeling and social sciences. We propose a generalized computational agent-based modeling framework grounded by Theory of Planned Behavior to model conflict-induced migration outflows within Ukraine during the start of that conflict in 2022. Existing migration modeling frameworks that attempt to address policy implications primarily focus on destination while leaving absent a generalized computational framework grounded by social theory focused on the conflict-induced region. We propose an agent-based framework utilizing a spatiotemporal gravity model and a Bi-threshold model over a Graph Dynamical System to update migration status of agents in conflict-induced regions at fine temporal and spatial granularity. This approach significantly outperforms previous work when examining the case of Russian invasion in Ukraine. Policy implications of the proposed framework are demonstrated by modeling the migration behavior of Ukrainian civilians attempting to flee from regions encircled by Russian forces. We also showcase the generalizability of the model by simulating a past conflict in Burundi, an alternative conflict setting. Results demonstrate the utility of the framework for assessing conflict-induced migration in varied settings as well as identifying vulnerable civilian populations.