\documentclass{sig-alternate-2013}
\pdfpagewidth=8.5in
\pdfpageheight=11in
\usepackage[utf8x]{inputenc}

\usepackage{amsmath, amsfonts, amssymb, bbm}
\usepackage{verbatim}
\newcommand{\reals}{\mathbb{R}}
\newcommand{\ints}{\mathbb{N}}
\renewcommand{\O}{\mathcal{O}}
\DeclareMathOperator{\E}{\mathbb{E}}
\let\P\relax
\DeclareMathOperator{\P}{\mathbb{P}}
\newcommand{\ex}[1]{\E\left[#1\right]}
\newcommand{\prob}[1]{\P\left[#1\right]}
\newcommand{\inprod}[2]{#1 \cdot #2}
\newcommand{\defeq}{\equiv}
\DeclareMathOperator*{\argmax}{argmax}
\DeclareMathOperator*{\argmin}{argmin}

\newtheorem{theorem}{Theorem}
\newtheorem{lemma}{Lemma}
\newtheorem{corollary}{Corollary}
\newtheorem{remark}{Remark}
\newtheorem{proposition}{Proposition}
\newtheorem{definition}{Definition}

\permission{Permission to make digital or hard copies of part or all of this
work for personal or classroom use is granted without fee provided that copies
are not made or distributed for profit or commercial advantage, and that copies
bear this notice and the full citation on the first page. Copyrights for
third-party components of this work must be honored. For all other uses,
contact the owner/author(s).  Copyright is held by the author/owner(s).}
\conferenceinfo{WWW 2015 Companion,}{May 18--22, 2015, Florence, Italy.}
\copyrightetc{ACM \the\acmcopyr}
\crdata{978-1-4503-3473-0/15/05. \\
http://dx.doi.org/10.1145/2740908.2744108}

\clubpenalty=10000
\widowpenalty = 10000

\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
Thibaut Horel\\
       \affaddr{Harvard University}\\
       \email{thorel@seas.harvard.edu}
\alignauthor
Yaron Singer\\
       \affaddr{Harvard University}\\
       \email{yaron@seas.harvard.edu}
}

\begin{document}

\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. 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}

\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{main}

%\balancecolumns
\end{document}
