Arrow Research search

Author name cluster

Anil Vullikanti

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

35 papers
1 author row

Possible papers

35

TMLR Journal 2026 Journal Article

Differentially Private and Scalable Estimation of the Network Principal Component

  • Alireza Khayatian
  • Anil Vullikanti
  • Aritra Konar

Computing the principal component (PC) of the adjacency matrix of an undirected graph has several applications ranging from identifying key vertices for influence maximization and controlling diffusion processes, to discovering densely interconnected vertex subsets. However, many networked datasets are sensitive, which necessitates private computation of the PC for use in the aforementioned applications. Differential privacy has emerged as the gold standard in privacy-preserving data analysis, but existing DP algorithms for private PC suffer from low accuracy due to large noise injection or high complexity. Motivated by the large gap between the local and global sensitivities of the PC on real-graphs, we consider instance-specific mechanisms for privately computing the PC under edge-DP. These mechanisms guarantee privacy for all datasets, but provide good utility on ``well-behaved'' datasets by injecting smaller amounts of noise. More specifically, we consider the Propose-Test-Release (PTR) framework. Although computationally expensive in general, we design a novel approach for implementing a PTR variant in the same time as computation of a non-private PC, while offering good utility. Our framework tests in a differentially-private manner whether a given graph is ``well-behaved'' or not, and then tests whether its private to release a noisy PC with small noise. As a consequence, this also leads to the first DP algorithm for the Densest-$k$-subgraph problem, a key graph mining primitive. We run our method on diverse real-world networks, with the largest having 3 million vertices, and compare its utility to a pre-existing baseline based on the private power method (PPM). Although PTR requires a slightly larger privacy budget, on average, it achieves a 180-fold improvement in runtime over PPM.

PDF Details

AAAI Conference 2026 Conference Paper

Information Theoretic Optimal Surveillance for Epidemic Prevalence in Networks

  • Ritwick Mishra
  • Abhijin Adiga
  • Madhav Marathe
  • S. S. Ravi
  • Ravi Tandon
  • Anil Vullikanti

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.

PDF Details DOI

AAMAS Conference 2025 Conference Paper

Contrastive Explainable Clustering with Differential Privacy

  • DungXXX Nguyen
  • Ariel Vetzler
  • Sarit Kraus
  • Anil Vullikanti

This paper presents a novel approach to Explainable AI (XAI) that combines contrastive explanations with differential privacy for clustering algorithms. Focusing on k-median and k-means problems, we calculate contrastive explanations as the utility difference between original clustering and clustering with a centroid fixed to a specific data point. This method provides personalized insights into centroid placement. Our key contribution is demonstrating that these differentially private explanations achieve essentially the same utility bounds as non-private explanations. Experiments across various datasets show that our approach offers meaningful, privacy-preserving, and individually relevant explanations without significantly compromising clustering utility. This work advances privacy-aware machine learning by balancing data protection, explanation quality, and personalization in clustering tasks.

PDF

NeurIPS Conference 2025 Conference Paper

Controlling The Spread of Epidemics on Networks with Differential Privacy

  • Dũng Nguyen
  • Aravind Srinivasan
  • Renata Valieva
  • Anil Vullikanti
  • Jiayi Wu

Designing effective strategies for controlling epidemic spread by vaccination is an important question in epidemiology, especially in the early stages when vaccines are limited. This is a challenging question when the contact network is very heterogeneous, and strategies based on controlling network properties, such as the degree and spectral radius, have been shown to be effective. Implementation of such strategies requires detailed information on the contact structure, which might be sensitive in many applications. Our focus here is on choosing effective vaccination strategies when the edges are sensitive and differential privacy guarantees are needed. Our main contributions are $(\varepsilon, \delta)$-differentially private algorithms for designing vaccination strategies by reducing the maximum degree and spectral radius. Our key technique is a private algorithm for the multi-set multi-cover problem, which we use for controlling network properties. We evaluate privacy-utility tradeoffs of our algorithms on multiple synthetic and real-world networks, and show their effectiveness.

PDF Details

AAMAS Conference 2024 Conference Paper

Assessing Fairness of Residential Dynamic Pricing for Electricity using Active Learning with Agent-based Simulation

  • Swapna Thorve
  • Henning Mortveit
  • Anil Vullikanti
  • Madhav Marathe
  • Samarth Swarup

