Anshul Sawant
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Previous Organizations / Institutes
The organizations / institutes from the scholar's other articles in the past ten years
Anshul Sawant has a total of 7 co-authors. Here are the top co-authors by number of shared publications:
- MohammadTaghi Hajiaghayi
University of Maryland, College Park, USA
2 shared publications - David L. Malec
University of Maryland College Park MD USA
1 shared publication - Erik D. Demaine
Computer Science and Artificial Intelligence Laboratory, MIT, Cambridge, MA, USA
1 shared publication - Hamid Mahini
Department of Computer Science, University of Maryland
1 shared publication - Hamid Mahini
Department of Computer Science Univeristy of Maryland dehghani
1 shared publication - Morteza Zadimoghaddam
MIT Cambridge MA USA
1 shared publication
Latest Publications
- Open Access
How to Influence People with Partial Incentives
We study the power of fractional allocations of resources to maximize influence in a network. This work extends in a natural way the well-studied model by Kempe, Kleinberg, and Tardos (2003), where a designer selects a (small) seed set of nodes in a social network to influence directly, this influence cascades when other nodes reach certain thresholds of neighbor influence, and the goal is to maximize the final number of influenced nodes. Despite extensive study from both practical and theoretical viewpoints, this model limits the designer to a binary choice for each node, with no way to apply intermediate levels of influence. This model captures some settings precisely, e.g. exposure to an idea or pathogen, but it fails to capture very relevant concerns in others, for example, a manufacturer promoting a new product by distributing five "20% off" coupons instead of giving away one free product. While fractional versions of problems tend to be easier to solve than integral versions, for influence maximization, we show that the two versions have essentially the same computational complexity. On the other hand, the two versions can have vastly different solutions: the added flexibility of fractional allocation can lead to significantly improved influence. Our main theoretical contribution is to show how to adapt the major positive results from the integral case to the fractional case. Specifically, Mossel and Roch (2006) used the submodularity of influence to obtain their integral results; we introduce a new notion of continuous submodularity, and use this to obtain matching fractional results. We conclude that we can achieve the same greedy $(1-1/e-\epsilon)$-approximation for the fractional case as the integral case. In practice, we find that the fractional model performs substantially better than the integral model, according to simulations on real-world social network data.
Open AccessHow to Influence People with Partial Incentives
We study the power of fractional allocations of resources to maximize influence in a network. This work extends in a natural way the well-studied model by Kempe, Kleinberg, and Tardos (2003), where a designer selects a (small) seed set of nodes in a social network to influence directly, this influence cascades when other nodes reach certain thresholds of neighbor influence, and the goal is to maximize the final number of influenced nodes. Despite extensive study from both practical and theoretical viewpoints, this model limits the designer to a binary choice for each node, with no way to apply intermediate levels of influence. This model captures some settings precisely, e.g. exposure to an idea or pathogen, but it fails to capture very relevant concerns in others, for example, a manufacturer promoting a new product by distributing five "20% off" coupons instead of giving away one free product. While fractional versions of problems tend to be easier to solve than integral versions, for influence maximization, we show that the two versions have essentially the same computational complexity. On the other hand, the two versions can have vastly different solutions: the added flexibility of fractional allocation can lead to significantly improved influence. Our main theoretical contribution is to show how to adapt the major positive results from the integral case to the fractional case. Specifically, Mossel and Roch (2006) used the submodularity of influence to obtain their integral results; we introduce a new notion of continuous submodularity, and use this to obtain matching fractional results. We conclude that we can achieve the same greedy $(1-1/e-\epsilon)$-approximation for the fractional case as the integral case. In practice, we find that the fractional model performs substantially better than the integral model, according to simulations on real-world social network data.
- Open Access
Scheduling a Cascade with Opposing Influences
Adoption or rejection of ideas, products, and technologies in a society is often governed by simultaneous propagation of positive and negative influences. Consider a planner trying to introduce an idea in different parts of a society at different times. How should the planner design a schedule considering this fact that positive reaction to the idea in early areas has a positive impact on probability of success in later areas, whereas a flopped reaction has exactly the opposite impact? We generalize a well-known economic model which has been recently used by Chierichetti, Kleinberg, and Panconesi (ACM EC'12). In this model the reaction of each area is determined by its initial preference and the reaction of early areas. We generalize previous works by studying the problem when people in different areas have various behaviors. We first prove, independent of the planner's schedule, influences help (resp., hurt) the planner to propagate her idea if it is an appealing (resp., unappealing) idea. We also study the problem of designing the optimal non-adaptive spreading strategy. In the non-adaptive spreading strategy, the schedule is fixed at the beginning and is never changed. Whereas, in adaptive spreading strategy the planner decides about the next move based on the current state of the cascade. We demonstrate that it is hard to propose a non-adaptive spreading strategy in general. Nevertheless, we propose an algorithm to find the best non-adaptive spreading strategy when probabilities of different behaviors of people in various areas drawn i.i.d from an unknown distribution. Then, we consider the influence propagation phenomenon when the underlying influence network can be any arbitrary graph. We show it is $\#P$-complete to compute the expected number of adopters for a given spreading strategy.
Open AccessScheduling a Cascade with Opposing Influences
Adoption or rejection of ideas, products, and technologies in a society is often governed by simultaneous propagation of positive and negative influences. Consider a planner trying to introduce an idea in different parts of a society at different times. How should the planner design a schedule considering this fact that positive reaction to the idea in early areas has a positive impact on probability of success in later areas, whereas a flopped reaction has exactly the opposite impact? We generalize a well-known economic model which has been recently used by Chierichetti, Kleinberg, and Panconesi (ACM EC'12). In this model the reaction of each area is determined by its initial preference and the reaction of early areas. We generalize previous works by studying the problem when people in different areas have various behaviors. We first prove, independent of the planner's schedule, influences help (resp., hurt) the planner to propagate her idea if it is an appealing (resp., unappealing) idea. We also study the problem of designing the optimal non-adaptive spreading strategy. In the non-adaptive spreading strategy, the schedule is fixed at the beginning and is never changed. Whereas, in adaptive spreading strategy the planner decides about the next move based on the current state of the cascade. We demonstrate that it is hard to propose a non-adaptive spreading strategy in general. Nevertheless, we propose an algorithm to find the best non-adaptive spreading strategy when probabilities of different behaviors of people in various areas drawn i.i.d from an unknown distribution. Then, we consider the influence propagation phenomenon when the underlying influence network can be any arbitrary graph. We show it is $\#P$-complete to compute the expected number of adopters for a given spreading strategy.