diff options
Diffstat (limited to 'poster_abstract')
22 files changed, 70 insertions, 14 deletions
diff --git a/poster_abstract/images/adaptive_seeding.pdf b/poster_abstract/images/adaptive_seeding.pdf Binary files differnew file mode 100644 index 0000000..0b20ac0 --- /dev/null +++ b/poster_abstract/images/adaptive_seeding.pdf diff --git a/poster_abstract/images/beta.pdf b/poster_abstract/images/beta.pdf Binary files differnew file mode 100644 index 0000000..3264317 --- /dev/null +++ b/poster_abstract/images/beta.pdf diff --git a/poster_abstract/images/comp.pdf b/poster_abstract/images/comp.pdf Binary files differnew file mode 100644 index 0000000..2179c1b --- /dev/null +++ b/poster_abstract/images/comp.pdf diff --git a/poster_abstract/images/comp2.pdf b/poster_abstract/images/comp2.pdf Binary files differnew file mode 100644 index 0000000..6505ace --- /dev/null +++ b/poster_abstract/images/comp2.pdf diff --git a/poster_abstract/images/deg.pdf b/poster_abstract/images/deg.pdf Binary files differnew file mode 100644 index 0000000..4cb2298 --- /dev/null +++ b/poster_abstract/images/deg.pdf diff --git a/poster_abstract/images/dist.pdf b/poster_abstract/images/dist.pdf Binary files differnew file mode 100644 index 0000000..0ac9c59 --- /dev/null +++ b/poster_abstract/images/dist.pdf diff --git a/poster_abstract/images/gauss.pdf b/poster_abstract/images/gauss.pdf Binary files differnew file mode 100644 index 0000000..7f4c1f6 --- /dev/null +++ b/poster_abstract/images/gauss.pdf diff --git a/poster_abstract/images/hbo_likes.pdf b/poster_abstract/images/hbo_likes.pdf Binary files differnew file mode 100644 index 0000000..fb3eee7 --- /dev/null +++ b/poster_abstract/images/hbo_likes.pdf diff --git a/poster_abstract/images/para.pdf b/poster_abstract/images/para.pdf Binary files differnew file mode 100644 index 0000000..eae1c16 --- /dev/null +++ b/poster_abstract/images/para.pdf diff --git a/poster_abstract/images/perf2.pdf b/poster_abstract/images/perf2.pdf Binary files differnew file mode 100644 index 0000000..fe08879 --- /dev/null +++ b/poster_abstract/images/perf2.pdf diff --git a/poster_abstract/images/perf3.pdf b/poster_abstract/images/perf3.pdf Binary files differnew file mode 100644 index 0000000..4df052d --- /dev/null +++ b/poster_abstract/images/perf3.pdf diff --git a/poster_abstract/images/perf_synth.pdf b/poster_abstract/images/perf_synth.pdf Binary files differnew file mode 100644 index 0000000..fdf6bdf --- /dev/null +++ b/poster_abstract/images/perf_synth.pdf diff --git a/poster_abstract/images/power.pdf b/poster_abstract/images/power.pdf Binary files differnew file mode 100644 index 0000000..4ecb11e --- /dev/null +++ b/poster_abstract/images/power.pdf diff --git a/poster_abstract/images/prob.pdf b/poster_abstract/images/prob.pdf Binary files differnew file mode 100644 index 0000000..a4125fe --- /dev/null +++ b/poster_abstract/images/prob.pdf diff --git a/poster_abstract/images/sampling.pdf b/poster_abstract/images/sampling.pdf Binary files differnew file mode 100644 index 0000000..517cf2e --- /dev/null +++ b/poster_abstract/images/sampling.pdf diff --git a/poster_abstract/images/samplinga.pdf b/poster_abstract/images/samplinga.pdf Binary files differnew file mode 100644 index 0000000..9434939 --- /dev/null +++ b/poster_abstract/images/samplinga.pdf diff --git a/poster_abstract/images/synthetic.pdf b/poster_abstract/images/synthetic.pdf Binary files differnew file mode 100644 index 0000000..cd7893c --- /dev/null +++ b/poster_abstract/images/synthetic.pdf diff --git a/poster_abstract/images/time.pdf b/poster_abstract/images/time.pdf Binary files differnew file mode 100644 index 0000000..02eaf19 --- /dev/null +++ b/poster_abstract/images/time.pdf diff --git a/poster_abstract/images/usandthem.pdf b/poster_abstract/images/usandthem.pdf Binary files differnew file mode 100644 index 0000000..0f43933 --- /dev/null +++ b/poster_abstract/images/usandthem.pdf diff --git a/poster_abstract/images/usandthem.png b/poster_abstract/images/usandthem.png Binary files differnew file mode 100644 index 0000000..f09e7bc --- /dev/null +++ b/poster_abstract/images/usandthem.png diff --git a/poster_abstract/images/voter.pdf b/poster_abstract/images/voter.pdf Binary files differnew file mode 100644 index 0000000..68a3ec7 --- /dev/null +++ b/poster_abstract/images/voter.pdf 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.
+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. 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.
+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}
|