Extreme weather events and fast-paced adoption of green energy technologies have led to new challenges in demand-side management, maintaining grid reliability, and fulfilling variable consumer demands One of the effective ways to address these difficulties is by introducing economic incentives – replacing the flat rate tariffs with dynamic tariffs. However, dynamic pricing schemes need to be designed carefully to consider fairness and benefits for consumers as well as power companies. This paper describes an ML-based simulation framework for exploring two fairness constructs of dynamic pricing for residential electricity with behavioral agent-based models based on social theory combined with active learning. As an example, we simulate behavior adaptations in response to changes in electricity prices to study cost savings through monthly bills and peak demand reduction in synthetic household agents in a Time Of Use (TOU) pricing scheme in Virginia, USA. Further, we can show that there exists a region in the parameter space that corresponds to a fair TOU pricing scheme for both entities: all income-stratified communities and power companies.

PDF

AAAI Conference 2024 Conference Paper

Learning the Topology and Behavior of Discrete Dynamical Systems

  • Zirou Qiu
  • Abhijin Adiga
  • Madhav V. Marathe
  • S. S. Ravi
  • Daniel J. Rosenkrantz
  • Richard E. Stearns
  • Anil Vullikanti

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.

PDF Details DOI

AAMAS Conference 2024 Conference Paper

Strategic Routing and Scheduling for Evacuations

  • Kazi Ashik Islam
  • Da Qi Chen
  • Madhav Marathe
  • Henning Mortveit
  • Samarth Swarup
  • Anil Vullikanti

Evacuation planning is an essential part of disaster management where the goal is to relocate people under imminent danger to safety. Although government authorities often prescribe routes and schedule, evacuees generally behave as self-interested agents and may choose their actions in a selfish manner. It is crucial to understand the degree of inefficiency this can cause to the evacuation process. In this paper, we present a strategic routing and scheduling game (Evacuation Planning Game, epg), where evacuees choose their route and time of departure. We prove that every instance of epg has at least one pure strategy Nash equilibrium. We then present a polynomial time algorithm (Sequential Action Algorithm, saa), for finding equilibria in a given instance. We also provide bounds on how bad an equilibrium state can be compared to a socially optimal state. Finally, we use Harris County of Houston, Texas as our study area and construct a game instance for it. Our results show that, saa can efficiently find equilibria in this instance that have social objective close to the optimal value.

PDF

AAMAS Conference 2023 Conference Paper

Assigning Agents to Increase Network-Based Neighborhood Diversity

  • Zirou Qiu
  • Andrew Yuan
  • Chen Chen
  • Madhav V. Marathe
  • S. S. Ravi
  • Daniel J. Rosenkrantz
  • Richard E. Stearns
  • Anil Vullikanti

Motivated by real-world applications such as the allocation of public housing, we examine the problem of assigning a group of agents to vertices (e. g. , spatial locations) of a network so that the diversity level is maximized. Specifically, agents are of two types (characterized by features), and we measure diversity by the number of agents who have at least one neighbor of a different type. This problem is known to be NP-hard, and we focus on developing approximation algorithms with provable performance guarantees. We first present a local-improvement algorithm for general graphs that provides an approximation factor of 1⇑2. For the special case where the sizes of agent subgroups are similar, we present a randomized approach based on semidefinite programming that yields an approximation factor better than 1⇑2. Further, we show that the problem can be solved efficiently when the underlying graph is treewidth-bounded and obtain a polynomial time approximation scheme (PTAS) for the problem on planar graphs. Lastly, we conduct experiments to evaluate the performance of the proposed algorithms on synthetic and real-world networks.

PDF

JAAMAS Journal 2023 Journal Article

Deploying vaccine distribution sites for improved accessibility and equity to support pandemic response

  • George Z. Li
  • Ann Li
  • Anil Vullikanti

Abstract In response to COVID-19, many countries have mandated social distancing and banned large group gatherings in order to slow down the spread of SARS-CoV-2. These social interventions along with vaccines remain the best way forward to reduce the spread of SARS CoV-2. In order to increase vaccine accessibility, states such as Virginia have deployed mobile vaccination centers to distribute vaccines across the state. When choosing where to place these sites, there are two important factors to take into account: accessibility and equity. We formulate a combinatorial problem that captures these factors and then develop efficient algorithms with theoretical guarantees on both of these aspects. Furthermore, we study the inherent hardness of the problem, and demonstrate strong impossibility results. Finally, we run computational experiments on real-world data to show the efficacy of our methods.

Details DOI

AAAI Conference 2023 Conference Paper

Detecting Sources of Healthcare Associated Infections

  • Hankyu Jang
  • Andrew Fu
  • Jiaming Cui
  • Methun Kamruzzaman
  • B. Aditya Prakash
  • Anil Vullikanti
  • Bijaya Adhikari
  • Sriram V. Pemmaraju

