BZPEERPapers, people, evidence and research paths
Menu

Discover

SearchFind papers, people, topics, institutions and opportunities from one place.GraphSee how papers, authors, topics and evidence connect.

Research tools

HomeContinue from the papers, people and topics that matter now.CollectionsTurn saved papers into reading lists, evidence maps and shareable context.ResearchReconstruct the path that led you from search to paper to question.CollaborationMove from a paper, topic or expert request into a focused thread.PublishCreate full-text research articles with metadata, formulas and versions.

Network

ExpertsFind specialists whose work and reviews explain why they can help.CommunitiesJoin research groups organized around papers, topics and shared evidence.

Opportunities

ListingsBrowse roles, calls and collaborations connected to real research context.

Account

Log inReturn to your saved papers, graph views and active threads.Create accountStart saving papers, building a research trail and joining teams.
Log inCreate account

Source author record

V. S. Subrahmanian

V. S. Subrahmanian appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record
Artificial IntelligenceSocial and Information NetworksData Structures and Algorithmsphysics.soc-phDatabasesDiscrete MathematicsLogic in Computer ScienceMachine Learning

Catalog footprint

What is connected

8works
8topics
4close collaborators

Actions

Connect this record

Log in to claim
Open graphBrowse works

Research graph

See the researcher in context

Open full explorer

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Published work

8 published item(s)

preprint2020arXiv

BB_Evac: Fast Location-Sensitive Behavior-Based Building Evacuation

Past work on evacuation planning assumes that evacuees will follow instructions -- however, there is ample evidence that this is not the case. While some people will follow instructions, others will follow their own desires. In this paper, we present a formal definition of a behavior-based evacuation problem (BBEP) in which a human behavior model is taken into account when planning an evacuation. We show that a specific form of constraints can be used to express such behaviors. We show that BBEPs can be solved exactly via an integer program called BB_IP, and inexactly by a much faster algorithm that we call BB_Evac. We conducted a detailed experimental evaluation of both algorithms applied to buildings (though in principle the algorithms can be applied to any graphs) and show that the latter is an order of magnitude faster than BB_IP while producing results that are almost as good on one real-world building graph and as well as on several synthetically generated graphs.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

ChoiceGAPs: Competitive Diffusion as a Massive Multi-Player Game in Social Networks

