NDLI: An exact almost optimal algorithm for target set selection in social networks

Please wait, while we are loading the content...

On the complexity of nash dynamics and sink equilibria

Limited and online supply and the bayesian foundations of prior-free mechanism design

Characterizing truthful multi-armed bandit mechanisms: extended abstract

Eliciting truthful answers to multiple-choice questions

Optimal collusion-resistant mechanisms with verification

Approximate mechanism design without money

Managing the quality of CPC traffic

Information aggregation in dynamic markets with strategic traders

The price of uncertainty

Social influence and the diffusion of user-created content

On representing coalitional games with externalities

Computational analysis of perfect-information position auctions

Self-correcting sampling-based dynamic multi-unit auctions

Crowdsourcing and all-pay auctions

But who will monitor the monitor?

On random sampling auctions for digital goods

Simple versus optimal mechanisms

A unified framework for dynamic pari-mutuel information market design

Policy teaching through reward function learning

Social lending

Pricing traffic in a spanning network

Selling ad campaigns: online algorithms with cancellations

The price of truthfulness for pay-per-click auctions

Designing incentives for online question and answer forums

Network bargaining: algorithms and structural results

A qualitative vickrey auction

Efficiency of (revenue-)optimal mechanisms

Collective revelation: a mechanism for self-verified, weighted, and truthful predictions

The price of anarchy in bertrand games

Sybilproof transitive trust protocols

A new perspective on implementation by voting trees

The adwords problem: online keyword matching with budgeted bidders under random permutations

Bayes-nash equilibria of the generalized second price auction

Substitutes or complements: another step forward in recommendations

An optimal lower bound for anonymous scheduling mechanisms

Destroy to save

Revenue submodularity

Modeling volatility in prediction markets

On the price of mediation

An exact almost optimal algorithm for target set selection in social networks

Content Provider	ACM Digital Library
Author	Newman, Ilan Ben-Zwi, Oren Hermelin, Danny Lokshtanov, Daniel
Abstract	The Target Set Selection problem proposed by Kempe, Kleinberg, and Tardos, gives a nice clean combinatorial formulation for many problems arising in economy, sociology, and medicine. Its input is a graph with vertex thresholds, the social network, and the goal is to find a subset of vertices, the target set, that "activates" a prespecified number of vertices in the graph. Activation of a vertex is defined via a so-called activation process as follows: Initially, all vertices in the target set become active. Then at each step i of the process, each vertex gets activated if the number of its active neighbors at iteration i -- 1 exceeds its threshold. The activation process is "monotone" in the sense that once a vertex is activated, it remains active for the entire process. Unsurprisingly perhaps, Target Set Selection is NPC. More surprising is the fact that both of its maximization and minimization variants turn out to be extremely hard to approximate, even for very restrictive special cases. The only known case for which the problem is known to have some sort of acceptable worst-case solution is the case where the given social network is a tree and the problem becomes polynomial-time solvable. In this paper, we attempt at extending this sparse landscape of tractable instances by considering the treewidth parameter of graphs. This parameter roughly measures the degree of tree-likeness of a given graph, e.g. the treewidth of a tree is 1, and has previously been used to tackle many classical NPhard problems in the literature. Our contribution is twofold: First, we present an algorithm for Target Set Selection running in $n^{O(w)}$ time, for graphs with n vertices and treewidth bounded by w. The algorithm utilizes various combinatorial properties of the problem; drifting somewhat from standard dynamic-programming algorithms for small treewidth graphs. Also, it can be adopted to much more general settings, including the case of directed graphs, weighted edges, and weighted vertices. On the other hand, we also show that it is highly unlikely to find an $n^{O(√w)}$ time algorithm for Target Set Selection, as this would imply a sub-exponential algorithm for all problems in SNPclass. Together with our upper bound result, this shows that the treewidth parameter determines the complexity of Target Set Selection to a large extent, and should be taken into consideration when tackling this problem in any scenario.
Starting Page	355
Ending Page	362
Page Count	8
File Format	PDF
ISBN	9781605584584
DOI	10.1145/1566374.1566424
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	2009-07-06
Publisher Place	New York
Access Restriction	Subscribed
Subject Keyword	Bounded tree-width algorithm Viral marketing Social networks Bounded tree-width lower-bound Target set selection
Content Type	Text
Resource Type	Article

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

An exact almost optimal algorithm for target set selection in social networks.

An exact almost optimal algorithm for target set selection in social networks (extended abstract) (2009).

An exact almost optimal algorithm for target set selection in social networks (2009)

Target Set Selection Problem for Honeycomb Networks

Latency-Bounded Target Set Selection in Social Networks

Exact quantum lower bound for grover’s problem ∗ (810).

Influence Maximization over Large-Scale Social Networks: A Bounded Linear Approach

Minimum-sized influential node set selection for social networks under the independent cascade model

Learning Bounded Tree-width Bayesian Networks using Integer Linear Programming (2014)

An exact almost optimal algorithm for target set selection in social networks

Similar Documents

An exact almost optimal algorithm for target set selection in social networks.

An exact almost optimal algorithm for target set selection in social networks (extended abstract) (2009).

An exact almost optimal algorithm for target set selection in social networks (2009)

Target Set Selection Problem for Honeycomb Networks

Latency-Bounded Target Set Selection in Social Networks

Exact quantum lower bound for grover’s problem ∗ (810).

Influence Maximization over Large-Scale Social Networks: A Bounded Linear Approach

Minimum-sized influential node set selection for social networks under the independent cascade model

Learning Bounded Tree-width Bayesian Networks using Integer Linear Programming (2014)

An exact almost optimal algorithm for target set selection in social networks