WWW version

1 files changed, 270 insertions, 31 deletions

diff --git a/paper/sections/introduction.tex b/paper/sections/introduction.tex
index 6c2e345..bd99791 100644
--- a/paper/sections/introduction.tex
+++ b/paper/sections/introduction.tex
@@ -5,51 +5,226 @@
 %
 %
 %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}. 
+The massive adoption of social networking services in recent years creates a unique platform for promoting ideas and spreading information.  Communication 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 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.  
+%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.  
 
-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.
+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.  As an
+example, consider an online retailer who wishes to promote a product through
+word-of-mouth by rewarding influential customers who purchased the product.
+The retailer is then limited to select influential users from the set of users
+who purchased the product. 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 that govern 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
+%(not necessarily the highest)
+degree nodes, a naive application of influence
+maximization techniques to the core set can become ineffective.\newline
 
-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
+%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.  
 
 \begin{figure}
     \centering
     \includegraphics[scale=0.55]{images/dist.pdf}
+    \vspace{-15pt}
     \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}
 
+\noindent \textbf{An adaptive approach.}
+An alternative approach to spending the entire budget on the core set is an
+adaptive two-stage approach.  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}.  Intuitively, the friendship paradox
+says that individuals are not likely to have many friends, but they likely
+have a friend that does (``your friends have more friends than you'').  In
+Figure~\ref{fig:para} we give an example of such an effect by plotting a CDF of
+the degree distribution of a core set of users who responded to a post on
+Facebook and the degree distribution of their friends.  Remarkably, there are
+also formal guarantees of such effects.  Recent work shows that for any network
+that has a power law degree distribution and a small fraction of random edges,
+there is an asymptotic gap between the average degree of small samples of nodes
+and that of their neighbors, with constant probability~\cite{LS13}.  The
+implication is that when considering the core 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.\newline
 
-\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
+%The benefit of this method is that it can incentivizes influential nodes to influence their peers.  
+%The idea of two-stage (or in general, a multi-stage) approach is to use the
+%nodes who arrive in the first stage to recruit influential users who can be
+%incentivized to spread information.  In standard influence maximization, the
+%nodes who are not in the initial seed do not receive incentives to propagate
+%information, and cascades tend to die off
+%quickly~\cite{YC10,BHMW11,GWG12,CADKL14}.
+
+
+
+%\noindent \textbf{The friendship paradox.}  Remarkably, while a random individual in a social network 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 that has a power law degree distribution, with a small fraction of random edges 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, with constant probability ~\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.}
+%    \includegraphics[scale=0.08]{images/adaptive_seeding.pdf}
+%    \caption{Adaptive seeding.}
 %    \label{fig:para}
 %\end{figure*}
+%
+%
 
+%\noindent \textbf{An adaptive approach.}
+%Motivated by the friendship paradox, an alternative approach to spending the
+%entire budget on the users who are accessible is to adaptively select
+%influencers in two stages.  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.
+%%The benefit of this method is that it can incentivizes influential nodes to influence their peers.  
+%The idea of two-stage (or in general, a multi-stage) approach is to use the
+%nodes who arrive in the first stage to recruit influential users who can be
+%incentivized to spread information.  In standard influence maximization, the
+%nodes who are not in the initial seed do not receive incentives to propagate
+%information, and cascades tend to die off
+%quickly~\cite{YC10,BHMW11,GWG12,CADKL14}.
+%\newline  
 