We consider the problem of modeling competitive diffusion in real world social networks via the notion of ChoiceGAPs which combine choice logic programs due to Sacca` and Zaniolo and Generalized Annotated Programs due to Kifer and Subrahmanian. We assume that each vertex in a social network is a player in a multi-player game (with a huge number of players) - the choice part of the ChoiceGAPs describe utilities of players for acting in various ways based on utilities of their neighbors in those and other situations. We define multi-player Nash equilibrium for such programs - but because they require some conditions that are hard to satisfy in the real world, we introduce a new model-theoretic concept of strong equilibrium. We show that stable equilibria can capture all Nash equilibria. We prove a host of complexity (intractability) results for checking existence of strong equilibria (as well as related counting complexity results), together with algorithms to find them. We then identify a class of ChoiceGAPs for which stable equilibria can be polynomially computed. We develop algorithms for computing these equilibria under various restrictions. We come up with the important concept of an estimation query which can compute quantities w.r.t. a given strong equilibrium, and approximate ranges of values (answers) across the space of strong equilibria. Even though we show that computing range answers to estimation queries exactly is intractable, we are able to identify classes of estimation queries that can be answered in polynomial time. We report on experiments we conducted with a real-world FaceBook data set surrounding the 2013 Italian election showing that our algorithms have good predictive accuracy with an Area Under a ROC Curve that, on average, is over 0.76.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Ensemble-Based Algorithms to Detect Disjoint and Overlapping Communities in Networks

Given a set ${\cal AL}$ of community detection algorithms and a graph $G$ as inputs, we propose two ensemble methods $\mathtt{EnDisCO}$ and $\mathtt{MeDOC}$ that (respectively) identify disjoint and overlapping communities in $G$. $\mathtt{EnDisCO}$ transforms a graph into a latent feature space by leveraging multiple base solutions and discovers disjoint community structure. $\mathtt{MeDOC}$ groups similar base communities into a meta-community and detects both disjoint and overlapping community structures. Experiments are conducted at different scales on both synthetically generated networks as well as on several real-world networks for which the underlying ground-truth community structure is available. Our extensive experiments show that both algorithms outperform state-of-the-art non-ensemble algorithms by a significant margin. Moreover, we compare $\mathtt{EnDisCO}$ and $\mathtt{MeDOC}$ with a recent ensemble method for disjoint community detection and show that our approaches achieve superior performance. To the best of our knowledge, $\mathtt{MeDOC}$ is the first ensemble approach for overlapping community detection.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

VEWS: A Wikipedia Vandal Early Warning System

We study the problem of detecting vandals on Wikipedia before any human or known vandalism detection system reports flagging potential vandals so that such users can be presented early to Wikipedia administrators. We leverage multiple classical ML approaches, but develop 3 novel sets of features. Our Wikipedia Vandal Behavior (WVB) approach uses a novel set of user editing patterns as features to classify some users as vandals. Our Wikipedia Transition Probability Matrix (WTPM) approach uses a set of features derived from a transition probability matrix and then reduces it via a neural net auto-encoder to classify some users as vandals. The VEWS approach merges the previous two approaches. Without using any information (e.g. reverts) provided by other users, these algorithms each have over 85% classification accuracy. Moreover, when temporal recency is considered, accuracy goes to almost 90%. We carry out detailed experiments on a new data set we have created consisting of about 33K Wikipedia users (including both a black list and a white list of editors) and containing 770K edits. We describe specific behaviors that distinguish between vandals and non-vandals. We show that VEWS beats ClueBot NG and STiki, the best known algorithms today for vandalism detection. Moreover, VEWS detects far more vandals than ClueBot NG and on average, detects them 2.39 edits before ClueBot NG when both detect the vandal. However, we show that the combination of VEWS and ClueBot NG can give a fully automated vandal early warning system with even higher accuracy.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Empirical Probabilities in Monadic Deductive Databases

We address the problem of supporting empirical probabilities in monadic logic databases. Though the semantics of multivalued logic programs has been studied extensively, the treatment of probabilities as results of statistical findings has not been studied in logic programming/deductive databases. We develop a model-theoretic characterization of logic databases that facilitates such a treatment. We present an algorithm for checking consistency of such databases and prove its total correctness. We develop a sound and complete query processing procedure for handling queries to such databases.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Geospatial Optimization Problems

There are numerous applications which require the ability to take certain actions (e.g. distribute money, medicines, people etc.) over a geographic region. A disaster relief organization must allocate people and supplies to parts of a region after a disaster. A public health organization must allocate limited vaccine to people across a region. In both cases, the organization is trying to optimize something (e.g. minimize expected number of people with a disease). We introduce "geospatial optimization problems" (GOPs) where an organization has limited resources and budget to take actions in a geographic area. The actions result in one or more properties changing for one or more locations. There are also certain constraints on the combinations of actions that can be taken. We study two types of GOPs - goal-based and benefit-maximizing (GBGOP and BMGOP respectively). A GBGOP ensures that certain properties must be true at specified locations after the actions are taken while a BMGOP optimizes a linear benefit function. We show both problems to be NP-hard (with membership in NP for the associated decision problems). Additionally, we prove limits on approximation for both problems. We present integer programs for both GOPs that provide exact solutions. We also correctly reduce the number of variables in for the GBGOP integer constraints. For BMGOP, we present the BMGOP-Compute algorithm that runs in PTIME and provides a reasonable approximation guarantee in most cases.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Hybrid Probabilistic Programs: Algorithms and Complexity

Hybrid Probabilistic Programs (HPPs) are logic programs that allow the programmer to explicitly encode his knowledge of the dependencies between events being described in the program. In this paper, we classify HPPs into three classes called HPP_1,HPP_2 and HPP_r,r>= 3. For these classes, we provide three types of results for HPPs. First, we develop algorithms to compute the set of all ground consequences of an HPP. Then we provide algorithms and complexity results for the problems of entailment ("Given an HPP P and a query Q as input, is Q a logical consequence of P?") and consistency ("Given an HPP P as input, is P consistent?"). Our results provide a fine characterization of when polynomial algorithms exist for the above problems, and when these problems become intractable.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Non-monotonic Negation in Probabilistic Deductive Databases

In this paper we study the uses and the semantics of non-monotonic negation in probabilistic deductive data bases. Based on the stable semantics for classical logic programming, we introduce the notion of stable formula, functions. We show that stable formula, functions are minimal fixpoints of operators associated with probabilistic deductive databases with negation. Furthermore, since a. probabilistic deductive database may not necessarily have a stable formula function, we provide a stable class semantics for such databases. Finally, we demonstrate that the proposed semantics can handle default reasoning naturally in the context of probabilistic deduction.

0 citations0 reviewsNo code linkedOpen access