Zirou Qiu

Summary. Networked dynamical systems are widely used as formal models of real-world cascading phenomena, such as the spread of diseases and information. Prior research has addressed the problem of learning the behavior of an unknown dynamical system when the underlying network has a single layer. In this work, we study the learnability of dynamical systems over multilayer networks, which are more realistic and challenging. First, we present an efficient PAC learning algorithm with provable guarantees to show that the learner only requires a small number of training examples to infer an unknown system. We further provide a tight analysis of the Natarajan dimension which measures the model complexity. Asymptotically, our bound on the Nararajan dimension is tight for all multilayer graphs.

Keywords. PAC learning; multilayer graphs; discrete dynamical systems; sample complexity; machine learning

Summary. Due to the large scale of real-world cascades, a complete specification of the underlying dynamical system is often not available. In this work, we study the problem of learning both the behavior and topology of a black-box discrete dynamical system. We show that, in general, this problem is computationally intractable. On the positive side, we present efficient learning methods for different classes of graphs. Further, under a relaxed setting where the topology of an unknown system is partially observed, we develop an efficient PAC learner to infer the full system. Lastly, we present a formal analysis of the expressive power of the hypothesis class of dynamical systems using the formalism of the Natarajan dimension.

Keywords. PAC learning; discrete dynamical systems; sample complexity; machine learning

Summary. Motivated by the allocation of public housing, we examine the problem of assigning a group of agents (from different demographic subgroups) to vertices (e.g., spatial locations) of a network so that the diversity level is maximized. We first present a local-improvement algorithm for general graphs that provides an approximation factor of 2. For the case where the sizes of demographic subgroups are similar, we present a randomized approach based on semidefinite programming that yields an approximation in range [0.516, 0.649]. Lastly, we show that the problem can be solved efficiently when the graph is treewidth-bounded and obtain a polynomial time approximation scheme (PTAS) for the problem on planar graphs.

Keywords. Optimization; approximation algorithms; resource allocation; diversity

Summary. Anti-coordination games capture strategic situations such as market and social competition. We examine the existence of a Nash equilibrium (NE) and the convergence time for the games under sequential and synchronous dynamics. Using a connection to dynamical systems, we identiy a dichotomy on the players' strategy for the tractability of finding an NE. When finding an NE is intractable, we further identify game variants for which an NE can be obtained efficiently. In terms of convergence time, we show that the best-response dynamics converges in a polynomial number of steps in the synchronous scheme; for the sequential scheme, the convergence time is polynomial only under a particular class of player strategy.

Keywords. Anti-coordination games; dynamical systems; Nash equilibrium, convergence time

Summary. Group gathering in enclosed spaces (e.g., classrooms, conferences) is an important route for the spread of respiratory diseases. In this work, we propose a modeling framework to examine airborne disease transmission among a group of people, under scenarios of indoor meetings involving multiple time scales. Towards this end, we study the epidemiological trade-offs emerging by implementing control measures aimed at controlling the viral load. Numerical analysis suggests that ventilation and break times are critical in preventing high viral load levels. Moreover, we found that their impact would equal or exceed that of masking and moderate isolation of infected individuals.

Keywords. Group gathering; multiple time scales; large-scale modeling; pandemic science;

Summary. Non-pharmaceutical interventions such as mask-wearing play a critical role in reducing disease prevalence. In this work, we propose a framework to model the co-evoluation of a disease and a mask-wearing over multilayer networks. We observe a robust non-monotonic relationship between the attack rate (i.e., the fraction of the ever-infected population) and the transmission probability of the disease. Specifically, the attack rate exhibits an abrupt reduction as the transmission probability increases to a critical threshold. Furthermore, we characterize regimes of the transmission probability where multiple waves of infection and mask adoption are expected.

Keywords. Dueling dynamics, multilayer networks, non-pharmaceutical interventions, pandemic science

Summary. In the dissemination of undesirable contagions (such as rumors and misinformation), convergence to fixed points with a small number of infected vertices is a desirable goal. Motivated by such considerations, we formulate a novel optimization problem of finding a fixed point of the system with the minimum number of infected vertices. We fist establish a strong inapproximability for the problem. To cope with the hardness, we identify variants of the problem that can be solved efficiently. Further, we introduce an ILP to address the problem for networks of reasonable sizes. For solving the problem on larger networks, we propose a general heuristic framework along with strategic selection methods. Extensive experimental results on real-world networks demonstrate the effectiveness of the algorithms.

Keywords. Optimization; dynamical systems; fixed point; contagion diffusion

Summary. We study the problem of inferring both the network topology and the behavior of such a system through active queries. We present efficient inference algorithms under both batch and adaptive query models for dynamical systems with symmetric local functions. The proposed algorithms show that the structure and behavior of such dynamical systems can be learnt using only a polynomial number of queries. Further, we establish a lower bound on the number of queries needed to learn such dynamical systems. We also present experimental results obtained by running our algorithms on synthetic and real-world networks.

Keywords. Active learning; query model; discrete dynamical systems; query complexity

Summary. Network alignment is a foundamental task in social network analysis; the goal is to infer the similarities over cross-network vertices and discover node-level correspondence between two different networks. In this work, we propose ELRUNA, a novel network alignment framework that relies exclusively on the underlying graph structure. ELRUNA computes the similarity between a pair of cross-network vertices iteratively by accumulating the similarities between their selected neighbors. The resulting cross-network similarity matrix is then used to infer a permutation matrix that encodes the final alignment of cross-network vertices. Through extensive numerical experiments on real networks, we demonstrate that ELRUNA significantly outperforms the state-of-the-art alignment methods in terms of alignment accuracy. Moreover, ELRUNA is robust to network perturbations such that it can maintain a close to optimal objective value under a high level of noise added to the original networks.

Keywords. Optimization; network alignment; social network analysis