diff options
| author | Thibaut Horel <thibaut.horel@gmail.com> | 2014-10-24 12:32:08 -0400 |
|---|---|---|
| committer | Thibaut Horel <thibaut.horel@gmail.com> | 2014-10-24 12:32:08 -0400 |
| commit | 4f7d4804234f5515a4dded8b05d9568653b7ae3c (patch) | |
| tree | 98d3bbb27692a861d602d52d1650e6d60c2b045c /paper/sections | |
| parent | ece1d828d53d6123fcecb5ea8bf9b126d1728ccc (diff) | |
| download | fast-seeding-4f7d4804234f5515a4dded8b05d9568653b7ae3c.tar.gz | |
Add paper
Diffstat (limited to 'paper/sections')
| -rw-r--r-- | paper/sections/abstract.tex | 6 | ||||
| -rw-r--r-- | paper/sections/algorithms.log | 1500 | ||||
| -rw-r--r-- | paper/sections/algorithms.tex | 508 | ||||
| -rw-r--r-- | paper/sections/appendix.tex | 76 | ||||
| -rw-r--r-- | paper/sections/combinatorial.tex | 299 | ||||
| -rw-r--r-- | paper/sections/experiments.log | 0 | ||||
| -rw-r--r-- | paper/sections/experiments.tex | 128 | ||||
| -rw-r--r-- | paper/sections/introduction.log | 0 | ||||
| -rw-r--r-- | paper/sections/introduction.tex | 92 | ||||
| -rw-r--r-- | paper/sections/lp.log | 0 | ||||
| -rw-r--r-- | paper/sections/model.tex | 67 | ||||
| -rw-r--r-- | paper/sections/performance.tex | 1 | ||||
| -rw-r--r-- | paper/sections/related.tex | 9 |
13 files changed, 2686 insertions, 0 deletions
diff --git a/paper/sections/abstract.tex b/paper/sections/abstract.tex new file mode 100644 index 0000000..b166d6a --- /dev/null +++ b/paper/sections/abstract.tex @@ -0,0 +1,6 @@ +In recent years social networking platforms have developed into extraordinary channels for spreading and consuming information. +Along with the rise of such infrastructure, there is continuous progress on techniques for spreading information effectively through influential users. + +In this paper, we describe scalable algorithms for a new method of information diffusion called adaptive seeding. In many applications, one is restricted to select influencers from a set of users who engaged with the topic being promoted, and due to the structure of social networks, these users often rank low in terms of their influence potential. To overcome this hurdle, adaptive seeding aims to select users in a manner which targets their influential neighbors. + +Despite the various complexities involved with the optimization problem, we show that scalable adaptive seeding is achievable. In particular, we develop algorithms for linear influence models with provable approximation guarantees that can be gracefully parallelized. To show the effectiveness of our methods we collected data from various verticals social network users follow. For each vertical, we collected data on the users who responded to a certain post as well as their neighbors, and applied our methods on this data. Our experiments show that adaptive seeding is scalable, and importantly, that it obtains dramatic improvements over standard approaches of information dissemination. diff --git a/paper/sections/algorithms.log b/paper/sections/algorithms.log new file mode 100644 index 0000000..6265672 --- /dev/null +++ b/paper/sections/algorithms.log @@ -0,0 +1,1500 @@ +This is pdfTeX, Version 3.1415926-2.5-1.40.14 (TeX Live 2013) (format=pdflatex 2013.5.30) 19 FEB 2014 20:53 +entering extended mode + restricted \write18 enabled. + file:line:error style messages enabled. + %&-line parsing enabled. +**algorithms.tex +(./algorithms.tex +LaTeX2e <2011/06/27> +Babel <3.9f> and hyphenation patterns for 78 languages loaded. + +./algorithms.tex:4: LaTeX Error: Missing \begin{document}. + +See the LaTeX manual or LaTeX Companion for explanation. +Type H <return> for immediate help. + ... + +l.4 W + e will say that a policy is non-adaptive if it selects a set of nodes $... + +? +Missing character: There is no W in font nullfont! +Missing character: There is no e in font nullfont! +Missing character: There is no w in font nullfont! +Missing character: There is no i in font nullfont! +Missing character: There is no l in font nullfont! +Missing character: There is no l in font nullfont! +Missing character: There is no s in font nullfont! +Missing character: There is no a in font nullfont! +Missing character: There is no y in font nullfont! +Missing character: There is no t in font nullfont! +Missing character: There is no h in font nullfont! +Missing character: There is no a in font nullfont! +Missing character: There is no t in font nullfont! +Missing character: There is no a in font nullfont! +Missing character: There is no p in font nullfont! +Missing character: There is no o in font nullfont! +Missing character: There is no l in font nullfont! +Missing character: There is no i in font nullfont! +Missing character: There is no c in font nullfont! +Missing character: There is no y in font nullfont! +Missing character: There is no i in font nullfont! +Missing character: There is no s in font nullfont! +Missing character: There is no n in font nullfont! +Missing character: There is no o in font nullfont! +Missing character: There is no n in font nullfont! +Missing character: There is no - in font nullfont! +Missing character: There is no a in font nullfont! +Missing character: There is no d in font nullfont! +Missing character: There is no a in font nullfont! +Missing character: There is no p in font nullfont! +Missing character: There is no t in font nullfont! +Missing character: There is no i in font nullfont! +Missing character: There is no v in font nullfont! +Missing character: There is no e in font nullfont! +Missing character: There is no i in font nullfont! +Missing character: There is no f in font nullfont! +Missing character: There is no i in font nullfont! +Missing character: There is no t in font nullfont! +Missing character: There is no s in font nullfont! +Missing character: There is no e in font nullfont! +Missing character: There is no l in font nullfont! +Missing character: There is no e in font nullfont! +Missing character: There is no c in font nullfont! +Missing character: There is no t in font nullfont! +Missing character: There is no s in font nullfont! +Missing character: There is no a in font nullfont! +Missing character: There is no s in font nullfont! +Missing character: There is no e in font nullfont! +Missing character: There is no t in font nullfont! +Missing character: There is no o in font nullfont! +Missing character: There is no f in font nullfont! +Missing character: There is no n in font nullfont! +Missing character: There is no o in font nullfont! +Missing character: There is no d in font nullfont! +Missing character: There is no e in font nullfont! +Missing character: There is no s in font nullfont! +LaTeX Font Info: External font `cmex10' loaded for size +(Font) <7> on input line 4. +LaTeX Font Info: External font `cmex10' loaded for size +(Font) <5> on input line 4. +Missing character: There is no t in font nullfont! +Missing character: There is no o in font nullfont! +Missing character: There is no b in font nullfont! +Missing character: There is no e in font nullfont! +Missing character: There is no s in font nullfont! +Missing character: There is no e in font nullfont! +Missing character: There is no e in font nullfont! +Missing character: There is no d in font nullfont! +Missing character: There is no e in font nullfont! +Missing character: There is no d in font nullfont! +Missing character: There is no i in font nullfont! +Missing character: There is no n in font nullfont! +Missing character: There is no t in font nullfont! +Missing character: There is no h in font nullfont! +Missing character: There is no e in font nullfont! +Missing character: There is no f in font nullfont! +Missing character: There is no i in font nullfont! +Missing character: There is no r in font nullfont! +Missing character: There is no s in font nullfont! +Missing character: There is no t in font nullfont! +Missing character: There is no s in font nullfont! +Missing character: There is no t in font nullfont! +Missing character: There is no a in font nullfont! +Missing character: There is no g in font nullfont! +Missing character: There is no e in font nullfont! +Missing character: There is no a in font nullfont! +Missing character: There is no n in font nullfont! +Missing character: There is no d in font nullfont! +Missing character: There is no a in font nullfont! +Missing character: There is no v in font nullfont! +Missing character: There is no e in font nullfont! +Missing character: There is no c in font nullfont! +Missing character: There is no t in font nullfont! +Missing character: There is no o in font nullfont! +Missing character: There is no r in font nullfont! +Missing character: There is no o in font nullfont! +Missing character: There is no f in font nullfont! +Missing character: There is no p in font nullfont! +Missing character: There is no r in font nullfont! +Missing character: There is no o in font nullfont! +Missing character: There is no b in font nullfont! +Missing character: There is no a in font nullfont! +Missing character: There is no b in font nullfont! +Missing character: There is no i in font nullfont! +Missing character: There is no l in font nullfont! +Missing character: There is no i in font nullfont! +Missing character: There is no t in font nullfont! +Missing character: There is no i in font nullfont! +Missing character: There is no e in font nullfont! +Missing character: There is no s in font nullfont! +Missing character: There is no , in font nullfont! +Missing character: There is no s in font nullfont! +Missing character: There is no . in font nullfont! +Missing character: There is no t in font nullfont! +Missing character: There is no . in font nullfont! +Missing character: There is no e in font nullfont! +Missing character: There is no a in font nullfont! +Missing character: There is no c in font nullfont! +Missing character: There is no h in font nullfont! +Missing character: There is no n in font nullfont! +Missing character: There is no e in font nullfont! +Missing character: There is no i in font nullfont! +Missing character: There is no g in font nullfont! +Missing character: There is no h in font nullfont! +Missing character: There is no b in font nullfont! +Missing character: There is no o in font nullfont! +Missing character: There is no r in font nullfont! +Missing character: There is no o in font nullfont! +Missing character: There is no f in font nullfont! +Missing character: There is no w in font nullfont! +Missing character: There is no h in font nullfont! +Missing character: There is no i in font nullfont! +Missing character: There is no c in font nullfont! +Missing character: There is no h in font nullfont! +Missing character: There is no r in font nullfont! +Missing character: There is no e in font nullfont! +Missing character: There is no a in font nullfont! +Missing character: There is no l in font nullfont! +Missing character: There is no i in font nullfont! +Missing character: There is no z in font nullfont! +Missing character: There is no e in font nullfont! +Missing character: There is no s in font nullfont! +Missing character: There is no i in font nullfont! +Missing character: There is no s in font nullfont! +Missing character: There is no i in font nullfont! +Missing character: There is no n in font nullfont! +Missing character: There is no c in font nullfont! +Missing character: There is no l in font nullfont! +Missing character: There is no u in font nullfont! +Missing character: There is no d in font nullfont! +Missing character: There is no e in font nullfont! +Missing character: There is no d in font nullfont! +Missing character: There is no i in font nullfont! +Missing character: There is no n in font nullfont! +Missing character: There is no t in font nullfont! +Missing character: There is no h in font nullfont! +Missing character: There is no e in font nullfont! +Missing character: There is no s in font nullfont! +Missing character: There is no o in font nullfont! +Missing character: There is no l in font nullfont! +Missing character: There is no u in font nullfont! +Missing character: There is no t in font nullfont! +Missing character: There is no i in font nullfont! +Missing character: There is no o in font nullfont! +Missing character: There is no n in font nullfont! +Missing character: There is no i in font nullfont! +Missing character: There is no n in font nullfont! +Missing character: There is no d in font nullfont! +Missing character: There is no e in font nullfont! +Missing character: There is no p in font nullfont! +Missing character: There is no e in font nullfont! +Missing character: There is no n in font nullfont! +Missing character: There is no d in font nullfont! +Missing character: There is no e in font nullfont! +Missing character: There is no n in font nullfont! +Missing character: There is no t in font nullfont! +Missing character: There is no l in font nullfont! +Missing character: There is no y in font nullfont! +Missing character: There is no w in font nullfont! +Missing character: There is no i in font nullfont! +Missing character: There is no t in font nullfont! +Missing character: There is no h in font nullfont! +Missing character: There is no p in font nullfont! +Missing character: There is no r in font nullfont! +Missing character: There is no o in font nullfont! +Missing character: There is no b in font nullfont! +Missing character: There is no a in font nullfont! +Missing character: There is no b in font nullfont! +Missing character: There is no i in font nullfont! +Missing character: There is no l in font nullfont! +Missing character: There is no i in font nullfont! +Missing character: There is no t in font nullfont! +Missing character: There is no y in font nullfont! +Missing character: There is no . in font nullfont! +Missing character: There is no T in font nullfont! +Missing character: There is no h in font nullfont! +Missing character: There is no e in font nullfont! +Missing character: There is no c in font nullfont! +Missing character: There is no o in font nullfont! +Missing character: There is no n in font nullfont! +Missing character: There is no s in font nullfont! +Missing character: There is no t in font nullfont! +Missing character: There is no r in font nullfont! +Missing character: There is no a in font nullfont! +Missing character: There is no i in font nullfont! +Missing character: There is no n in font nullfont! +Missing character: There is no t in font nullfont! +Missing character: There is no w in font nullfont! +Missing character: There is no i in font nullfont! +Missing character: There is no l in font nullfont! +Missing character: There is no l in font nullfont! +Missing character: There is no n in font nullfont! +Missing character: There is no o in font nullfont! +Missing character: There is no w in font nullfont! +Missing character: There is no b in font nullfont! +Missing character: There is no e in font nullfont! +Missing character: There is no t in font nullfont! +Missing character: There is no h in font nullfont! +Missing character: There is no a in font nullfont! +Missing character: There is no t in font nullfont! +Missing character: There is no t in font nullfont! +Missing character: There is no h in font nullfont! +Missing character: There is no e in font nullfont! +Missing character: There is no b in font nullfont! +Missing character: There is no u in font nullfont! +Missing character: There is no d in font nullfont! +Missing character: There is no g in font nullfont! +Missing character: There is no e in font nullfont! +Missing character: There is no t in font nullfont! +Missing character: There is no i in font nullfont! +Missing character: There is no s in font nullfont! +Missing character: There is no o in font nullfont! +Missing character: There is no n in font nullfont! +Missing character: There is no l in font nullfont! +Missing character: There is no y in font nullfont! +Missing character: There is no r in font nullfont! +Missing character: There is no e in font nullfont! +Missing character: There is no s in font nullfont! +Missing character: There is no p in font nullfont! +Missing character: There is no e in font nullfont! +Missing character: There is no c in font nullfont! +Missing character: There is no t in font nullfont! +Missing character: There is no e in font nullfont! +Missing character: There is no d in font nullfont! +Missing character: There is no i in font nullfont! +Missing character: There is no n in font nullfont! +Missing character: There is no e in font nullfont! +Missing character: There is no x in font nullfont! +Missing character: There is no p in font nullfont! +Missing character: There is no e in font nullfont! +Missing character: There is no c in font nullfont! +Missing character: There is no t in font nullfont! +Missing character: There is no a in font nullfont! +Missing character: There is no t in font nullfont! +Missing character: There is no i in font nullfont! +Missing character: There is no o in font nullfont! +Missing character: There is no n in font nullfont! +Missing character: There is no , in font nullfont! +Missing character: There is no i in font nullfont! +Missing character: There is no . in font nullfont! +Missing character: There is no e in font nullfont! +Missing character: There is no . in font nullfont! +Missing character: There is no . in font nullfont! +Missing character: There is no N in font nullfont! +Missing character: There is no o in font nullfont! +Missing character: There is no t in font nullfont! +Missing character: There is no e in font nullfont! +Missing character: There is no t in font nullfont! +Missing character: There is no h in font nullfont! +Missing character: There is no a in font nullfont! +Missing character: There is no t in font nullfont! +Missing character: There is no u in font nullfont! +Missing character: There is no s in font nullfont! +Missing character: There is no i in font nullfont! +Missing character: There is no n in font nullfont! +Missing character: There is no g in font nullfont! +Missing character: There is no n in font nullfont! +Missing character: There is no o in font nullfont! +Missing character: There is no n in font nullfont! +Missing character: There is no - in font nullfont! +Missing character: There is no a in font nullfont! +Missing character: There is no d in font nullfont! +Missing character: There is no a in font nullfont! +Missing character: There is no p in font nullfont! +Missing character: There is no t in font nullfont! +Missing character: There is no i in font nullfont! +Missing character: There is no v in font nullfont! +Missing character: There is no e in font nullfont! +Missing character: There is no s in font nullfont! +Missing character: There is no o in font nullfont! +Missing character: There is no l in font nullfont! +Missing character: There is no u in font nullfont! +Missing character: There is no t in font nullfont! +Missing character: There is no i in font nullfont! +Missing character: There is no o in font nullfont! +Missing character: There is no n in font nullfont! +Missing character: There is no s in font nullfont! +Missing character: There is no i in font nullfont! +Missing character: There is no s in font nullfont! +Missing character: There is no o in font nullfont! +Missing character: There is no n in font nullfont! +Missing character: There is no l in font nullfont! +Missing character: There is no y in font nullfont! +Missing character: There is no a in font nullfont! +Missing character: There is no t in font nullfont! +Missing character: There is no e in font nullfont! +Missing character: There is no c in font nullfont! +Missing character: There is no h in font nullfont! +Missing character: There is no n in font nullfont! +Missing character: There is no i in font nullfont! +Missing character: There is no q in font nullfont! +Missing character: There is no u in font nullfont! +Missing character: There is no e in font nullfont! +Missing character: There is no a in font nullfont! +Missing character: There is no n in font nullfont! +Missing character: There is no d in font nullfont! +Missing character: There is no w in font nullfont! +Missing character: There is no e in font nullfont! +Missing character: There is no w in font nullfont! +Missing character: There is no i in font nullfont! +Missing character: There is no l in font nullfont! +Missing character: There is no l in font nullfont! +Missing character: There is no l in font nullfont! +Missing character: There is no a in font nullfont! +Missing character: There is no t in font nullfont! +Missing character: There is no e in font nullfont! +Missing character: There is no r in font nullfont! +Missing character: There is no s in font nullfont! +Missing character: There is no h in font nullfont! +Missing character: There is no o in font nullfont! +Missing character: There is no w in font nullfont! +Missing character: There is no h in font nullfont! +Missing character: There is no o in font nullfont! +Missing character: There is no w in font nullfont! +Missing character: There is no t in font nullfont! +Missing character: There is no o in font nullfont! +Missing character: There is no t in font nullfont! +Missing character: There is no r in font nullfont! +Missing character: There is no a in font nullfont! +Missing character: There is no n in font nullfont! +Missing character: There is no s in font nullfont! +Missing character: There is no f in font nullfont! +Missing character: There is no o in font nullfont! +Missing character: There is no r in font nullfont! +Missing character: There is no m in font nullfont! +Missing character: There is no n in font nullfont! +Missing character: There is no o in font nullfont! +Missing character: There is no n in font nullfont! +Missing character: There is no - in font nullfont! +Missing character: There is no a in font nullfont! +Missing character: There is no d in font nullfont! +Missing character: There is no a in font nullfont! +Missing character: There is no p in font nullfont! +Missing character: There is no t in font nullfont! +Missing character: There is no i in font nullfont! +Missing character: There is no v in font nullfont! +Missing character: There is no e in font nullfont! +Missing character: There is no s in font nullfont! +Missing character: There is no o in font nullfont! +Missing character: There is no l in font nullfont! +Missing character: There is no u in font nullfont! +Missing character: There is no t in font nullfont! +Missing character: There is no i in font nullfont! +Missing character: There is no o in font nullfont! +Missing character: There is no n in font nullfont! +Missing character: There is no s in font nullfont! +Missing character: There is no i in font nullfont! +Missing character: There is no n in font nullfont! +Missing character: There is no t in font nullfont! +Missing character: There is no o in font nullfont! +Missing character: There is no a in font nullfont! +Missing character: There is no d in font nullfont! +Missing character: There is no a in font nullfont! +Missing character: There is no p in font nullfont! +Missing character: There is no t in font nullfont! +Missing character: There is no i in font nullfont! +Missing character: There is no v in font nullfont! +Missing character: There is no e in font nullfont! +Missing character: There is no o in font nullfont! +Missing character: There is no n in font nullfont! +Missing character: There is no e in font nullfont! +Missing character: There is no s in font nullfont! +Missing character: There is no . in font nullfont! +Missing character: There is no F in font nullfont! +Missing character: There is no o in font nullfont! +Missing character: There is no r in font nullfont! +Missing character: There is no m in font nullfont! +Missing character: There is no a in font nullfont! +Missing character: There is no l in font nullfont! +Missing character: There is no l in font nullfont! +Missing character: There is no y in font nullfont! +Missing character: There is no t in font nullfont! +Missing character: There is no h in font nullfont! +Missing character: There is no e in font nullfont! +Missing character: There is no o in font nullfont! +Missing character: There is no p in font nullfont! +Missing character: There is no t in font nullfont! +Missing character: There is no i in font nullfont! +Missing character: There is no m in font nullfont! +Missing character: There is no i in font nullfont! +Missing character: There is no z in font nullfont! +Missing character: There is no a in font nullfont! +Missing character: There is no t in font nullfont! +Missing character: There is no i in font nullfont! +Missing character: There is no o in font nullfont! +Missing character: There is no n in font nullfont! +Missing character: There is no p in font nullfont! +Missing character: There is no r in font nullfont! +Missing character: There is no o in font nullfont! +Missing character: There is no b in font nullfont! +Missing character: There is no l in font nullfont! +Missing character: There is no e in font nullfont! +Missing character: There is no m in font nullfont! +Missing character: There is no f in font nullfont! +Missing character: There is no o in font nullfont! +Missing character: There is no r in font nullfont! +Missing character: There is no n in font nullfont! +Missing character: There is no o in font nullfont! +Missing character: There is no n in font nullfont! +Missing character: There is no - in font nullfont! +Missing character: There is no a in font nullfont! +Missing character: There is no d in font nullfont! +Missing character: There is no a in font nullfont! +Missing character: There is no p in font nullfont! +Missing character: There is no t in font nullfont! +Missing character: There is no i in font nullfont! +Missing character: There is no v in font nullfont! +Missing character: There is no e in font nullfont! +Missing character: There is no p in font nullfont! +Missing character: There is no o in font nullfont! +Missing character: There is no l in font nullfont! +Missing character: There is no i in font nullfont! +Missing character: There is no c in font nullfont! +Missing character: There is no i in font nullfont! +Missing character: There is no e in font nullfont! +Missing character: There is no s in font nullfont! +Missing character: There is no c in font nullfont! +Missing character: There is no a in font nullfont! +Missing character: There is no n in font nullfont! +Missing character: There is no b in font nullfont! +Missing character: There is no e in font nullfont! +Missing character: There is no w in font nullfont! +Missing character: There is no r in font nullfont! +Missing character: There is no i in font nullfont! +Missing character: There is no t in font nullfont! +Missing character: There is no t in font nullfont! +Missing character: There is no e in font nullfont! +Missing character: There is no n in font nullfont! +Missing character: There is no a in font nullfont! +Missing character: There is no s in font nullfont! +Missing character: There is no : in font nullfont! + +Overfull \hbox (20.0pt too wide) in paragraph at lines 4--10 +[] + [] + + +Overfull \hbox (17.26382pt too wide) in paragraph at lines 4--10 +\OML/cmm/m/it/10 S \OMS/cmsy/m/n/10 ^^R + [] + + +Overfull \hbox (9.06943pt too wide) in paragraph at lines 4--10 +\OML/cmm/m/it/10 X$ + [] + + +Overfull \hbox (6.06941pt too wide) in paragraph at lines 4--10 +[]$ + [] + + +Overfull \hbox (5.72458pt too wide) in paragraph at lines 4--10 +\OML/cmm/m/it/10 u$ + [] + + +Overfull \hbox (6.70831pt too wide) in paragraph at lines 4--10 +\OML/cmm/m/it/10 S$ + [] + + +Overfull \hbox (9.69218pt too wide) in paragraph at lines 4--10 +\OML/cmm/m/it/10 q[]$ + [] + + +Overfull \hbox (20.04169pt too wide) in paragraph at lines 4--10 +\OMS/cmsy/m/n/10 j\OML/cmm/m/it/10 S\OMS/cmsy/m/n/10 j \OT1/cmr/m/n/10 + + [] + + +Overfull \hbox (29.31343pt too wide) in paragraph at lines 4--10 +[][][] \OMS/cmsy/m/n/10 ^^T + [] + + +Overfull \hbox (5.52084pt too wide) in paragraph at lines 4--10 +\OML/cmm/m/it/10 k$ + [] + + +./algorithms.tex:11: LaTeX Error: Missing \begin{document}. + +See the LaTeX manual or LaTeX Companion for explanation. +Type H <return> for immediate help. + ... + +l.11 \begin{equation} + \label{eq:relaxed} +? + +Overfull \hbox (20.0pt too wide) in paragraph at lines 11--11 +[] + [] + + +./algorithms.tex:12: LaTeX Error: Environment split undefined. + +See the LaTeX manual or LaTeX Companion for explanation. +Type H <return> for immediate help. + ... + +l.12 \begin{split} + +? +./algorithms.tex:14: Undefined control sequence. +l.14 \max_{\substack + {S\subseteq X\\q\in[0,1]^n} }& \; +? +./algorithms.tex:14: Misplaced alignment tab character &. +l.14 ...x_{\substack{S\subseteq X\\q\in[0,1]^n} }& + \; +? +./algorithms.tex:15: Undefined control sequence. +l.15 \sum_{R\subseteq\neigh + {X}}\textbf{p}\odot\textbf{q}_Rf(R)\\ +? +./algorithms.tex:16: Undefined control sequence. +<recently read> \text + +l.16 \text + {s.t. } & \; |S|+\textbf{p}^T\textbf{q} \leq k,\; +? +./algorithms.tex:16: Misplaced alignment tab character &. +l.16 \text{s.t. } & + \; |S|+\textbf{p}^T\textbf{q} \leq k,\; +? +./algorithms.tex:17: Undefined control sequence. +l.17 q_u \leq \mathbf{1}_{\{u\in\neigh + {S}\}} +? + +./algorithms.tex:18: LaTeX Error: \begin{equation} on input line 11 ended by \e +nd{split}. + +See the LaTeX manual or LaTeX Companion for explanation. +Type H <return> for immediate help. + ... + +l.18 \end{split} + +? + +Overfull \hbox (255.8566pt too wide) detected at line 19 +[][] [] [] \OMS/cmsy/m/n/10 ^^L [][]\OML/cmm/m/it/10 f\OT1/cmr/m/n/10 (\OML/cm +m/m/it/10 R\OT1/cmr/m/n/10 )[] [] \OMS/cmsy/m/n/10 j\OML/cmm/m/it/10 S\OMS/cmsy +/m/n/10 j \OT1/cmr/m/n/10 + [][][] \OMS/cmsy/m/n/10 ^^T \OML/cmm/m/it/10 k; q[ +] \OMS/cmsy/m/n/10 ^^T \OT1/cmr/bx/n/10 1[] + [] + + +./algorithms.tex:21: LaTeX Error: Missing \begin{document}. + +See the LaTeX manual or LaTeX Companion for explanation. +Type H <return> for immediate help. + ... + +l.21 w + here $n\defeq|\neigh{X}|$,$\textbf{p}\odot \textbf{q}$ denotes compone... + +? +Missing character: There is no w in font nullfont! +Missing character: There is no h in font nullfont! +Missing character: There is no e in font nullfont! +Missing character: There is no r in font nullfont! +Missing character: There is no e in font nullfont! +./algorithms.tex:21: Undefined control sequence. +l.21 where $n\defeq + |\neigh{X}|$,$\textbf{p}\odot \textbf{q}$ denotes compone... + +? +./algorithms.tex:21: Undefined control sequence. +l.21 where $n\defeq|\neigh + {X}|$,$\textbf{p}\odot \textbf{q}$ denotes compone... + +? +Missing character: There is no , in font nullfont! +Missing character: There is no d in font nullfont! +Missing character: There is no e in font nullfont! +Missing character: There is no n in font nullfont! +Missing character: There is no o in font nullfont! +Missing character: There is no t in font nullfont! +Missing character: There is no e in font nullfont! +Missing character: There is no s in font nullfont! +Missing character: There is no c in font nullfont! +Missing character: There is no o in font nullfont! +Missing character: There is no m in font nullfont! +Missing character: There is no p in font nullfont! +Missing character: There is no o in font nullfont! +Missing character: There is no n in font nullfont! +Missing character: There is no e in font nullfont! +Missing character: There is no n in font nullfont! +Missing character: There is no t in font nullfont! +Missing character: There is no w in font nullfont! +Missing character: There is no i in font nullfont! +Missing character: There is no s in font nullfont! +Missing character: There is no e in font nullfont! +Missing character: There is no m in font nullfont! +Missing character: There is no u in font nullfont! +Missing character: There is no l in font nullfont! +Missing character: There is no t in font nullfont! +Missing character: There is no i in font nullfont! +Missing character: There is no p in font nullfont! +Missing character: There is no l in font nullfont! +Missing character: There is no i in font nullfont! +Missing character: There is no c in font nullfont! +Missing character: There is no a in font nullfont! +Missing character: There is no t in font nullfont! +Missing character: There is no i in font nullfont! +Missing character: There is no o in font nullfont! +Missing character: There is no n in font nullfont! +Missing character: There is no a in font nullfont! +Missing character: There is no n in font nullfont! +Missing character: There is no d in font nullfont! +Missing character: There is no d in font nullfont! +Missing character: There is no e in font nullfont! +Missing character: There is no n in font nullfont! +Missing character: There is no o in font nullfont! +Missing character: There is no t in font nullfont! +Missing character: There is no e in font nullfont! +Missing character: There is no s in font nullfont! +Missing character: There is no t in font nullfont! +Missing character: There is no h in font nullfont! +Missing character: There is no e in font nullfont! +Missing character: There is no p in font nullfont! +Missing character: There is no o in font nullfont! +Missing character: There is no s in font nullfont! +Missing character: There is no i in font nullfont! +Missing character: There is no t in font nullfont! +Missing character: There is no i in font nullfont! +Missing character: There is no v in font nullfont! +Missing character: There is no e in font nullfont! +Missing character: There is no e in font nullfont! +Missing character: There is no n in font nullfont! +Missing character: There is no t in font nullfont! +Missing character: There is no r in font nullfont! +Missing character: There is no i in font nullfont! +Missing character: There is no e in font nullfont! +Missing character: There is no s in font nullfont! +Missing character: There is no o in font nullfont! +Missing character: There is no f in font nullfont! +Missing character: There is no o in font nullfont! +Missing character: There is no n in font nullfont! +Missing character: There is no n in font nullfont! +Missing character: There is no o in font nullfont! +Missing character: There is no d in font nullfont! +Missing character: There is no e in font nullfont! +Missing character: There is no s in font nullfont! +Missing character: There is no i in font nullfont! +Missing character: There is no n in font nullfont! +Missing character: There is no : in font nullfont! + +Overfull \hbox (20.0pt too wide) in paragraph at lines 21--22 +[] + [] + + +Overfull \hbox (34.794pt too wide) in paragraph at lines 21--22 +\OML/cmm/m/it/10 n\OMS/cmsy/m/n/10 j\OML/cmm/m/it/10 X\OMS/cmsy/m/n/10 j$$[] ^^ +L + [] + + +Overfull \hbox (6.06941pt too wide) in paragraph at lines 21--22 +[]$ + [] + + +Overfull \hbox (12.6295pt too wide) in paragraph at lines 21--22 +[][]$ + [] + + +Overfull \hbox (6.06941pt too wide) in paragraph at lines 21--22 +[]$ + [] + + +Overfull \hbox (7.67015pt too wide) in paragraph at lines 21--22 +\OML/cmm/m/it/10 R$ + [] + + +./algorithms.tex:23: LaTeX Error: Missing \begin{document}. + +See the LaTeX manual or LaTeX Companion for explanation. +Type H <return> for immediate help. + ... + +l.23 \begin{displaymath} + +? + +Overfull \hbox (20.0pt too wide) in paragraph at lines 23--23 +[][] + [] + +./algorithms.tex:24: Undefined control sequence. +l.24 \txtbf + {p}\circ \textbf{q}_R = \prod_{u\in R} p_uq_u\prod_{u\in\neig... + +? +./algorithms.tex:24: Undefined control sequence. +l.24 ...R = \prod_{u\in R} p_uq_u\prod_{u\in\neigh + {X}\setminus +? + +Overfull \hbox (143.33928pt too wide) detected at line 26 +\OML/cmm/m/it/10 p \OMS/cmsy/m/n/10 ^^N [][] \OT1/cmr/m/n/10 = [] \OML/cmm/m/it +/10 p[]q[] []\OT1/cmr/m/n/10 (1 \OMS/cmsy/m/n/10 ^^@ \OML/cmm/m/it/10 p[]q[]\OT +1/cmr/m/n/10 ) + [] + + +./algorithms.tex:28: LaTeX Error: Missing \begin{document}. + +See the LaTeX manual or LaTeX Companion for explanation. +Type H <return> for immediate help. + ... + +l.28 N + ote that because of the condition $q_u\leq \mathbf{1}_{\{u\in\neigh{S}... + +? +Missing character: There is no N in font nullfont! +Missing character: There is no o in font nullfont! +Missing character: There is no t in font nullfont! +Missing character: There is no e in font nullfont! +Missing character: There is no t in font nullfont! +Missing character: There is no h in font nullfont! +Missing character: There is no a in font nullfont! +Missing character: There is no t in font nullfont! +Missing character: There is no b in font nullfont! +Missing character: There is no e in font nullfont! +Missing character: There is no c in font nullfont! +Missing character: There is no a in font nullfont! +Missing character: There is no u in font nullfont! +Missing character: There is no s in font nullfont! +Missing character: There is no e in font nullfont! +Missing character: There is no o in font nullfont! +Missing character: There is no f in font nullfont! +Missing character: There is no t in font nullfont! +Missing character: There is no h in font nullfont! +Missing character: There is no e in font nullfont! +Missing character: There is no c in font nullfont! +Missing character: There is no o in font nullfont! +Missing character: There is no n in font nullfont! +Missing character: There is no d in font nullfont! +Missing character: There is no i in font nullfont! +Missing character: There is no t in font nullfont! +Missing character: There is no i in font nullfont! +Missing character: There is no o in font nullfont! +Missing character: There is no n in font nullfont! +./algorithms.tex:28: Undefined control sequence. +l.28 ...ondition $q_u\leq \mathbf{1}_{\{u\in\neigh + {S}\}}$, +? +Missing character: There is no , in font nullfont! +Missing character: There is no w in font nullfont! +Missing character: There is no h in font nullfont! +Missing character: There is no e in font nullfont! +Missing character: There is no n in font nullfont! +Missing character: There is no e in font nullfont! +Missing character: There is no v in font nullfont! +Missing character: There is no e in font nullfont! +Missing character: There is no r in font nullfont! +Missing character: There is no c in font nullfont! +Missing character: There is no o in font nullfont! +Missing character: There is no n in font nullfont! +Missing character: There is no t in font nullfont! +Missing character: There is no a in font nullfont! +Missing character: There is no i in font nullfont! +Missing character: There is no n in font nullfont! +Missing character: There is no s in font nullfont! +Missing character: There is no a in font nullfont! +Missing character: There is no n in font nullfont! +Missing character: There is no e in font nullfont! +Missing character: There is no l in font nullfont! +Missing character: There is no e in font nullfont! +Missing character: There is no m in font nullfont! +Missing character: There is no e in font nullfont! +Missing character: There is no n in font nullfont! +Missing character: There is no t in font nullfont! +Missing character: There is no o in font nullfont! +Missing character: There is no f in font nullfont! +./algorithms.tex:30: Undefined control sequence. +<recently read> \neigh + +l.30 $\neigh + {X}\setminus\neigh{S}$. Hence, the summation in \eqref{eq:relaxe... + +? +./algorithms.tex:30: Undefined control sequence. +l.30 $\neigh{X}\setminus\neigh + {S}$. Hence, the summation in \eqref{eq:relaxe... + +? +Missing character: There is no . in font nullfont! +Missing character: There is no H in font nullfont! +Missing character: There is no e in font nullfont! +Missing character: There is no n in font nullfont! +Missing character: There is no c in font nullfont! +Missing character: There is no e in font nullfont! +Missing character: There is no , in font nullfont! +Missing character: There is no t in font nullfont! +Missing character: There is no h in font nullfont! +Missing character: There is no e in font nullfont! +Missing character: There is no s in font nullfont! +Missing character: There is no u in font nullfont! +Missing character: There is no m in font nullfont! +Missing character: There is no m in font nullfont! +Missing character: There is no a in font nullfont! +Missing character: There is no t in font nullfont! +Missing character: There is no i in font nullfont! +Missing character: There is no o in font nullfont! +Missing character: There is no n in font nullfont! +Missing character: There is no i in font nullfont! +Missing character: There is no n in font nullfont! +./algorithms.tex:30: Undefined control sequence. +l.30 ...\neigh{S}$. Hence, the summation in \eqref + {eq:relaxed} is +? +Missing character: There is no e in font nullfont! +Missing character: There is no q in font nullfont! +Missing character: There is no : in font nullfont! +Missing character: There is no r in font nullfont! +Missing character: There is no e in font nullfont! +Missing character: There is no l in font nullfont! +Missing character: There is no a in font nullfont! +Missing character: There is no x in font nullfont! +Missing character: There is no e in font nullfont! +Missing character: There is no d in font nullfont! +Missing character: There is no i in font nullfont! +Missing character: There is no s in font nullfont! +Missing character: There is no r in font nullfont! +Missing character: There is no e in font nullfont! +Missing character: There is no s in font nullfont! +Missing character: There is no t in font nullfont! +Missing character: There is no r in font nullfont! +Missing character: There is no i in font nullfont! +Missing character: There is no c in font nullfont! +Missing character: There is no t in font nullfont! +Missing character: There is no e in font nullfont! +Missing character: There is no d in font nullfont! +Missing character: There is no t in font nullfont! +Missing character: There is no o in font nullfont! +./algorithms.tex:31: Undefined control sequence. +l.31 restricted to $R\subseteq\neigh + {S}$ as in \eqref{eq:problem}. +? +Missing character: There is no a in font nullfont! +Missing character: There is no s in font nullfont! +Missing character: There is no i in font nullfont! +Missing character: There is no n in font nullfont! +./algorithms.tex:31: Undefined control sequence. +l.31 ...cted to $R\subseteq\neigh{S}$ as in \eqref + {eq:problem}. +? +Missing character: There is no e in font nullfont! +Missing character: There is no q in font nullfont! +Missing character: There is no : in font nullfont! +Missing character: There is no p in font nullfont! +Missing character: There is no r in font nullfont! +Missing character: There is no o in font nullfont! +Missing character: There is no b in font nullfont! +Missing character: There is no l in font nullfont! +Missing character: There is no e in font nullfont! +Missing character: There is no m in font nullfont! +Missing character: There is no . in font nullfont! + +Overfull \hbox (20.0pt too wide) in paragraph at lines 28--32 +[] + [] + + +Overfull \hbox (20.2477pt too wide) in paragraph at lines 28--32 +\OML/cmm/m/it/10 q[] \OMS/cmsy/m/n/10 ^^T + [] + + +Overfull \hbox (29.85446pt too wide) in paragraph at lines 28--32 +\OT1/cmr/bx/n/10 1[]$ + [] + + +Overfull \hbox (10.03127pt too wide) in paragraph at lines 28--32 +\OML/cmm/m/it/10 p \OMS/cmsy/m/n/10 ^^N + [] + + +Overfull \hbox (21.57973pt too wide) in paragraph at lines 28--32 +\OML/cmm/m/it/10 q[] \OT1/cmr/m/n/10 = + [] + + +Overfull \hbox (5.00002pt too wide) in paragraph at lines 28--32 +\OT1/cmr/m/n/10 0$ + [] + + +Overfull \hbox (7.67015pt too wide) in paragraph at lines 28--32 +\OML/cmm/m/it/10 R$ + [] + + +Overfull \hbox (14.06944pt too wide) in paragraph at lines 28--32 +\OML/cmm/m/it/10 X \OMS/cmsy/m/n/10 n + [] + + +Overfull \hbox (6.70831pt too wide) in paragraph at lines 28--32 +\OML/cmm/m/it/10 S$ + [] + + +Overfull \hbox (18.22566pt too wide) in paragraph at lines 28--32 +\OML/cmm/m/it/10 R \OMS/cmsy/m/n/10 ^^R + [] + + +Overfull \hbox (6.70831pt too wide) in paragraph at lines 28--32 +\OML/cmm/m/it/10 S$ + [] + +./algorithms.tex:60: Undefined control sequence. +l.60 \subsection + {Adaptivity gap for additive functions} +? + +./algorithms.tex:60: LaTeX Error: Missing \begin{document}. + +See the LaTeX manual or LaTeX Companion for explanation. +Type H <return> for immediate help. + ... + +l.60 \subsection{A + daptivity gap for additive functions} +? +Missing character: There is no A in font nullfont! +Missing character: There is no d in font nullfont! +Missing character: There is no a in font nullfont! +Missing character: There is no p in font nullfont! +Missing character: There is no t in font nullfont! +Missing character: There is no i in font nullfont! +Missing character: There is no v in font nullfont! +Missing character: There is no i in font nullfont! +Missing character: There is no t in font nullfont! +Missing character: There is no y in font nullfont! +Missing character: There is no g in font nullfont! +Missing character: There is no a in font nullfont! +Missing character: There is no p in font nullfont! +Missing character: There is no f in font nullfont! +Missing character: There is no o in font nullfont! +Missing character: There is no r in font nullfont! +Missing character: There is no a in font nullfont! +Missing character: There is no d in font nullfont! +Missing character: There is no d in font nullfont! +Missing character: There is no i in font nullfont! +Missing character: There is no t in font nullfont! +Missing character: There is no i in font nullfont! +Missing character: There is no v in font nullfont! +Missing character: There is no e in font nullfont! +Missing character: There is no f in font nullfont! +Missing character: There is no u in font nullfont! +Missing character: There is no n in font nullfont! +Missing character: There is no c in font nullfont! +Missing character: There is no t in font nullfont! +Missing character: There is no i in font nullfont! +Missing character: There is no o in font nullfont! +Missing character: There is no n in font nullfont! +Missing character: There is no s in font nullfont! +Missing character: There is no W in font nullfont! +Missing character: There is no e in font nullfont! +Missing character: There is no w in font nullfont! +Missing character: There is no i in font nullfont! +Missing character: There is no l in font nullfont! +Missing character: There is no l in font nullfont! +Missing character: There is no n in font nullfont! +Missing character: There is no o in font nullfont! +Missing character: There is no w in font nullfont! +Missing character: There is no j in font nullfont! +Missing character: There is no u in font nullfont! +Missing character: There is no s in font nullfont! +Missing character: There is no t in font nullfont! +Missing character: There is no i in font nullfont! +Missing character: There is no f in font nullfont! +Missing character: There is no y in font nullfont! +Missing character: There is no t in font nullfont! +Missing character: There is no h in font nullfont! +Missing character: There is no e in font nullfont! +Missing character: There is no u in font nullfont! +Missing character: There is no s in font nullfont! +Missing character: There is no e in font nullfont! +Missing character: There is no o in font nullfont! +Missing character: There is no f in font nullfont! +Missing character: There is no n in font nullfont! +Missing character: There is no o in font nullfont! +Missing character: There is no n in font nullfont! +Missing character: There is no - in font nullfont! +Missing character: There is no a in font nullfont! +Missing character: There is no d in font nullfont! +Missing character: There is no a in font nullfont! +Missing character: There is no p in font nullfont! +Missing character: There is no t in font nullfont! +Missing character: There is no i in font nullfont! +Missing character: There is no v in font nullfont! +Missing character: There is no e in font nullfont! +Missing character: There is no s in font nullfont! +Missing character: There is no t in font nullfont! +Missing character: There is no r in font nullfont! +Missing character: There is no a in font nullfont! +Missing character: There is no t in font nullfont! +Missing character: There is no e in font nullfont! +Missing character: There is no g in font nullfont! +Missing character: There is no i in font nullfont! +Missing character: There is no e in font nullfont! +Missing character: There is no s in font nullfont! +Missing character: There is no b in font nullfont! +Missing character: There is no y in font nullfont! +Missing character: There is no s in font nullfont! +Missing character: There is no h in font nullfont! +Missing character: There is no o in font nullfont! +Missing character: There is no w in font nullfont! +Missing character: There is no i in font nullfont! +Missing character: There is no n in font nullfont! +Missing character: There is no g in font nullfont! +Missing character: There is no t in font nullfont! +Missing character: There is no h in font nullfont! +Missing character: There is no a in font nullfont! +Missing character: There is no t in font nullfont! +Missing character: There is no t in font nullfont! +Missing character: There is no h in font nullfont! +Missing character: There is no e in font nullfont! +Missing character: There is no o in font nullfont! +Missing character: There is no p in font nullfont! +Missing character: There is no t in font nullfont! +Missing character: There is no i in font nullfont! +Missing character: There is no m in font nullfont! +Missing character: There is no a in font nullfont! +Missing character: There is no l in font nullfont! +Missing character: There is no s in font nullfont! +Missing character: There is no o in font nullfont! +Missing character: There is no l in font nullfont! +Missing character: There is no u in font nullfont! +Missing character: There is no t in font nullfont! +Missing character: There is no i in font nullfont! +Missing character: There is no o in font nullfont! +Missing character: There is no n in font nullfont! +Missing character: There is no f in font nullfont! +Missing character: There is no o in font nullfont! +Missing character: There is no r in font nullfont! +Missing character: There is no t in font nullfont! +Missing character: There is no h in font nullfont! +Missing character: There is no i in font nullfont! +Missing character: There is no s in font nullfont! +Missing character: There is no f in font nullfont! +Missing character: There is no o in font nullfont! +Missing character: There is no r in font nullfont! +Missing character: There is no m in font nullfont! +Missing character: There is no o in font nullfont! +Missing character: There is no f in font nullfont! +Missing character: There is no n in font nullfont! +Missing character: There is no o in font nullfont! +Missing character: There is no n in font nullfont! +Missing character: There is no - in font nullfont! +Missing character: There is no a in font nullfont! +Missing character: There is no d in font nullfont! +Missing character: There is no a in font nullfont! +Missing character: There is no p in font nullfont! +Missing character: There is no t in font nullfont! +Missing character: There is no i in font nullfont! +Missing character: There is no v in font nullfont! +Missing character: There is no e in font nullfont! +Missing character: There is no s in font nullfont! +Missing character: There is no t in font nullfont! +Missing character: There is no r in font nullfont! +Missing character: There is no a in font nullfont! +Missing character: There is no t in font nullfont! +Missing character: There is no e in font nullfont! +Missing character: There is no g in font nullfont! +Missing character: There is no i in font nullfont! +Missing character: There is no e in font nullfont! +Missing character: There is no s in font nullfont! +Missing character: There is no y in font nullfont! +Missing character: There is no i in font nullfont! +Missing character: There is no e in font nullfont! +Missing character: There is no l in font nullfont! +Missing character: There is no d in font nullfont! +Missing character: There is no s in font nullfont! +Missing character: There is no a in font nullfont! +Missing character: There is no h in font nullfont! +Missing character: There is no i in font nullfont! +Missing character: There is no g in font nullfont! +Missing character: There is no h in font nullfont! +Missing character: There is no e in font nullfont! +Missing character: There is no r in font nullfont! +Missing character: There is no v in font nullfont! +Missing character: There is no a in font nullfont! +Missing character: There is no l in font nullfont! +Missing character: There is no u in font nullfont! +Missing character: There is no e in font nullfont! +Missing character: There is no t in font nullfont! +Missing character: There is no h in font nullfont! +Missing character: There is no a in font nullfont! +Missing character: There is no n in font nullfont! +Missing character: There is no a in font nullfont! +Missing character: There is no d in font nullfont! +Missing character: There is no a in font nullfont! +Missing character: There is no p in font nullfont! +Missing character: There is no t in font nullfont! +Missing character: There is no i in font nullfont! +Missing character: There is no v in font nullfont! +Missing character: There is no e in font nullfont! +Missing character: There is no o in font nullfont! +Missing character: There is no n in font nullfont! +Missing character: There is no e in font nullfont! +Missing character: There is no s in font nullfont! +Missing character: There is no . in font nullfont! + +Overfull \hbox (20.0pt too wide) in paragraph at lines 60--62 +[] + [] + + +./algorithms.tex:63: LaTeX Error: Missing \begin{document}. + +See the LaTeX manual or LaTeX Companion for explanation. +Type H <return> for immediate help. + ... + +l.63 t + his form of non-adap +? +Missing character: There is no t in font nullfont! +Missing character: There is no h in font nullfont! +Missing character: There is no i in font nullfont! +Missing character: There is no s in font nullfont! +Missing character: There is no f in font nullfont! +Missing character: There is no o in font nullfont! +Missing character: There is no r in font nullfont! +Missing character: There is no m in font nullfont! +Missing character: There is no o in font nullfont! +Missing character: There is no f in font nullfont! +Missing character: There is no n in font nullfont! +Missing character: There is no o in font nullfont! +Missing character: There is no n in font nullfont! +Missing character: There is no - in font nullfont! +Missing character: There is no a in font nullfont! +Missing character: There is no d in font nullfont! +Missing character: There is no a in font nullfont! +Missing character: There is no p in font nullfont! +Missing character: There is no W in font nullfont! +Missing character: There is no e in font nullfont! +Missing character: There is no a in font nullfont! +Missing character: There is no l in font nullfont! +Missing character: There is no r in font nullfont! +Missing character: There is no e in font nullfont! +Missing character: There is no a in font nullfont! +Missing character: There is no d in font nullfont! +Missing character: There is no y in font nullfont! +Missing character: There is no k in font nullfont! +Missing character: There is no n in font nullfont! +Missing character: There is no o in font nullfont! +Missing character: There is no w in font nullfont! +Missing character: There is no t in font nullfont! +Missing character: There is no h in font nullfont! +Missing character: There is no a in font nullfont! +Missing character: There is no t in font nullfont! +Missing character: There is no t in font nullfont! +Missing character: There is no h in font nullfont! +Missing character: There is no e in font nullfont! +Missing character: There is no a in font nullfont! +Missing character: There is no d in font nullfont! +Missing character: There is no a in font nullfont! +Missing character: There is no p in font nullfont! +Missing character: There is no t in font nullfont! +Missing character: There is no i in font nullfont! +Missing character: There is no v in font nullfont! +Missing character: There is no i in font nullfont! +Missing character: There is no t in font nullfont! +Missing character: There is no y in font nullfont! +Missing character: There is no g in font nullfont! +Missing character: There is no a in font nullfont! +Missing character: There is no p in font nullfont! +Missing character: There is no i in font nullfont! +Missing character: There is no s in font nullfont! +Missing character: There is no b in font nullfont! +Missing character: There is no o in font nullfont! +Missing character: There is no u in font nullfont! +Missing character: There is no n in font nullfont! +Missing character: There is no d in font nullfont! +Missing character: There is no e in font nullfont! +Missing character: There is no d in font nullfont! +Missing character: There is no f in font nullfont! +Missing character: There is no o in font nullfont! +Missing character: There is no r in font nullfont! +Missing character: There is no a in font nullfont! +Missing character: There is no g in font nullfont! +Missing character: There is no e in font nullfont! +Missing character: There is no n in font nullfont! +Missing character: There is no e in font nullfont! +Missing character: There is no r in font nullfont! +Missing character: There is no a in font nullfont! +Missing character: There is no l in font nullfont! +Missing character: There is no c in font nullfont! +Missing character: There is no l in font nullfont! +Missing character: There is no a in font nullfont! +Missing character: There is no s in font nullfont! +Missing character: There is no s in font nullfont! +Missing character: There is no o in font nullfont! +Missing character: There is no f in font nullfont! +Missing character: There is no i in font nullfont! +Missing character: There is no n in font nullfont! +Missing character: There is no f in font nullfont! +Missing character: There is no l in font nullfont! +Missing character: There is no u in font nullfont! +Missing character: There is no e in font nullfont! +Missing character: There is no n in font nullfont! +Missing character: There is no c in font nullfont! +Missing character: There is no e in font nullfont! +Missing character: There is no f in font nullfont! +Missing character: There is no u in font nullfont! +Missing character: There is no n in font nullfont! +Missing character: There is no c in font nullfont! +Missing character: There is no t in font nullfont! +Missing character: There is no i in font nullfont! +Missing character: There is no o in font nullfont! +Missing character: There is no n in font nullfont! +Missing character: There is no . in font nullfont! +Missing character: There is no F in font nullfont! +Missing character: There is no o in font nullfont! +Missing character: There is no r in font nullfont! +Missing character: There is no a in font nullfont! +Missing character: There is no d in font nullfont! +Missing character: There is no a in font nullfont! +Missing character: There is no p in font nullfont! +Missing character: There is no t in font nullfont! +Missing character: There is no i in font nullfont! +Missing character: There is no v in font nullfont! +Missing character: There is no e in font nullfont! +Missing character: There is no f in font nullfont! +Missing character: There is no u in font nullfont! +Missing character: There is no n in font nullfont! +Missing character: There is no c in font nullfont! +Missing character: There is no t in font nullfont! +Missing character: There is no i in font nullfont! +Missing character: There is no o in font nullfont! +Missing character: There is no n in font nullfont! +Missing character: There is no s in font nullfont! +Missing character: There is no , in font nullfont! +Missing character: There is no w in font nullfont! +Missing character: There is no e in font nullfont! +Missing character: There is no g in font nullfont! +Missing character: There is no e in font nullfont! +Missing character: There is no t in font nullfont! +Missing character: There is no a in font nullfont! +Missing character: There is no s in font nullfont! +Missing character: There is no t in font nullfont! +Missing character: There is no r in font nullfont! +Missing character: There is no o in font nullfont! +Missing character: There is no n in font nullfont! +Missing character: There is no g in font nullfont! +Missing character: There is no e in font nullfont! +Missing character: There is no r in font nullfont! +Missing character: There is no r in font nullfont! +Missing character: There is no e in font nullfont! +Missing character: There is no s in font nullfont! +Missing character: There is no u in font nullfont! +Missing character: There is no l in font nullfont! +Missing character: There is no t in font nullfont! +Missing character: There is no : in font nullfont! +Missing character: There is no . in font nullfont! + +Overfull \hbox (20.0pt too wide) in paragraph at lines 63--67 +[] + [] + + +Overfull \hbox (33.38863pt too wide) in paragraph at lines 63--67 +\OT1/cmr/m/it/10 relaxed- + [] + + +Overfull \hbox (16.35547pt too wide) in paragraph at lines 63--67 +\OT1/cmr/m/it/10 non + [] + + +Overfull \hbox (24.02208pt too wide) in paragraph at lines 63--67 +\OT1/cmr/m/it/10 adap- + [] + + +Overfull \hbox (15.58876pt too wide) in paragraph at lines 63--67 +\OT1/cmr/m/it/10 tive + [] + + +Overfull \hbox (18.91098pt too wide) in paragraph at lines 63--67 +\OT1/cmr/m/it/10 poli- + [] + + +Overfull \hbox (16.35544pt too wide) in paragraph at lines 63--67 +\OT1/cmr/m/it/10 cies + [] + + +Overfull \hbox (13.41655pt too wide) in paragraph at lines 63--67 +\OT1/cmr/m/it/10 are + [] + + +Overfull \hbox (35.26639pt too wide) in paragraph at lines 63--67 +\OT1/cmr/m/it/10 stronger + [] + + +Overfull \hbox (19.16655pt too wide) in paragraph at lines 63--67 +\OT1/cmr/m/it/10 than + [] + + +Overfull \hbox (19.93321pt too wide) in paragraph at lines 63--67 +\OT1/cmr/m/it/10 non- + [] + + +Overfull \hbox (36.0331pt too wide) in paragraph at lines 63--67 +\OT1/cmr/m/it/10 adaptive + [] + + +Overfull \hbox (18.91098pt too wide) in paragraph at lines 63--67 +\OT1/cmr/m/it/10 poli- + [] + + +Overfull \hbox (16.35544pt too wide) in paragraph at lines 63--67 +\OT1/cmr/m/it/10 cies + [] + + +./algorithms.tex:69: LaTeX Error: Environment proposition undefined. + +See the LaTeX manual or LaTeX Companion for explanation. +Type H <return> for immediate help. + ... + +l.69 \begin{proposition} + \label{prop:gap} +? + +./algorithms.tex:70: LaTeX Error: Missing \begin{document}. + +See the LaTeX manual or LaTeX Companion for explanation. +Type H <return> for immediate help. + ... + +l.70 F + or additive functions of the form given by \eqref{eq:voter}, non-a... + +? +Missing character: There is no F in font nullfont! +Missing character: There is no o in font nullfont! +Missing character: There is no r in font nullfont! +Missing character: There is no a in font nullfont! +Missing character: There is no d in font nullfont! +Missing character: There is no d in font nullfont! +Missing character: There is no i in font nullfont! +Missing character: There is no t in font nullfont! +Missing character: There is no i in font nullfont! +Missing character: There is no v in font nullfont! +Missing character: There is no e in font nullfont! +Missing character: There is no f in font nullfont! +Missing character: There is no u in font nullfont! +Missing character: There is no n in font nullfont! +Missing character: There is no c in font nullfont! +Missing character: There is no t in font nullfont! +Missing character: There is no i in font nullfont! +Missing character: There is no o in font nullfont! +Missing character: There is no n in font nullfont! +Missing character: There is no s in font nullfont! +Missing character: There is no o in font nullfont! +Missing character: There is no f in font nullfont! +Missing character: There is no t in font nullfont! +Missing character: There is no h in font nullfont! +Missing character: There is no e in font nullfont! +Missing character: There is no f in font nullfont! +Missing character: There is no o in font nullfont! +Missing character: There is no r in font nullfont! +Missing character: There is no m in font nullfont! +Missing character: There is no g in font nullfont! +Missing character: There is no i in font nullfont! +Missing character: There is no v in font nullfont! +Missing character: There is no e in font nullfont! +Missing character: There is no n in font nullfont! +Missing character: There is no b in font nullfont! +Missing character: There is no y in font nullfont! +./algorithms.tex:70: Undefined control sequence. +l.70 ...tive functions of the form given by \eqref + {eq:voter}, non-adaptive +? +Missing character: There is no e in font nullfont! +Missing character: There is no q in font nullfont! +Missing character: There is no : in font nullfont! +Missing character: There is no v in font nullfont! +Missing character: There is no o in font nullfont! +Missing character: There is no t in font nullfont! +Missing character: There is no e in font nullfont! +Missing character: There is no r in font nullfont! +Missing character: There is no , in font nullfont! +Missing character: There is no n in font nullfont! +Missing character: There is no o in font nullfont! +Missing character: There is no n in font nullfont! +Missing character: There is no - in font nullfont! +Missing character: There is no a in font nullfont! +Missing character: There is no d in font nullfont! +Missing character: There is no a in font nullfont! +Missing character: There is no p in font nullfont! +Missing character: There is no t in font nullfont! +Missing character: There is no i in font nullfont! +Missing character: There is no v in font nullfont! +Missing character: There is no e in font nullfont! +Missing character: There is no p in font nullfont! +Missing character: There is no o in font nullfont! +Missing character: There is no l in font nullfont! +Missing character: There is no i in font nullfont! +Missing character: There is no c in font nullfont! +Missing character: There is no i in font nullfont! +Missing character: There is no e in font nullfont! +Missing character: There is no s in font nullfont! +Missing character: There is no a in font nullfont! +Missing character: There is no r in font nullfont! +Missing character: There is no e in font nullfont! +Missing character: There is no s in font nullfont! +Missing character: There is no t in font nullfont! +Missing character: There is no r in font nullfont! +Missing character: There is no o in font nullfont! +Missing character: There is no n in font nullfont! +Missing character: There is no g in font nullfont! +Missing character: There is no e in font nullfont! +Missing character: There is no r in font nullfont! +Missing character: There is no t in font nullfont! +Missing character: There is no h in font nullfont! +Missing character: There is no a in font nullfont! +Missing character: There is no n in font nullfont! +Missing character: There is no a in font nullfont! +Missing character: There is no d in font nullfont! +Missing character: There is no a in font nullfont! +Missing character: There is no p in font nullfont! +Missing character: There is no t in font nullfont! +Missing character: There is no i in font nullfont! +Missing character: There is no v in font nullfont! +Missing character: There is no e in font nullfont! +Missing character: There is no p in font nullfont! +Missing character: There is no o in font nullfont! +Missing character: There is no l in font nullfont! +Missing character: There is no i in font n
\ No newline at end of file diff --git a/paper/sections/algorithms.tex b/paper/sections/algorithms.tex new file mode 100644 index 0000000..e59de2a --- /dev/null +++ b/paper/sections/algorithms.tex @@ -0,0 +1,508 @@ +%In our context, a non-adaptive policy is simply a policy that makes all its decision before the realizations occur. That is, before the algorithm sees which neighbors arrive, it decides on how to allocate its seeding budget. This is in contrast to the optimal adaptive policy which waits for nodes to arrive. +% + +We start by introducing \emph{non-adaptive policies} for the adaptive seeding problem. These policies are used as a tool to obtain adaptive solutions as will be discussed in Sections~\ref{sec:gap} and~\ref{sec:round}. +We will say that a policy is non-adaptive if it selects a set of nodes $S +\subseteq X$ to be seeded in the first stage and a vector of probabilities +$\mathbf{q}\in[0,1]^n$, s.t. each neighbor $u$ of $S$ which realizes +is included in the solution independently with probability $q_u$. The +constraint will now be that the budget is only respected in expectation, i.e. +$|S| + \textbf{p}^T\textbf{q} \leq k$. Formally the optimization problem for non-adaptive policies can be written as: +\begin{equation}\label{eq:relaxed} + \begin{split} + %&\max_{} + \max_{\substack{S\subseteq X\\q\in[0,1]^n} }& \; + \sum_{R\subseteq\neigh{X}} \Big (\prod_{u\in R} p_uq_u\prod_{u\in\neigh{X}\setminus + R}(1-p_uq_u) \Big ) + f(R)\\ + \text{s.t. } & \; |S|+\textbf{p}^T\textbf{q} \leq k,\; +q_u \leq \mathbf{1}_{\{u\in\neigh{S}\}} +\end{split} +\end{equation} + +%$\textbf{p}\odot \textbf{q}$ denotes componentwise multiplication and $\textbf{q}_R$ denotes the positive entries of $\textbf{q}$ on nodes in $R$: +% +%\begin{displaymath} +% \textbf{p}\circ \textbf{q}_R = \prod_{u\in R} p_uq_u\prod_{u\in\neigh{X}\setminus +% R}(1-p_uq_u) +%\end{displaymath} +% +%\begin{displaymath} +% \Pr[R \ |\ \textbf{p}\odot \textbf{q} ] = \prod_{u\in R} p_uq_u\prod_{u\in\neigh{X}\setminus +% R}(1-p_uq_u) +%\end{displaymath} + +Note that because of the condition $q_u\leq \mathbf{1}_{\{u\in\neigh{S}\}}$, +the summand associated with $R$ in \eqref{eq:relaxed} vanishes whenever $R$ +contains $u\in\neigh{X}\setminus\neigh{S}$. Hence, the summation is restricted +to $R\subseteq\neigh{S}$ as in \eqref{eq:problem}. + +%The relaxed non-adaptive optimization \eqref{eq:relaxed} problem can be written +%more concisely using the \emph{multi-linear extension} of $f$: +%\begin{displaymath} +% \forall p\in[0,1]^m,\; F(p) +% \defeq\mathbb{E}_{p_R}\big[f(R)\big] +% =\sum_{R\subseteq\neigh{X}} p_R f(R) +%\end{displaymath} +%This \emph{extension by expectation} is known to present cross-convecity +%properties which can exploited in maximization problems when $f$ is +%a submodular function \cite{dughmi, vondrak}. Using this definition, \eqref{eq:relaxed} +%can be re-written as: +%\begin{equation}\label{eq:relaxed-multi} +% \begin{split} +% &\max_{S\subseteq X} \max_{q\in[0,1]^n}F(p\circ q)\\ +% &\text{s.t. }|S|+\sum_{u\in\neigh{X}}p_uq_u \leq k,\; +%q_u \leq \mathbf{1}_{\{u\in\neigh{S}\}} +%\end{split} +%\end{equation} +% +%When $f$ is an ìnfluence function from the triggering model, it has been proved +%in \cite{singer} that adaptive seeding has a bounded \emph{adaptivity gap}: +%denoting by $OPT$ the optimal solution of \eqref{eq:problem} and by $OPT_{NA}$ +%the optimal solution of \eqref{eq:relaxed}, we have $OPT\leq\alpha OPT_{NA}$. +%This inequality justifies using non-adaptive policies to approximate solutions +%to the adaptive seeding problem. + +\subsection{Adaptivity gap for additive functions}\label{sec:gap} + +We will now justify the use of non-adaptive strategies by showing that the optimal solution for this form of non-adaptive strategies yields a higher value than adaptive ones. +For brevity, given a probability vector $\mathbf{p}$ we will write: +\begin{equation}\label{eq:multi} + F(\textbf{p}) \defeq\mathbb{E}_{\mathbf{p}}\big[f(R)\big] + =\sum_{R\subseteq\neigh{X}}p_R f(R) +\end{equation} +as well as $\textbf{p}\circ \textbf{q}$ to denote the component-wise multiplication between vectors $\textbf{p}$ and $\textbf{q}$. Finally, we will use $\mathcal{F}_{A} := \{S \subseteq X : |S|\leq k\}$, and $\mathcal{F}_{NA} :=\{(S,\textbf{q}), |S|+\textbf{p}^T\textbf{q} \leq k, q_u \leq \mathbf{1}_{\{u\in\neigh{S}\}}\}$ to denote the feasible regions of the adaptive and non adaptive problems, respectively. + +%this form of non-adap +%We already know that the adaptivity gap is bounded for a general class of +%influence function. For adaptive functions, we get a stronger result: +%\emph{relaxed-non adaptive policies are stronger than non-adaptive policies}. +% +% +\begin{proposition}\label{prop:gap} +For additive functions given by \eqref{eq:voter}, non-adaptive + policies are stronger than adaptive policies: + \begin{displaymath} + \begin{aligned}[t] + &\max_{S\subseteq X} \sum_{R\subseteq\neigh{S}} p_R + \max_{\substack{T\subseteq R\\|T|\leq k-|S|}}f(T)\\ + &\text{s.t. }S \in \mathcal{F}_{A} + \end{aligned} + \leq + \begin{aligned}[t] + &\max_{\substack{S\subseteq X\\q\in[0,1]^n}} + F(\mathbf{p}\circ\mathbf{q})\\ + &\text{s.t. } (S,q) \in \mathcal{F}_{NA} + \end{aligned} + \end{displaymath} +\end{proposition} + +%\begin{proposition}\label{prop:gap} +%Let $\mathcal{F}_{A} := \{T \subseteq X : |T|\leq k\}$, $\mathcal{F}_{NA} :=\{(T,\textbf{q}), |S|+\textbf{p}^T\textbf{q} \leq k, q_u \leq \mathbf{1}_{\{u\in\neigh{S}\}}\}$. +%For additive functions of the form given by \eqref{eq:voter}, non-adaptive +% policies are stronger than adaptive policies: +% \begin{displaymath} +% \begin{aligned}[t] +% &\max_{S\subseteq X} \sum_{R\subseteq\neigh{S}} p_R +% \max_{\substack{T\subseteq R\\|T|\leq k-|S|}}f(T)\\ +% &\text{s.t. }|S|\leq k +% \end{aligned} +% \leq +% \begin{aligned}[t] +% &\max_{S\subseteq X} \max_{q\in[0,1]^n}F(p\circ q)\\ +% &\text{s.t. }|S|+\sum_{u\in\neigh{X}}p_uq_u \leq k,\; +% q_u \leq \mathbf{1}_{\{u\in\neigh{S}\}} +% \end{aligned} +% \end{displaymath} +%\end{proposition} + +\begin{proof} + We will first show that the optimal adaptive policy can be interpreted as + a non-adaptive policy. Let $S$ be the optimal adaptive + solution and define $\delta_R:\neigh{X}\mapsto \{0,1\}$: + \begin{displaymath} + \delta_R(u) \defeq \begin{cases} + 1&\text{if } u\in\argmax\big\{f(T);\; T\subseteq R,\; |T|\leq + k-|S|\big\} \\ + 0&\text{otherwise} + \end{cases}, + \end{displaymath} + one can write + \begin{displaymath} + \begin{split} + \sum_{R\subseteq\neigh{S}} p_R + \max_{\substack{T\subseteq R\\|T|\leq k-|S|}}f(T) + &= + \sum_{R\subseteq\neigh{S}} p_R + \sum_{u\in\neigh{X}}\delta_R(u)w_u\\ + &= + \sum_{u\in\neigh{X}}w_u\sum_{R\subseteq\neigh{S}}p_R\delta_R(u). + \end{split} + \end{displaymath} + + Let us now define for $u\in\neigh{X}$: + \begin{displaymath} + q_u \defeq \begin{cases} + \sum_{R\subseteq\neigh{S}}\frac{p_R}{p_u}\delta_R(u) + &\text{if }p_u\neq 0\\ + 0&\text{otherwise} + \end{cases}. + \end{displaymath} + This allows us to write: + \begin{displaymath} + \sum_{R\subseteq\neigh{S}} p_R + \max_{\substack{T\subseteq R\\|T|\leq k-|S|}}f(T) + = \sum_{u\in\neigh{X}}p_uq_uw_u = F(\mathbf{p}\circ\mathbf{q}) + \end{displaymath} + where the last equality is obtained from \eqref{eq:multi} by successively using the linearity of the expectation and the linearity of $f$. + + Furthermore, observe that $q_u\in[0,1]$, $q_u=0$ if $u\notin\neigh{S}$ and: + \begin{displaymath} + \begin{split} + |S|+\sum_{u\in\neigh{X}}p_uq_u + &= |S|+\sum_{R\subseteq\neigh{S}}p_R\sum_{u\in\neigh{X}}\delta_R(u)\\ + &\leq |S| + \sum_{R\subseteq\neigh{S}}p_R(k-|S|)\leq k + \end{split} + \end{displaymath} + + Hence, $(S,\mathbf{q})\in\mathcal{F}_{NA}$. In other words, we have written the optimal adaptive solution as a relaxed + non-adaptive solution. This conclude the proof of the proposition. +\end{proof} + +\subsection{From non-adaptive to adaptive solutions}\label{sec:round} +From the above proposition we now know that optimal non-adaptive solutions have +higher values than adaptive solutions. A priori, this does not imply that non-adaptive solutions are good adaptive solutions. More precisely, a non-adaptive solution is a pair $(S, \mathbf{q})$ such that starting from $S$ on the first stage and sampling nodes with probability $\mathbf{q}$ on the second stage will result in a solution which is as good as $\mathrm{A}(S)$ in expectation, where $\mathrm{A}$ denotes the objective function of the adaptive problem \eqref{eq:relaxed}. However, the set resulting from the sampling might exceed the budget on the second stage, hence preventing us from directly obtaining a feasible adaptive solution. + +Fortunately, the probability of exceeding the budget is small enough and with high probability the sampled set will be feasible. This property is leveraged in \cite{vondrak} to design a randomized rounding method with approximation guarantees. This randomized roundings are called \emph{contention resolution schemes}. More precisely, we note that once the set $S$ is fixed, the feasibility constraint of problem~\eqref{eq:relaxed} becomes a single Knapsack constraint, for which \cite{vondrak} constructs a $(1-\varepsilon, 1-\varepsilon)$-balanced contention resolution scheme. Applying Theorem~1.3 of the same paper, this contention resolution scheme will compute from $\mathbf{q}$ a \emph{feasible} random set $I$, such that: +\begin{equation}\label{eq:cr} +\mathbb{E}\big[f(I)\big] +\geq (1-\varepsilon) F(\mathbf{q}) +\end{equation} + +Equation~\eqref{eq:cr} allows us to prove the following proposition, where $\mathrm{OPT}_{NA}$ denotes the optimal value of problem~\eqref{eq:relaxed} and $\mathrm{OPT}_A$ denotes the optimal value of problem~\eqref{eq:problem}. + +\begin{proposition}\label{prop:cr} + Let $(S,\textbf{q})$ be an $\alpha$-approximate solution to the non-adaptive problem \eqref{eq:relaxed}, then $\mathrm{A}(S) \geq \alpha \mathrm{OPT}_A$. +\end{proposition} + +\begin{proof} + Using the definition of $\mathrm{A}(S)$, one can write: + \begin{displaymath} + \mathrm{A}(S) = \sum_{R\subseteq\neigh{S}} p_R + \max_{\substack{T\subseteq R\\|T|\leq k-|S|}}f(T) + \geq \sum_{R\subseteq\neigh{S}} p_R \mathbf{E}\big[f(I)\big] + \end{displaymath} + where the inequality comes from the fact that $I$ is a feasible random set: $|I|\leq k-|S|$, hence the expected value of $f(I)$ is bounded by the maximum of $f$ over feasible sets. + +Equation~\eqref{eq:cr} then implies: +\begin{equation}\label{eq:tmp} + \mathrm{A}(S) + \geq (1-\varepsilon)\sum_{R\subseteq\neigh{S}} p_R F(\mathbf{q}) + = (1-\varepsilon)F(\mathbf{p}\circ\mathbf{q}). +\end{equation} + +Equation~\eqref{eq:tmp} holds for any $\varepsilon\geq 0$. In particular, for $\varepsilon$ smaller than $\inf_{S\neq T} |A(S)-A(T)|$, we obtain that $\mathrm{A}(S)\geq F(\mathbf{p}\circ\mathbf{q})$. Note that such a $\varepsilon$ is at most polynomially small in the size of the instance. +$(S, \mathbf{q})$ is an $\alpha$-approximate non adaptive solution, hence $F(\mathbf{p}\circ\mathbf{q}) \geq \alpha\mathrm{OPT}_{NA}$. We can then conclude by applying Proposition~\ref{prop:gap}. +\end{proof} + +Therefore the adaptive seeding problem reduces to the non-adaptive problem. We will now discuss two approaches to construct non-adaptive solutions. The first is an LP-based approach, and the second is a combinatorial algorithm. Both approaches have the same $(1-1/e)$ approximation ratio, which is then translated to a $(1-1/e)$ approximation ratio for the adaptive seeding problem~\eqref{eq:problem} via Proposition~\ref{prop:cr}. + +\subsection{An LP-Based Approach} +Note that due to linearity of expectation, for a linear function $f$ of the form given by \eqref{eq:voter} we have: +\begin{equation}\label{eq:multi-voter} + \begin{split} + F(\textbf{p}) + &=\mathbb{E}_{p_R}\big[f(R)\big] + =\mathbb{E}_{p_R}\Bigg[\sum_{u\in\neigh{X}}w_u\mathbf{1}_{\{u\in + R\}}\Bigg]\\ + &=\sum_{u\in\neigh{X}}w_u\mathbb{P}[u\in R] + =\sum_{u\in\neigh{X}}p_uw_u + \end{split} +\end{equation} + +Thus, the non-adaptive optimization problem \eqref{eq:relaxed} can be written as: +\begin{displaymath} + \begin{split} + \max_{\substack{S\subseteq X\\q\in[0,1]^n} } + & \sum_{u\in\neigh{X}}p_uq_uw_u\\ + \text{s.t. } & |S|+ \textbf{p}^T\textbf{q} \leq k,\; + q_u \leq \mathbf{1}_{\{u\in\neigh{S}\}} + \end{split} +\end{displaymath} + +The choice of the set $S$ can be relaxed by introducing a variable +$\lambda_v\in[0,1]$ for each $v\in X$. We obtain the following +LP for the adaptive seeding problem: +\begin{equation}\label{eq:lp} + \begin{split} + \max_{\substack{q\in[0,1]^n\\\lambda\in[0,1]^m}} + & \;\sum_{u\in\neigh{X}}p_uq_uw_u\\ + \text{s.t. } & \sum_{v\in X}\lambda_v+\textbf{p}^T\textbf{q} \leq k,\; + q_u \leq \sum_{v\in\neigh{u}} \lambda_v +\end{split} +\end{equation} + +An optimal solution to the above problem can be found using standard LP-solvers, in polynomial time. The solution returned by the LP is \emph{fractional}, and requires a rounding procedure to return a feasible solution to our problem, where $S$ is integral. We briefly describe our approach which uses the \emph{pipage rounding} method.\newline + +\noindent \textbf{Pipage Rounding.} +The pipage rounding method~\cite{pipage} is a deterministic rounding method that can be applied to a variety of problems. In particular, it can be applied to LP-relaxations of the \textsc{Max-K-Cover} problem where we are given a family of sets that cover elements of a universe and the goal is to find $k$ subsets whose union has the maximal cardinality. The LP-relaxation is a fractional solution over subsets, and the pipage rounding procedure then rounds the allocation in linear time, and the integral solution is guaranteed to be within a factor of $(1-1/e)$ of the fractional solution. +We make the following key observation: for any given $\textbf{q}$, one can remove all elements in $\mathcal{N}(X)$ for which $q_{u}=0$, without changing the value of any solution $(\lambda,\textbf{q})$. +Our rounding procedure can therefore be described as follows: given a solution $(\lambda,\textbf{q})$ we remove all nodes $u \in \mathcal{N}(X)$ for which $q_{u}=0$, which leaves us with a fractional solution to a (weighted) version of the \textsc{Max-K-Cover} problem where nodes in $X$ are the sets and the universe is the set of weighted nodes in $\mathcal{N}(X)$ that were not removed. We can therefore apply pipage rounding and lose only a factor of $(1-1/e)$ in quality of the solution. + +\begin{lemma} + For \mbox{\textsc{AdaptiveSeeding-LP}} as defined in \eqref{eq:lp}, any fractional solution $(\lambda, \mathbf{q})\in[0,1]^m\times[0,1]^n$ can be rounded to an integral solution $\bar{\lambda} \in \{0,1\}^{m}$ s.t. $(1-1/e) F(\mathbf{p}\circ\mathbf{q}) \leq A(\bar{\lambda})$ in $O(m + n)$ steps. +\end{lemma} + +\subsection{A Combinatorial Algorithm} +In this section, we will introduce a combinatorial algorithm with an identical approximation guarantee to the LP-based approach. The main idea is to reduce the problem to a monotone submodular maximization problem and apply a variant of the celebrated greedy algorithm~\cite{nemhauser}. +This property is quite a remarkable feature of linear influence models; for influence models such as independent cascade and linear threshold, the adaptive seeding problem does not reduce to submodular maximization, and a completely different approach is required~\cite{singer}. In contrast with standard influence maximization, the submodularity of the non-adaptive seeding problem is not simply a consequence of properties of the influence function. It also strongly relies on the combinatorial structure of the two stage optimization. + +Intuitively, we can think of our problem as trying to find a set $S$ in the first stage, for which the nodes that can be seeded on the second stage have the largest possible value. To formalize this, for a budget $b\in\reals^+$ used in the second stage and a set of neighbors $T\subseteq\mathcal{N}(X)$, we will use +$\mathcal{O}(T,b)$ to denote the solution to: +\begin{equation}\label{eq:knap} + \begin{split} + \mathcal{O}(T,b)\defeq + \max_{q\in[0,1]^n} & \sum_{u\in\neigh{X}} p_uq_uw_u\\ + \text{s.t. } & \mathbf{p}^T\mathbf{q}\leq b\text{ and } q_u=0\text{ if + }u\notin T +\end{split} +\end{equation} + +The optimization problem \eqref{eq:relaxed} for +non-adaptive policies can now be written as: +\begin{equation}\label{eq:sub} + \begin{split} + \max_{S\subseteq X} &\; \mathcal{O}\big(\neigh{S},k-|S|\big)\\ + \text{s.t. } & |S|\leq k + \end{split} +\end{equation} + +We start by proving in Proposition~\ref{prop:sub} that for fixed $t$, $\mathcal{O}(\neigh{\cdot}, t)$ is submodular. This proposition relies on lemmas~\ref{lemma:nd} and~\ref{lemma:sub} about the properties of $\mathcal{O}(T,b)$ first seen as a function $b$, then as a function of $T$. + +\begin{lemma}\label{lemma:nd} + Let $T \subseteq \mathcal{N}(X)$ and $x \in \mathcal{N}(X)$, then + $\mathcal{O}(T\cup\{x\},b)-\mathcal{O}(T,b)$ is + non-decreasing in $b$. +\end{lemma} + +\begin{proof} +\emph{W.l.o.g} we can rename and order the pairs in $T$ so that $w_1\geq w_2\geq\ldots\geq w_m $. +Then, $\mathcal{O}(T,b)$ has the following simple piecewise linear expression: +\begin{displaymath}\label{eq:pw} + \mathcal{O}(T,b) = + \begin{cases} + b w_1&\text{if }0\leq b<p_1\\ + \displaystyle + \sum_{k=1}^{i-1}p_k(w_k-w_i) + + b w_i + &\displaystyle\text{if } 0\leq b - \sum_{k=1}^{i-1}p_k< p_i\\ + \displaystyle + \sum_{k=1}^m p_kw_k + &\displaystyle\text{if } b\geq\sum_{i=1}^m p_k + + \end{cases} +\end{displaymath} + +Let us define for $t\in\reals^+$, $n(t)\defeq \inf\Big\{i\text{ s.t. +} \sum_{k=1}^i p_k > t\Big \}$ with $n(t)=+\infty$ when the set is empty. In +particular, note that $x\mapsto n(t)$ is non-decreasing. Denoting +$\partial_+\mathcal{O}_T$ the right derivative of $\mathcal{O}(T,\cdot)$, one +can write $\partial_+\mathcal{O}_T(t)=w_{n(t)}$, with the convention that +$w_\infty = 0$. + +Writing $i \defeq \sup\Big\{j\text{ s.t. +} w_j\geq w_x\Big\}$, it is easy to see that +$\partial_+\mathcal{O}_{T\cup\{x\}}\geq\partial_+\mathcal{O}_T$. Indeed: +\begin{enumerate} + \item if $n(t)\leq i$ then $\partial_+\mathcal{O}_{T\cup\{x\}}(t) + = \partial_+\mathcal{O}_T(t)= w_{n(t)}$. + \item if $n(t)\geq i+1$ and $n(t-c)\leq i$ then $\partial_+\mathcal{O}_{T\cup\{x\}}(t) + = w_x\geq w_{n(t)}= \partial_+\mathcal{O}_T(t)$. + \item if $n(t-c)\geq i+1$, then $\partial_+\mathcal{O}_{T\cup\{x\}} + = w_{n(t-c)}\geq w_{n(t)}=\partial_+\mathcal{O}_T(t)$. +\end{enumerate} + +Let us now consider $b$ and $c$ such that $b\leq c$. Then, using the integral +representation of $\mathcal{O}(T\cup\{x\},\cdot)$ and $\mathcal{O}(T,\cdot)$, we get: +\begin{multline*} + \mathcal{O}(T\cup\{x\},c)-\mathcal{O}(T\cup\{x\},b)=\int_b^c\partial_+\mathcal{O}_{T\cup\{x\}}(t)dt\\ + \geq\int_b^c\partial_+\mathcal{O}_T(t)dt=\mathcal{O}(T,c)-\mathcal{O}(T,b) +\end{multline*} +Re-ordering the terms, $\mathcal{O}(T\cup\{x\},c)-\mathcal{O}(T,c)\geq +\mathcal{O}(T\cup\{x\},b)-\mathcal{O}(T,b)$ +which concludes the proof of the lemma. +\end{proof} + +\begin{lemma}\label{lemma:sub} + For any $b\in\reals^+$, $\mathcal{O}(T,b)$ is submodular in $T$, $T\subseteq\neigh{X}$. +\end{lemma} + +\begin{proof} + Let $T\subseteq\neigh{X}$ and $x, y\in\neigh{X}\setminus T$. Using the + second-order characterization of submodular functions, it suffices to show + that: + \begin{displaymath}\label{eq:so} + \mathcal{O}(T\cup\{x\},b)-\mathcal{O}(T,b)\geq + \mathcal{O}(T\cup\{y, x\},b)-\mathcal{O}(T\cup\{y\},b) + \end{displaymath} + + We distinguish two cases based on the relative position of $w_x$ and $w_y$. + The following notations will be useful: $S_T^x \defeq \big\{u\in + T\text{ s.t. }w_x\leq w_u\big\}$ and $P_T^x\defeq + T\setminus S_T^x$. + + \textbf{Case 1:} If $w_y\geq w_x$, then one can + write: + \begin{gather*} + \mathcal{O}(T\cup\{y,x\},b) = \mathcal{O}(P_T^y\cup\{y\},b_1)+ + \mathcal{O}(S_T^y\cup\{x\},b_2)\\ + \mathcal{O}(T\cup\{y\},b) = \mathcal{O}(P_T^y\cup\{y\},b_1) + + \mathcal{O}(S_T^y,b_2) + \end{gather*} + where $b_1$ is the fraction of the budget $b$ spent on $P_T^y\cup\{y\}$ and + $b_2=b-b_1$. + + Similarly: + \begin{gather*} + \mathcal{O}(T\cup\{x\},b) = \mathcal{O}(P_T^y, c_1) + \mathcal{O}(S_T^y\cup\{x\},c_2)\\ + \mathcal{O}(T, b) = \mathcal{O}(P_T^y, c_1) + \mathcal{O}(S_T^y,c_2) + \end{gather*} + where $c_1$ is the fraction of the budget $b$ spent on $P_T^y$ and $c_2 + = b - c_1$. + + Note that $b_1\geq c_1$: an optimal solution will first spent as much + budget as possible on $P_T^y\cup\{y\}$ before adding elements in + $S_T^y\cup\{x\}$. + + In this case: + \begin{displaymath} + \begin{split} + \mathcal{O}(T\cup\{x\},b)-\mathcal{O}(T,b)&= + \mathcal{O}(S_T^y\cup\{x\},c_2)+\mathcal{O}(S_T^y,c_2)\\ + &\geq \mathcal{O}(S_T^y\cup\{x\},b_2)+\mathcal{O}(S_T^y,b_2)\\ + & = \mathcal{O}(T\cup\{y, x\},b)-\mathcal{O}(T\cup\{y\},b) + \end{split} + \end{displaymath} + where the inequality comes from Lemma~\ref{lemma:nd} and + $c_2\geq b_2$. + + \textbf{Case 2:} If $w_x > w_y$, we now decompose + the solution on $P_T^x$ and $S_T^x$: + \begin{gather*} + \mathcal{O}(T\cup\{x\},b) = \mathcal{O}(P_T^x\cup\{x\},b_1) + + \mathcal{O}(S_T^x,b_2)\\ + \mathcal{O}(T,b) = \mathcal{O}(P_T^x,c_1)+\mathcal{O}(S_T^x,c_2)\\ + %\intertext{and} + \mathcal{O}(T\cup\{y, x\},b) = \mathcal{O}(P_T^x\cup\{x\},b_1) + + \mathcal{O}(S_T^x\cup\{y\},b_2)\\ + \mathcal{O}(T\cup\{y\},b) = \mathcal{O}(P_T^x,c_1)+\mathcal{O}(S_T^x\cup\{y\},c_2) + \end{gather*} + with $b_1+b_2=b$, $c_1+c_2=b$ and $b_2\leq c_2$. + + In this case again: + \begin{multline*} + \mathcal{O}(T\cup\{x\},b)-\mathcal{O}(T,b)= + \mathcal{O}(S_T^x,b_2)-\mathcal{O}(S_T^x,c_2)\\ + \geq \mathcal{O}(S_T^x\cup\{y\},b_2)-\mathcal{O}(S_T^x\cup\{y\},c_2)\\ + = \mathcal{O}(T\cup\{y, x\},b)-\mathcal{O}(T\cup\{y\},b) + \end{multline*} + where the inequality uses Lemma~\ref{lemma:nd} and $c_2\geq b_2$. + + In both cases, we were able to obtain the second-order characterization of submodularity. This concludes the proof of the lemma. +\end{proof} + +\begin{proposition}\label{prop:sub} + Let $b\in\mathbf{R}^+$, then $\mathcal{O}(\neigh{S},b)$ is submodular in $S$, $S\subseteq X$. +\end{proposition} + +\begin{proof} + Let us consider $S$ and $T$ such that $S\subseteq T\subseteq X$ and $x\in + X\setminus T$. In particular, note that $\neigh{S}\subseteq\neigh{T}$. + + Let us write $\neigh{S\cup\{x\}}=\neigh{S}\cup R$ with $\neigh{S}\cap + R=\emptyset$ and similarly, $\neigh{T\cup\{x\}}=\neigh{T}\cup R'$ with + $\neigh{T}\cap R'=\emptyset$. It is clear that $R'\subseteq R$. Writing $R'=\{u_1,\ldots,u_k\}$: + \begin{multline*} + \mathcal{O}(\neigh{T\cup\{x\}},b)- \mathcal{O}(\neigh{T},b)\\ + =\sum_{i=1}^k\mathcal{O}(\neigh{T}\cup\{u_1,\ldots u_i\},b) + -\mathcal{O}(\neigh{T}\cup\{u_1,\ldots u_{i-1}\},b)\\ + \leq \sum_{i=1}^k\mathcal{O}(\neigh{S}\cup\{u_1,\ldots u_i\},b) + -\mathcal{O}(\neigh{S}\cup\{u_1,\ldots u_{i-1}\},b)\\ + =\mathcal{O}(\neigh{S}\cup R',b)-\mathcal{O}(\neigh{S},b) + \end{multline*} + where the inequality comes from the submodularity of $\mathcal{O}(\cdot,b)$ proved in Lemma~\ref{lemma:sub}. This same function is also obviously set-increasing, hence: + \begin{multline*} + \mathcal{O}(\neigh{S}\cup R',b)-\mathcal{O}(\neigh{S},b)\\ + \leq \mathcal{O}(\neigh{S}\cup R,b)-\mathcal{O}(\neigh{S},b)\\ + =\mathcal{O}(\neigh{S\cup\{x\}},b)-\mathcal{O}(\neigh{S},b) + \end{multline*} + This concludes the proof of the proposition. +\end{proof} + +We can now use Proposition~\ref{prop:sub} to reduce \eqref{eq:sub} to a monotone submodular maximization problem. First, we note that~\eqref{eq:sub} can be rewritten: +\begin{equation}\label{eq:sub-mod} + \begin{split} + &\max_{t}\max_{S\subseteq X} \; \mathcal{O}\big(\neigh{S},t\big)\\ + &\text{s.t. } |S| + t\leq k + \end{split} +\end{equation} + +Intuitively, we fix $t$ arbitrarily so that the inner $\max$ in \eqref{eq:sub-mod} becomes a submodular maximization problem with fixed budget $t$. We then optimize over the value of $t$. Combining this observation with the greedy algorithm for monotone submodular maximization~\cite{nemhauser}, we obtain Algorithm~\ref{alg:comb}, whose performance guarantee is summarized in Proposition~\ref{prop:main_result}. + +\begin{algorithm} + \caption{Combinatorial algorithm} + \label{alg:comb} + \algsetup{indent=2em} + \begin{algorithmic}[1] + \STATE $S\leftarrow \emptyset$ + \FOR{$t=1$ \TO $k-1$} + \STATE $S_t\leftarrow \emptyset$ + \FOR{$i=1$ \TO $k-t$} + \STATE $x^*\leftarrow\argmax_{x\in + X\setminus S_t}\mathcal{O}(\neigh{S_t\cup\{x\}},t) + -\mathcal{O}(\neigh{S_t},t)$\label{line:argmax} + \STATE $S_t\leftarrow S_t\cup\{x^*\}$ + \ENDFOR + \IF{$\mathcal{O}(\neigh{S_t},t)>\mathcal{O}(\neigh{S},k-|S|)$} + \STATE $S\leftarrow S_t$ + \ENDIF + \ENDFOR + \RETURN $S$ + \end{algorithmic} +\end{algorithm} + +\begin{proposition}\label{prop:main_result} + Let $S$ be the set computed by Algorithm~\ref{alg:comb} and let us denote + by $\mathrm{A}(S)$ the value of the adaptive policy selecting $S$ on the first + stage. Then $\mathrm{A}(S) \geq (1-1/e)\mathrm{OPT}_A$. +\end{proposition} + +\begin{proof} + We simply note that the content of the outer \textsf{for} loop on line 2 of Algorithm~\ref{alg:comb} is the greedy submodular maximization algorithm of \cite{nemhauser}. Since $\mathcal{O}(\neigh{\cdot}, t)$ is submodular (Proposition~\ref{prop:sub}), this solves the inner $\max$ in \eqref{eq:sub-mod} with an approximation ratio of $(1-1/e)$. The outer \textsf{for} loop then computes the outer $\max$ of \eqref{eq:sub-mod}. + + As a consequence, Algorithm~\ref{alg:comb} computes a $(1-1/e)$-approximate non-adaptive solution. We conclude by applying Proposition~\ref{prop:cr}. +\end{proof} +\subsection{Running time} +The algorithm described above considers all possible ways to split the seeding budget between the first and the second stage. For each possible split $\{(t,k-t)\}_{t=1\ldots,k-1}$, the algorithm computes an approximation to the optimal non adaptive solution that uses $k-t$ nodes in the first stage and $t$ nodes in the second stage, and returns the solution for the split with the highest value (breaking ties arbitrarily). This process can be trivially parallelized across $k-1$ machines, each performing a computation of a single split. + +A slightly more sophisticated approach is to consider only $\log n$ splits: $(1,k-1),(2,k-2),\ldots,(2^{\lfloor \log n \rfloor},1)$ and then select the best solution from this set. It is not hard to see that in comparison to the previous approach, this would reduce the approximation guarantee by a factor of at most 2: if the optimal solution is obtained by spending $t$ on the first stage and $k-t$ in the second stage, then since $t \leq 2\cdot2^{\lfloor \log t \rfloor}$ the solution computed for $(2^{\lfloor \log t \rfloor}, k - 2^{\lfloor \log t \rfloor})$ will have at least half that value. +More generally, for any $\epsilon>0$ one can parallelize over $\log_{1+\epsilon}n$ machines at the cost of losing a factor of $(1+\epsilon)$ in the approximation guarantee. + + +To implement Algorithm~\ref{alg:comb} efficiently, the computation of the $\argmax$ on line 5 must be dealt with carefully. $\mathcal{O}(\neigh{S_t\cup\{x\}},t)$ is the optimal solution to the fractional Knapsack problem~\eqref{eq:knap} with budget $t$ and can be computed in time $\min(\frac{t}{p_\text{min}},n)$ by iterating over the list of nodes in $\neigh{S_t\cup\{x\}}$ by decreasing order of the degrees. This decreasing order of $\neigh{S_t}$ can be maintained throughout the greedy construction of $S_t$ by: +\begin{itemize} +\item ordering the list of neighbors of nodes in $X$ by decreasing order of the degrees when initially constructing the graph. This is responsible for the $n\log n$ additive factor. +\item when adding node $x$ to $S_t$, observe that $\neigh{S_t\cup\{x\}} = \neigh{S_t}\cup\neigh{\{x\}}$. Hence, if $\neigh{S_t}$ and $\neigh{\{x\}}$ are sorted lists, then $\mathcal{O}(\neigh{S_t\cup\{x\}},t)$ can be computed in a single iteration of length $\min(\frac{t}{p_\text{min}},n)$ where the two sorted lists are merged on the fly. +\end{itemize} +As a consequence, the running time of line 5 is bounded from above by $m\min(\frac{t}{p_\text{min}},n)$. The two nested \textsf{for} loops are responsible for the additional $k^2$ factor. The running time of Algorithm~\ref{alg:comb} is summarized in Proposition~\ref{prop:running_time}. + +\begin{proposition}\label{prop:running_time} + Algorithm~\ref{alg:comb} runs in time $O\big(n\log + n + k^2 m \min(\frac{k}{p_\text{min}},n)\big)$, with $p_\text{min} =\min\{p_u,u\in\neigh{X}\}$. +\end{proposition} + + + + + + diff --git a/paper/sections/appendix.tex b/paper/sections/appendix.tex new file mode 100644 index 0000000..64ca77e --- /dev/null +++ b/paper/sections/appendix.tex @@ -0,0 +1,76 @@ + +\noindent \textbf{From expectation to high probability.} + +%\begin{lemma}\label{lemma:nd} +% Let $A\subseteq\mathcal{U}$ and $x=(v,c)\in\mathcal{U}\setminus A$, then +% the function $b\mapsto \mathcal{O}(A\cup\{x\},b)-\mathcal{O}(A,b)$ is +% non-decreasing over $\reals^+$. +%\end{lemma} + + + + + + +\begin{proof}[of Proposition~\ref{main_result}] + For each realization of the neighbors $R$, let us define by $X_R$ the + random set which includes each $u\in R$ with probability $q_u$ on the + second day and: + \begin{displaymath} + \tilde{X}_R= + \begin{cases} + X_R&\text{if } |X_R|\leq t\\ + \emptyset&\text{otherwise} + \end{cases} + \end{displaymath} + where $t = k-|S|$. $\tilde{X}_R$ is a random variable over the feasible + solutions on the second day. As a consequence: + \begin{displaymath} + A(S) \geq \sum_{R\subseteq\neigh{S}} p_R\mathbb{E}\big[f(\tilde{X}_R)\big] + \end{displaymath} + Let us define by $Y$ the random set which includes each $u\in\neigh{X}$ + with probability $p_uq_u$ and: + \begin{displaymath} + \tilde{Y}= + \begin{cases} + Y&\text{if } |Y|\leq t\\ + \emptyset&\text{otherwise} + \end{cases}. + \end{displaymath} + It is easy to see that $\tilde{X}_R$ is the conditional expectation of + $\tilde{Y}$ given + $R$. Hence: + \begin{displaymath} + \sum_{R\subseteq\neigh{S}} p_R\mathbb{E}\big[f(\tilde{X}_R)\big] + = \mathbb{E}\big[f(\tilde{Y})\big] + \end{displaymath} + But: + \begin{align*} + \mathbb{E}\big[f(\tilde{Y})\big] + &=\sum_{T\subseteq\neigh{X}}\mathbb{P}\big[\tilde{Y}=T\big]f(T) + = \sum_{\substack{T\subseteq\neigh{X}\\|T|\leq + t}}\mathbb{P}\big[Y=T\big]f(T)\\ + &= \mathbb{E}\big[f(Y)\big]-\sum_{\substack{T\subseteq\neigh{X}\\|T|> + t}}\mathbb{P}\big[Y=T\big]f(T) + \end{align*} + Roughly: + \begin{displaymath} + \sum_{\substack{T\subseteq\neigh{X}\\|T|> + t}}\mathbb{P}\big[Y=T\big]f(T)\leq + \frac{1}{2}\mathbb{E}\big[f(Y)\big] + \end{displaymath} + Combining the above inequalities we get: + \begin{displaymath} + A(S)\geq \frac{1}{2} \mathbb{E}\big[f(Y)\big] + \end{displaymath} + But $\mathbb{E}\big[f(Y)\big]$ is precisely the value of the non-adaptive + solution computed by Algorithm~\ref{alg:comb} which is + a $\left(1-\frac{1}{e}\right)$ approximation of the + optimal non adaptive solution. Hence: + \begin{displaymath} + A(S) \geq \frac{1}{2}\left(1-\frac{1}{e}\right) OPT_{NA} + \end{displaymath} + Finally, we conclude with Proposition~\ref{prop:gap} +\end{proof} + + diff --git a/paper/sections/combinatorial.tex b/paper/sections/combinatorial.tex new file mode 100644 index 0000000..b744564 --- /dev/null +++ b/paper/sections/combinatorial.tex @@ -0,0 +1,299 @@ +\subsection{Submodularity of the problem} +Let $\mathcal{U} = \{(v_u,c_u);\, u\in\neigh{X}\}$ with $v_u=p_uw_u$ and +$c_u=p_u$. Let $b\in\reals^+$ and $A\subseteq\mathcal{U}$, we denote by +$\mathcal{O}(A,b)$ the optimal solution to: +\begin{displaymath} + \begin{split} + &\max_{q\in[0,1]^n}\sum_{u\in\neigh{X}}q_uv_u\\ + &\text{s.t. }\sum_{u\in\neigh{X}}q_uc_u\leq b\text{ and } q_u=0\text{ if + }u\notin A +\end{split} +\end{displaymath} +so that the optimization problem \eqref{eq:relaxed-multi} for relaxed +non-adaptive policies can be written: +\begin{equation}\label{eq:sub} + \begin{split} + &\max_{S\subseteq X}\mathcal{O}\big(\neigh{S},k-|S|\big)\\ + &\text{s.t. }|S|\leq k + \end{split} +\end{equation} + +In this section, we will show how \eqref{eq:sub} can be reduced to a submodular +maximization problem, leading to a fast combinatorial algorithm for the +adaptive seeding model in the voter model. + +\begin{lemma}\label{lemma:nd} + Let $A\subseteq\mathcal{U}$ and $x=(v,c)\in\mathcal{U}\setminus A$, then + the function $b\mapsto \mathcal{O}(A\cup\{x\},b)-\mathcal{O}(A,b)$ is + non-decreasing over $\reals^+$. +\end{lemma} + +\begin{proof} +\emph{W.l.o.g} we can rename and order the pairs in $A$ so that: +\begin{displaymath} +\frac{v_1}{c_1}\geq \frac{v_2}{c_2}\geq\ldots\geq\frac{v_m}{c_m}. +\end{displaymath} +Then, $\mathcal{O}(A,b)$ has the following simple piecewise linear expression: +\begin{equation}\label{eq:pw} + \mathcal{O}(A,b) = + \begin{cases} + b\frac{v_1}{c_1}&\text{if }0\leq b<c_1\\ + \sum_{k=1}^{i-1}v_k + \left(b-\sum_{k=1}^{i-1}c_k\right)\frac{v_i}{c_i} + &\text{if } \sum_{k=1}^{i-1}c_k\leq b< \sum_{k=1}^ic_k\\ + \sum_{k=1}^m v_k&\text{if } b\geq\sum_{i=1}^m c_k + + \end{cases} +\end{equation} + +Let us define for $t\in\reals^+$, $n(t)\defeq \inf\Big\{i\text{ s.t. +} \sum_{k=1}^i c_k > t\Big \}$ with $n(t)=+\infty$ when the set is empty. In +particular, note that $x\mapsto n(t)$ is non-decreasing. Denoting +$\partial_+\mathcal{O}_A$ the right derivative of $\mathcal{O}(A,\cdot)$, one +can write $\partial_+\mathcal{O}_A(t) +=\frac{v_{n(t)}}{c_{n(t)}}$, with the convention that +$\frac{v_\infty}{c_\infty} = 0$. + +Writing $i \defeq \sup\Big\{j\text{ s.t. +} \frac{v_j}{c_j}\geq\frac{v}{c}\Big\}$, it is easy to see that +$\partial_+\mathcal{O}_{A\cup\{x\}}\geq\partial_+\mathcal{O}_A$. Indeed: +\begin{enumerate} + \item if $n(t)\leq i$ then $\partial_+\mathcal{O}_{A\cup\{x\}}(t) + = \partial_+\mathcal{O}_A(t)= \frac{v_{n(t)}}{c_{n(t)}}$. + \item if $n(t)\geq i+1$ and $n(t-c)\leq i$ then $\partial_+\mathcal{O}_{A\cup\{x\}}(t) + = \frac{v}{c}\geq\frac{v_{n(t)}}{c_{n(t)}}= \partial_+\mathcal{O}_A(t)$. + \item if $n(t-c)\geq i+1$, then $\partial_+\mathcal{O}_{A\cup\{x\}} + = \frac{v_{n(t-c)}}{c_{n(t-c)}}\geq + \frac{v_{n(t)}}{c_{n(t)}}=\partial_+\mathcal{O}_A(t)$. +\end{enumerate} + +Let us now consider $b$ and $c$ such that $b\leq c$. Then, using the integral +representation of $\mathcal{O}(A\cup\{x\},\cdot)$ and $\mathcal{O}(A,\cdot)$, we get: +\begin{multline*} + \mathcal{O}(A\cup\{x\},c)-\mathcal{O}(A\cup\{x\},b)=\int_b^c\partial_+\mathcal{O}_{A\cup\{x\}}(t)dt\\ + \geq\int_b^c\partial_+\mathcal{O}_A(t)dt=\mathcal{O}(A,c)-\mathcal{O}(A,b) +\end{multline*} +Re-ordering the terms, $\mathcal{O}(A\cup\{x\},c)-\mathcal{O}(A,c)\geq +\mathcal{O}(A\cup\{x\},b)-\mathcal{O}(A,b)$ +which concludes the proof of the lemma. +\end{proof} + +\begin{lemma}\label{lemma:sub} + Let $b\in\reals^+$, then the function $A\mapsto \mathcal{O}(A,b)$ is submodular. +\end{lemma} + +\begin{proof} + Let $A\subseteq\mathcal{U}$ and $x, y\in\mathcal{U}\setminus A$. Using the + second-order characterization of submodular functions, it suffices to show + that: + \begin{equation}\label{eq:so} + \mathcal{O}(A\cup\{x\},b)-\mathcal{O}(A,b)\geq + \mathcal{O}(A\cup\{y\}\cup\{x\},b)-\mathcal{O}(A\cup\{y\},b) + \end{equation} + + Let us write $x=(v_x, c_x)$ and $y=(v_y,c_y)$. We distinguish two cases + based on the relative position of $\frac{v_x}{c_x}$ and $\frac{v_y}{c_y}$. + The following notations will be useful: $S_A^x \defeq \big\{(v,c)\in + A\text{ s.t. }\frac{v_x}{c_x}\leq\frac{v}{c}\big\}$ and $P_A^x\defeq + A\setminus S_A^x$. + + \textbf{Case 1:} If $\frac{v_y}{c_y}\geq \frac{v_x}{c_x}$, then one can + write: + \begin{gather*} + \mathcal{O}(A\cup\{y\}\cup\{x\},b) = \mathcal{O}(P_A^y\cup\{y\},b_1)+ + \mathcal{O}(S_A^y\cup\{x\},b_2)\\ + \mathcal{O}(A\cup\{y\},b) = \mathcal{O}(P_A^y\cup\{y\},b_1) + + \mathcal{O}(S_A^y,b_2) + \end{gather*} + where $b_1$ is the fraction of the budget $b$ spent on $P_A^y\cup\{y\}$ and + $b_2=b-b_1$. + + Similarly: + \begin{gather*} + \mathcal{O}(A\cup\{x\},b) = \mathcal{O}(P_A^y, c_1) + \mathcal{O}(S_A^y\cup\{x\},c_2)\\ + \mathcal{O}(A, b) = \mathcal{O}(P_A^y, c_1) + \mathcal{O}(S_A^y,c_2) + \end{gather*} + where $c_1$ is the fraction of the budget $b$ spent on $P_A^y$ and $c_2 + = b - c_1$. + + Note that $b_1\geq c_1$: an optimal solution will first spent as much + budget as possible on $P_A^y\cup\{y\}$ before adding elements in + $S_A^y\cup\{x\}$. We can now rewrite \eqref{eq:so}: + \begin{displaymath} + \mathcal{O}(S_A^y\cup\{x\},c_2)+\mathcal{O}(S_A^y,c_2)\geq + \mathcal{O}(S_A^y\cup\{x\},b_2)+\mathcal{O}(S_A^y,b_2) + \end{displaymath} + with $c_2\geq b_2$. This inequality is true by Lemma~\ref{lemma:nd}. + + \textbf{Case 2:} If $\frac{v_x}{c_x}\geq \frac{v_y}{c_y}$, we now decompose + the solution on $P_A^x$ and $S_A^x$: + \begin{gather*} + \mathcal{O}(A\cup\{x\},b) = \mathcal{O}(P_A^x\cup\{x\},b_1) + + \mathcal{O}(S_A^x,b_2)\\ + \mathcal{O}(A,b) = \mathcal{O}(P_A^x,c_1)+\mathcal{O}(S_A^x,c_2) + \intertext{and} + \mathcal{O}(A\cup\{y\}\cup\{x\},b) = \mathcal{O}(P_A^x\cup\{x\},b_1) + + \mathcal{O}(S_A^x\cup\{y\},b_2)\\ + \mathcal{O}(A\cup\{y\},b) = \mathcal{O}(P_A^x,c_1)+\mathcal{O}(S_A^x\cup\{y\},c_2) + \end{gather*} + with $b_1+b_2=b$, $c_1+c_2=b$ and $b_2\leq c_2$. The equation \eqref{eq:so} + can be rewritten: + \begin{displaymath} + \mathcal{O}(S_A^x,b_2)-\mathcal{O}(S_A^x,c_2)\geq + \mathcal{O}(S_A^x\cup\{u\},b_2)-\mathcal{O}(S_A^x\cup\{y\},c_2) + \end{displaymath} + Reordering the terms, we get: + \begin{displaymath} + \mathcal{O}(S_A^x\cup\{y\},c_2) -\mathcal{O}(S_A^x,c_2)\geq + \mathcal{O}(S_A^x\cup\{u\},b_2)-\mathcal{O}(S_A^x,b_2) + \end{displaymath} + with $c_2\geq b_2$. This is again true by Lemma~\ref{lemma:nd}. +\end{proof} + +\begin{proposition}\label{prop:sub} + Let $b\in\mathbf{R}^+$, then the function + $S\mapsto\mathcal{O}(\neigh{S},b)$ is submodular over $2^X$. +\end{proposition} + +\begin{proof} + Let us consider $S$ and $T$ such that $S\subseteq T\subseteq X$ and $x\in + X\setminus T$. In particular, note that $\neigh{S}\subseteq\neigh{T}$. + + Let us write $\neigh{S\cup\{x\}}=\neigh{S}\cup R$ with $\neigh{S}\cap + R=\emptyset$ and similarly, $\neigh{T\cup\{x\}}=\neigh{T}\cup R'$ with + $\neigh{T}\cap R'=\emptyset$. Using these notations, it is clear that + $R'\subseteq R$. Let us enumerate the elements in $R'$ using an arbitrary + order: $R'=\{u_1,\ldots,u_k\}$. Then one can write: + \begin{displaymath} + \begin{split} + \mathcal{O}(\neigh{T\cup\{x\}},b)&=\mathcal{O}(\neigh{T}\cup R',b)\\ + &=\sum_{i=1}^k\mathcal{O}(\neigh{T}\cup\{u_1,\ldots u_i\},b) + -\mathcal{O}(\neigh{T}\cup\{u_1,\ldots u_{i-1}\},b)\\ + &\leq \sum_{i=1}^k\mathcal{O}(\neigh{S}\cup\{u_1,\ldots u_i\},b) + -\mathcal{O}(\neigh{S}\cup\{u_1,\ldots u_{i-1}\},b)\\ + &=\mathcal{O}(\neigh{S}\cup R',b)-\mathcal{O}(\neigh{S},b) + \end{split} + \end{displaymath} + where the inequality comes from the submodularity of + $A\mapsto\mathcal{O}(A,b)$ proved in Lemma~\ref{lemma:sub}. This same + function is also obviously set-increasing, hence: + \begin{displaymath} + \begin{split} + \mathcal{O}(\neigh{S}\cup R',b)-\mathcal{O}(\neigh{S},b) + &\leq \mathcal{O}(\neigh{S}\cup R,b)-\mathcal{O}(\neigh{S},b)\\ + &=\mathcal{O}(\neigh{S\cup\{x\}},b)-\mathcal{O}(\neigh{S},b) + \end{split} + \end{displaymath} + This concludes the proof of the proposition. +\end{proof} + +Using Proposition~\ref{prop:sub}, we can finally reduce \eqref{eq:sub} to +a submodular optimization problem by treating $|S|$ as a variable to optimize. +Specifically, \eqref{eq:sub} is equivalent to the following problem: +\begin{equation}\label{eq:sub2} +\begin{split} + \max_{1\leq t\leq k}\max_{|S|\leq k-t}\mathcal{O}(\neigh{S},t) +\end{split} +\end{equation} + +\begin{algorithm} + \caption{Combinatorial algorithm} + \label{alg:comb} + \algsetup{indent=2em} + \begin{algorithmic}[1] + \STATE $S\leftarrow \emptyset$ + \FOR{$t=1$ \TO $k-1$} + \STATE $S_t\leftarrow \emptyset$ + \FOR{$i=1$ \TO $k-t$} + \STATE $x^*\leftarrow\argmax_{x\in + X\setminus S_t}\mathcal{O}(\neigh{S_t\cup\{x\}},t) + -\mathcal{O}(\neigh{S_t},t)$\label{line:argmax} + \STATE $S_t\leftarrow S_t\cup\{x^*\}$ + \ENDFOR + \IF{$\mathcal{O}(\neigh{S_t},t)>\mathcal{O}(\neigh{S},k-|S|)$} + \STATE $S\leftarrow S_t$ + \ENDIF + \ENDFOR + \RETURN $S$ + \end{algorithmic} +\end{algorithm} + +\begin{proposition} + Let $S$ be the set computed by Algorithm~\ref{alg:comb} and let us denote + by $A(S)$ the value of the adaptive policy which selects $S$ on the first + day. Then: + \begin{displaymath} + A(S) \geq \frac{1}{2}\left(1-\frac{1}{e}\right)OPT. + \end{displaymath} + Furthermore, Algorithm~\ref{alg:comb} runs in time $O\left(n\log + n+k^2m\min(\frac{k}{p_\text{min}},n)\right)$, where $m=|X|$, $n=|\neigh{X}|$ + and $p_\text{min} =\min\{p_u,u\in\neigh{X}\}$. +\end{proposition} + +\begin{proof} + For each realization of the neighbors $R$, let us define by $X_R$ the + random set which includes each $u\in R$ with probability $q_u$ on the + second day and: + \begin{displaymath} + \tilde{X}_R= + \begin{cases} + X_R&\text{if } |X_R|\leq t\\ + \emptyset&\text{otherwise} + \end{cases} + \end{displaymath} + where $t = k-|S|$. $\tilde{X}_R$ is a random variable over the feasible + solutions on the second day. As a consequence: + \begin{displaymath} + A(S) \geq \sum_{R\subseteq\neigh{S}} p_R\mathbb{E}\big[f(\tilde{X}_R)\big] + \end{displaymath} + Let us define by $Y$ the random set which includes each $u\in\neigh{X}$ + with probability $p_uq_u$ and: + \begin{displaymath} + \tilde{Y}= + \begin{cases} + Y&\text{if } |Y|\leq t\\ + \emptyset&\text{otherwise} + \end{cases}. + \end{displaymath} + It is easy to see that $\tilde{X}_R$ is the conditional expectation of + $\tilde{Y}$ given + $R$. Hence: + \begin{displaymath} + \sum_{R\subseteq\neigh{S}} p_R\mathbb{E}\big[f(\tilde{X}_R)\big] + = \mathbb{E}\big[f(\tilde{Y})\big] + \end{displaymath} + But: + \begin{align*} + \mathbb{E}\big[f(\tilde{Y})\big] + &=\sum_{T\subseteq\neigh{X}}\mathbb{P}\big[\tilde{Y}=T\big]f(T) + = \sum_{\substack{T\subseteq\neigh{X}\\|T|\leq + t}}\mathbb{P}\big[Y=T\big]f(T)\\ + &= \mathbb{E}\big[f(Y)\big]-\sum_{\substack{T\subseteq\neigh{X}\\|T|> + t}}\mathbb{P}\big[Y=T\big]f(T) + \end{align*} + Roughly: + \begin{displaymath} + \sum_{\substack{T\subseteq\neigh{X}\\|T|> + t}}\mathbb{P}\big[Y=T\big]f(T)\leq + \frac{1}{2}\mathbb{E}\big[f(Y)\big] + \end{displaymath} + Combining the above inequalities we get: + \begin{displaymath} + A(S)\geq \frac{1}{2} \mathbb{E}\big[f(Y)\big] + \end{displaymath} + But $\mathbb{E}\big[f(Y)\big]$ is precisely the value of the non-adaptive + solution computed by Algorithm~\ref{alg:comb} which is + a $\left(1-\frac{1}{e}\right)$ approximation of the + optimal non adaptive solution. Hence: + \begin{displaymath} + A(S) \geq \frac{1}{2}\left(1-\frac{1}{e}\right) OPT_{NA} + \end{displaymath} + Finally, we conclude with Proposition~\ref{prop:gap} +\end{proof} + +\subsection{From expectation to high probability} + +\subsection{Questions} + +\begin{itemize} + \item Can it be parallelized (map-reduce)? +\end{itemize} diff --git a/paper/sections/experiments.log b/paper/sections/experiments.log new file mode 100644 index 0000000..e69de29 --- /dev/null +++ b/paper/sections/experiments.log diff --git a/paper/sections/experiments.tex b/paper/sections/experiments.tex new file mode 100644 index 0000000..1a085d1 --- /dev/null +++ b/paper/sections/experiments.tex @@ -0,0 +1,128 @@ +In this section, we give experimental evidence of the validity of our approach. Specifically, we show that our algorithms obtain significant improvement over standard influence maximization, that these improvements are observed in various scenarios (different verticals, different models of influence propagation), and that our approach is efficient in terms of running-time and scalable to large social networks. + +\subsection{Data description} + +Our main testbed is the friendship graph of the social network service Facebook~\cite{facebook}. We start by observing that an efficient campaign run on a social network will primarily target users who have already expressed interests in the topic being promoted. In the adaptive seeding terminology, these users constitute the set of initial nodes that can be targeted during the seeding phase. + +In order to reproduce this process, we selected ten different verticals (topics) and for each of these verticals, a person, an institution or an entity whose associated Facebook page is regularly used for promotional posts related to this topic. On each of these pages, we selected a recent post (posted no later than January 2014) with approximately 1,000 \emph{likes}. The set of users who liked those posts constitute our initial sets of nodes. + +We then crawled the social network of these sets: for each user, we collected her list of friends, and the degrees (number of friends) of these friends. Table~\ref{tab:data} summarizes statistics about the collected data. + +\begin{table}[h!] + \small + \centering + \setlength{\tabcolsep}{3pt} + \begin{tabular}{llrr} + \toprule + Vertical & Page & $m$ & $n$ \\%& $S$ & $F$\\ + \midrule + Charity & Kiva & 978 & 131334 \\%& 134.29 & 1036.26\\ + Travel & Lonely Planet & 753 & 113250 \\%& 150.40 & 898.50\\ + Public Action & LaManifPourTous & 1041 & 97959 \\%& 94.10 & 722.02\\ + Fashion & GAP & 996 & 115524 \\%& 115.99 & 681.98\\ + Events & Coachella & 826 & 102291 \\%& 123.84 & 870.16\\ + Politics & Green Party & 1044 & 83490 \\%& 79.97 & 1053.25\\ + Technology & Google Nexus & 895 & 137995 \\%& 154.19 & 827.84\\ + News & The New York Times & 894 & 156222 \\%& 174.74 & 1033.94 \\ + Consumption & Peet's & 776 & 56268 \\%& 72.51 & 520.47\\ + Entertainment & HBO & 828 & 108699 \\%& 131.28 & 924.09\\ + \bottomrule +\end{tabular} +\caption{Dataset statistics. $m$: number of initial users, $n$: number of friends of the initial users.} +%$S$: avg. degree of an initial user, $F$: avg. degree of a friend of an initial user.} +\label{tab:data} +\end{table} + +We note that depending on the privacy settings of the initial users, it was not always possible to access their list of friends. We decided to remove these users since their ability to spread information could not be readily determined. This effect, combined with various errors encountered during the data collection, accounts for an approximate 15\% reduction between the users who liked a post and the number of users in the datasets we used. + +\begin{figure}[t!] + \centering + \includegraphics[scale=0.7]{images/para.pdf} + \caption{Comparison of the average degree of the initial users and the average degree of their friends.} + \label{fig:para} +\end{figure} + +Following our discussion in the introduction, we observe that on average, the degrees of initial users is much lower than the degrees of their friends. This is highlighted on Figure~\ref{fig:para} and justifies our approach. + +\subsection{Performance of Adaptive Seeding} +\label{sec:performance} + +We start by comparing the performance of adaptive seeding to standard influence maximization approaches. The following heuristics were considered: +\begin{itemize} + \item \emph{Max degree:} selecting as many initial users as the budget permits, in decreasing order of degrees. + \item \emph{Random:} selecting a random sample of initial users of the size permitted by the budget. + \item \emph{Random friend:} spending half of the budget to select a random sample of initial users. For each of the selected random users, we then select randomly one of her friend (hence spending the total budget overall). +\end{itemize} + +\begin{figure*}[p] + \centerline{\includegraphics{images/perf.pdf}} + \caption{Performance of adaptive seeding compared to other influence maximization approaches. The influence, on the $y$-axis is displayed in logarithmic scale and is measured by the sum of the degrees of the selected users~\eqref{eq:voter}. The budget is represented on the $x$-axis as a fraction of the seed size.} + \label{fig:performance} +\end{figure*} + +Figure~\ref{fig:performance} compares the performance of \emph{Adaptive seeding}, our own approach, to the afore-mentioned approaches for all the verticals we collected. For this figure, the probability of initial users' friends joining on the second day was set to one. Section~\ref{sec:robustness} explores other influence propagation scenarios. + +We note that the \emph{Random friend} heuristic significantly outperforms \emph{Max degree}. Using the same budget, the degree gain induced by moving from initial users to their friends is such that selecting at random among the initial users' friends already does better than the best heuristic restricted only on initial users. Using \emph{Adaptive seeding} to optimize the choice of initial users based on their friends' degrees then results in an order of magnitude increase over \emph{Random friend}, consistently for all the verticals. + +We also compare the relative improvements of \emph{Adaptive seeding} over \emph{Max degree} across the different verticals. The results are shown in Figure~\ref{fig:compare}. +\begin{figure}[ht!] + \centerline{ \includegraphics[scale=0.7]{images/comp.pdf} } + \vspace{-10pt} + \caption{Ratio of the performance of adaptive seeding to max. degree for several verticals.} + \label{fig:compare} +\end{figure} + +\subsection{Robustness to spread of influence frictions} +\label{sec:robustness} + +The results presented in Section~\ref{sec:performance} were computed assuming a probability of propagation between the two stages of adaptive seeding equal to one. Estimating this probability is a research problem on its own; however, we note that it can be controlled to some extent by the social networking service on which the campaign is being run. By showing prominently the campaign material (sponsored links, fund-raising banners, etc.), the conversion rate can be increased beyond what would happen via regular word-of-mouth propagation. + +Figure~\ref{fig:prob} shows the impact of the probability of propagation between the two stages. For several values of $p$, we computed the performance of \emph{Adaptive seeding} when each friend of a seeded initial user joins during the second stage independently with probability $p$. We see that even with $p=0.01$, \emph{Adaptive seeding} still outperforms \emph{Max degree}. As $p$ increases, the performance of \emph{Adaptive seeding} quickly increases and reaches $80\%$ of the values of Figure~\ref{fig:performance} at $p=0.5$. + +\begin{figure}[ht!] + \begin{subfigure}[t]{0.23\textwidth} + \includegraphics[scale=0.45]{images/prob.pdf} + \vspace{-10pt} + \caption{} + \label{fig:prob} +\end{subfigure} +\begin{subfigure}[t]{0.23\textwidth} + \includegraphics[scale=0.45]{images/hbo_likes.pdf} + \vspace{-10pt} + \caption{} + \label{fig:killer} + \end{subfigure} + \caption{(a) Performance of Adaptive seeding in logarithmic scale for various propagation probabilities. (b) In logarithmic scale, performance of \emph{Adaptive seeding} when restricted to users who \emph{liked} HBO (\textsf{Adapt. seed. (rest.)}), compared to \emph{Max degree} and the unrestricted \emph{Adaptive seeding}.} +\end{figure} + +In practice, the propagation probability will vary among individuals. However, for those who have already expressed interest in the promoted content, we can expect this probability to be close to one. For our next experiment, we chose a vertical (HBO) and trimmed the social graph we collected by only keeping on the second stage users who indicated this vertical (HBO) in their list of interests. Figure~\ref{fig:killer} shows that even on this very restricted set of users, \emph{Adaptive seeding} still outperforms \emph{Max degree} and reaches approximately $50\%$ of the unrestricted adaptive seeding. + +%\item Fix budget; plot the number of people that tweeted coffee between 9am to 10am, between 10am to 11am, between 11am to noon,..., +%\item Argue: if the probability for a friend joining is small, then as long as each person has a few high degree friends, we will get a constant fraction of high degree friends joining, in expectation. +%\item Experiment only on friends who also followed the topic: go to a vertical with a lot of followers (but hopefully number of ``likes'' are under 1000) and perform the adaptive seeding experiment only on people who also follow that vertical. Should roughly be 3x requests as other experiments. +%\end{itemize} + +\subsection{Scalability}\label{sec:scalability} + +Finally, we look at the scalability of our approaches. More specifically, we compare the running time of the LP-based approach and the combinatorial approach for different instance sizes. + +Figure~\ref{fig:time} shows the running time and number of CPU cycles used by the LP algorithm and the combinatorial algorithm as a function of the network size $n$. The varying size of the network was obtained by randomly sampling a varying fraction of initial users and then trimming the social graph by only keeping friends of this random sample on the second stage. The computations were run on Intel Core i5 CPU 4x2.40Ghz. The LP solver used was CLP~\cite{clp}. + +\begin{figure}[h!] + \centerline{ \includegraphics[scale=0.9]{images/time.pdf} } + \vspace{-10pt} + \caption{Running time and number of CPU cycles of the combinatorial algorithm and the LP algorithm as a function of the number of nodes $n$. First row with budget $k=100$, second row with budget $k=500$.} + \label{fig:time} +\end{figure} + +We observe that for a \emph{small} value of the budget $k$ ($k=100$, first row of Figure~\ref{fig:time}), the combinatorial algorithm outperforms the LP algorithm. When $k$ becomes \emph{large} ($k=500$, second row of Figure~\ref{fig:time}), the LP algorithm becomes faster. This can be explained by the $k^2$ factor in the running time guarantee of the combinatorial algorithm (see Proposition~\ref{prop:running_time}). Even though the asymptotic $n\log n$ guarantee of the combinatorial algorithm should theoretically outperform the LP-based approach for large $n$, we were not able to observe it for our instance sizes. In practice, one can choose which of the two algorithms to apply depending on the relative sizes of $k$ and $n$. + +%\noindent \textbf{Others} +%\begin{itemize} +%\item One plot with Twitter data on the same verticals/ same posts. +%\item Run pipeline on available data sets, with random samples; +%\item It's true that adaptive seeding is looking at more people, but so what? If you waited a day, it would still be better: take a vertical, split it at random to two days. Perform adaptive seeding on one day, and compare to influence max. on two days. +%\item compare to other influence maximization algorithms? +%\item test on several public datasets +%\item LP vs combinatorial algorithm vs sampling running time +%\end{itemize} diff --git a/paper/sections/introduction.log b/paper/sections/introduction.log new file mode 100644 index 0000000..e69de29 --- /dev/null +++ b/paper/sections/introduction.log diff --git a/paper/sections/introduction.tex b/paper/sections/introduction.tex new file mode 100644 index 0000000..6c2e345 --- /dev/null +++ b/paper/sections/introduction.tex @@ -0,0 +1,92 @@ + + + +%The massive adoption of social networking services in recent years creates a unique platform for disseminating information and promoting ideas. Effective means to spread information through this platform are continuously being developed, and in particular methods for selecting influential users who can trigger large word-of-mouth cascade have been heavily studied throughout the past decade. Initially studied by Domingos and Richarson~\cite{} and formalized by Kempe +% +% +%Effective means to spread information through this platform are continuously being developed, and in particular methods for s +The massive adoption of social networking services in recent years creates a unique platform for promoting ideas and spreading information. The joy and ease of communicating through online social networks leaves traces of behavioral data which allow observing, predicting and even engineering processes of information diffusion. First posed by Domingos and Richardson~\cite{DR01,RD02} and elegantly formulated and further developed by Kempe, Kleinberg, and Tardos~\cite{KKT03}, \emph{influence maximization} is the algorithmic challenge of selecting individuals who can serve as early adopters of a new idea, product, or technology in a manner that will trigger a large cascade in the social network. Since its inception, numerous techniques and improvements have been developed ranging from sophisticated predictive models of influence ~\cite{LAH06,RLK10,BHMW11,ACKS13,manuel2013icml,du13nips} to fast approximation methods~\cite{LKGFVG07,MR07,C08,KDD11,borgs2012influence}. + +While there has been a great deal of progress on efficient algorithmic methods for this problem and impressive methods for learning models of influence from data, a fundamental problem has been largely overlooked. Due to the heavy-tailed degree distribution of social networks, influential users are rare, and thus the application of influence maximization techniques can often become ineffective. + +For a concrete example, consider a scenario where the goal is to select influential users who visit an online store and reward them for promoting a product through their social network. In such a case, if the users who visit the online store are not influential, even the best techniques for identifying influential users would have poor performance. \newline + +\begin{figure} + \centering + \includegraphics[scale=0.55]{images/dist.pdf} + \caption{CDF of the degree distribution of users who liked a post by Kiva on Facebook and that of their friends.} + \label{fig:para} +\end{figure} + + +\noindent \textbf{The power of random neighbors.} Remarkably, while a random individual in a social networks is not likely to be influential, it turns out that she is likely to know someone who is. Recent work shows that for any network with a power law degree distribution with a small fraction of random edges, with constant probability there is an asymptotic gap between influence (either the total number of neighbors or sum of degrees) of small samples of the network and that of their neighbors~\cite{LS13}. %Intuitively, as influential nodes are well connected, one can hope that many users know an influential user who can serve as an early adopter. +The implication is that when considering the accessible users (e.g. those who visit the online store) as random samples from a social network, any algorithm which can use their neighbors as influencers will have dramatic improvement over the direct application of influence maximization over the accessible users.\newline + +%\begin{figure*}[t!] +% \centering +% \includegraphics[scale=0.60]{images/dist.pdf} +% \caption{CDF of the degree distribution of seed users and their friends.} +% \label{fig:para} +%\end{figure*} + + + +\noindent \textbf{Adaptive Seeding.} +An alternative approach to spending the entire budget on the users who are accessible is to follow a two-stage approach. In the first stage, one can spend a fraction of the budget on the accessible users to invite their friends to participate in the campaign, hope their friends arrive, and in the second stage spend the rest of the budget on the friends who arrived. This approach, called \emph{adaptive seeding} has been recently formalized in~\cite{singer}. As in the standard formulation of influence maximization, the setup in adaptive seeding includes a network, a budget, and an influence function. %which encodes the expected number of nodes influenced as a result of selecting a subset in the network. +In addition, there is a subset of nodes $X$, the set of accessible users, and their neighbors $\mathcal{N}(X)$, where each neighbor has some probability indicating their likelihood to arrive if invited. The framework is a two-stage stochastic optimization problem. In the first stage any fraction of the budget can be used to select a subset of nodes in $X$, and as a result each neighbor of this set is then realized independently. In the second stage the remaining budget can be used to select from the set of neighbors that arrived. The goal is to select a subset of nodes in $X$, s.t. the influence function is maximized in expectation over all possible arrivals of the neighbors. The main result in~\cite{singer} is a constant factor approximation algorithm for well-studied influence models such as independent cascade and linear threshold. +%More formally, adaptive seeding is phrased as a two-stage stochastic optimization problem. + +\subsection{A scalable approach to adaptive seeding} +The constant-factor approximation guarantees for adaptive seeding are, at large, a theoretical triumph. +Although the algorithms for adaptive seeding have desirable approximation guarantees~\cite{singer}, they rely on various forms of sampling, which creates significant blowup in the input size. While such techniques provide strong theoretical guarantees, for social network data sets which are often either large or massive, such approaches are inapplicable. The natural question is therefore: + +\begin{center} +\textit{Is adaptive seeding scalable?} +\end{center} + +In this paper our main goal is to develop scalable approaches to adaptive seeding and to provide compelling experimental evidence of the dramatic impact such approaches can have in various applications of influence maximization. +\newline + +\noindent \textbf{Challenges.} +The challenges in designing adaptive seeding algorithms are due to both the combinatorial and stochastic nature of the problem. The combinatorial aspect involves the selection of the nodes in the first stage which affects which nodes will realize in the second stage. As we will later show, this aspect makes the problem $\textsc{NP}$-Hard even for the simplest of objective functions. The stochastic aspect requires the optimization to be over potentially exponentially-many realizations. A common approach in stochastic optimization is Sample Average Approximation (SAA). The main idea behind SAA is to sample realizations of the second stage, solve the optimization problem by taking a solution which is optimal on average over the sampled instances. + For the instances we are interested in here that have size of over $N=10^5$ nodes, the required number of samples are on the order of $O(N^3)$, the algorithms can have $O(N^2)$ running time, and the total running time is then on the order of $10^{30}$ operations and SAA is simply infeasible.\footnote{In \cite{singer} SAA is used for linear models. For models such as independent cascade and linear threshold, a different sampling method is introduced which requires similar blowup in the input size to generate a concave relaxation of the optimization problem.}\newline + +%The first of these challenges can be addressed by sampling realizations of the +%neighbors $R$ and averaging over them to get an arbitrarly-accurate +%approximation of the objective function. This approach, which is widely used in +%classical influence maximization, has been succesfully applied in \cite{singer} +%to obtain general guarantees on the approximability of the adaptive seeding +%problem. +% +%The second challenge has been addressed in \cite{singer} by considering relaxed +%an non-adaptive policies which are discussed in Section~\ref{sec:relaxed}. + + + +\noindent \textbf{Stochastic optimization sans sampling.} +In this paper we develop a framework for adaptive seeding which circumvents the use of sampling, while maintaining desirable approximation guarantees. We say that a policy is \emph{adaptive} if it selects nodes in the first stage, and only after the realization of their neighbors, selects a subset of nodes with the remaining budget in the second stage. In contract, a \emph{non-adaptive} policy makes all its decisions before the realizations occur. +The framework we develop in this work involves designing non-adaptive policies which could then be turned into adaptive ones. At a high level, the main idea would be to use a particular version of non-adaptive policies whose optimal solution is an upper bound to the optimal adaptive policy. We will then argue that a solution to the non-adaptive problem can be turned into a solution to the adaptive policy, without losing almost any value. This will therefore reduce our problem to that of designing solutions to the non-adaptive problem we define, for which we then develop specialized algorithms. The main advantage in the non-adaptive framework is that unlike standard approaches in stochastic optimization, it avoids using sampling. As we will later discuss, this dramatically reduces the running time of the algorithms, both in theory and in practice.\newline + +%\noindent \textbf{Main results.} +\subsection{Main results} +Our results are for linear models of influence, i.e. models for which the influence of a set can be expressed as the sum of the influence of its members. While this class does not include models such as the independent cascade and the linear threshold model, it includes the well-studied \emph{voter model}~\cite{holley1975ergodic} and measures such as node degree and click-through-rate of users which serve as a natural proxies of influence in many settings. In comparison to submodular influence functions, the relative simplicity of linear models allows making substantial progress on this challenging problem. +Using this framework, we develop two algorithms, both achieving an approximation ratio of $(1-1/e)$ for the adaptive problem. The first algorithm is implemented through a linear program, which proves to be extremely efficient over instances where there is a large budget. The second approach is a combinatorial algorithm with the same approximation guarantee which has good theoretical guarantees on its running time and does well on instances with smaller budgets. + +To show the applicability of these approaches, and the potential of adaptive seeding at large, we performed several experiments on real social network data sets. We collected publicly available data from Facebook on users who expressed interest (``liked'') a certain post from a topic they follow and data on their friends. The premise here is that such users mimic potential participants in a viral marketing campaign. The performance of our algorithms on these data sets shows adaptive seeding can have dramatic improvements over standard approaches for influence maximization. + + + + +%\subsection{Stochastic optimization sans sampling} +%A common approach in stochastic optimization is Sample Average Approximation (SAA). +%The main idea behind SAA is to sample realizations of the second stage, solve the optimization problem on the sampled instances, and average the solution. Often, when the number of samples is polynomial in the input size of the problem. In our case the problem is too large. +% +%In this paper we show a new technique for solving stochastic optimization problems which does not use sampling. +% +% +%\subsection{Roadmap} +%The main framework we apply in this paper is to develop non-adaptive algorithms which we will then use to create adaptive solutions. At a high level, the main idea would be to use a particular version of non-adaptive algorithms whose optimal solution is an upper bound to the optimal adaptive policy. We will then argue that a solution to the non-adaptive problem can be turned into a solution to the adaptive policy, without losing almost any value. This will therefore reduce our problem to that of designing solutions to the non-adaptive problem we define, for which we develop specialized algorithms. +% +%Beyond the approximation guarantees, the main advantage in the non-adaptive framework is that unlike standard approaches in stochastic optimization, it avoids using sampling. As we will later discuss, this dramatically reduces the running time the algorithms, both in theory and practice. +% +% diff --git a/paper/sections/lp.log b/paper/sections/lp.log new file mode 100644 index 0000000..e69de29 --- /dev/null +++ b/paper/sections/lp.log diff --git a/paper/sections/model.tex b/paper/sections/model.tex new file mode 100644 index 0000000..10c34d0 --- /dev/null +++ b/paper/sections/model.tex @@ -0,0 +1,67 @@ +%\subsection{Problem and notations} +Let us begin by introducing the following notation. +%We will use the following notation to formally discuss the model. +Given a graph $G=(V,E)$, for a node $u\in V$ we denote by $\neigh{u}$ +the neighborhood of $u$. By extension, for any subset of nodes $S\subseteq V$, +$\neigh{S}\defeq \bigcup_{u\in S}\neigh{u}$ will denote the neighborhood of +$S$. The notion of influence in the graph is captured by a function +$f:2^{|V|}\rightarrow \reals_+$ mapping a subset of nodes to a non-negative +influence value.\newline + +\noindent \textbf{The adaptive seeding model.} +The input of the \emph{adaptive seeding} problem is a set of initial nodes +$X\subseteq V$ and for any node $u\in\neigh{X}$ a probability $p_u$ that $u$ +realizes if one of its neighbor in $X$ is seeded. We will write $m=|X|$ and $n=|\neigh{X}|$ the parameters controlling the input size. The seeding process +is the following: +\begin{enumerate} + \item \emph{Seeding:} the seeder selects a subset of nodes $S\subseteq + X$ among the initial nodes. + \item \emph{Realization of the neighbors:} every node $u\in\neigh{S}$ + realizes independently with probability $p_u$. We denote by + $R\subseteq\neigh{S}$ the subset of nodes that is realized during this + stage. + \item \emph{Influence maximization:} the seeder selects the set of nodes + $T\subseteq R$ that maximizes the influence function $f$. +\end{enumerate} + +There is a budget constraint $k$ on the total number of nodes that can be +selected: $S$ and $T$ must satisfy $|S|+|T|\leq k$. The seeder chooses the set +$S$ before observing the realization $R$ and thus wishes to select optimally in +expectation over all such possible realizations. Formally, the objective can be stated +as: +\begin{equation}\label{eq:problem} + \begin{split} + &\max_{S\subseteq X} \sum_{R\subseteq\neigh{S}} p_R + \max_{\substack{T\subseteq R\\|T|\leq k-|S|}}f(T)\\ + &\text{s.t. }|S|\leq k + \end{split} +\end{equation} +where $p_R$ is the probability that the set $R$ realizes under the +probabilities $p_u,\,u\in\neigh{S}$: +\begin{displaymath} + p_R \defeq \prod_{u\in R}p_u\prod_{u\in\neigh{S}\setminus R}(1-p_u) +\end{displaymath} + +It is important to note that the process through which nodes arrive in the second stage is \emph{not} an influence process. The nodes in the second stage arrive if they are willing to spread information in exchange for a unit of the budget. Only when they have arrived does the influence process occur. This process is encoded in the influence function and occurs during the influence maximization stage without incentivizing nodes along the propagation path.\newline + + +\noindent \textbf{Influence functions.} +In this paper we focus on \emph{linear} (or additive) influence models: influence models for which the value of a subset of nodes can be expressed as a weighted sum of their individual influence. +One important example of such models is the \emph{voter model} \cite{richardson} used to represent the spread of opinions in a social network: at each time step, a node +adopts an opinion with a probability equal to the fraction of its neighbors +sharing this opinion at the previous time step. Formally, this can be written +as a discrete-time Markov chain over opinion configurations of the network. +In this model influence maximization amounts to ``converting'' the +optimal subset of nodes to a given opinion at the initial time so as to +maximize the number of converts after a given period of time. +Remarkably, a simple analysis shows that under this model, the influence +function $f$ is additive: +\begin{equation}\label{eq:voter} + \forall S\subseteq V,\; f(S) = \sum_{u\in S} w_u +\end{equation} +where $w_u, u\in V$ are weights which can be easily computed from the powers of +the transition matrix of the Markov chain. This observation led to the +development of fast algorithms for influence maximization under the voter +model~\cite{even-dar}.\newline + +\noindent \textbf{\textsc{NP}-Hardness.} In contrast to standard influence maximization, adaptive seeding is already \textsc{NP}-Hard even for the simplest influence functions. In the case when $f(S)=|S|$ and all probabilities equal one, the decision problem is whether given a budget $k$ and target value $\ell$ there exists a subset of $X$ of size $k-t$ which yields a solution with expected value of $\ell$ using $t$ nodes in $\mathcal{N}(X)$. This is equivalent to deciding whether there are $k-t$ nodes in $X$ that have $t$ neighbors in $\mathcal{N}(X)$. To see this is \textsc{NP}-hard, consider reducing from \textsc{Set-Cover} where there is one node $i$ for each input set $T_i$, $1\leq i\leq n$, with $\neigh{i}= T_i$ and integers $k,\ell$, and the output is ``yes'' if there is a family of $k$ sets in the input which cover at least $\ell$ elements, and ``no'' otherwise. diff --git a/paper/sections/performance.tex b/paper/sections/performance.tex new file mode 100644 index 0000000..8b13789 --- /dev/null +++ b/paper/sections/performance.tex @@ -0,0 +1 @@ + diff --git a/paper/sections/related.tex b/paper/sections/related.tex new file mode 100644 index 0000000..b4200c1 --- /dev/null +++ b/paper/sections/related.tex @@ -0,0 +1,9 @@ +\subsection{Related work} +Influence maximization was introduced by Domingos and Richardson~\cite{DR01, RD02}, and later formulated by Kempe, Kleinberg and Tardos~\cite{KKT03, KKT05}, and has been extensively studied since. Kempe, Kleinberg and Tardos~\cite{KKT03, KKT05} were able to cast this problem as a submodular optimization problem for many classes of influence models, hence allowing for algorithms with good approximations guarantees. Further refinements of the influence models and associated approximation guarantees can be found in \cite{MR07, C08}. In~\cite{even-dar}, the authors look at the special case of the voter model and design efficient algorithms in this setting. + +Our two-stage model for influence maximization is related to the field of stochastic optimization where problems are commonly solved using the \emph{sample average approximation} method \cite{SampleAverage}. In \cite{dean2004approximating, gupta2012approximation}, the authors use a notion of non-adaptive solutions related though not equivalent to ours. + +%The problem we study is the same as in \cite{singer} but our goals are different. +%Our main goal here is to obtain scalable algorithms that can be applied on the datasets we collected. + +Other models of adaptive optimization have been previously studied in the context of influence maximization. In \cite{asadpour2008stochastic}, the authors study a stochastic sequential submodular maximization problem where at each step an element is chosen, its realization is revealed and the next decision is made. Golovin and Krause \cite{golovin2011adaptive} study a similar model and apply it to a multi-stage influence maximization problem. We note that contrary to our model, the decision made at a given stage does not affect the following stages as the entire set of nodes is available as potential seeds at every stage. |