NDLI: On the Approximability of Influence in Social Networks

Content Provider	Society for Industrial and Applied Mathematics (SIAM)
Author	Chen, Ning
Copyright Year	2009
Abstract	In this paper, we study the spread of influence through a social network in a model initiated by Kempe, Kleinberg, and Tardos [Maximizing the spread of influence through a social network, in Proceedings of the 9th ACM SIGKIDD International Conference, Washington, D.C., 2003, pp. 137146], [Influential nodes in a diffusion model for social networks, in Proceedings of the 32nd International Colloquium on Automata, Languages, and Programming (ICALP), Lisbon, Portugal, CITI, 2005, pp. 11271138]: Given a graph modeling a social network, where each node v has a (fixed) threshold $t_v$, the node will adopt a new product if $t_v$ of its neighbors adopt it. Our goal is to find a small set S of nodes such that targeting the product to S would lead to adoption of the product by a large number of nodes in the graph. We show strong inapproximability results for several variants of this problem. Our main result says that the problem of minimizing the size of S, while ensuring that targeting S would influence the whole network into adopting the product, is hard to approximate within a polylogarithmic factor. This implies a similar result if only a fixed fraction of the network is ensured to adopt the product. Further, the hardness of approximation result continues to hold when all nodes have majority thresholds or have constant degrees and thresholds two. The latter answers a complexity question proposed in [P. A. Dreyer, Applications and Variations of Domination in Graphs, Ph.D. thesis, Rutgers University, Piscataway, NJ, 2000], [F. S. Roberts, Graph-theoretical problems arising from defending against bioterrorism and controlling the spread of fires, in Proceedings of DIMACS/DIMATIA/Renyi Combinatorial Challenges Conference, Piscataway, NJ, 2006]. When the underlying graph is a tree, we give a polynomial-time algorithm to find an optimal solution.
Starting Page	1400
Ending Page	1415
Page Count	16
File Format	PDF
ISSN	08954801
DOI	10.1137/08073617X
e-ISSN	10957146
Journal	SIAM Journal on Discrete Mathematics (SJDMEC)
Issue Number	3
Volume Number	23
Language	English
Publisher	Society for Industrial and Applied Mathematics
Publisher Date	2009-09-23
Access Restriction	Subscribed
Subject Keyword	social networks Social networks General approximability
Content Type	Text
Resource Type	Article
Subject	Mathematics

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

On the approximability of influence in social networks

Parameterized Approximability of Influence in Social Networks

Approximability of Adaptive Seeding under Knapsack Constraints

Parameterized approximability of maximizing the spread of influence in networks (2012)

A new method for maximizing influence on social networks based on node membership in communities

On the approximability of positive influence dominating set in social networks

Parameterized Approximability of Maximizing the Spread of Influence in Networks

Parameterized Approximability of Maximizing the Spread of Influence in Networks (2014)

Parameterized approximability of influence in social networks (2013)

On the Approximability of Influence in Social Networks

Similar Documents

On the approximability of influence in social networks

Parameterized Approximability of Influence in Social Networks

Approximability of Adaptive Seeding under Knapsack Constraints

Parameterized approximability of maximizing the spread of influence in networks (2012)

A new method for maximizing influence on social networks based on node membership in communities

On the approximability of positive influence dominating set in social networks

Parameterized Approximability of Maximizing the Spread of Influence in Networks

Parameterized Approximability of Maximizing the Spread of Influence in Networks (2014)

Parameterized approximability of influence in social networks (2013)

On the Approximability of Influence in Social Networks