Search NASA⌕ Search

Engineering topics

Vullikanti, Anil

Publications and source records attributed to Vullikanti, Anil.

Faster approximate subgraph counts with privacy

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

Nguyen, Dung↗

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

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.

Sambaturu, Prathyush↗

Detection of Spatiotemporal Prescription Opioid Hot Spots With Network Scan Statistics: Multistate Analysis

Background: Overuse and misuse of prescription opioids have become significant public health burdens in the United States. About 11.5 million people are estimated to have misused prescription opioids for nonmedical purposes in 2016. This has led to a significant number of drug overdose deaths in the United States. Previous studies have examined spatiotemporal clusters of opioid misuse, but they have been restricted to circular shaped regions. Objective: The goal of this study was to identify spatiotemporal hot spots of opioid users and opioid prescription claims using Medicare data. Methods: We examined spatiotemporal clusters with significantly higher number of beneficiaries and rate of prescriptions for opioids using Medicare payment data from the Centers for Medicare & Medicaid Services. We used network scan statistics to detect significant clusters with arbitrary shapes, the Kulldorff scan statistic to examine the significant clusters for each year (2013, 2014, and 2015) and an expectation-based version to examine the significant clusters relative to past years. Regression analysis was used to characterize the demographics of the counties that are a part of any significant cluster, and data mining techniques were used to discover the specialties of the anomalous providers. Results: We examined anomalous spatial clusters with respect to opioid prescription claims and beneficiary counts and found some common patterns across states: the counties in the most anomalous clusters were fairly stable in 2014 and 2015, but they have shrunk from 2013. In Virginia, a higher percentage of African Americans in a county lower the odds of the county being anomalous in terms of opioid beneficiary counts to about 0.96 in 2015. For opioid prescription claim counts, the odds were 0.92. This pattern was consistent across the 3 states and across the 3 years. A higher number of people in the county with access to Medicaid increased the odds of the county being in the anomalous cluster to 1.16 in both types of counts in Virginia. A higher number of people with access to direct purchase of insurance plans decreased the odds of a county being in an anomalous cluster to 0.85. The expectation-based scan statistic, which captures change over time, revealed different clusters than the Kulldorff statistic. Providers with an unusually high number of opioid beneficiaries and opioid claims include specialties such as physician’s assistant, nurse practitioner, and family practice. Conclusions: Our analysis of the Medicare claims data provides characteristics of the counties and provider specialties that have higher odds of being anomalous. The empirical analysis identifies highly refined spatial hot spots that are likely to encounter prescription opioid misuse and overdose. The methodology is generic and can be applied to monitor providers and their prescription behaviors in regions that are at a high risk of abuse.

60 APPLIED LIFE SCIENCES↗

Near-Optimal and Practical Algorithms for Graph Scan Statistics with Connectivity Constraints

One fundamental task in network analysis is detecting “hotspots” or “anomalies” in the network; that is, detecting subgraphs where there is significantly more activity than one would expect given historical data or some baseline process. Scan statistics is one popular approach used for anomalous subgraph detection. This methodology involves maximizing a score function over all connected subgraphs, which is a challenging computational problem. A number of heuristics have been proposed for these problems, but they do not provide any quality guarantees. Here, we propose a framework for designing algorithms for optimizing a large class of scan statistics for networks, subject to connectivity constraints. Our algorithms run in time that scales linearly on the size of the graph and depends on a parameter we call the “effective solution size,” while providing rigorous approximation guarantees. In contrast, most prior methods have super-linear running times in terms of graph size. Extensive empirical evidence demonstrates the effectiveness and efficiency of our proposed algorithms in comparison with state-of-the-art methods. Our approach improves on the performance relative to all prior methods, giving up to over 25% increase in the score. Further, our algorithms scale to networks with up to a million nodes, which is 1–2 orders of magnitude larger than all prior applications.

97 MATHEMATICS AND COMPUTING↗

Data-driven efficient network and surveillance-based immunization

Given a contact network and coarse-grained diagnostic information such as electronic Healthcare Reimbursement Claims (eHRC) data, can we develop efficient intervention policies from data to control an epidemic? Immunization is an important problem in multiple areas, especially epidemiology and public health. However, most existing studies rely on assuming prior epidemiological models to develop pre-emptive strategies, which may fail to adapt to the change in new epidemiological patterns and the availability of rich data such as eHRC. In practice, disease spread is usually complicated, hence assuming an underlying model may deviate from true spreading patterns, leading to possibly inaccurate interventions. Additionally, the abundance of health care surveillance data (such as eHRC) makes it possible to study data-driven strategies without too many restrictive assumptions. Therefore, such a data-driven intervention approach can help public-health experts take more practical decisions. In this work, we take into account propagation log and contact networks for controlling propagation. Furthermore, different from previous model-based approaches, our solutions are solely data driven in a sense that we develop immunization strategies directly from the network and eHRC without assuming classical epidemiological models. In particular, we formulate the novel and challenging data-driven immunization problem. To solve it, we first propose an efficient sampling approach to align surveillance data with contact networks, then develop an efficient algorithm with the provably approximate guarantee for immunization. Finally, we show the effectiveness and scalability of our methods via extensive experiments on multiple datasets, and conduct case studies on nation-wide real medical surveillance data.

60 APPLIED LIFE SCIENCES↗