Healthcare acquired infections (HAIs) (e.g., Methicillin-resistant Staphylococcus aureus infection) have complex transmission pathways, spreading not just via direct person-to-person contacts, but also via contaminated surfaces. Prior work in mathematical epidemiology has led to a class of models – which we call load sharing models – that provide a discrete-time, stochastic formalization of HAI-spread on temporal contact networks. The focus of this paper is the source detection problem for the load sharing model. The source detection problem has been studied extensively in SEIR type models, but this prior work does not apply to load sharing models. We show that a natural formulation of the source detection problem for the load sharing model is computationally hard, even to approximate. We then present two alternate formulations that are much more tractable. The tractability of our problems depends crucially on the submodularity of the expected number of infections as a function of the source set. Prior techniques for showing submodularity, such as the "live graph" technique are not applicable for the load sharing model and our key technical contribution is to use a more sophisticated "coupling" technique to show the submodularity result. We propose algorithms for our two problem formulations by extending existing algorithmic results from submodular optimization and combining these with an expectation propagation heuristic for the load sharing model that leads to orders-of-magnitude speedup. We present experimental results on temporal contact networks based on fine-grained EMR data from three different hospitals. Our results on synthetic outbreaks on these networks show that our algorithms outperform baselines by up to 5.97 times. Furthermore, case studies based on hospital outbreaks of Clostridioides difficile infection show that our algorithms identify clinically meaningful sources.

PDF Details DOI

IJCAI Conference 2023 Conference Paper

Differentially Private Partial Set Cover with Applications to Facility Location

  • George Z. Li
  • Dung Nguyen
  • Anil Vullikanti

Set Cover is a fundamental problem in combinatorial optimization which has been studied for many decades due to its various applications across multiple domains. In many of these domains, the input data consists of locations, relationships, and other sensitive information of individuals which may leaked due to the set cover output. Attempts have been made to design privacy-preserving algorithms to solve the Set Cover under privacy constraints. Under differential privacy, it has been proved that the Set Cover problem has strong impossibility results and no explicit forms of the output can be released to the public. In this work, we observe that these hardness results dissolve when we turn to the Partial Set Cover problem, where we only need to cover a ρ ∈ (0, 1) fraction of the elements. We show that this relaxation enables us to avoid the impossibility results, and give the first algorithm which outputs an explicit form of set cover with non-trivial utility guarantees under differential privacy. Using our algorithm as a subroutine, we design a differentially private bicriteria algorithm to solve a recently proposed facility location problem for vaccine distribution which generalizes the k-supplier with outliers. Our analysis shows that relaxing the covering requirement to serve only a ρ ∈ (0, 1) fraction of the population/universe also allows us to circumvent the inherent hardness of k-supplier and give the first non-trivial guarantees.

PDF Details DOI

IJCAI Conference 2023 Conference Paper

Efficient and Equitable Deployment of Mobile Vaccine Distribution Centers

  • Da Qi Chen
  • Ann Li
  • George Z. Li
  • Madhav Marathe
  • Aravind Srinivasan
  • Leonidas Tsepenekas
  • Anil Vullikanti

Vaccines have proven to be extremely effective in preventing the spread of COVID-19 and potentially ending the pandemic. Lack of access caused many people not getting vaccinated early, so states such as Virginia deployed mobile vaccination sites in order to distribute vaccines across the state. Here we study the problem of deciding where these facilities should be placed and moved over time in order to minimize the distance each person needs to travel in order to be vaccinated. Traditional facility location models for this problem fail to incorporate the fact that our facilities are mobile (i. e. , they can move over time). To this end, we instead model vaccine distribution as the Dynamic k-Supplier problem and give the first approximation algorithms for this problem. We then run extensive simulations on real world datasets to show the efficacy of our methods. In particular, we find that natural baselines for Dynamic k-Supplier cannot take advantage of the mobility of the facilities, and perform worse than non-mobile k-Supplier algorithms.

PDF Details DOI

NeurIPS Conference 2023 Conference Paper

Faster approximate subgraph counts with privacy

  • Dung Nguyen
  • Mahantesh Halappanavar
  • Venkatesh Srinivasan
  • Anil Vullikanti

One of the most common problems studied in the context of differential privacy for graph data is counting the number of non-induced embeddings of a subgraph in a given graph. These counts have very high global sensitivity. Therefore, adding noise based on powerful alternative techniques, such as smooth sensitivity and higher-order local sensitivity have been shown to give significantly better accuracy. However, all these alternatives to global sensitivity become computationally very expensive, and to date efficient polynomial time algorithms are known only for few selected subgraphs, such as triangles, $k$-triangles, and $k$-stars. In this paper, we show that good approximations to these sensitivity metrics can be still used to get private algorithms. Using this approach, we much faster algorithms for privately counting the number of triangles in real-world social networks, which can be easily parallelized. We also give a private polynomial time algorithm for counting any constant size subgraph using less noise than the global sensitivity; we show this can be improved significantly for counting paths in special classes of graphs.

PDF Details

AAAI Conference 2023 Conference Paper

