From 31d3855776bae984c3afc0afa8aabd4241fdc45f Mon Sep 17 00:00:00 2001 From: Thibaut Horel Date: Sun, 15 Mar 2015 22:07:19 -0400 Subject: Poster abstract: introduction --- poster_abstract/images/adaptive_seeding.pdf | Bin 0 -> 15465 bytes poster_abstract/images/beta.pdf | Bin 0 -> 150198 bytes poster_abstract/images/comp.pdf | Bin 0 -> 107708 bytes poster_abstract/images/comp2.pdf | Bin 0 -> 108450 bytes poster_abstract/images/deg.pdf | Bin 0 -> 150213 bytes poster_abstract/images/dist.pdf | Bin 0 -> 106821 bytes poster_abstract/images/gauss.pdf | Bin 0 -> 150195 bytes poster_abstract/images/hbo_likes.pdf | Bin 0 -> 136434 bytes poster_abstract/images/para.pdf | Bin 0 -> 105140 bytes poster_abstract/images/perf2.pdf | Bin 0 -> 145513 bytes poster_abstract/images/perf3.pdf | Bin 0 -> 148148 bytes poster_abstract/images/perf_synth.pdf | Bin 0 -> 140975 bytes poster_abstract/images/power.pdf | Bin 0 -> 150214 bytes poster_abstract/images/prob.pdf | Bin 0 -> 223953 bytes poster_abstract/images/sampling.pdf | Bin 0 -> 138009 bytes poster_abstract/images/samplinga.pdf | Bin 0 -> 138111 bytes poster_abstract/images/synthetic.pdf | Bin 0 -> 110720 bytes poster_abstract/images/time.pdf | Bin 0 -> 139236 bytes poster_abstract/images/usandthem.pdf | Bin 0 -> 136492 bytes poster_abstract/images/usandthem.png | Bin 0 -> 63022 bytes poster_abstract/images/voter.pdf | Bin 0 -> 108920 bytes poster_abstract/main.tex | 86 +++++++++++++++++++++++----- 22 files changed, 71 insertions(+), 15 deletions(-) create mode 100644 poster_abstract/images/adaptive_seeding.pdf create mode 100644 poster_abstract/images/beta.pdf create mode 100644 poster_abstract/images/comp.pdf create mode 100644 poster_abstract/images/comp2.pdf create mode 100644 poster_abstract/images/deg.pdf create mode 100644 poster_abstract/images/dist.pdf create mode 100644 poster_abstract/images/gauss.pdf create mode 100644 poster_abstract/images/hbo_likes.pdf create mode 100644 poster_abstract/images/para.pdf create mode 100644 poster_abstract/images/perf2.pdf create mode 100644 poster_abstract/images/perf3.pdf create mode 100644 poster_abstract/images/perf_synth.pdf create mode 100644 poster_abstract/images/power.pdf create mode 100644 poster_abstract/images/prob.pdf create mode 100644 poster_abstract/images/sampling.pdf create mode 100644 poster_abstract/images/samplinga.pdf create mode 100644 poster_abstract/images/synthetic.pdf create mode 100644 poster_abstract/images/time.pdf create mode 100644 poster_abstract/images/usandthem.pdf create mode 100644 poster_abstract/images/usandthem.png create mode 100644 poster_abstract/images/voter.pdf (limited to 'poster_abstract') diff --git a/poster_abstract/images/adaptive_seeding.pdf b/poster_abstract/images/adaptive_seeding.pdf new file mode 100644 index 0000000..0b20ac0 Binary files /dev/null and b/poster_abstract/images/adaptive_seeding.pdf differ diff --git a/poster_abstract/images/beta.pdf b/poster_abstract/images/beta.pdf new file mode 100644 index 0000000..3264317 Binary files /dev/null and b/poster_abstract/images/beta.pdf differ diff --git a/poster_abstract/images/comp.pdf b/poster_abstract/images/comp.pdf new file mode 100644 index 0000000..2179c1b Binary files /dev/null and b/poster_abstract/images/comp.pdf differ diff --git a/poster_abstract/images/comp2.pdf b/poster_abstract/images/comp2.pdf new file mode 100644 index 0000000..6505ace Binary files /dev/null and b/poster_abstract/images/comp2.pdf differ diff --git a/poster_abstract/images/deg.pdf b/poster_abstract/images/deg.pdf new file mode 100644 index 0000000..4cb2298 Binary files /dev/null and b/poster_abstract/images/deg.pdf differ diff --git a/poster_abstract/images/dist.pdf b/poster_abstract/images/dist.pdf new file mode 100644 index 0000000..0ac9c59 Binary files /dev/null and b/poster_abstract/images/dist.pdf differ diff --git a/poster_abstract/images/gauss.pdf b/poster_abstract/images/gauss.pdf new file mode 100644 index 0000000..7f4c1f6 Binary files /dev/null and b/poster_abstract/images/gauss.pdf differ diff --git a/poster_abstract/images/hbo_likes.pdf b/poster_abstract/images/hbo_likes.pdf new file mode 100644 index 0000000..fb3eee7 Binary files /dev/null and b/poster_abstract/images/hbo_likes.pdf differ diff --git a/poster_abstract/images/para.pdf b/poster_abstract/images/para.pdf new file mode 100644 index 0000000..eae1c16 Binary files /dev/null and b/poster_abstract/images/para.pdf differ diff --git a/poster_abstract/images/perf2.pdf b/poster_abstract/images/perf2.pdf new file mode 100644 index 0000000..fe08879 Binary files /dev/null and b/poster_abstract/images/perf2.pdf differ diff --git a/poster_abstract/images/perf3.pdf b/poster_abstract/images/perf3.pdf new file mode 100644 index 0000000..4df052d Binary files /dev/null and b/poster_abstract/images/perf3.pdf differ diff --git a/poster_abstract/images/perf_synth.pdf b/poster_abstract/images/perf_synth.pdf new file mode 100644 index 0000000..fdf6bdf Binary files /dev/null and b/poster_abstract/images/perf_synth.pdf differ diff --git a/poster_abstract/images/power.pdf b/poster_abstract/images/power.pdf new file mode 100644 index 0000000..4ecb11e Binary files /dev/null and b/poster_abstract/images/power.pdf differ diff --git a/poster_abstract/images/prob.pdf b/poster_abstract/images/prob.pdf new file mode 100644 index 0000000..a4125fe Binary files /dev/null and b/poster_abstract/images/prob.pdf differ diff --git a/poster_abstract/images/sampling.pdf b/poster_abstract/images/sampling.pdf new file mode 100644 index 0000000..517cf2e Binary files /dev/null and b/poster_abstract/images/sampling.pdf differ diff --git a/poster_abstract/images/samplinga.pdf b/poster_abstract/images/samplinga.pdf new file mode 100644 index 0000000..9434939 Binary files /dev/null and b/poster_abstract/images/samplinga.pdf differ diff --git a/poster_abstract/images/synthetic.pdf b/poster_abstract/images/synthetic.pdf new file mode 100644 index 0000000..cd7893c Binary files /dev/null and b/poster_abstract/images/synthetic.pdf differ diff --git a/poster_abstract/images/time.pdf b/poster_abstract/images/time.pdf new file mode 100644 index 0000000..02eaf19 Binary files /dev/null and b/poster_abstract/images/time.pdf differ diff --git a/poster_abstract/images/usandthem.pdf b/poster_abstract/images/usandthem.pdf new file mode 100644 index 0000000..0f43933 Binary files /dev/null and b/poster_abstract/images/usandthem.pdf differ diff --git a/poster_abstract/images/usandthem.png b/poster_abstract/images/usandthem.png new file mode 100644 index 0000000..f09e7bc Binary files /dev/null and b/poster_abstract/images/usandthem.png differ diff --git a/poster_abstract/images/voter.pdf b/poster_abstract/images/voter.pdf new file mode 100644 index 0000000..68a3ec7 Binary files /dev/null and b/poster_abstract/images/voter.pdf differ diff --git a/poster_abstract/main.tex b/poster_abstract/main.tex index 2c8689c..5b9570b 100644 --- a/poster_abstract/main.tex +++ b/poster_abstract/main.tex @@ -39,8 +39,8 @@ http://dx.doi.org/10.1145/2740908.2744108} \clubpenalty=10000 \widowpenalty = 10000 -\title{Scalable Methods for Adaptively Seeding A Social Network} - +\title{Scalable Methods for Adaptively Seeding a Social Network\titlenote{The +full version of this work is available as~\cite{full}.}} \numberofauthors{2} \author{ \alignauthor @@ -58,28 +58,84 @@ Yaron Singer\\ \maketitle \begin{abstract} -In many applications of influence maximization, 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. An alternative approach one can -consider is an adaptive method which selects users in a manner which targets -their influential neighbors. The advantage of such an approach is that it -leverages the friendship paradox in social networks: while users are often not -influential, they often know someone who is. - -Despite the various complexities in such optimization problems, 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. +In many applications of influence maximization, 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 alleviate this issue, one can consider an +adaptive method which selects users in a manner which targets their influential +neighbors. The advantage of such an approach is that it leverages the +friendship paradox in social networks: while users are often not influential, +they often know someone who is. + +Despite the various complexities in such optimization problems, we show that +scalable adaptive seeding is achievable. To show the effectiveness of our +methods we collected data from various verticals social network users follow, +and applied our methods on it. Our experiments show that adaptive seeding is +scalable, and importantly, that it obtains dramatic improvements over standard +approaches of information dissemination. \end{abstract} \category{H.2.8}{Database Management}{Database Applications}[Data Mining] \category{F.2.2}{Analysis of Algorithms and Problem Complexity}{Nonnumerical Algorithms and Problems} -\terms{Theory, Algorithms, Performance} -\keywords{Influence Maximization; Two-stage Optimization} +%\terms{Theory, Algorithms, Performance} +%\keywords{Influence Maximization; Two-stage Optimization} \section{Introduction} +Influence Maximization~\cite{KKT03, DR01} is the algorithmic challenge of +selecting a fixed number of 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. In many cases where influence maximization +methods are applied one cannot select any user in the network but is limited to +some subset of users. In general, we will call the \emph{core set} the set of +users an influence maximization campaign can access. When the goal is to +select influential users from the core set, the laws governing social +networks can lead to poor outcomes: due to the heavy-tailed degree +distribution of social networks, high degree nodes are rare, and since +influence maximization techniques often depend on the ability to select high +degree nodes, a naive application of influence maximization techniques to the +core set can become ineffective. + +\begin{figure} + \centering + \includegraphics[scale=0.55]{images/dist.pdf} + \vspace{-20pt} + \caption{CDF of the degree distribution of users who liked a post by Kiva + on Facebook and that of their friends.} + \label{fig:para} + \vspace{-15pt} +\end{figure} + +An alternative method recently introduced in~\cite{singer} is a two-stage +approach called adaptive seeding. In the first stage, one can spend a fraction +of the budget on the core users so that they invite their friends to +participate in the campaign, then in the second stage spend the rest of the +budget on the influential friends who hopefully have arrived. The idea behind +this approach is to leverage a structural phenomenon in social networks known +as the friendship paradox~\cite{feld1991}: even though individuals are not +likely to have many friends, they likely have a friend that does (``your +friends have more friends than you''). Figure~\ref{fig:para} gives an +example of such an effect on Facebook. + +In this work, we present efficient algorithms for adaptive seeding achieving an +optimal approximation ratio of $(1-1/e)$. The guarantees of our algorithms +hold for linear models of influence. 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}. We then use these +algorithms to conduct a series of experiments to show the potential of adaptive +approaches for influence maximization both on synthetic and real social +networks. +%The main component of the experiments involved collecting 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 results on these data sets suggest that adaptive seeding can +%have dramatic improvements over standard influence maximization methods. + + \bibliographystyle{abbrv} -\bibliography{} +\bibliography{main} %\balancecolumns \end{document} -- cgit v1.2.3-70-g09d2