DocumentCode :
655213
Title :
Adaptive Seeding in Social Networks
Author :
Seeman, Lior ; Singer, Yaron
Author_Institution :
Dept. of Comput. Sci., Cornell Univ., Ithaca, NY, USA
fYear :
2013
fDate :
26-29 Oct. 2013
Firstpage :
459
Lastpage :
468
Abstract :
The algorithmic challenge of maximizing information diffusion through word-of-mouth processes in social networks has been heavily studied in the past decade. While there has been immense progress and an impressive arsenal of techniques has been developed, the algorithmic frameworks make idealized assumptions regarding access to the network that can often result in poor performance of state-of-the-art techniques. In this paper we introduce a new framework which we call Adaptive Seeding. The framework is a two-stage stochastic optimization model designed to leverage the potential that typically lies in neighboring nodes of arbitrary samples of social networks. Our main result is an algorithm which provides a constant factor approximation to the optimal adaptive policy for any influence function in the Triggering model.
Keywords :
social networking (online); stochastic programming; adaptive seeding; algorithmic framework; constant factor approximation; influence function; information diffusion; optimal adaptive policy; social networks; triggering model; two-stage stochastic optimization model; word-of-mouth process; Adaptation models; Algorithm design and analysis; Approximation algorithms; Approximation methods; Optimization; Social network services; Stochastic processes; approximation algorithms; influence maximization; social networks; stochastic optimization; submodularity;
fLanguage :
English
Publisher :
ieee
Conference_Titel :
Foundations of Computer Science (FOCS), 2013 IEEE 54th Annual Symposium on
Conference_Location :
Berkeley, CA
ISSN :
0272-5428
Type :
conf
DOI :
10.1109/FOCS.2013.56
Filename :
6686182
Link To Document :
بازگشت