Networked Anti-coordination Games Meet Graphical Dynamical Systems: Equilibria and Convergence

  • Zirou Qiu
  • Chen Chen
  • Madhav V. Marathe
  • S. S. Ravi
  • Daniel J. Rosenkrantz
  • Richard E. Stearns
  • Anil Vullikanti

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.

PDF Details DOI

JMLR Journal 2023 Journal Article

PAC-learning for Strategic Classification

  • Ravi Sundaram
  • Anil Vullikanti
  • Haifeng Xu
  • Fan Yao

The study of strategic or adversarial manipulation of testing data to fool a classifier has attracted much recent attention. Most previous works have focused on two extreme situations where any testing data point either is completely adversarial or always equally prefers the positive label. In this paper, we generalize both of these through a unified framework by considering strategic agents with heterogenous preferences, and introduce the notion of strategic VC-dimension (SVC) to capture the PAC-learnability in our general strategic setup. SVC provably generalizes the recent concept of adversarial VC-dimension (AVC) introduced by Cullina et al. (2018). We instantiate our framework for the fundamental strategic linear classification problem. We fully characterize: (1) the statistical learnability of linear classifiers by pinning down its SVC; (2) its computational tractability by pinning down the complexity of the empirical risk minimization problem. Interestingly, the SVC of linear classifiers is always upper bounded by its standard VC-dimension. This characterization also strictly generalizes the AVC bound for linear classifiers in (Cullina et al., 2018). Finally, we briefly investigate the power of randomization in our strategic classification setup. We show that randomization may strictly increase the accuracy in general, but will not help in the special case of adversarial classification with zero-manipulation-cost. [abs] [ pdf ][ bib ] &copy JMLR 2023. ( edit, beta )

PDF Details

AAAI Conference 2023 Conference Paper

Reconstructing an Epidemic Outbreak Using Steiner Connectivity

  • Ritwick Mishra
  • Jack Heavey
  • Gursharn Kaur
  • Abhijin Adiga
  • Anil Vullikanti

Only a subset of infections is actually observed in an outbreak, due to multiple reasons such as asymptomatic cases and under-reporting. Therefore, reconstructing an epidemic cascade given some observed cases is an important step in responding to such an outbreak. A maximum likelihood solution to this problem ( referred to as CascadeMLE ) can be shown to be a variation of the classical Steiner subgraph problem, which connects a subset of observed infections. In contrast to prior works on epidemic reconstruction, which consider the standard Steiner tree objective, we show that a solution to CascadeMLE, based on the actual MLE objective, has a very different structure. We design a logarithmic approximation algorithm for CascadeMLE, and evaluate it on multiple synthetic and social contact networks, including a contact network constructed for a hospital. Our algorithm has significantly better performance compared to a prior baseline.

PDF Details DOI

IJCAI Conference 2023 Conference Paper

Simulation-Assisted Optimization for Large-Scale Evacuation Planning with Congestion-Dependent Delays

  • Kazi Ashik Islam
  • Da Qi Chen
  • Madhav Marathe
  • Henning Mortveit
  • Samarth Swarup
  • Anil Vullikanti

Evacuation planning is a crucial part of disaster management. However, joint optimization of its two essential components, routing and scheduling, with objectives such as minimizing average evacuation time or evacuation completion time, is a computationally hard problem. To approach it, we present MIP-LNS, a scalable optimization method that utilizes heuristic search with mathematical optimization and can optimize a variety of objective functions. We also present the method MIP-LNS-SIM, where we combine agent-based simulation with MIP-LNS to estimate delays due to congestion, as well as, find optimized plans considering such delays. We use Harris County in Houston, Texas, as our study area. We show that, within a given time limit, MIP-LNS finds better solutions than existing methods in terms of three different metrics. However, when congestion dependent delay is considered, MIP-LNS-SIM outperforms MIP-LNS in multiple performance metrics. In addition, MIP-LNS-SIM has a significantly lower percent error in estimated evacuation completion time compared to MIP-LNS.

PDF Details DOI

AAMAS Conference 2023 Conference Paper

Towards Optimal and Scalable Evacuation Planning Using Data-driven Agent Based Models

  • Kazi Ashik Islam
  • Da Qi Chen
  • Madhav Marathe
  • Henning Mortveit
  • Samarth Swarup
  • Anil Vullikanti

Evacuation planning is a crucial part of disaster management where the goal is to relocate people to safety and minimize casualties. Every evacuation plan has two essential components: routing and scheduling. However, joint optimization of these two components with objectives such as minimizing average evacuation time is a computationally hard problem. To approach it, we present MIP- LNS, a scalable optimization method that can optimize a variety of objective functions. We also present the method MIP-LNS-SIM, where we combine agent-based simulation with MIP-LNS to more accurately estimate delays on roads due to congestion. We use Harris County in Houston, Texas as our study area. We show that, within a given time limit, MIP-LNS finds better solutions than existing methods in terms of three different metrics. We also perform experiments with MIP-LNS-SIM to show its efficacy in estimating delays due to congestion. Our results show that, when such delays are considered, MIP-LNS-SIM can find better evacuation plans than MIP-LNS. Furthermore, MIP-LNS-SIM provides an estimate of the evacuation completion time for its plan with a small percent error.