+\noindent \textbf{Warmup.}  Suppose we are given a network, a random set of
+core users $X$ and a budget $k$, and the goal is to select a subset of nodes in
+$X$ of size $t\leq k$ which has the most influential set of neighbors of size
+$k-t$.  For simplicity, assume for now that the influence of a set is simply
+its average degree.  If we take the $k/2$ highest degree neighbors of $X$, then
+surely there is a set $S$ of size at most $k/2$ in $X$ connected to this set,
+and selecting $S$ would be a two-approximation to this problem.  In comparison,
+the standard approach of influence maximization is to select the $k$ highest
+degree nodes in $X$.  Thus, standard influence maximization would have $k$ of
+the most influential nodes in $X$ while the approximation algorithm we propose
+has $k/2$ of the most influential nodes from its set of neighbors.  How much
+better or worse is it to use this approach over the standard one?  If
+the network has a power-law degree distribution with a small fraction of random
+edges, and influence is measured in terms of sum of degrees of a set, then the
+results of~\cite{LS13} discussed above imply that the two-stage approach
+which allows seeding neighbors can do asymptotically (in the size of the
+network) better.
+%\footnote{\tiny{In fact, the results of~\cite{LS13} hold not only for measures of influence such as degree, but also for measures like coverage functions, and the voter model which we discuss in this paper.}}.  
+Thus, at least intuitively, it looks as if two-stage approaches may be worth
+investigating.   
+\newline
 
-\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:
+In this paper, our goal is to study the potential benefits of adaptive approaches for influence maximization.  We are largely motivated by the following question.
 
 \begin{center}
-\textit{Is adaptive seeding scalable?}
+\textit{Can adaptive optimization lead to significant improvements in influence maximization?}
 \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
+To study this question we use the adaptive seeding model recently formalized
+in~\cite{singer}.  The main distinctions from the caricature model in the
+warmup problem above is that in adaptive seeding the core set $X$ can be
+arbitrary (it does not have to be random), and every neighbor of $X$ is assumed
+to arrive with some independent probability. These probabilities are used to
+model the uncertainty we have in that the neighbors would be interested in
+promoting the product, as they are not in the core set.  The goal in adaptive
+seeding is to select a subset of nodes in $X$ such that, in expectation over
+all possible arrivals of its neighbors, one can select a maximally influential
+set of neighbors with the remaining budget.\footnote{\tiny{The model can be
+        extended to the case where nodes take on different costs, and results
+        we present here largely generalize to such settings as well.  Although
+        it seems quite plausible that the probability of attracting neighbors
+        could depend on the rewards they receive, the model deliberately
+        assumes unit costs, consistent with the celebrated
+Kempe-Kleinberg-Tardos model~\cite{KKT03}. Of course, if the likelihood of
+becoming an early adopter is inversely proportional to one's influence, then
+any influence maximization model loses substance.}}  It is worth noting that
+using $X$ to be the entire set of nodes in the network we get the
+Kempe-Kleinberg-Tardos model~\cite{KKT03}, and thus adaptive seeding can be
+seen as a generalization of this model.\newline
+
+%This is a simplified version of adaptive seeding where every neighbor realizes with probability one.  A simple algorithm would be to find the most influential subset of size $k/2$ nodes from $\mathcal{N}(X)$, and then select its (at most) $k/2$ neighbors.  For any submodular influence function, this gives a two-approximation.    
+%
+%The crux comes when introducing probabilities.  
+%
+%The standard approach to   
+%
+%When the measure of influence is proportional to sum of degrees or cover of a set, then the discussion 
+%
+%If we measure influence as the sum of degrees (or any submodular function)     
+%
+
+
+
+
+%   
+%More formally, adaptive seeding is phrased as a two-stage stochastic optimization problem.  
+
+%\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.  
+%A two-stage approach, called \emph{adaptive seeding} was 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
+%%~\footnote{The probability of a node being influenced does not model influence, but the likelihood of that node to be willing to disseminate information in exchange for the reward offered.  In other words, this is a standard bayesian utility model with no externalities.}.  
+%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 goal is to recruit the neighbors to become influencers using the budget (free samples), as opposed to try influencing them to forward the information without incentives~\footnote{i.e. the assumption is that nodes have a standard bayesian utility model with no externalities.}.  The function $f(\cdot)$ quantifies the number of individuals in the networks that will be influenced as a result of selecting a subset of early adopters.  Influence functions are known to be special cases of submodular function~\cite{KKT03,MR07}. 
+%Although it seems quite plausible that the probabilities of attracting neighbors could depend on the rewards they receive, the simplification assuming unit costs is deliberate. 
+%This simplification is consistent with the celebrated Kempe-Kleinberg-Tardos model~\cite{KKT03}, and can be extended to the case where nodes take on different costs.  Of course, if the likelihood of becoming an early adopter is inversely proportional to one's influence, then any influence maximization model loses substance.   
+%
+
+
+%\subsection{A scalable approach}
+%The main result in~\cite{singer} is a constant factor approximation algorithm for well-studied influence models such as independent cascade and linear threshold.  These 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.}  
+
+\noindent \textbf{Scalability.}  One of the challenges in adaptive seeding is
+scalability.  This is largely due to the stochastic nature of the problem
+derived from uncertainty about arrival of 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 which is, at
+large, a theoretical triumph.  These algorithms rely on various forms of
+sampling, which lead to a 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
+main technical challenge we address in this work is how to design scalable
+adaptive optimization techniques for influence maximization which do not
+require sampling.\newline
+
+\noindent \textbf{Beyond random users.}  The motivation for the adaptive
+approach hinges on the friendship paradox, but what if the core set is not
+a random sample?  The results in~\cite{LS13} hold when the core set of users is
+random but since users who follow a particular topic are not a random sample of
+the network, we must somehow evaluate adaptive seeding on representative data
+sets.  The experimental challenge is to estimate the prominence of high degree
+neighbors in settings that are typical of viral marketing campaigns.
+Figure~\ref{fig:para} is a foreshadowing of the experimental methods we used to
+show that an effect similar to the friendship paradox exists in such cases as
+well.  \newline
+
+%\noindent \textbf{Adaptive optimization sans sampling.}
+%To consider practical applications of adaptive approaches we require scalable methods.
+%The main technical idea we develop in this work can be described as follows.  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 
+   
+
+
+%The crux in designing adaptive seeding algorithms is 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  
+ 
+
+
+
 
