Search for: All records

Estimating the true prevalence of an epidemic outbreak is a key public health problem. This is challenging because surveillance is usually resource intensive and biased. In the network setting, prior work on cost sensitive disease surveillance has focused on choosing a subset of individuals (or nodes) to minimize objectives such as probability of outbreak detection. Such methods do not give insights into the outbreak size distribution which, despite being complex and multi-modal, is very useful in public health planning.We introduce TESTPREV, a problem of choosing a subset of nodes which maximizes the mutual information with disease prevalence, which directly provides information about the outbreak size distribution. We show that, under the independent cascade (IC) model, solutions computed by all prior disease surveillance approaches are highly sub-optimal for TESTPREV in general. We also show that TESTPREV is hard to even approximate. While this mutual information objective is computationally challenging for general networks, we show that it can be computed efficiently for various network classes. We present a greedy strategy, called GREEDYMI, that uses estimates of mutual information from cascade simulations and thus can be applied on any network and disease model. We find that GREEDYMI does better than natural baselines in terms of maximizing the mutual information as well as reducing the expected variance in outbreak size, under the IC model. 

Abstract Allocating students to schools or universities, people to teams or groups, people to urban housing, and matching users on social platforms are prominent examples of allocating limited goods, spaces, or positions to optimize social welfare. We study a welfare maximization problem that arises when such resource allocation scenarios involve peer effects, where people have preferences over the others who are nearby (e.g. their classmates, teammates, neighbors, or partners). We first develop a unified mathematical framework for this “position allocation problem,” which assigns people to positions in a given network, with people caring about both their positions and their neighbors’ attributes. We show that welfare maximization for the corresponding position allocation problem is computationally intractable, even when people have preferences that depend only on who is allocated to nearby positions, and those preferences satisfy simple constraints that arise naturally in urban and other real-world systems. In contrast to this computational lower bound, we show that if people can be classified into a fixed number of (demographic) groups and the network satisfies certain realistic spatial conditions, then efficiently computable allocations can be obtained for many natural scenarios. Importantly, the achieved social welfare is either optimal or arbitrarily close to optimal for natural forms of preferences. Our methods provide a foundation for position allocation with peer effects, and guide the design of optimal allocation strategies when people can be classified into a fixed number of groups in which members share similar preferences. 

Researchers have modeled contagion processes on social networks for wide ranging applications, including spreading of epidemics, financial defaults, actions such as joining social media sites, and rumors. So, too, researchers have developed a host of intervention methods to control harmful contagions on networks; among these approaches are node and edge removal, separating network communities, altering contagion properties, and introducing a second competing contagion. In this work, minimum dominating sets are used to identify blocking nodes—nodes that do not contract a contagion and therefore also do not assist in transmitting it. A novel, generalized method that utilizes integer linear programming to determine exact minimum dominating sets (which is an NP-hard problem) has been developed for a subgraph of any social network for any combination of covering distance and coverage requirement. Three social networks are used to understand and evaluate (i) the method itself and (ii) the efficacy of the blocking nodes that the method produces to stop contagion spread. 

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. 

Evolutionary anti-coordination games on networks capture real-world strategic situations such as traffic routing and market competition. Two key problems concerning evolutionary games are the existence of a pure Nash equilibrium (NE) and the convergence time. In this work, we study these two problems for anti-coordination games under sequential and synchronous update schemes. For each update scheme, we examine two decision modes based on whether an agent considers its own previous action (self essential) or not (self non-essential) in choosing its next action. Using a relationship between games and dynamical systems, we show that for both update schemes, finding an NE can be done efficiently under the self non-essential mode but is computationally intractable under the self essential mode. We then identify special cases for which an NE can be obtained efficiently. For convergence time, we show that the dynamics converges in a polynomial number of steps under the synchronous scheme; for the sequential scheme, the convergence time is polynomial only under the self non-essential mode. Through experiments, we empirically examine the convergence time and the equilibria for both synthetic and real-world networks.