PDF

IJCAI Conference 2022 Conference Paper

A Reliability-aware Distributed Framework to Schedule Residential Charging of Electric Vehicles

  • Rounak Meyur
  • Swapna Thorve
  • Madhav Marathe
  • Anil Vullikanti
  • Samarth Swarup
  • Henning Mortveit

Residential consumers have become active participants in the power distribution network after being equipped with residential EV charging provisions. This creates a challenge for the network operator tasked with dispatching electric power to the residential consumers through the existing distribution network infrastructure in a reliable manner. In this paper, we address the problem of scheduling residential EV charging for multiple consumers while maintaining network reliability. An additional challenge is the restricted exchange of information: where the consumers do not have access to network information and the network operator does not have access to consumer load parameters. We propose a distributed framework which generates an optimal EV charging schedule for individual residential consumers based on their preferences and iteratively updates it until the network reliability constraints set by the operator are satisfied. We validate the proposed approach for different EV adoption levels in a synthetically created digital twin of an actual power distribution network. The results demonstrate that the new approach can achieve a higher level of network reliability compared to the case where residential consumers charge EVs based solely on their individual preferences, thus providing a solution for the existing grid to keep up with increased adoption rates without significant investments in increasing grid capacity.

PDF Details DOI

AAMAS Conference 2022 Conference Paper

Data-driven Agent-based Models for Optimal Evacuation of Large Metropolitan Areas for Improved Disaster Planning

  • Kazi Ashik Islam
  • Madhav Marathe
  • Henning Mortveit
  • Samarth Swarup
  • Anil Vullikanti

Evacuation plans are designed to move people to safety in case of a disaster. It mainly consists of two components: routing and scheduling. Joint optimization of these two components with the goal of minimizing total evacuation time is a computationally hard problem, specifically when the problem instance is large. Moreover, often in disaster situations, there is uncertainty regarding the passability of roads throughout the evacuation time period. In this paper, we present a way to model the time-varying risk associated with roads in disaster situations. We also design a heuristic method based on the well known Large Neighborhood Search framework to perform the joint optimization task. We use real-world road network and population data from Harris County in Houston, Texas and apply our heuristic to find evacuation routes and schedules for the area. We show that the proposed method is able to find good solutions within a reasonable amount of time. We also perform agent-based simulations of the evacuation using these solutions to evaluate their quality and efficacy.

PDF

AAMAS Conference 2022 Conference Paper

Deploying Vaccine Distribution Sites for Improved Accessibility and Equity to Support Pandemic Response

  • George Z. Li
  • Ann Li
  • Madhav Marathe
  • Aravind Srinivasan
  • Leonidas Tsepenekas
  • Anil Vullikanti

In response to COVID-19, many countries have mandated social distancing and banned large group gatherings in order to slow down the spread of SARS-CoV-2. These social interventions along with vaccines remain the best way forward to reduce the spread of SARS CoV-2. In order to increase vaccine accessibility, states such as Virginia have deployed mobile vaccination centers to distribute vaccines across the state. When choosing where to place these sites, there are two important factors to take into account: accessibility and equity. We formulate a combinatorial problem that captures these factors and then develop efficient algorithms with theoretical guarantees on both of these aspects. Furthermore, we study the inherent hardness of the problem, and demonstrate strong impossibility results. Finally, we run computational experiments on real-world data to show the efficacy of our methods.

PDF

AAAI Conference 2022 Conference Paper

Finding Nontrivial Minimum Fixed Points in Discrete Dynamical Systems: Complexity, Special Case Algorithms and Heuristics

  • Zirou Qiu
  • Chen Chen
  • Madhav Marathe
  • S.S. Ravi
  • Daniel J. Rosenkrantz
  • Richard Stearns
  • Anil Vullikanti

Networked discrete dynamical systems are often used to model the spread of contagions and decision-making by agents in coordination games. Fixed points of such dynamical systems represent configurations to which the system converges. In the dissemination of undesirable contagions (such as rumors and misinformation), convergence to fixed points with a small number of affected nodes is a desirable goal. Motivated by such considerations, we formulate a novel optimization problem of finding a nontrivial fixed point of the system with the minimum number of affected nodes. We establish that, unless P = NP, there is no polynomial time algorithm for approximating a solution to this problem to within the factor n1−ϵ for any constant ϵ > 0. To cope with this computational intractability, we identify several special cases for which the problem can be solved efficiently. Further, we introduce an integer linear program to address the problem for networks of reasonable sizes. For solving the problem on larger networks, we propose a general heuristic framework along with greedy selection methods. Extensive experimental results on real-world networks demonstrate the effectiveness of the proposed heuristics. A full version of the manuscript, source code and data are available at: https: //github. com/bridgelessqiu/NMIN-FPE