-\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
@@ -63,20 +238,84 @@ The challenges in designing adaptive seeding algorithms are due to both the comb
 
 
 
-\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{Main Results}
+%Our main results in this paper show that adaptive seeding is a scalable
+%approach which can dramatically improve upon standard approaches of influence
+%maximization in cases when limited to marketing through users that expressed
+%interest in a topic.  We first design adaptive seeding algorithms that avoid
+%sampling. This allows implementation and experimentation with this approach on
+%large data sets.  We then use these algorithms to conduct a series of
+%experiments to show the potential of adaptive approaches for influence
+%maximization.
+%
+%The guarantees of our algorithms hold 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,even-dar} and measures
+%such as node degree and click-through-rate or retetweet measures of users which
+%serve as a natural proxies of influence in many settings~\cite{ZHGS10}.  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 can be
+%easily parallelized, has good theoretical guarantees on its running time and
+%does well on instances with smaller budgets.
+%
+%After obtaining scalable algorithms with desirable guarantees, we used the
+%algorithms in our experiments.  We performed several experiments on synthetic
+%and real social network data sets.  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.\newline
 
+\noindent \textbf{Main results.}
+Our main results in this paper show that adaptive seeding is a scalable
+approach which can dramatically improve upon standard approaches of influence
+maximization.  We present a general method that enables designing adaptive
+seeding algorithms in a manner that avoids sampling, and thus makes adaptive
+seeding scalable to large size graphs.  We use this approach as a basis for
+designing 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 can be easily parallelized, has good theoretical
+guarantees on its running time and does well on instances with smaller budgets.
+The guarantees of our algorithms hold for linear models of influence,
+\emph{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,even-dar} and measures
+such as node degree, click-through-rate or retweet measures of users which
+serve as natural proxies of influence in many settings~\cite{ZHGS10}.  In
+comparison to submodular influence functions, the relative simplicity of linear
+models allows making substantial progress on this challenging problem.
 
+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.\newline
 
+\noindent \textbf{Paper organization.}
+We begin by formally describing the model and the assumptions we make in the
+following section.  In Section~\ref{sec:adaptivity} we describe the reduction
+of the adaptive seeding problem to a non-adaptive relaxation.  In
+Section~\ref{sec:algorithms} we describe our non-adaptive algorithms for
+adaptive seeding. In Section~\ref{sec:experiments} we describe our
+experiments, and conclude with a brief discussion on related work.
+ 
 %\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.