PDF Details

AAAI Conference 2022 Conference Paper

Provable Sensor Sets for Epidemic Detection over Networks with Minimum Delay

  • Jack Heavey
  • Jiaming Cui
  • Chen Chen
  • B. Aditya Prakash
  • Anil Vullikanti

The efficient detection of outbreaks and other cascading phenomena is a fundamental problem in a number of domains, including disease spread, social networks, and infrastructure networks. In such settings, monitoring and testing a small group of pre-selected nodes from the susceptible population (i. e. , a sensor set) is often the preferred testing regime. We study the problem of selecting a sensor set that minimizes the delay in detection—we refer to this as the MinDelSS problem. Prior methods for minimizing the detection time rely on greedy algorithms using submodularity. We show that this approach can sometimes lead to a worse approximation for minimizing the detection time than desired. We also show that MinDelSS is hard to approximate within an O(n1−1/γ )factor for any constant γ ≥ 2 for a graph with n nodes. This instead motivates seeking a bicriteria approximations. We present the algorithm ROUNDSENSOR, which gives a rigorous worst case O(log n)-factor for the detection time, while violating the budget by a factor of O(log2 n). Our algorithm is based on the sample average approximation technique from stochastic optimization, combined with linear programming and rounding. We evaluate our algorithm on several networks, including hospital contact networks, which validates its effectiveness in real settings.

PDF Details

IJCAI Conference 2022 Conference Paper

Scalable and Memory-Efficient Algorithms for Controlling Networked Epidemic Processes Using Multiplicative Weights Update Method

  • Prathyush Sambaturu
  • Marco Minutoli
  • Mahantesh Halappanavar
  • Ananth Kalyanaraman
  • Anil Vullikanti

We study the problem of designing scalable algorithms to find effective intervention strategies for controlling stochastic epidemic processes on networks. This is a common problem arising in agent based models for epidemic spread. Previous approaches to this problem focus on either heuristics with no guarantees or approximation algorithms that scale only to networks corresponding to county-sized populations, typically, with less than a million nodes. In particular, the mathematical-programming based approaches need to solve the Linear Program (LP) relaxation of the problem using an LP solver, which restricts the scalability of this approach. In this work, we overcome this restriction by designing an algorithm that adapts the multiplicative weights update (MWU) framework, along with the sample average approximation (SAA) technique, to approximately solve the linear program (LP) relaxation for the problem. To scale this approach further, we provide a memory-efficient algorithm that enables scaling to large networks, corresponding to country-size populations, with over 300 million nodes and 30 billion edges. Furthermore, we show that this approach provides near-optimal solutions to the LP in practice.

PDF Details DOI

AAMAS Conference 2022 Conference Paper

Theoretical Models and Preliminary Results for Contact Tracing and Isolation

  • George Z. Li
  • Arash Haddadan
  • Ann Li
  • Madhav V. Marathe
  • Aravind Srinivasan
  • Anil Vullikanti
  • Zeyu Zhao

Efficient contact tracing and isolation is an effective strategy to control epidemics, as seen in the Ebola epidemic and COVID-19 pandemic. An important consideration in contact tracing is the budget on the number of individuals asked to quarantine—the budget is limited for socioeconomic reasons (e. g. , having a limited number of contact tracers). Here, we present a Markov Decision Process (MDP) framework to formulate the problem of using contact tracing to reduce the size of an outbreak while limiting the number of people quarantined. We formulate each step of the MDP as a combinatorial problem, MinExposed, which we demonstrate is NP-Hard. Next, we develop two approximation algorithms, one based on rounding the solutions of a linear program and another (greedy algorithm) based on choosing nodes with a high (weighted) degree. A key feature of the greedy algorithm is that it does not need complete information of the underlying social contact network, making it implementable in practice. Using simulations over realistic networks, we show how the algorithms can help in bending the epidemic curve with a limited number of isolated individuals.

PDF

AAAI Conference 2021 Conference Paper

Persistence of Anti-vaccine Sentiment in Social Networks Through Strategic Interactions

  • A S M Ahsan-Ul Haque
  • Mugdha Thakur
  • Matthew Bielskas
  • Achla Marathe
  • Anil Vullikanti

Vaccination is the primary intervention for controlling the spread of infectious diseases. A certain level of vaccination rate (referred to as “herd immunity”) is needed for this intervention to be effective. However, there are concerns that herd immunity might not be achieved due to an increasing level of hesitancy and opposition to vaccines. One of the primary reasons for this is the cost of non-conformance with one’s peers. We use the framework of network coordination games to study the persistence of anti-vaccine sentiment in a population. We extend it to incorporate the opposing forces of the pressure of conforming to peers, herd-immunity and vaccination benefits. We study the structure of the equilibria in such games, and the characteristics of unvaccinated nodes. We also study Stackelberg strategies to reduce the number of nodes with anti-vaccine sentiment. Finally, we evaluate our results on different kinds of real world social networks.

PDF Details

AAAI Conference 2020 Conference Paper

Bounds and Complexity Results for Learning Coalition-Based Interaction Functions in Networked Social Systems

  • Abhijin Adiga
  • Chris Kuhlman
  • Madhav Marathe
  • S. Ravi
  • Daniel Rosenkranz
  • Richard Stearns
  • Anil Vullikanti

Using a discrete dynamical system model for a networked social system, we consider the problem of learning a class of local interaction functions in such networks. Our focus is on learning local functions which are based on pairwise disjoint coalitions formed from the neighborhood of each node. Our work considers both active query and PAC learning models. We establish bounds on the number of queries needed to learn the local functions under both models. We also establish a complexity result regarding efficient consistent learners for such functions. Our experimental results on synthetic and real social networks demonstrate how the number of queries depends on the structure of the underlying network and number of coalitions.

PDF Details

AAAI Conference 2020 Conference Paper

Efficient Algorithms for Generating Provably Near-Optimal Cluster Descriptors for Explainability

  • Prathyush Sambaturu
  • Aparna Gupta
  • Ian Davidson
  • S. S. Ravi
  • Anil Vullikanti
  • Andrew Warren

Improving the explainability of the results from machine learning methods has become an important research goal. Here, we study the problem of making clusters more interpretable by extending a recent approach of [Davidson et al. , NeurIPS 2018] for constructing succinct representations for clusters. Given a set of objects S, a partition π of S (into clusters), and a universe T of tags such that each element in S is associated with a subset of tags, the goal is to find a representative set of tags for each cluster such that those sets are pairwise-disjoint and the total size of all the representatives is minimized. Since this problem is NP-hard in general, we develop approximation algorithms with provable performance guarantees for the problem. We also show applications to explain clusters from datasets, including clusters of genomic sequences that represent different threat levels.

PDF Details

AAMAS Conference 2018 Conference Paper

Designing Incentives to Maximize the Adoption of Rooftop Solar Technology

  • Aparna Gupta
  • Samarth Swarup
  • Achla Marathe
  • Anil Vullikanti
  • Kiran Lakkaraju
  • Joshua Letchford

Household level rooftop solar technology adoption is rising in many regions, driven by a multitude of factors, including falling prices and incentives such as tax breaks. It has also been shown in recent research that peer effects have an important role in the spread of solar adoption. This leads to a natural problem of how to design incentives to maximize adoption in such a model. While this is an instance of an “influence maximization” problem, prior results from the influence maximization literature cannot be used directly. In this work, we extend prior results from the literature on the use of submodularity to obtain a greedy approximation. We use this new result to do optimal “seed set” selection for a highly detailed, datadriven, agent-based model of household rooftop solar adoption.

PDF

AAAI Conference 2018 Conference Paper

Graph Scan Statistics With Uncertainty

  • Jose Cadena
  • Arinjoy Basak
  • Anil Vullikanti
  • Xinwei Deng

Scan statistics is one of the most popular approaches for anomaly detection in spatial and network data. In practice, there are numerous sources of uncertainty in the observed data. However, most prior works have overlooked such uncertainty, which can affect the accuracy and inferences of such methods. In this paper, we develop the first systematic approach to incorporating uncertainty in scan statistics. We study two formulations for robust scan statistics, one based on the sample average approximation and the other using a max-min objective. We show that uncertainty significantly increases the computational complexity of these problems. Rigorous algorithms and efficient heuristics for both formulations are developed with justification of theoretical bounds. We evaluate our proposed methods on synthetic and real datasets, and we observe that our methods give significant improvement in the detection power as well as optimization objective, relative to a baseline.

PDF Details

AAAI Conference 2018 Conference Paper

Mining Heavy Temporal Subgraphs: Fast Algorithms and Applications

  • Jose Cadena
  • Anil Vullikanti

Anomaly detection is a fundamental problem in dynamic networks. In this paper, we study an approach for identifying anomalous subgraphs based on the Heaviest Dynamic Subgraph (HDS) problem. The HDS in a time-evolving edgeweighted graph consists of a pair containing a subgraph and sub-interval whose sum of edge weights is maximized. The HDS problem in a static graph is equivalent to the Prize Collecting Steiner Tree (PCST) problem with the Net-Worth objective—this is a very challenging problem, in general, and numerous heuristics have been proposed. Prior methods for the HDS problem use the PCST solution as a heuristic, and run in time quadratic in the size of the graph. As a result, they do not scale well to large instances. In this paper, we develop a new approach for the HDS problem, which combines rigorous algorithmic and practical techniques and has much better scalability. Our algorithm is able to extend to other variations of the HDS problem, such as the problem of finding multiple anomalous regions. We evaluate our algorithms in a diverse set of real and synthetic networks, and we find solutions with higher score and better detection power for anomalous events compared to earlier heuristics.

PDF Details

AAAI Conference 2016 Conference Paper

Hospital Stockpiling Problems with Inventory Sharing

  • Eric Lofgren
  • Anil Vullikanti

Hospitals are typically optimized to operate near capacity, and there are serious concerns that our healthcare system is not prepared for the next pandemic. Stockpiles of different supplies, e. g. , personal protective equipments (PPE) and medical equipment, need to be maintained in order to be able to respond to any future pandemics. Large outbreaks occur with a low probability, and such stockpiles require big investments. Further, hospitals often have mutual sharing agreements, which makes the problem of stockpiling decisions a natural game-theoretical problem. In this paper, we formalize hospital stockpiling as a game-theoretical problem, HSTOCKPILE. We use the notion of pairwise Nash stability as a solution concept for this problem, and characterize its structure. We show that stable strategies can lead to high unsatisfied demands in some scenarios, and stockpiles might not be maintained at all nodes. We show that stable strategies and the social optimum can be computed efficiently.

PDF Details

AAAI Conference 2016 Conference Paper

Temporal Vaccination Games under Resource Constraints

  • Abhijin Adiga
  • Anil Vullikanti

The decision to take vaccinations and other protective interventions for avoiding an infection is a natural game-theoretic setting. Most of the work on vaccination games has focused on decisions at the start of an epidemic. However, a lot of people defer their vaccination decisions, in practice. For example, in the case of the seasonal flu, vaccination rates gradually increase, as the epidemic rate increases. This motivates the study of temporal vaccination games, in which vaccination decisions can be made more than once. An important issue in the context of temporal decisions is that of resource limitations, which may arise due to production and distribution constraints. While there has been some work on temporal vaccination games, resource constraints have not been considered. In this paper, we study temporal vaccination games for epidemics in the SI (susceptible-infectious) model, with resource constraints in the form of a repeated game in complex social networks, with budgets on the number of vaccines that can be taken at any time. We find that the resource constraints and the vaccination and infection costs have a significant impact on the structure of Nash equilibria (NE). In general, the budget constraints can cause NE to become very inefficient, and finding efficient NE as well as the social optimum are NP-hard problems. We develop algorithms for finding NE and approximating the social optimum. We evaluate our results using simulations on different kinds of networks.

PDF Details

IS Journal 2015 Journal Article

Model-Based Forecasting of Significant Societal Events

  • Naren Ramakrishnan
  • Chang-Tien Lu
  • Madhav Marathe
  • Achla Marathe
  • Anil Vullikanti
  • Stephen Eubank
  • Scotland Leman
  • Michael Roan

The article outlines some salient aspects of Embers-generated forecasts through its design considerations, system architecture, and user interface.

Details DOI

AAAI Conference 2014 Conference Paper

Equilibria in Epidemic Containment Games

  • Sudip Saha
  • Abhijin Adiga
  • Anil Vullikanti

The spread of epidemics and malware is commonly modeled by diffusion processes on networks. Protective interventions such as vaccinations or installing anti-virus software are used to contain their spread. Typically, each node in the network has to decide its own strategy of securing itself, and its benefit depends on which other nodes are secure, making this a natural game-theoretic setting. There has been a lot of work on network security game models, but most of the focus has been either on simplified epidemic models or homogeneous network structure. We develop a new formulation for an epidemic containment game, which relies on the characterization of the SIS model in terms of the spectral radius of the network. We show in this model that pure Nash equilibria (NE) always exist, and can be found by a best response strategy. We analyze the complexity of finding NE, and derive rigorous bounds on their costs and the Price of Anarchy or PoA (the ratio of the cost of the worst NE to the optimum social cost) in general graphs as well as in random graph models. In particular, for arbitrary power-law graphs with exponent β > 2, we show that the PoA is bounded by O(T2(β−1) ), where T = γ/α is the ratio of the recovery rate to the transmission rate in the SIS model. We prove that this bound is tight up to a constant factor for the Chung-Lu random power-law graph model. We study the characteristics of Nash equilibria empirically in different real communication and infrastructure networks, and find that our analytical results can help explain some of the empirical observations.

PDF Details