Where is the Influence? \\Providing Explanations to Influence %\title{Who do you Influence and on What? \\Providing Explanations for %Influencer Validation} %\title{Influence Explanation by Segment Identification} %\title{Influence Explanation by Market Segment Strength Identification} %\title{Network Value of Customer Revisited: Providing Explanations for %Influencer Validation} \title{Validating Network Value of Influencers by means of Explanations} %\author{Author names suppressed for blind review} % \eat{ %\numberofauthors{1} \author{ \begin{tabular}{cccc} Glenn S. Bevilacqua$^\dag$ \hspace{2mm} & Shealen Clare$^\ddag$ \hspace{2mm} & Amit Goyal$^\dag$ \hspace{2mm} & Laks V. S. Lakshmanan$^\dag$ \\ \end{tabular} \\$ $\\ \begin{tabular}{ccc} %\affaddr{University of British Columbia} \\ %\affaddr{Vancouver, B.C., Canada} \\ University of British Columbia \\ Vancouver, B.C., Canada \\ {$^\dag$\{lennson,goyal,laks\}@cs.ubc.ca, $^\ddag$shealen.clare@gmail.com} \end{tabular} }%} \eat{ \numberofauthors{4} \author{ \alignauthor Glenn Bevilacqua\\ \affaddr{University of British Columbia}\\ \affaddr{Vancouver, BC, Canada}\\ skip \email{lennson@cs.ubc.ca} \and \alignauthor Shealen Clare\\ \affaddr{University of British Columbia}\\ \affaddr{Vancouver, BC, Canada}\\ skip \email{shealen.clare@gmail.com} \linebreak \and \alignauthor Amit Goyal \\ \affaddr{University of British Columbia}\\ \affaddr{Vancouver, BC, Canada}\\ skip \email{goyal@cs.ubc.ca} \and \alignauthor Laks V. S. Lakshmanan \\ \affaddr{University of British Columbia}\\ \affaddr{Vancouver, BC, Canada}\\ skip \email{laks@cs.ubc.ca} } } \maketitle \sloppy \input{abstract} \section{Introduction} \label{sec:intro} \input{intro} %\section{Framework} %\label{sec:approach} %\input{approach} \section{Related Work} \label{sec:related} \input{related} %\section{Background and Problem Studied} %\label{sec:background} %\input{background} %\section{Can Seeding Make A Difference?} %\label{sec:seeding} %\input{seeding} \section{Problem Definition} \label{sec:probdef} \input{probdef} %\section{Complexity of RecMax} %\label{sec:hardness} %\input{hardness} \section{Algorithm} \label{sec:algo} \input{algo} %\section{Explanation Compacting} %\label{sec:exCompact} %\input{exCompact} \section{Experiments} \label{sec:exp} \input{exp} %\section{Case Study 1: Flixster} %\label{sec:flixster} %\input{flixster} %\section{Case Study 2: Twitter} %\label{sec:twitter} %\input{twitter} %\section{Data Sets} %\label{sec:data} %\input{data} %\section{Experiments} %\label{sec:exp} %\input{exp} \section{Conclusions and Future Work} \label{sec:concl} \input{concl} %\section{Appendix} %\label{sec:appendix} %\input{appendix} \vspace*{-4pt} \scriptsize \bibliographystyle{abbrv} \bibliography{singlebib} \end{document} \GB{We consider a directed social graph, $G = (V,D)$ over a set of users $V$ where each arc $(u,v)\in D$ indicates that user $v$ follows user $u$,\footnote{Our ideas and algorithms easily extend to undirected graphs such as those corresponding to friendship links.} %In addition, consider and a propagation log $\mathbb{L}$, %i.e. a set of triples $(u, a, t_u)$ signifying that user $u$ performed action $a$ at time $t_u$.} When the action $a$ is clear from the context, by $t_u$ we mean the time at which user $u$ performed action $a$. We say an action $a$ is propagated from $u$ to $v$ if $(u,v) \in D$, and the log $\mathbb{L}$ cotains the tuples $(u,a,t_u)$ and $(v,a,t_v)$ for some $t_u$ and $t_v$, such that $t_u < t_v$. This defines a propagation graph of $a$ as a directed graph $G(a) = (V(a), D(a))$, with $V(a) = \{u \in V | \exists t_u: (u, a, t_u) \in \mathbb{L}\}$ and $D(a) = \{(u,v) \in D | u \in V(a), v \in V(a), \mbox{ and } t_u < t_v\}$. Define an influence cube $\C$ over the dimensions Users (as influencers), Actions and Users (as followers) as follows: for a cell $(u, a, v)$, $\C(u,a,v) = 1$ if there exists a (directed) path from $u$ to $v$ in $G(a)$, i.e., $v$ performed action $a$ after $u$ did. All other cells have value $0$. Given a user $u$, by a followup of u, we mean a cell $(u,a,v)$ for which $\C(u,a,v) = 1$. The followup set of $u$ is then the set of followups of $u$: $\M_u = \{(u,a,v) \mid \C(u,a,v) = 1\}$. When the user is understood from the context, we use $\M$ instead of $\M_u$. We assume users are equipped with a set of features (e.g., age, location etc), and similarly for actions (e.g., topic). Descriptions for followup sets are derived from attributes by means of predicates of the form $A = val$ where A is an attribute and val is a value from its domain. \LL{We assume numeric attributes are binned into appropriate intervals. Thus it suffices to consider only equality. E.g., year = pre-1997, maturity-rating = ``rated R'', and gender = female are predicates/features.} {\em We use the terms predicates and features interchangeably}. Let $\calP$ be the set of all predicates. Consider a cell $(u,a,v)$ in $\M_u$, the followup set of user $u$, and a predicate $p \in \calP$, we say the cell satisfies the predicate, $(u, a, v) \models p$, provided \eat{that the $p$ is derived from the attribute-value of action $a$ or from user $v$. } either $p$ is a user predicate and user $u$ satisfies this predicate or $p$ is an action predicate and action $a$ satisfies this predicate. % %Given a %cell $(u,a,v) \in \M_u$ and a predicate $p \in \calP$ of the form %$A \mbox{ op } val$, we say the cell satisfies the %predicate, $(u, a, v) \models p$, provided $f$ is an action feature, the %action $a$ has feature $f$ and $a.f \mbox{ op } val$ is true; or $f$ is %a user feature, the user $v$ has feature $f$ and $u.f \mbox{ op } val$ %is true. %Let $\calP$ be the set of all predicates. Given a %cell $(u,a,v) \in \M_u$ and a %predicate $p \in \calP$ of the form $A \mbox{ op } val$, we say the cell satisfies %the predicate, $(u, a, v) \models p$, provided $f$ is an action feature, %the action $a$ has feature $f$ and $a.f \mbox{ op } val$ is true; or $f$ %is a user feature, the user $v$ has feature $f$ and $u.f \mbox{ op } %val$ is true. Here, $a.f$ ($u.f$) refers to the value of action $a$ %(resp., user $u$) for feature $f$. For a predicate $p$, we define $\M^p = \{(u,a,v) \mid (u,a,v)\in\M \,\&\,(u,a,v) \models p\}$, i.e., the subset of followups satisfying the predicate. We define an explanation as a conjunction of one or more (user and/or action) predicates. Given an explanation $E$, we define $\M^E = \bigcap_{p \in E} \M^{p}$. %Given an %explanation $E = \{p_1, \cdots , p_l\}$, we define $\M^E = %\bigcap_{1\le i\le l} \M^{p_i}$, i.e., the set of followups satisfying all the predicates in $E$. We define the coverage of an explanation to be $\cov(E) = |\M^E|$, i.e., the number of followups satisfying $E$. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \eat{ Essentially, our problem takes as input an influence cube $\C: Users \times Actions \times Users$. Each cell $(u, a, v) \in \C$ contains a boolean value: it is 1 if $u$ performed an action $a$ and user $v$ followed it up, and $v$ is socially connected to $u$. We next provide a way to build the cube $\C$ from a commonly used data for social influence analysis \cite{leaders, amit2010, goyal2012}: social graph and propagation log. Suppose we are given a directed social graph $G = (V,D)$ such that a directed edge $(u,v) \in D$ implies that user $v \in V$ follows user $u \in V$. Thus, the influence (or information) flows from $u$ to $v$. Suppose we are also given a propagation log $\mathbb{L}$ in which a tuple $(u, a, t_u) \in \mathbb{L}$ implies that user $u$ performed action $a$ at time $t_u$. Given such input, we say that an action $a$ is propagated from user $u$ to user $v$ if $(u,v) \in D$ and $t_v > t_u$. %That is, $u$ and %$v$ are friends and $v$ follows up the the action after $u$. This defines a propagation graph of $a$ as a directed graph $G(a) = (V(a), D(a))$, with $V(a) = \{u \in V | (u, a, t_u) \in \mathbb{L}\}$ and $D(a) = \{(u,v) \in D | u \in V(a), v \in V(a), t_v > t_u\}$. Now, we can build the cube $\C$ as follows: we say that a cell $(u, a, v) \in \C$ is 1 if there exists a path from $u$ to $v$ in $G(a)$. All other cells have value 0 in $\C$. Given a user $u$ of which we are interested in analyzing influence, we define its followup set $\M_u$ as the set of cells $(u, \cdot, \cdot) \in \C$ whose value is 1. Hereforth, for the ease of exposition, we drop the subscript $u$ from $\M_u$ and refer to it as $\M$. In addition to $\C$, we also take as input $\F$: the set of binary features, for both actions and users. For each attribute-value pair (in action or user dimension), we construct a binary feature. For instance, an attribute ``Gender'' in user dimension may assume two values -- Male and Female. Correspondingly, we construct two features -- Gender\_Male and Gender\_Female. A feature may be either ``absent'' or ``present''. Let $\F_v$ be the set of user features present for user $v$ and $\F_a$ be the set of action features present for action $a$. Then, the features present for a cell $(u,a,v)$, is defined to be $\F_{(a,v)} = \F_a \cup \F_v$. Furthermore, with $\M^f \subseteq \M$, we denote the set of cells selected by the feature $f$. That is, $\M^f = \{(u,a,v) | f \in \F_{(a,v)} \}$. Our goal is to construct a set of $k$ explanations for a user's followup set, each of which is of length at least $l$ such that these explanations cover as much influence of $u$ as possible. } %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% Our goal is to provide explanations for the followup set of a user (candidate influencer). On one hand, we would like each explanation to be as informative as possible. On the other, the total size of explanations should be concise or crisp so that a human (marketer) can quickly make sense of them. At the same time, between them, the explanations should cover as much ``influence mass'' as possible. We formalize these intuitions by insisting that each explanation should have length $\ge l$ and ask for a set of at most $k$ explanations $\E = \{E_1, ..., E_k\}$ such that the number of followups covered by these explanations is as large as possible. For a set of explanations $\E$, we extend coverage as follows: define $\M^{\E} = \bigcup_{E\in\E} \M^E$ and finally, define the coverage of a set of explanations as $\cov(\E) = |\M^{\E}|$, i.e., the number of followps in $\M$ which satisfy at least one explanation in $\E$. That is, \begin{align} \cov(\E) = |\M^{\E}| = | \bigcup_{E\in\E} \M^E | = | \bigcup_{E\in\E} \bigcap_{p \in E} \M^{p} | \end{align} %Consider again the example illustrated in Table %\ref{tab:flixster_firstUser}. There, the parameters $k$ and $l$ are set %to 6 and 3. %\note{Laks: Revisit the (NEW) motivating example from Sec. 1 and illustrate a set of %two expanations of length $> 1$. } %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \eat{ Intuitively, we wish each explanation to be as expressive as possible, and thus we impose $l$ as the lower bound on the length of an explanation. Moreover, we want to describe as much influence (or as many followups) as possible with a small number of explanations. Hence, we set $k$ as the upper bound on the number of explanations. With $E \subseteq 2^{\F}$, we denote a set of features that constitutes one explanation. Similarly, with $\E \subseteq 2^{2^\F}$, we denote a set of explanations. %Let $E \in \E$ be one explanation, which can also be %viewed as a set of features. We use $\M^E \subseteq \M$ as the set of the cells selected by features in $E$, as follows. \begin{align} \M^E = \bigcap_{f \in E} \M^f = \{(u,a,v) | \forall f \in E: f \in \F_{(a,v)} \} \end{align} %We let $\E \subseteq 2^{\F}$ denote a set of explanations. Our goal is to %construct a set of $k$ explanations, each of which is of length at least %$l$ such that these explanations cover as much influence of $u$ as %possible. %We can denote each explanation with a set of features $F$. Moreover, we define $\cov(E) : 2^\F \rightarrow \mathbb{R}$ as the coverage of an explanation $E$. And similarly, we overload $\cov(\cdot)$ and let $\cov(\E) : 2^{2^\F} \rightarrow \mathbb{R}$ denote the coverage of explanations $\E$, for the user in the context $u$. \begin{align}\label{eq:cov} \cov(\E) = | \M^\E | = | \bigcup_{E \in \E} \M^E | \end{align} where $\M^\E$ denote the set of cells selected by explanations $\E$. We are now ready to define our problem \probname (PROviding eXpLanations) formally. } %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \LL{Note the term coverage is defined for a single explanation as well as for a set of explanations. In discussing the properties of the coverage function,} \GB{we %would want to consider } \LL{both $\sigma(E): 2^{\calP} \rightarrow \mathbb{R}$, coverage of a single explanation as a function of the features in the explanation, as well as $\sigma(\E): 2^{2^{\calP}} \rightarrow \mathbb{R}$, coverage of a set of explanations as a function of the explanations in the set $\E$. The notation and the context should make it clear.} The main problem we study in this paper is \probname (PROviding eXplanations for validating the network value of Influencers): \begin{problem}[\probname]\label{prob} {\em Given a user $u$, followup set $\M$, the available user and action predicates $\calP$, and numbers $k$ and $l$, find a set of at most $k$ explanations $\E = \{E_1, ..., E_k\}$, where each explanation $E_i$ is a conjunction of at least $l$ (user/action) predicates such that $\cov(\E)$ is maximized. } \end{problem} The lower bound $l$ on the size of each explanation captures the intuition that explanations should be informative. The upper bound $k$ on the number of explanations captures the intuition that overall the explanations should be crisp. At the same time, problem asks for the influence mass covered (coverage) to be maximum. \subsection{Hardness of PROXI} Not surprisingly, it turns out that \probname is \NPhard. Unfortunately though, not only it is \NPhard to solve exactly, it is \NPhard to approximate within any reasonable factor, even when $k=1$, which in other words is the problem of generating one explanation (Thm.~\ref{thm:nphardness}). We establish the hardness by exploiting its equivalence with the problem of Maximum $l$-Subset Intersection (MSI for short). However, to develop intuitions for building our algorithm, we show some interesting properties of the objective function $\cov(\E)$. In particular, we show that the function $\cov(\E)$ is monotonically increasing and submodular (Thm.~\ref{thm:sm1}), while the function $\cov(E)$ is monotonically decreasing and supermodular (Thm.~\ref{thm:sm2}). We exploit these results to develop our algorithm (\textsection\ref{sec:algo}). %It implies that if somehow we have a subroutine for MSI that outputs an optimal %explanation of length $l$, then we can use this subroutine to %approximate \probname within a factor of $(1-1/e)$, using a %greedy algorithm\footnote{Nemhauser et al.~\cite{submodular} showed that %a greedy algorithm approximates the problem of maximizing monotone %submodular functions within a factor of $(1-1/e)$. Later, it was shown %that this approximation factor cannot be improved unless P=NP %\cite{feige98}.}. Since we cannot have an optimal subroutine for MSI, %we cannot guarantee any approximation factor. However, this insight %suggests us that a reasonable heuristic to generate the set of %explanations $\E$ would be to use the greedy algorithm %(\textsection\ref{sec:algo}). \begin{theorem}\label{thm:nphardness} Problem \probname is \NPhard to solve exactly. Moreover, it cannot be approximated within a factor of $0.5 n^{1 - 2\epsilon} + O(1 - 3 \epsilon)$ for any $\epsilon > 0$, unless P=NP. \end{theorem} % http://www.ic.unicamp.br/~eduardo/publications/ipl12.pdf \begin{proof} We prove the claim for the special case when $k=1$. In this case, the problem reduces to finding exactly one explanation $E$, of length $l$ such that $\cov(E)$ is maximized. Since $\cov(E)$ is defined as the intersection of sets $\M^p$ for all $p \in E$, the problem is equivalent to Maximum $l$-Subset Intersection (MSI) Problem \cite{xavier2012, shieh2012}: Given a collection of sets $\S = \{S_1, S_2, \ldots, S_m\}$ over a universe of elements $\mathcal{U} = \{e_1, e_2, \ldots, e_n\}$, the objective is to select (no less than) $l$ sets $\S' \subseteq \S$, $\S' = \{S_{i_1}, S_{i_2}, \ldots, S_{i_l}\}$ such that its intersection size, $|S_{i_1} \cap S_{i_2} \cap \cdots S_{i_l}|$, is maximum. It is easy to see that MSI is equivalent to \probname when $k=1$. An element $e \in \mathcal{U}$ in MSI corresponds to a cell $(u,a,v)$ with a value 1 in \probname. Similarly, a set $S$ corresponds to $\M^p$, the set of cells selected by a predicate $p$. Furthermore, the objective is equivalent -- select $l$ sets ($l$ predicates) such that the resulting intersection size is maximum. The formal reduction from MSI to \probname and the other way around is thus straightforward and we skip it for brevity. It is well known that MSI is \NPhard, and is \NPhard to approximate it within a factor a $0.5 n^{1 - 2 \epsilon} + O(1 - 3 \epsilon)$ \cite{shieh2012}. Given the equivalence between \probname and MSI, the theorem follows. \end{proof} %%%%%%%%%%%%%%%%%%%%% \eat{ \note{Laks: ${\cal E}*$ vs. ${\cal E}'$ issue needs to be fixed. Glenn: resolved} } %%%%%%%%%%%%%%%%%%%%% \begin{theorem}\label{thm:sm1} The function $\cov(\E): 2^{2^{\calP}} \rightarrow \mathbb{R}$ is monotonically increasing and submodular. That is, $\forall \E \subseteq \E' \subseteq 2^{2^\calP} : \cov(\E) \le \cov(\E')$ and $ \cov(\E \cup \{E\}) - \cov(\E) \ge \cov(\E' \cup \{E\}) - \cov(\E')$. \end{theorem} \begin{proof} First, we show that the objective function $\cov(\E)$ is monotonically increasing. By definition of $\cov(\E)$, we have, \begin{align*} \cov(\E \cup \{E\}) - \cov(\E) = |\M^{\E} \cup \M^{E}| - |\M^{\E}| \end{align*} Clearly, $\M^{\E} \cup \M^{E}$ is a superset of $\M^\E$, the above quantity is non-negative, implying that $\cov(\E)$ is monotonically increasing. Next, we show the property of submodularity. \begin{align*} \cov(\E' \cup \{E\}) & - \cov(\E') = |\M^{\E'} \cup \M^{E}| - |\M^{\E'}|\\ % Step via \M^{\E'} being a subset of \M^{\E'} \cup \M^{E} &= |(\M^{\E'} \cup \M^{E}) \setminus \M^{\E'}| \\ % Step via \M^{\E} being a subset of \M^{\E'}, so \M^{\E'} == \M^{\E} \cup \M^{\E'} &= |(\M^{\E} \cup \M^{\E'} \cup \M^{E}) \setminus (\M^{\E} \cup \M^{\E'}) | \\ % Step via splitting minus of union into two minuses and (\M^{\E} \cup \M^{\E'} \cup \M^{E}) \ \M^{\E'} == (\M^{\E} \cup \M^{E}) \ \M^{\E'} &= |((\M^{\E} \cup \M^{E}) \setminus \M^{\E}) \setminus \M^{\E'} | \end{align*} Since set subraction may only remove set elements, \begin{align*} \cov(\E' \cup \{E\}) - \cov(\E') &\le |(\M^{\E} \cup \M^{E}) \setminus \M^{\E} | \\ &\le \cov(\E \cup \{E\}) - \cov(\E) \end{align*} which is what we wanted to prove. \end{proof} %%%%%%%%%%%%%%%%%%%%%%%%% \eat{ \note{Laks: For monotone non-increasing, isn't it obvious the more features you add the smaller the intersection? For submodularity, I wonder whether there is a need for $E^*$. Can't we prove it from first principles just using $E$ and $E'$ and $f\not\in E'$? The proof looks more complicated than it needs to be. Glenn: resolved} } \begin{theorem}\label{thm:sm2} The function $\cov(E): 2^\calP \rightarrow \mathbb{R}$ is monotonically decreasing and supermodular. That is, $\forall E \subseteq E' \subseteq 2^\calP : \cov(E) \ge \cov(E')$ and $ \cov(E \cup \{p\}) - \cov(E) \le \cov(E' \cup \{p\}) - \cov(E')$. \end{theorem} \begin{proof} First, we show that the objective function $\cov(E)$ is monotonically decreasing. By definition of $\cov(E)$, we have, \begin{align*} \cov(E \cup \{p\}) - \cov(E) = |\M^{E} \cap \M^{p}| - |\M^{E}| \end{align*} Clearly, $\M^{E} \cap \M^{p}$ is a subset of $\M^E$, the above quantity is non-positive, implying that $\cov(E)$ is monotonically decreasing. We next show the property of supermodularity. \begin{align*} \cov(E' \cup \{p\}) & - \cov(E') = - (|\M^{E'}| - |\M^{E'} \cap \M^{p}|)\\ % Step via \M^{E'} \cap \M^{f} being a subset of \M^{E'} &= - |\M^{E'} \setminus (\M^{E'} \cap \M^{p})| \\ % Step via \M^{E'} being a subset of \M^{\E}, so \M^{\E'} == \M^{\E} \cup \M^{\E'} &= - |(\M^{E} \cap \M^{E'}) \setminus (\M^{E} \cap \M^{E'} \cap \M^{p})| \\ % Step via factoring out \M^{E'} &= - |\M^{E'} \cap (\M^{E} \setminus (\M^{E} \cap \M^{p}))| \end{align*} Since set intersect may only remove set elements, \begin{align*} \cov(E' \cup \{p\}) - \cov(E') &\ge - |(\M^{E} \setminus (\M^{E} \cap \M^{p}) |\\ &\ge \cov(E \cup \{p\}) - \cov(E) \end{align*} which is what we wanted to prove. \end{proof} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%% BIG EAT \eat{ \note{Amit: Notes above are written by me.} The goal is the creation of detailed explanations by enssuring the use of a sufficient number of user and action attributes while capturing a substantial porition of the target user's influence. Given as input is a followup set, $\M$, where $\M_u$ is the set of followups that correspond to actions of the influencer $u$. A followup element, $(u,a,v)$, is present in $\M_u$ if user $v$ followedup on $u$'s action $a$. Also provided is a set of binary attributes, $\F$, for both actions and followers. An attribute may be either ``absent'' or ``present''. Let $\F_u$ be the set of user attributes present for user $u$ and $\F_a$ be the set of action attributes present for action $a$. Then, the attributes present for a followup element, $(u,a,v)$, is defined to be $\F_{(a,v)} = \F_a \cup \F_v$. In construction of an explanation we are interested in finding user and action attributes that select many of the followups contained in $\M_u$. Each attribute selects a subset of the followups present in $\M_u$. The selected followups are those that have the attribute present. Let $\M_u^f$ be the subset of $\M_u$ selected by attribute $f \in \F$. An explantion that makes use of a conjunction of attribute is more specific but comes at the consequence of potentially reducing the followups captured. We are interested in finding a set of attribute, $F \subset \F$, of at least a certain size that retains the largest number of followups contained $\M_u$ in their intersection. Formally, we want to maximize the coverage of the attribute set, where the coverage of a set of attribute with respect $\M_u$, denoted by $\cov(F; \M_u)$, is defined to be cardinality of the set $\M_u^F$. %Formally, we want to maximize the coverage of the attribute set, where the coverage of a set of attribute with respect $\M_u$, denoted by $\cov(F; \M_u)$, is be defined as, \begin{align} \M_u^F = \bigcap_{f \in F} \M_u^f %\\ %\cov(F; \M_S) = cm(\M_S^F) \end{align} \begin{problem} {\em Given a user $u$, followup set $\M$, the available attributes and their correspondence to users and actions $\F$, and a number $k$, find a set of attributes $F \subset \F: |F| \ge k$ such that $|\M_u^F|$ is maximized. } \end{problem} The coverage of $F$ is monotonic decreasing in the number of attributes in $F$ due to the addition of an attributes results in one more set intersection. Intersecting an additional set with the previous result can only maintain all elements of the previous result or remove elements. Furthermore, the coverage lost by the addition of a attributes is reduced as other attributes are added. That is, coverage is supermodular, statisfing the property: $f(A \cup {v}) - f(A) \le f(B \cup {v}) - f(B)$ where $A \subset B$. \begin{proof} Given an arbitary $\M_u$, for syntactic simplicity let this be $\M$, and some current set of attributes $F$ the addition of an arbitrary attribute $f$ results in the marginal change of, {\setlength\arraycolsep{0.1em} \begin{eqnarray} \cov(F \cup {f}; \M) - \cov(F; \M) &=& -|\M^F \setminus (\M^F \cap \M^f)| \nonumber %\cov(F \cup {f}; \M_S) - \cov(F; \M_S) &=& cm(\M_S^F \cap \M_S^f) - cm(\M_S^F) \nonumber \\ %&=& -(cm(\M_S^F) - cm(\M_S^F \cap \M_S^f)) \nonumber \\ %&=& -cm(\M_S^F - \M_S^F \cap \M_S^f) \nonumber \end{eqnarray} } The equivalence holds due to $\M^F$ containing all elements of $\M^F \cap \M^f$. Adding an arbitrary a set of attributes $F^{*}$, other than $f$, to the set $F$ to create a new attribute set $F' = F \cup F^{*}$. Now, the addition of $f$ to $F'$ results in the marginal change of, {\setlength\arraycolsep{0.1em} \begin{eqnarray} \cov(F' \cup {f}; \M) &-& \cov(F'; \M) = -|\M^{F'} \setminus (\M^{F'} \cap \M^f)| \nonumber \\ &=& -|(\M^F \cap \M^{F^{*}}) \setminus (\M^F \cap \M^{F^{*}} \cap \M^f)| \nonumber \\ &=& -|(\M^F \setminus (\M^F \cap \M^f)) \cap \M^{F^{*}}| \nonumber %\cov(F' \cup {f}; \M_S) &-& \cov(F'; \M_S) = cm(\M_S^{F'} \cap \M_S^f) - cm(\M_S^{F'}) \nonumber \\ %&=& -cm(\M_S^{F'} - \M_S^{F'} \cap \M_S^f) \nonumber \\ %&=& -cm(\M_S^F \cap \M_S^{F^{*}} - \M_S^F \cap \M_S^{F^{*}} \cap \M_S^f) \nonumber \\ %&=& -cm((\M_S^F - \M_S^F \cap \M_S^f) \cap \M_S^{F^{*}}) \nonumber \end{eqnarray} } Since set intersection may only remove set elements, \begin{align} |\M^F \setminus (\M^F \cap \M^f)| \ge |(\M^F \setminus (\M^F \cap \M^f)) \cap \M^{F^{*}}| \nonumber \end{align} Hence, region coverage is supermodular. \end{proof} The problem of maximizing a supermodular function with a cardinality constraint is known to be NP-hard. The negation ,$-\cov(\cdot)$, converts from maximizing a supermodular function to an equivalent minimization of a submodular function problem. Minimizing a general submodular function under a cardinality constraint is known to be inapproximable within $O(\sqrt{n/\log{n}})$ \cite{submodularhardness}. Furthermore, we are interested in finding not just one region but rather a set of regions, such that even with each block having high specificity (large $k$) the collection of regions still captures the bulk followups. An explanation, $E \subset 2^{\F}$, then is a set of sets of attributes. The coverage of an explanation, $\cov(E; \M_u)$, is defined to be the cardinality of $\M_u^E$. \begin{align} \M_u^E = \bigcup_{F \in E} \M_u^F %\\ %\cov(E; \M_S) = cm(\M_S^E) \end{align} \begin{problem} {\em Given a user $u$, followup set $\M$, the available attributes and their correspondence to users and actions $\F$, and numbers $k$ and $l$, find a set of sets of attributes $E \subset 2^{\F}: |E| \le l$ where $\forall_{F \in E}: |F| \ge k$, such that $\cov(E; \M_u)$ is maximized. } \end{problem} The coverage of $E$ is monotonic increasing in the number of sets of attributes in $E$ due to the addition of a set of attributes results in one more set union. The union of an additional set with the previous result can only maintain all elements of the previous result or add elements. Furthermore, the coverage gained by the addition of a set of attributes is reduced as other sets of attributes are added. That is, explanation coverage is submodular, statisfing the property: $f(A \cup {v}) - f(A) \ge f(B \cup {v}) - f(B)$ where $A \subset B$. \begin{proof} Given an arbitary $\M_u$, for syntactic simplicity let this be $\M$, and some current set of sets of attributes $E$ the addition of an arbitrary set of attributes $F$ results in the marginal change of, {\setlength\arraycolsep{0.1em} \begin{eqnarray} \cov(E \cup {F}; \M) - \cov(E; \M) &=& |(\M^E \cup \M^F) \setminus \M^E| \nonumber %\cov(E \cup {F}; \M_S) - \cov(E; \M_S) &=& cm(\M_S^E \cup \M_S^F) - cm(\M_S^E) \nonumber \\ %&=& cm(\M_S^E \cup \M_S^F - \M_S^E) \nonumber \end{eqnarray} } The equivalence holds due to $\M_S^F$ containing all elements of $\M_S^F \cap \M_S^f$. Adding arbitrary set of attributes other than $F$, $E^{*}$, to the set $E$ to create a new explanation $E' = E \cup E^{*}$. The addition of $F$ to $E'$ results in the marginal change of, {\setlength\arraycolsep{0.1em} \begin{eqnarray} \cov(E' \cup {F}; \M) &-& \cov(E'; \M) = |(\M^{E'} \cup \M^F) \setminus \M^{E'}| \nonumber \\ &=& |(\M^{E} \cup \M^{E^{*}} \cup \M^F) \setminus (\M^{E} \cup \M^{E^{*}})| \nonumber \\ &=& |((\M^{E} \cup \M^F) \setminus \M^{E}) \setminus \M^{E^{*}}| \nonumber %\cov(E' \cup {F}; \M_S) &-& \cov(E'; \M_S) = cm(\M_S^{E'} \cup \M_S^F) - cm(\M_S^{E'}) \nonumber \\ %&=& cm(\M_S^{E'} \cup \M_S^F - \M_S^{E'}) \nonumber \\ %&=& cm(\M_S^{E} \cup \M_S^{E^{*}} \cup \M_S^F - \M_S^{E} \cup \M_S^{E^{*}}) \nonumber \\ %&=& cm((\M_S^{E} \cup \M_S^F - \M_S^{E}) - \M_S^{E^{*}}) \nonumber \end{eqnarray} } Since set subraction may only remove set elements, \begin{align} |(\M^E \cup \M^F) \setminus \M^E| \ge |((\M^{E} \cup \M^F) \setminus \M^{E}) \setminus \M^{E^{*}}| \nonumber \end{align} Hence, explanation coverage is submodular. \end{proof} While being known to be NP-hard maximization of a monotone submodular functions a greedy algorithm, repeatedly adding an element that gives the maximum marginal gain, approximates the optimal solution within a factor of $(1 - 1/e)$. If the internal problem of finding the optimal sets of attributes is resolved by an oracle the outer task of the selecting $l$ of these sets of attributes can provide an $(1 - 1/e)$ guarentee on the coverage of the explanation. } %Let $\M$ be the three dimensional influence cube $Users \times Actions %\times Users$, such that $\M_u(a, v)$ represents the influence credit %that is given to user $u$ for influencing user $v$ for action $a$. As %the first problem statement, given a user $u$, we are interested in %providing justification for the influence that $u$ possesses. We use %$\M_u$ to represent the projection of the influence cube $\M$ on user %$u$ in first dimension. %In other words, $\M_u$ represents the influence %matrix containing actions that $u$ performs, such that $\M_u(a, v)$ is %the influence credit given to $u$ for influencing $v$ on action $a$. %In addition, we assume we are given the set of features (in binary form) %for both actions and users. Each feature can have only two values %corresponding to whether the feature is ``absent'' or ``present''. %Let $F = \{f_1, f_2, \cdots\}$ be the set of features that are present. %For a given user $u$, we are interested in finding the set of features %$F$ such that these features explain the bulk mass of influence score %that user $u$ has. In other words, we want to maximize the %coverage of the feature set, where coverage, denoted by $\cov$, %can be defined as, %\begin{align} %\cov(F) = \sum_{(a,v)} M_u(a,v) \cdot I(a \mbox{ belongs to } F) \cdot %I(v \mbox{ belongs to } F) %\end{align} % %That is, coverage of a feature set $F$ is the sum of matrix that %corresponds to feature set $F$. %Now, we formally define the problem statement. %\begin{problem} %{\em %Given a user $u$, $\M_u$, feature sets on all actions and users, and a %number $k$, find a set of features $S: |S| \ge k$ such that $\cov(S)$ is maximized. %} %\end{problem} %It should be noted that as we expand the feature set $F$, the coverage %decreases and hence, the function $\cov(\cdot)$ is a monotonically %decreasing function. It also seems that the marginal loss should %decrease in each iteration, and hence, it looks like the function %$\cov(\cdot)$ is supermodular. Thus, our problems looks very similar to %supermodular function maximization, and thus, submodular function %minimization. Through qualitative analysis, we mainly seek to validate our problem settings, approach and algorithm. But we note the limitations imposed by the public datasets available. In Twitter dataset, we know the identity of the influencers. We can thus validate our approach by checking if the distribution of influence is along the expected lines. On the other hand, in Flixster dataset, we do not know the identity of the influencers, but have the access to both user and action attributes. Thus, in this case, we can examine the benefits of incorporating followers' demographics (as we saw in the example shown in Table \ref{tab:flixster_firstUser}). %Thus, in this case, we can do the checking at a high level. %We begin by examining Flixster. %\begin{table*}[t] %\parbox{.48\linewidth}{ %\input{table_flixsterAttributes} %} %\begin{table*}[t] %\parbox{.48\linewidth}{ %\input{table_flixster1stUser} %} %\end{table*} %\hfill \begin{table*}[t] \parbox{.48\linewidth}{ \input{table_flixster2ndUser} } \parbox{.48\linewidth}{ \input{table_flixster3rdUser} } %\hfill \end{table*} \eat{ \begin{table} \input{table_flixster1stUser} \input{table_flixster2ndUser} \input{table_flixster3rdUser} \end{table} } %\input{table_flixster1stUser} %\input{table_flixster2ndUser} \noindent Formatting the Explanations. %\input{exCompact} To avoid clutter, in the explanation tables, we do not mention the name of each attribute, and instead show its required value directly. For instance, consider the example in Table \ref{tab:flixster_firstUser}. Here, ``rated R'' indicates the feature ``maturity rating = rating R'' and ``thriller'' implies ``genre = thriller''. Similarly, we combine overlapping features (or predicates) from various explanations, to allow us to visualize the explanations in a tree structure. As an example, the features ``rated R'' and ``thriller'' are present in the first two explanations. We order the features in a manner that minimizes the repetition of the features in the explanations table. \noindent Flixster. % %\eat{ %\note{Laks: Please show flixster tables together and twitter tables togethr. they are %currently split. Be sure to mention the names of users (Mike, Kali, Julie) in the table that %concerns them. E.g., `` ... Top user (Mike) ...''} %} We take the top-3 influencers measured in terms of the number of followups they recieve, and apply our algorithm to generate explanations, for examining their influence distribution. The results are presented in Tables \ref{tab:flixster_firstUser}, \ref{tab:flixster_secondUser} and \ref{tab:flixster_thirdUser}. For simplicity, we refer to the top-3 users as Mike, Kali, and Julie, even though their identities in Flixster are unknown. Table \ref{tab:flixster} shows the complete set of movie features. For users, we have the features corresponding to attributes gender and age. The intent should be clear from the context. %Consider user Mike (Table %\ref{tab:flixster_firstUser}). As shown in the table, Mike has rated 3K movies and has 106 active %followers (friends of Mike who have rated at least one movie after Mike). In %total, he has received 37.9K followups, that is, 12.6 followups on each movie he %rated. We run our algorithm to generate the explanations with parameter %settings $k$ and $l$ as 3. % %With just 6 crisp explanations, our algorithm is able to explain 56.3\% of Mike's %followups. As an example, 6.7K followups came from male followers, on Mike's %ratings on thriller movies rated R. %(movies restricted to persons of %age 17 or older). %Moreover, 2.3K followups came from females on the same %category of movies, suggesting that Mike is quite influential on R-rated %thriller movies. The Actions column tells us that there are 708 such movies %(thriller, R rated) that are rated by Mike, while the Followers column tells us %that out of 106 followers, 67 are males and 37 are females and 2 (= 106 - (67 + 37)) %others did not %specify their gender. Other explanations reveal that Mike is also influential on %drama movies on males, and old (pre-1997) comedy movies regardless of gender. While Table \ref{tab:flixster_firstUser} shows the explanations for the most influential user (please see \textsection\ref{sec:intro} for more details about this user), Tables \ref{tab:flixster_secondUser} and \ref{tab:flixster_thirdUser} show the explanations for users who received second and third most number of followups, Kali and Julie, respectively. Kali has rated 2.8K movies and received 27K followups from her 93 active followers. Julie has rated 1.8K movies and received 23.5K followups from her 73 active followers. While Kali's explanations cover 51.4\% of her followups, Julie's explanations cover 68.7\% of her followups. Julie in particular is influential on female users, with all her followups in the explanations coming from female users. In fact, 63 among 73 of her followers are females. Finally, she is influential on all sorts of movies (on female users), ranging from comedy, drama, thiller and action. This implies that {\sl Julie might be a very good seed if the target market is females}, perhaps better than the top-2 users whose influence is distributed among both males and females. This is the sort of insight that simply cannot be gained by viewing network values solely as a scalar! A final remark about the explanations found is that they are heterogeneous, in that they involve a mix of user and action features. \noindent Twitter. We next analyze the results from Twitter dataset. Recall that we have user identities of key influencers in Twitter, which allows us to validate whether the topics on which these influencers reported to be influential by our algorithm are along the expected lines. This provides us a nice strategy to validate our problem settings \GB{and approach}. For instance, we expect news accounts like New York Times (NYTimes) and CNN to be influential on topics like news, politics, media, etc, and individuals like Tim O'Reilly to be influential on news on software, tech, programming etc. Fortunately, we were able to generate a rich set of topics for tweets by expanding their mentioned URLs. %\note{Laks: Check!, Glenn: checked} While we have the identity of the key influencers, for followers, we could not collect user attributes due to demographic data not being available through the API. Thus, our analysis is restricted to the action attributes, which consist of tweet topics. We focus on explanations of four influencers (Twitter accounts) -- New York Times, National Geographic, CNN Breaking News and Tim O'Reilly, the results of which are presented in Tables \ref{tab:nytimes}, \ref{tab:cnn}, \ref{tab:timreilly} and \ref{tab:nationalgeo}. \eat{ \begin{table} \input{table_twitterNYTimes} \input{table_twitterCNN} \input{table_twitterTimReilly} \input{table_twitterNationalGeo} \end{table} } \begin{table*}[t] \parbox{.5\linewidth}{ \input{table_twitterNYTimes} } %\hfill \parbox{.5\linewidth}{ \input{table_twitterCNN} } \end{table*} \begin{table*}[t] \parbox{.5\linewidth}{ \input{table_twitterTimReilly} } %\hfill \parbox{.5\linewidth}{ \input{table_twitterNationalGeo} } \end{table*} %\input{table_twitterNYTimes} %\input{table_twitterNationalGeo} %\input{table_twitterCNN} %\input{table_twitterTimReilly} Consider the news accounts NYTimes and CNN first. As we expect, both these accounts are influential on topics ``news'' and ``politics''. Moreover, CNN is quite influential on topics like ``tv'' and ``breaking news'', which do not appear in explanations of NYTimes. This makes sense as CNN is a television news channel, while NYTimes is a newspaper. Another interesting observation is that topics like ``religion'' and ``christianity'' appear in CNN explanations (but not in NYTimes explanations) indicating CNN airs programs about religion. In the sample we collected, CNN tweeted about religion and christianity only once, and received 434 retweets -- much higher than the average of 56200/390 = 144 retweets per CNN tweet. Similarly, topics ``journalism'' and ``photos'' can be found in NYTimes explanations but not in CNN ones, while the topics ``business'' and ``politics'' can be found in both. Finally, it is interesting to note that these explanations are able to cover almost all the followups -- 82.8\% for NYTimes and 99.8\% for CNN, suggesting that these accounts are followed mostly because of their news, politics, media etc, i.e., the topics represented in the explanations shown in these tables. Next, in Table \ref{tab:timreilly}, we show the explanations of influence of Tim O'Reilly, the founder of O'Reilly Media and a supporter of the free software and open source movements. Topics like ``news, tech, media, software, open source, programming, development, google'' etc.~emerge as the topics of his influence, which agrees with our expectation. Finally, we explore the influence of the National Geographic Channel in Table \ref{tab:nationalgeo}. This account is influential on ``science, nature, geography travel'' etc, again consistent with our expectations. Above, we have seen that our algorithm outputs the features (topics) that we expect these well known accounts to be influential on. These observations clearly indicate that our problem settings and framework are valid and effective for the purpose of digging deep into the influence spread of influencers and providing explanations. When coupled with user features, as in the case of Flixster dataset, we are able to answer the questions we raised in \textsection\ref{sec:intro: Where exactly does the influence of an influencer lie? How is it distributed? On what type of actions is an influencer influential? What are the demographics of its followers?} We next focus on evaluating our algorithm from a quantitative perspective and compare our algorithm with other algorithms, in terms of the coverage achieved (the fraction of total followups), running time, and memory usage. %We conclude this section by showing the scalability of our %algorithm. %skip \noindent Algorithms Compared: We compare our algorithm, which we refer to as \greedy, with the following baselines. \textsc{Random}: It selects the features randomly, with probability proportional to number of followups covered by each feature. \textsc{Most-Popular}: It orders the features by their popularity, i.e., number of followups they cover. Then, it picks the top $l$ features \GB{that have yet to be picked to build an explanation, this is repeated $k$ times. } It is an intuitive algorithm, as the features which cover most followups can be seen as the representative set of features on which the given influencer is influential. \eat{ \note{This doesn't say how the $kl$ features are packed off into $k$ explanations. The packaging could be good or bad in term sof coverage achieved.} } \exhaustive: It generates one explanation at a time, by exhaustively trying all possible combinations of features and picking the one that covers the maximum number of followups (which are not covered by previous explanations). Note that the number of possible combinations is \GB{${|\calP| \choose l}$}, where $l$ is the number of features in one explanation. Thus, each explanation is an optimal one, i.e., the one with the maximum marginal coverage w.r.t. the previous set of explanations chosen. %however, since they are generated one at a time in the greedy fashion (we pick %the best explanation at any step), this algorithm will provide us $(1-1/e)$ %approximation. Since the objective function \GB{$\cov: 2^{2^{\calP}} \rightarrow \mathbb{R}$} is monotone non-decreasing and submodular (see Thm.~\ref{thm:sm1}), %and it is known that the greedy algorithm that picks %the best element (in this case, explanation) at every step the set of explanations obtained using this algorithm is an $(1-1/e)$-approximation to the optimal solution \cite{submodular}. Thus, among the algorithms compared, algorithm \exhaustive provides the upper bound on the number of followups that can be possibly covered by the explanations generated. Because of its exhaustive nature, we expect the algorithm to be quite slow. %\greedy: This is our algorithm as described in \textsection\ref{sec:algo}. %skip Unless otherwise stated, on each dataset, we take top-100 influencers with respect to number of followups they received. The algorithms are then run on all of 100 influencers, and the median is picked as the representative value for the comparison. We use median instead of mean, as it is %a more robust against outliers. %\note{Laks: Did you compute mean as well? Did you check to see if there %were outliers? Glenn: running time, especially for exhausive has some %large outliers. Coverage has extreme cases, compete coverage and zero %coverage} %\note{Laks: Should we say by ``coverage'' we mean ``relative coverage'' below?} %skip \noindent Coverage w.r.t.~change in \textit{k}: Figure~\ref{fig:cov_k} shows the variation in relative coverage achieved when $k$ is varied. Recall that $k$ denotes the number of explanations (table rows) generated. Relative coverage is defined as the fraction of followups that are covered. The parameter $l$ is fixed to 3 in Flixster and 5 in Twitter. As expected, the (relative) coverage increases with $k$, but not at the same rate for all algorithms. Our algorithm \greedy consistently performs just as well as \exhaustive, while beating both \random and \mostpopular by huge margins, on both the datasets. In fact, the performance of \greedy is almost indistinguishable from that of \exhaustive. For instance, on Flixster, with just 6 explanations, \greedy is able to cover 0.57 fraction of followups, compared to the fraction 0.58 achieved by \exhaustive. On the other hand, \mostpopular covers 0.25 fraction of followups and \random performs dismally, covering only 0.03 fraction of followups. Moreover, it is worth mentioning that the coverage achieved quickly saturates (on Flickr only) for both \mostpopular and \random, implying that increasing $k$ would not have helped achieve better coverage from these algorithms. In case of Twitter, as we can observe, the coverage achieved, is in general higher, with \greedy covering up to 0.95 fraction of followups, again with 6 explanations. Recall, the longer an explanation (higher $l$) the smaller the coverage, in general. Despite this, the coverage achieved on Twitter with 6 longer explanations ($l=5$) is more than achieved on Flixster with 6 shorter explanations ($l=3$). This indicates that the influencers in Twitter are followed due to their niche. For example, news accounts like CNN and New York Times are mostly followed on topics like ``news'' and ``politics'' as we saw above. Once again, \greedy and \exhaustive significantly outperform other baselines while their performance is very close. The relative coverage of \random seems to grow sharply as $k$ increases but at $k = 6$ it still performs poorly. The challenge is to cover as much as possible with as few but as detailed explanations as possible, and \greedy is found to rise to this challenge. \begin{figure}[t] \vspace{-2mm} \centering \begin{tabular}{cc} \hspace{-4mm}\includegraphics[width=4.5cm]{flixsterCoverageWRTnumEx.pdf}& \hspace{-4mm}\includegraphics[width=4.5cm]{twitterCoverageWRTnumExf5.pdf} \end{tabular} \vspace{-4mm}\caption{Coverage achieved from various algorithms w.r.t.~variation in $k$ in Flixster (left) and Twitter (right). $l=3$ in Flixster and $l=5$ in Twitter.\label{fig:cov_k}} \vspace{-2mm} \end{figure} \begin{figure}[t] \vspace{-2mm} \centering \begin{tabular}{cc} \hspace{-4mm}\includegraphics[width=4.5cm]{flixsterCoverageWRTnumF.pdf}& \hspace{-4mm}\includegraphics[width=4.5cm]{twitterCoverageWRTnumF.pdf} \end{tabular} \vspace{-4mm}\caption{Coverage achieved from various algorithms w.r.t.~variation in $l$ in Flixster (left) and Twitter (right). $k$ is fixed to 6.\label{fig:cov_l}} \vspace{-2mm} \end{figure} \noindent Coverage w.r.t.~change in \textit{l}: In Figure \ref{fig:cov_l}, we show the variation in relative coverage when the parameter $l$, the number of features (table columns) per explanation, is changed. As expected, coverage decreases with the increase in $l$. Our \greedy algorithm continues to perform quite well. For instance, on Flixster, it covers 0.31 fraction of followups, compared to 0.05 and 0.00, the coverage achieved by \mostpopular and \random, respectively at $l=4$. \exhaustive on the other hand, covers 0.34 fraction of followups. We see a similar pattern in Twitter dataset as well. When $l=5$, \greedy covers 0.92 fraction of followups (same as 0.92 by \exhaustive), while the coverage from \mostpopular and \random is 0.66 and 0.35. Notice that \exhaustive took too long to complete for $l > 5$ on Twitter. \noindent Running Times and Memory Usage. Fig.~\ref{fig:running_time_k} %and \ref{fig:running_time_l} shows the running time of various algorithms, on both datasets. %, when $k$ and $l$ %are varied, respectively. As can be seen, our \greedy algorithm is an order of magnitude faster than the optimal \exhaustive algorithm. For instance, on Flixster, when $k=6$ and $l = 3$, while \greedy takes 26 ms to finish, \exhaustive finishes in 3,748 ms, that is, it takes 144 times longer than \greedy. The other algorithms -- \mostpopular and \random are faster than \greedy as we foresaw earlier. They complete in 5 ms and 3 ms. Similarly, on Twitter, when $k=6$ and $l = 5$, \exhaustive (finishes in 597 ms) is 18 times slower than \greedy (finishes in 32.5 ms). On the other hand, \mostpopular and \random take just 15 ms and 27 ms, respectively. %\note{Laks: 1. It seems we are two order of magnitude or more faster than \exhaustive. %2. The above para should discuss all the running time plots. Why arbitrarily jump to Fig. 6? %Also, when giving times, be consistent and report times for all algorithms, for each dataset. I %did not edit this para and am leaving it to you to do it right.} %skip %\noindent %Memory Usage. %We show the memory usage by various algorithms in Figure~\ref{fig:memory_usage}. %The interesting observation is that essentially, All the algorithms consume approximately the same amount of memory, up to a maximum of 446 MB and 2.92 GB on Flixster and Twitter, respectivly. This is because the memory usage primarily depends on the number of features and the number of followups they cover. To be precise, \greedy incurs additional space overhead on account of maintaining heaps of features, but this additional overhead is under 1 MB, which is negligible. %skip \noindent In sum, our \greedy algorithm performs essentially as well as \exhaustive algorithm in terms of coverage achieved, while being much more efficient in running time. \begin{figure} \vspace{-2mm} \centering \begin{tabular}{cc} \hspace{-4mm}\includegraphics[width=4.5cm]{flixsterRunningTimelogWRTk.pdf}& \hspace{-4mm}\includegraphics[width=4.5cm]{twitterRunningTimelogWRTk.pdf} \end{tabular} \vspace{-4mm}\caption{Running time comparison for various algorithms on Flixster with $l$ = 3 (left) and Twitter with $l$ = 5 (right). \label{fig:running_time_k}} \vspace{-2mm} \end{figure} %\begin{figure} %\vspace{-2mm} \centering %\begin{tabular}{cc} %\hspace{-4mm}\includegraphics[width=4.5cm]{images/flixster/flixsterRunningTime.pdf}& %\hspace{-4mm}\includegraphics[width=4.5cm]{images/twitter/twitterRunningTime.pdf} %\end{tabular} %\vspace{-4mm}\caption{Running time comparison for various algorithms on Flixster (left) and Twitter (right) (k = 6 for both). %\label{fig:running_time_l}} \vspace{-2mm} %\end{figure} %\begin{figure} %\vspace{-2mm} \centering %\begin{tabular}{cc} %\hspace{-4mm}\includegraphics[width=4.5cm]{images/flixster/flixsterRunningTimeWRTk.pdf}& %\hspace{-4mm}\includegraphics[width=4.5cm]{images/twitter/twitterRunningTimeWRTk.pdf} %\end{tabular} %\vspace{-4mm}\caption{Running time comparison for various algorithms on Flixster with l = 3 (left) and Twitter with l = 5 (right). %\label{fig:running_time}} \vspace{-2mm} %\end{figure} We summarize related work under three headings. \\ %\noindent %Identifying Influencers. \noindent {Identifying Influencers.} Identifying influencers has been extensively studied as the problem of influence maximization. The first work of this kind is due to %from a data mining perspective was first studied %by Domingos et al.~\cite{domingos01}. They refer to users' influence as network value and model it as the expected lift in profit due to influence propagation. Thus, the network value of a customer is captured as a number. %, that is, the expected additional %profit made due to users' influence in the social network. Later, Kempe et al.~\cite{kempe03} formulated this as a discrete optimization problem: select $k$ influencers in a given social network such that by targeting them, the expected spread of the influence is maximized, assuming the propagation follows a diffusion model such as independent cascades or linear threshold or their variants. The problem is \NPhard. However, the objective function satisfies the nice properties of monotonicity and submodularity, under the diffusion models considered, allowing a simple greedy algorithm to provide a $(1-1/e-\epsilon)$-approximation to the optimal solution, for any $\epsilon > 0$ \cite{submodular}. \AG{Further exploiting these properties, Leskovec et al.~\cite{LeskovecKDD07} proposed a lazy forward optimization that dramatically improves the efficiency of the greedy algorithm. The idea is that the marginal gain of a node in the current iteration cannot be better than its marginal gain in the previous iterations.} Goyal et al.~\cite{goyal2012} proposed a direct data driven approach to social influence maximization. They show this alternative approach is both accurate (in predicting the influence spread) and is scalable, compared to the probabilistic approach of Kempe et al.~\cite{kempe03}. \AG{Their work also highlights the importance of validating the influence prediction and spread.} Considerable work has been done on analyzing social influence on blogs and micro-blogs. %, particularly on Twitter, perhaps due to easiness of %collecting data from Twitter. Agarwal et al.~\cite{agarwal08} investigate the problem of identifying influential bloggers in a community. They show the most influential bloggers are not necessarily the most active. Gruhl et al.~\cite{Gruhl2004} analyze information diffusion in blogspace by characterizing the individuals and the topics of their blog postings. %\cite{} %How do we differ from them, then?
Author names suppressed for blind review
Recently, there has been significant interest in social influence analysis. One of the central problems in this area is the problem of identifying influencers, such that by convincing these users to perform a certain action (like buying a new product), a large number of other users get influenced to follow the action. The client of such an application is essentially a marketer who would target these influencers for marketing a given new product, say by providing free samples or discounts. It is natural that before committing resources for targeting an influencer the marketer would be interested in validating the influence \AG{(or network value)} of influencers returned. \GB{This requires} digging deeper into such analytical questions as: who are their followers, on what actions (or products) they are influential, etc. However, the current approaches to identifying influencers largely work as a black box in this respect. The goal of this paper is to open up the black box, address these questions and provide informative and crisp explanations \AG{for validating the network value} %of the influence distribution of influencers. We formulate the problem of providing explanations (called \probname) as a discrete optimization problem \GB{of feature selection}. We show that \probname is not only \NPhard to solve exactly, it is \NPhard to approximate within any reasonable factor. Nevertheless, we show interesting properties of the objective function and develop an intuitive greedy heuristic. We perform detailed experimental analysis on two real world datasets -- Twitter and Flixster, and show that our approach is useful in generating concise and insightful explanations of the influence distribution of users and that our greedy algorithm is \GB{effective and efficient with respect to} several baselines.
abstract.tex
\begin{abstract}
Recently, there has been significant interest in social influence
analysis. One of the central problems in this area is the problem of
identifying \emph{influencers}, such that by convincing these users to
perform a certain action (like buying a new product), a large number of
other users get influenced to follow the action. The client of such an
application is essentially a \emph{marketer} who would target these
influencers for marketing a given new product, say by providing
free samples or discounts. It is natural that before committing
resources for targeting an influencer the marketer would be interested
in validating the influence \AG{(or network value)} of influencers returned.
\GB{This requires} digging deeper into such analytical
questions as: who are their followers, on what actions (or products) they 
are influential, etc. However, the current approaches to identifying
influencers largely work as a black box in this respect. The goal of this paper is to
open up the black box, address these questions and provide informative and crisp explanations
\AG{for validating the network value}
%of the influence distribution 
of influencers. 

We formulate the problem of providing explanations (called \probname) as
a discrete optimization problem \GB{of feature selection}. We show that \probname is not only
\NPhard to solve exactly, it is \NPhard to approximate within any
reasonable factor. Nevertheless, we show interesting properties of the
objective function and develop an intuitive greedy heuristic. We perform
detailed experimental analysis on two real world datasets -- Twitter and Flixster, 
and show that our approach is useful in generating concise and insightful explanations 
of the influence distribution of users and that our greedy algorithm is
\GB{effective and efficient with respect to} several baselines. 
\end{abstract}


\eat{
The study of social influence analysis has attracted significant
attention ever since Kempe, Kleinberg and Tardos published their seminal
paper on the problem of influence maximization \cite{kempe03}. The
objective is to identify influential users (also called
\emph{influencers}) in a social network such that by convincing these
users to perform a certain action (like buying a new product), a large
number of other users get influenced to follow the action. The client
of such an application is essentially a \emph{marketer} who would target
these influencers for the marketing of the given new product (e.g., by
providing free samples or discounts). 
However, the current approaches to
identifying influencers, and in particular, for the problem of influence
maximization, largely work as black-box and just output the
list of influencers, with an estimate on expected influence spread. The goal of this
paper is to address these questions and provide informative and crisp explanations to
influence distribution of influencers. 
}


algo.tex

Even though \probname is \NPhard to approximate, the function
$\cov(\E)$ has nice properties as we show in Theorem
\ref{thm:sm1}. Nemhauser et al.~\cite{submodular} show
that maximizing monotonically increasing submodular
functions can be approximated within a factor of $(1-1/e)$ using a
greedy algorithm. Moreover, due to Feige \cite{feige98}, we know that
this is the best possible approximation factor that can be achieved in
polynomial time.  These results, in addition to Theorem \ref{thm:sm1},
suggest that the greedy heuristic which adds the current best explanation
$E$ to $\E$, until $|\E|$ is $k$ would be the best possible heuristic. 
However, the complex step here is to generate one explanation $E$, or
more generally, the next explanation $E$, such that the marginal
coverage $\cov(\E \cup \{E\}) - \cov(E)$ maximized, where $\E$ is the
current set of explanations. We showed that this particular problem is
\NPhard to approximate (see the proof of Theorem \ref{thm:nphardness}).
Thus, strictly speaking, we cannot expect to have an efficient algorithm with a provable
approximation guarantee for \probname.  

However, given the hardness of the problem, we believe that \GB{a} greedy
algorithm of successively generating \GB{explanations by repeatedly picking the best predicate would}
still be a good heuristic. More precisely, in any iteration, where $\E :
|\E| < k$ is the current set of explanations and $E : |E| < l$ is the
current explanation, the greedy algorithm picks the predicate, $p$,
\GB{that when added to $E$ gives an extended explanation that provides the maximum possible additional coverage, w.r.t.~$\E$}. That is,
$\cov(\E \cup \{E \cup \{p\}\}) - \cov(\E)$ is maximum.

Since the search space is massive, a naive greedy algorithm as explained
above would be extremely slow. So we focus our attention on making the
algorithm efficient, by cleverly avoiding unnecessary coverage
evaluations, in any given iteration.  In particular, we optimize our
algorithm by means of lazy evaluation.  Recall, the function $\cov(E):
2^{{\cal P}} \rightarrow \mathbb{R}$ is non-increasing and supermodular.
Thus, the lazy forward approach used by Leskovec et
al.~\cite{LeskovecKDD07} does not work here, as it relies on the
non-decreasing submodular nature of the objective function. We instead
exploit the fact that the coverage of a single explanation $\cov(E): 2^{{\cal
P}} \rightarrow \mathbb{R}$ is non-increasing in the number of features (predicates),
and devise a lazy evaluation optimization based on this.  The idea
is that, while constructing a 
single explanation, the %loss in the 
\GB{marginal coverage of the explanation} after adding a predicate $p$
to explanation $E$ \GB{also} cannot increase (since $\sigma(E)$ is non-\GB{increasing}). %non-decreasing). 
%(due to supermodularity). 
Thus, by
maintaining a max-heap of predicates\GB{, $p$,} sorted on additional coverage of 
\GB{the extended explanation $E \cup \{p\}$}
w.r.t.~$\E$, 
%(equivalently a min-heap, sorted on loss of coverage), 
we can avoid
coverage recomputations for many of the predicates, in any given iteration.
%the resulting coverage by adding a predicate, for all
%predicates, in each iteration. 

%\note{Amit: Write a couple of lines describing the lazy optimization.}

%We will explore the performance of this heuristic in
%Section~\ref{sec:exp}. 


%\eat{However, the objective function for this problem
%$\cov(E)$ is monotonically decreasing and supermodular. This class
%of functions can be viewed as complement of monotonically increasing
%submodular functions for which we know that the greedy algorithm is
%optimal. Hence, even here, we apply a greedy heuristic that adds the
%current best feature $f$ in $E$, until $|E|$ is $l$.} 

\eat{
Since the search space is massive, a naive greedy algorithm would be
extremely slow. So we focus our attention on making the algorithm
efficient, by cleverly avoiding unnecessary coverage evaluations, in any
given iteration.
In particular, we optimize our algorithm by
means of lazy evaluation. Since our algorithm seeks to add the next 
best explanation with maximum marginal coverage, we focus on 
optimizing the construction of the next best explanation. Each 
explanation consists of $l$ features. Recall, the function $\cov:
2^{{\cal P}} 
\rightarrow \mathbb{R}$ is non-increasing and supermodular. Thus, the 
lazy forward approach used by Leskovec et al.~\cite{LeskovecKDD07} 
does not work here, as it relies on the non-decreasing submodular nature of the (influence 
spread) function being optimized. We instead exploit the fact that 
coverage of a single explanation $\cov: 2^{{\cal F}} 
\rightarrow \mathbb{R}$ is non-increasing in the number of 
features, and devise a lazy evaluation optimization based on this. Intuitively, 
we maintain available features in a max heap. Each node contains a feature 
$f$ as well as the resulting coverage, if $f$ were to be added to a set of 
explanations $E$, i.e., $\cov(E\cup\{f\})$. If we find that the top element 
corresponds to the \emph{current} explanation $E$, we can remove it and add it to $E$, even if 
the coverage of any other heap node (say corresponding to feature $f'$) 
corresponds to a previously considered explanation 
$E'$, where $E'\subset E$, i.e., $\cov(E'\cup\{f'\})$, since 
$\cov(E\cup\{f'\}) \le \cov(E'\cup\{f'\})$, which in turn is 
$\le \cov(E\cup\{f\})$. 
}


%\eat{ 
%\note{Laks: I thought about organizing a top light heap defined based on marginal loss 
%(which is always non-negative). Greedy will add the feature $f$ with the least loss w.r.t. 
%the current explanation $E$ to $E$. If for $E' \subset E$, $MG(f' | E')$ is found to be 
%$> MG(f | E)$, can we conclude that $MG(f' | E) > MG(f | E)$? No. So this doesn't work. 
%I'd like to have a clear and convincing explanation of why CELF would work for 
%maximizing a mono. decreasing supermodular function.} 
%}  

We next explain our algorithm in detail, given in Algorithms
\ref{alg:MineExplanations} and \ref{alg:NextExplanation}.  In $Q$, we
store the max-heap of features. Each element $p$ in $Q$ represents a
predicate/feature with the following attributes: $p.cells$ denotes the
set of cells corresponding to the predicate, or equivalently $\M^p$;
$p.cov$ denotes the effective additional coverage of \GB{an explanation, $E$,} %feature,
w.r.t.~$\E$, \emph{if} $p$ were %to be
added to the explanation, that is, $p.cov = \cov(\E \cup \{E \cup
\{p\}\}) - \cov(\E)$.
Due to our lazy evaluation optimization, $p.cov$ may not always store
the correct value. Instead, it may store an outdated value, which may
have been calculated in some earlier iteration. To keep track of it, we
use $p.flag$  to save the iteration when $p.cov$ was last updated.
Moreover, we mark a cell when it is covered by the current set of explanations.
Initially, all cells are unmarked, and $p.flag$ for all the
features is set to $0$. 
The heap $Q$ is sorted on $p.cov$. Our main subroutine \MineExplanations
adds one explanation $E$ at a time, in a greedy fashion, while the
subroutine \NextExplanation generates the next best explanation, again
in a greedy fashion.  
%To make our algorithm efficient, we incorporate
%the lazy evaluation.


%\note{Laks: Please simplify and clean up the algo. pseudocode, as 
%discussed.} 

%\note{Laks: After spending considerable time, I find the algorithm pseudocode 
%and the explanation extremely confusing. Rather than edit based on my best 
%guess, I think you should rewrite this part clearly ASAP. I have not edited anything 
%below. I have read it several times and couldn't understand clearly enough. } 

%In our algorithm, at any point, we are interested in selecting the
%feature that provides us the maximum gain (or minimum loss) in terms of
%coverage.
%As we describe later, we adapt CELF optimization in a
%way that it exploits the properties of submodularity of $\cov(\E)$ in
%Algorithm \ref{alg:MineExplanations} and supermodularity 

\begin{algorithm}
\caption{\MineExplanations} \label{alg:MineExplanations}
\begin{algorithmic}[1]
\begin{small}
\REQUIRE{$Q$, $k$, $l$} 
\ENSURE{$\E$}
	\STATE $\E \gets \emptyset$.
	\WHILE {$|\E| < k$}
		\STATE $p \gets Q.peek()$.
		\IF {$p.flag < |\E| \cdot l$}
			\STATE $Q.poll()$.
			\STATE $p.cov \gets $ \#cells in $p.cells$ for which
			$cell$ is not marked. 
			\STATE $p.flag \gets |\E| \cdot l$.
			\STATE Reinsert $p$ in $Q$ (and reheapify w.r.t.~$p.cov$).
		\ELSE 
			\STATE $Q' \gets copy(Q)$ (copy includes features'
			coverage).
			\STATE $E \gets \NextExplanation(Q', l, |\E|)$.
			\STATE $\E \gets \E \cup \{E\}$.
		\ENDIF
	\ENDWHILE 
\end{small}
\end{algorithmic}
\end{algorithm}


\begin{algorithm}
\caption{\NextExplanation} \label{alg:NextExplanation}
\begin{algorithmic}[1]
\begin{small}
\REQUIRE{$Q'$, $l$, $|\E|$} \ENSURE{$E$}
	\STATE $E \gets \emptyset$.
	\WHILE {$|E| < l$}
		\STATE $p \gets Q'.poll()$.
		\IF {$p.flag < |\E| \cdot l + |E|$}
			\STATE $p.cov \gets$ \#cells in $p.cells$ for which
			$cell.flag = |\E| \cdot l + |E|$ and $cell$ is not marked. 
			\STATE $p.flag \gets |\E| \cdot l + |E|$.
			\STATE Reinsert $p$ in $Q'$ (and reheapify w.r.t.~$p.cov$).
		\ELSE 
			\STATE $E \gets E \cup \{p\}$.
			\FOR {each $cell \in p.cells$} 
				\STATE \textbf{if} $|E|= l$ \textbf{and} $cell.flag =
				|\E| \cdot l + l$ \textbf{then}
				\STATE \hspace{8pt} mark the \textit{cell}.
				\STATE \textbf{else if} $|E|=1$ \textbf{then} $cell.flag
				\gets|\E| \cdot l + 1$.
				\STATE \textbf{else} $cell.flag \gets cell.flag + 1$.
%				\IF {$|E|=1$}  
%					\STATE $cell.flag = |\E| \cdot l + 1$
%				\ELSIF {$|E|= l$}
%					\STATE \textbf{if} $cell.flag = |\E| \cdot l + |E|$	\textbf{then} mark the cell.
%				\ELSE
%					\STATE $cell.flag = cell.flag + 1$
%				\ENDIF
			\ENDFOR
		\ENDIF
	\ENDWHILE 
\end{small}
\end{algorithmic}
\end{algorithm}


%Without the optimization, the greedy algorithm
%must repeatedly explore all possible features, and then select the best
%feature. The lazy evaluation optimization avoids exploration of all
%possible features, by maintaining the heap. 
We first describe Algorithm \MineExplanations. 
$\E$ is initialized in line 1 and we iterate until $k$
explanations are generated (lines 2-12). In each of these $k$
iterations, we get the next best explanation by calling \NextExplanation,
and add it to $\E$ (lines 10-12). We make a copy of $Q$ before calling
\NextExplanation, because the ordering of the heap $Q$ can be changed by
the subroutine, and thus corrupt the original ordering. Other lines of
the algorithm implement the lazy evaluation optimization. The feature with
the maximum coverage is taken from the heap $Q$, without removing the
it from $Q$ (i.e., $peek()$, in line 3). 
%\LL{Note that $Q$
%is sorted on $f.cov$ where $f.cov$ is the number of cells covered by
%feature $f$ if $f$ were to be added to the explanation $E$ (that is, $\M^{E\cup\{f\}}$) 
%that are not marked (line 6).} 
If there is a
need to recompute the coverage $p.cov$ of the feature $p$ (this
condition is tested using $p.flag$), then we do so in line 6, after
removing it from $Q$ in line 5 (i.e., $poll()$). The flag is
updated in line 7 and the heap $Q$ is re-heapified accordingly.


Next, we describe Algorithm \ref{alg:NextExplanation}, which generates
one explanation at a time. This algorithm also employs a greedy strategy
to select the features in a lazy manner. $E$ is initialized in
line 1 and we iterate until we generate $l$ features in $E$. 
In this subroutine, we also assign a $flag$ to each cell. Intuitively,
$cell.flag$ stores the number of features in the current explanation $E$
that covers the cell. For example, $cell.flag$ is $|\E| \cdot l + 1$,
if it is covered by exactly one feature in $E$, and similarly, it is
$|\E| \cdot l + |E|$ when all features in $E$ cover the cell. It
should be noted that the term $|\E| \cdot l$ is added to ensure that the
flag values across different iterations of Algorithm
\ref{alg:MineExplanations} don't mix up.

We again exploit $p.flag$ to track the iteration when the coverage of
the predicate/feature was last updated. As in $cell.flag$, we also add $|\E| \cdot
l$ in $p.flag$ to avoid the mix up in the flag values across different
iterations.  If there is no need to recompute $p.cov$, then we add $p$
to $E$ (line 9). Next, if $|E| = l$, it implies that this is the last
iteration of Algorithm 2. In that case, we must mark the cells which are
selected by the explanation $E$. Recall that for a cell to be covered by
all features in $E$, its flag should be $|\E| \cdot
l + l$ (lines 11-12). On the other hand, if $|E| = 1$, indicating that
we just selected the first feature in $E$, then $cell.flag$ is initialized to $|\E|
\cdot l + 1$ (line 13). In other cases, that is, $1 < |E| < l$, we
increment $cell.flag$ (line 14). 

Lines 4-7 implement the lazy forward optimization.
If $p.flag$ indicates
that we must recompute $p.cov$, then we do so in line 5. Note that the
coverage of feature $p$ here is the number of cells in $p.cells$ that
are not marked, and which are covered by all the features in $E$. We
test this condition by checking that $cell.flag$ is $|\E| \cdot l +
|E|$. We update $p.flag$ in line 6, and re-heapify $Q'$
accordingly in line 7.





%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%% BIG EAT
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\eat{

\eat{
\begin{algorithm}[h]
\caption{\MineExplanations} \label{alg:MineExplanations}
\begin{algorithmic}[1]
\begin{small}
\REQUIRE{$Q$, $k$, $l$} 
\ENSURE{$\E$}
	\STATE $\E \gets \emptyset$.
	\WHILE {$|\E| < k$}
		\STATE $E \gets \NextExplanation(Q, |\E|, l)$.
		\STATE $\E \gets \E \cup \{E\}$.
	%	\STATE $\forall f \in E : \forall cell \in f.fCells : $ Mark the
	%	cell if $cell.k = |\E|$ and $cell.l = |E|$. 
	\ENDWHILE 
\end{small}
\end{algorithmic}
\end{algorithm}


\begin{algorithm}[h]
\caption{\MineExplanations Better} \label{alg:MineExplanations}
\begin{algorithmic}[1]
\begin{small}
\REQUIRE{$Q$, $k$, $l$} 
\ENSURE{$\E$}
	\STATE $\E \gets \emptyset$.
	\WHILE {$|\E| < k$}
		\STATE $f \gets Q.pop()$.
		\IF {$f.k < |\E|$}
			\STATE $f.cov \gets $ \#cells in $f.cells$ that are not marked. 
			\STATE Reinsert $f$ in $Q$ (and reheapify w.r.t.~$f.cov$).
			\STATE $f.k \gets |\E|$.
		\ENDIF
		\STATE $Q' \gets copy(Q)$.
		\STATE $E \gets \NextExplanation(Q', |\E|, l)$.
		\STATE $\E \gets \E \cup \{E\}$.
	%	\STATE $\forall f \in E : \forall cell \in f.cells : $ Mark the
	%	cell if $cell.k = |\E|$ and $cell.l = |E|$. 
	\ENDWHILE 
\end{small}
\end{algorithmic}
\end{algorithm}


\begin{algorithm}[h]
\caption{\NextExplanation} \label{alg:NextExplanation}
\begin{algorithmic}[1]
\begin{small}
\REQUIRE{$Q'$, $|\E|$, $l$} \ENSURE{$E$}
	\STATE $E \gets \emptyset$.
	\WHILE {$|E| < l$}
		\STATE $f \gets Q'.pop()$.
		\IF {$f.k < |\E|$ \textbf{or} $f.l < |E|$}
			\STATE $f.cov \gets$ \#cells in $f.cells$ that are not
			marked and $cell.k = |\E|$, $cell.l = |E|$. 
			\STATE $f.k \gets |\E|$, $f.l \gets |E|$.
			\STATE Reinsert $f$ in $Q'$ (and reheapify w.r.t.~$f.cov$).
		\ELSE 
			\STATE $E \gets E \cup \{f\}$.
			\FOR {each $cell \in f.cells$} 
				\STATE $cell.k = |\E|, cell.l = cell.l + 1$.
				\STATE \textbf{if} $|E|=1$ \textbf{then} $cell.l = 1$.
				\STATE \textbf{if} $|E|=l$ \textbf{and} $cell.l = l$
				\textbf{then} mark the cell.
			\ENDFOR
%			\STATE $\forall cell \in f.fCells: cell.k = |\E|, cell.l =
%			cell.l + 1$. If $|E| = 1$, then $cell.l = 1$. If $|E| = l$ and $cell.l = l$, then mark the cell as well.
		\ENDIF
	\ENDWHILE 
\end{small}
\end{algorithmic}
\end{algorithm}
}



\note{Amit: Notes above are written by me.}

Here the greedy algorithm for mining explanations is presented. 
The algorithm consists of the subroutine of mining individual explanations, $E$, and the incremental collection of the explanations mined, $\E$. It takes parameters $k$ and $l$ that allow specification of how many explanations to identify and how many features are to to be used in each explanation respectively. The algorithm seeks to find the best explanations first directing following explanations to cover cells that remain to be explained. The coverage attributed to each explanation is the number of cells that it covers that were not covered by previous explanations. In \MineExplanations (Algorithm \ref{alg:MineExplanations_simple}) $f.cells$ tracks the cells on which feature $f$ is present and have yet to be explained. $f.cells$ is initialized with $\M^f$ and following the addition of an explanation $E$ to $\E$ for each feature the cells covered by the explanation, $E.cells$, are removed from $f.cells$.

\begin{algorithm}[ht!]
\caption{\MineExplanations} \label{alg:MineExplanations_simple}
\begin{algorithmic}[1]
%\begin{small}
\REQUIRE{$k$, $l$} \ENSURE{$\E$}
	\STATE $\E \gets \emptyset$
	\WHILE {$|\E| < k$}		
		\STATE $f^{*} \gets \argmax_{f \in \F} (|f.cells|)$
		\STATE $E \gets \NextExplanation(f^{*}, l)$
		\STATE $\E \gets \E \cup \{E\}$
		\FORALL {$f \in \F$}
			\STATE $f.cells \gets f.cells \setminus E.cells$				
		\ENDFOR
	\ENDWHILE
%\end{small}
\end{algorithmic}
\end{algorithm}

\begin{algorithm}[ht!]
\caption{$\NextExplanation$} \label{alg:NextExplanation_simple}
\begin{algorithmic}[1]
%\begin{small}
\REQUIRE{$f^*$, $l$} \ENSURE{$E$}
	\STATE $E \gets \{f^*\}$
	\STATE $f.intersect\_cells \gets f^*.cells$
	\WHILE {$|E| < l$}
		\STATE \textbf{for all $f$ except $f^*$} set $f.intersect\_cells$ to $\emptyset$
		\FORALL {$(u,a,v) \in f^*.intersect\_cells$}		
			\FORALL {$f \in \F_{(a,v)}$}			
				\STATE $f.intersect\_cells \gets f.intersect\_cells \cup \{ (u,a,v) \}$
			\ENDFOR
		\ENDFOR	
		\STATE $f^{*} \gets \argmax_{f \in \F \setminus E} (|f.intersect\_cells|)$			
		\STATE $E \gets E \cup \{f^*\}$		
	\ENDWHILE
	\STATE $E.cells \gets f^*.intersect\_cells$
%\end{small}
\end{algorithmic}
\end{algorithm}


The mining of individual explanations follows the greedy heuristic, adding features to the explanation that result in minimum marginal loss of coverage. To begin each explanation $f.cells$ is used to find the feature that captures the most unexplained cells. Following this, \NextExplanation (Algorithm \ref{alg:NextExplanation_simple}) is called to complete the explanation. \NextExplanation repeatedly identifies the feature whos addition results in minimum marginal loss of coverage and adds it to the explanation until the target of $l$ features is met. The best feature at each step is determined by performing a pass over the cells currently covered by the explanation, $f^*.intersect\_cells$, and for each cell adding the cell to $f.intersect\_cells$ for each feature $f$ that is present for the cell. This implicitly computes the cells in the intersect of the features selected so far, $E$, with each feature $f$. Of the features that are not in $E$ the feature that retains the most coverage, indicated by largest $f.intersect\_cells$, is added to the explanation. This best $f$ is used as $f^*$ in the next step as its $intersect\_cells$ are exactly those covered by the explanation. Once all $l$ features are selected $E$ is returned with $E.cells$ as $f^*.intersect\_cells$, all of the cells covered by the explanation.



\eat{
%Old Algorithm pseudo code

\begin{algorithm}[ht!]
\caption{$FindExplanation$} \label{alg:findexplanation}
\begin{algorithmic}[1]
%\begin{small}
\REQUIRE{$\M_u$, $k$, $l$, $\F$} \ENSURE{$\E$}
	\FORALL {$f \in \F$}
		\STATE $o\_mass(f) \gets 0$
		\STATE $o\_cells(f) \gets \emptyset$
	\ENDFOR	
	
	\FORALL {$(u,a,v) \in \M_u$}
		\FORALL {$f \in \F_{(a,v)}$}
			\STATE $o\_mass(f) \gets o\_mass(f) + 1$
			\STATE $o\_cells(f) \gets o\_cells(f) \cup \{ (u,a,v) \}$
		\ENDFOR
	\ENDFOR
	
	\STATE $\E \gets \emptyset$
	
	\FOR {$i = 1 \to k$}		
		\STATE $f^{*} \gets argmax_{f \in \F} (mass(f))$
		\STATE $E, Ecells) \gets FindFeatureSet(f^{*}, o\_cells(f^*), l)$
		
		\FORALL {$(u,a,v) \in Ecells$}
			\FORALL {$f \in \F_{(a,v)}$}
			
				\STATE $o\_cells(f) \gets o\_cells(f) \setminus (u,a,v)$
				\STATE $o\_mass(f) \gets o\_mass(f) - 1$
				
			\ENDFOR
		\ENDFOR
		
		\STATE $\E \gets \E \cup E$
	\ENDFOR
%\end{small}
\end{algorithmic}
\end{algorithm}


\begin{algorithm}[ht!]
\caption{$FindFeatureSet$} \label{alg:findfeatureset}
\begin{algorithmic}[1]
%\begin{small}
\REQUIRE{$f^*$, $cells$, $l$} \ENSURE{$E$,$cells$}
	\STATE $F \gets \{f^*\}$

	\FOR {$i = 2 \to l$}
		\STATE $f^* \gets null$
		\STATE $F_{reset} \gets \emptyset$
		\FORALL {$(u,a,v) \in cells$}		
			\FORALL {$f \in \F_{(a,v)}$}
			
				\IF {$\exists f' \in F | f \cap f' = \emptyset$}
					\STATE continue
				\ENDIF
			
				\IF {$f \notin F_{reset}$}
					\STATE $cells(f) \gets \emptyset$
					\STATE $mass(f) = 0$
					\STATE $F_{reset} \gets F_{reset} \cup {f}$
				\ENDIF
				
				\STATE $mass(f) \gets mass(f) + 1$
				\STATE $cells(f) \gets cells(f) \cup \{ (u,a,v) \}$
				\STATE $E \gets E \cup \{ f \}$				
				\IF {$mass(f) > mass(f^*)$}
					\STATE $f^* \gets f$
				\ENDIF
			\ENDFOR
		\ENDFOR
		
		\STATE $E \gets E \cup \{f^*\}$
		\STATE $cells \gets cells(f^*)$
	\ENDFOR
%\end{small}
\end{algorithmic}
\end{algorithm}
}







\eat{
%Original Algorithm text by Shea

The algorithm consists of two functions: $OuterLoop$ and $InnerLoop$. For each of the $l$ blocks $OuterLoop$ finds the first feature and hands it off to $InnerLoop$. $InnerLoop$ receives the starter feature, greedily determines the remaining features in the block, and then returns the result to $OuterLoop$. $OuterLoop$ then stores the completed block, and then updates feature and cell information for the next iteration. 

Throughout its execution, each function maintains two map data structures $cells$ and $mass$ to track statistics on each feature. Let $B$ be the list of features making up the current block, and let $S$ be the set of users we are concerned with. Then for a given feature $f$, the evaluation of $cells[f]$ returns a particular subset of $\M ^{B \cap f} _{S}$. $mass[f]$ stores the total mass of exactly that subset of cells in $cells[f]$ which is used for efficiently determining the next feature to add to the block. 

These maps are distinguished in the pseudocode by a subscript. If a map belongs to the outer function it is given a subscript $\M$, and a subscript $\mu$ is given to the inner function maps. The following notation convention is also used in the pseudocode. Where $A$ and $B$ are ordered lists, the term $A \wedge B$ denotes the concatenation of $A$ and $B$, rather than the logical AND, or the intersection of the two lists.



% note: modified to work with algorithmic style file
\begin{algorithm}[ht!]
\caption{$InnerLoop$ $f^{*}, cells_{\M}, S, k$}
\begin{algorithmic}[1]
	\STATE $B \gets [ \spc ]$
	\STATE $I_{B} \gets cells_{\M}[f^{*}]$
	\FOR {$i = 2 \to k$}

		\STATE $cells_{\mu} \gets Map : feature \to \{ \emptyset \}$
		\STATE $mass_{\mu} \gets Map : feature \to 0.0$

		\STATE $F \gets \{ \emptyset \}$
		\FORALL {$(a,v) \in I_{B}$}
		
			\FORALL {$f \in \F_{(a,v)}$}
			
				\IF {$ f = f^{*}$}
					\STATE continue
				\ENDIF
				\STATE $mass_{\mu}[f] \gets mass_{\mu}[f] + \M_{S}(a,v)$
				\STATE $cells_{\mu}[f] \gets cells_{\mu}[f] \cup \{ (a,v) \}$
				\STATE $F \gets F \cup \{ f \}$
				
			\ENDFOR
		\ENDFOR
		
		\STATE $f^{*} \gets argmax _{f \in F} mass_{\mu}[f]$
		\STATE $B \gets B \wedge [f^{*}]$
		\STATE $I_{B} \gets cells_{\mu}[f^{*}]$

	\ENDFOR
	
	\STATE \textbf{return} $(B, I_{B})$
\end{algorithmic}
\end{algorithm}	

\subsection {$InnerLoop$ function}


Each call to $InnerLoop$ provides two results to $OuterLoop$. The first is $B$, the list of $k$ features beginning with $f^{*}$, and the second is $I_{B}$, the cells in the intersection of all of the block's features $\tilde{\M} ^{B} _{S}$ . ($\tilde{\M}$ is $\M$, minus any cells that have already been covered by blocks prior to $B$.)

To provide these, $InnerLoop$ repeats the following until the block has $k$ features: (1) for each $f$, determines the intersection $\tilde{\M} ^{B \cap f} _{S}$, (2) from those intersections, re-calculates the mass preserved by each feature $\sigma(B \cap f, \tilde{\M_{S}})$ and finally (3) adds the feature with the highest value to the block $B$. The first feature is provided by $OuterLoop$, but the rest must be obtained as just described.

The main purpose of maintaining the maps $cells_{\mu}$ and $mass_{\mu}$ for $InnerLoop$ is to reduce time complexity - particularly in the intersection step. Without optimization, determining the intersection $\tilde{\M} ^{B \cap f} _{S}$ would require comparing every cell in $\tilde{\M} ^{f} _{S}$ pairwise against every cell in $\tilde{\M} ^{B} _{S}$, for each feature $f \notin B$. For attributes like Gender, where male and female can each select half of all the cells, the cost of an intersection operation is high: on the order of $|\tilde{\M} ^{B} _{S}|$ multiplied by the total number of nonzero cells.

$InnerLoop$ performs the intersection operation implicitly on lines 5 to 17 by rebuilding $cells_{\mu}$ at each iteration from only the cells in $\tilde{\M} ^{B} _{S}$. This means the only cells the algorithm considers are the ones that actually occupy the intersection region that we are trying to capture. 

$InnerLoop$ will also ignore any features $f$ for which  $\tilde{\M} ^{B} _{S} \cap \tilde{\M} ^{f} _{S} = \{ \emptyset \}$. This situation occurs any time there is a family $F$ of mutually exclusive features (e.g. age, gender, release date). Since no cell may have more than one $f \in F$ "present", after the first feature $f' \in F$ is included in a block, all other $f \in F \setminus f'$ have an empty intersection with $\tilde{\M} ^{B} _{S}$. They will be automatically removed from consideration for the remainder of the function call's execution.

To reduce the complexity of calculating the mass $\sigma(B \cap f, \tilde{\M_{S}})$ for each feature $f$, the map $mass_{\mu}$ is constructed during the intersection process. Just as with $cells_{\mu}$, not all features will be included in $mass_{\mu}$, which reduces the time evaluating the term $argmax _{f \in F} mass_{\mu}[f]$ for finding the next feature to add to the block.

Finally, once the block has $k$ features, it is returned to $OuterLoop$ along with $\tilde{\M} ^{B} _{S}$ (denoted by $I_{B}$ in the pseudocode). The secondary purpose of maintaining $cells_{\mu}$ in $InnerLoop$ is that it makes finding $\tilde{\M} ^{B} _{S}$ a constant time operation. It is the result of evaluating $cells_{\mu}[f^{*}]$, where $f^{*}$ is the last selected feature.

% note: modified to work with algorithmic style file
\begin{algorithm}[ht!]
\caption{$OuterLoop$ $S, k, l$}
\begin{algorithmic}[1]
	\STATE $mass_{\M} \gets Map : feature \to 0.0$
	\STATE $cells_{\M} \gets Map : feature \to \{ \emptyset \}$
	
	\FORALL {$\{(a,v) | \M_{S}(a,v) > 0, a \in A, v \in V \} $}
		\FORALL {$f \in \F_{(a,v)}$}
			\STATE $mass_{\M}[f] \gets mass_{\M}[f] + \M_{S}(a,v)$
			\STATE $cells_{\M}[f] \gets cells_{\M}[f] \cup \{ (a,v) \}$
		\ENDFOR
	\ENDFOR
	
	\STATE $\B \gets [ \spc ]$
	
	\FOR {	$i = 1 \to l$}
		
		\STATE $f^{*} \gets argmax _{f \in F} mass_{\M}[f]$
		\STATE $(B, I_{B}) \gets InnerLoop(f^{*}, cells_{\M}, S, k)$
		
		\FORALL {$(a,v) \in I_{B}$}
			\FORALL {$f \in \F_{(a,v)}$}
			
				\STATE $cells_{\M}[f] \gets cells_{\M}[f] \setminus (a,v)$
				\STATE $mass_{\M}[f] \gets mass_{\M}[f] - \M_{S}(a,v)$
				
			\ENDFOR
		\ENDFOR
		
		\STATE $\B \gets \B \wedge [B]$
	\ENDFOR
	
	\STATE \textbf{return} $\B$
\end{algorithmic}
\end{algorithm}


\subsection {$OuterLoop$ function}

$OuterLoop$'s functions are to provide $InnerLoop$ with the correct starting feature for each block and to collect the completed blocks that $InnerLoop$ responds with. 

In order to determine the feature that will begin the next block, $OuterLoop$ uses $\sigma(f, \tilde{\M_{S}})$, stored in $mass_{\M}$. This map, along with $cells_{\M}$, must be updated any time a new block $B$ is selected to reflect the fact that the mass covered by $B$ no longer matters to future blocks. The update consists of removing all references to the cells selected by $B$ as well as any credit mass they contribute to $\sigma(f, \tilde{\M_{S}})$ for any $f$.

To improve the efficiency of this update, instead of re-evaluating $mass_{\M}[f]$ and $cells_{\M}[f]$ for each feature $f$, only a subset of the entries in each map are modified. $OuterLoop$ determines which entries require modification by iterating over the cells in $I_{B}$ (the cells coverd by $B$), since these are the only cells that are changed by the addition of $B$ to $\B$.

The final step, once all $l$ blocks have been collected, is to return $\B$.

}

}

concl.tex

Ever since Domingos and Richardson~\cite{domingos01} introduced the notion of
network value of users in social networks, a lot of work has been done
to identify influencers, community leaders, trendsetters etc. Work in 
this area has been further ignited since Kempe et al. \cite{kempe03} 
popularized influence maximization as a discrete optimization problem.  
Most of
the current approaches largely work as a black box that just outputs a list of
influencers or seeds, along with a scalar which is an estimate of
the expected influence spread. A marketer would 
want to investigate the influence demographics of the seeds returned to her 
and validate them with her own independent survery and/or background knowledge. 
Motivated by this, our goal has been to open up the above 
black box 
and provide informative and crisp
explanations for the influence distribution of influencers, thus allowing 
the marketer to drill down into a seed and address deeper analytic questions 
about what the seed is good for. 

We formalized the above problem as that of finding up to $k$ explanations, each 
containing $l$ or more features, while maximizing the coverage. We showed the problem is not only \NPhard to solve optimally, but is 
\NPhard to approximate within any reasonable factor. Yet, exploiting the nice properties of 
the objective function, we developed a simple greedy algorithm. Our experiments on 
Flixster and Twitter datasets show the validity and usefulness of the 
explanations generated by our framework. Furthermore, they show that the greedy 
algorithm significantly outperforms several natural baselines. 
One of these is an exhaustive approximation algorithm
that by repeatedly finding the explanation with the greatest
marginal coverage gain achieves a (1-1/e)-approximation of the
optimal coverage. However, our
greedy algorithm achieves a coverage very close to that of the
exhaustive approximation algorithm and is an order
of magnitude or more faster. It is interesting to investigate how algorithms for mining maximum frequency item sets of a given cardinality 
(e.g., see \cite{freqitemsetmining}) can be leveraged for finding explanations with the maximum marginal gain. 

Several interesting problems remain open. We give one example. Advertisers 
often like to target users in terms of properties like demographics, instead of 
targeting specific users. E.g., 
if we want to target female college grads in California, what would be an 
effective set of explanations that would describe the influence distribution of this 
demographic? How can we generate these explanations efficiently and validate them? 
\eat{On a more technical level, in this paper, we assumed our input is a social network 
along with an action log. Suppose we are instead given a model consisting of a social network along 
with pairwise user influence probabilities as input. In this case, how should we define 
explanations for {\sl expected} influence spread and how do we generate them efficiently 
and how do we validate them?  } 

\eat{ We have presented an efficient method of assembling an explanation
	of a user's or set of user's influence by identifying feature space
	regions of strong influence. Explaning influence adds value to seed
	set recommendation by giving a means to inspect the results of a
	recommender that otherwise functions as a blackbox. We find that
	proper feature design is critical to achieve balanced use of
	features in explanations, and present techniques to bin features to
	achieve this.  }

\eat{ 
\note{Laks: Need to write from scratch. Main points. Why explain? Why
looking at n/w value as just a scalar is not enough. Main contributions
recalled: f/w, analytical results, algos, experiments, lesson learned,
future work.} 
} 

datasets.tex

\noindent
\textbf{Flixster.}
Flixster (\url{www.flixster.com}) is a major player in the mobile and
social movie rating business. Originally collected by Jamali et
al.~\cite{Jamali10}, the dataset contains 1M users and 7.06M ratings,
distributed across 49K movies. Out of these 1M users, 148K users have provided 
one or more ratings and they have 2.43M edges among them.
%\footnote{This sample of dataset is slightly different from the one we
%have used earlier \cite{goyal2012}}. 
Here, an action is a user
rating a movie. 
For each rating, the dataset also includes the
timestamp at which the user rated the movie. 

%\note{Amit: Above, is it more than one rating, or: one or more rating?}

\textit{User Features:} There are two user attributes in the dataset:
Gender and Age. 
%While the attribute Gender assumes two
%values: Male and Female, the attribute Age assumes numerical values. 
As is done 
in other public datasets such as Movielens, we bin age values  into 7 age
ranges as follows: less than 18, 18--24, 25--34, 35--44, 45--49, 50--55
and 56+. Thus, we ended up with 9 binary user features.

\textit{Action Features:} 
To enrich action (movie) features, we queried IMDB API
(\url{imdbapi.com}) with the movie titles present in the
Flixster data set: 82\% of the movie titles found matches; we ignore
ratings on the remaining 18\% of the unmatched movies, which constituted
9\% of the ratings.
%\GB{These constitute only 9\% of the ratings provided.}
\eat{
\note{Laks: How many or what \% ratings did we lose as a result?} 
}
As shown in Table
\ref{tab:flixster}, 7 attributes were collected.
% from IMDB (\url{imdb.com}). 
Two of them -- Rating
and Year are numerical attributes, and we bin them into 3 ranges. For
instance, Rating is classified into three ranges: 1--6,
6--7 and 7--10. Similarly, attribute Year is classified into 3 bins: less
than 1998, 1998--2002 and 2002+. Other attributes include Genre, Maturity
Rating, Director, Actor and Writer. In total, we ended up with 7135
predicates.
In general, we perform the binning in a roughly equi-depth manner, that
is, equal number of (global) followups fall in each bin. The reason for
following such a binning strategy is to remove any prior bias on
selecting predicates.
%\GB{Since none of the bin predicates cover
%	significantly more followups globally than other bin predicates the
%selection of one bin predicate over the others to describe a users
%influence indicates that their influence in stronger than average
%(relatively) in that bin.}
%\note{Laks: How does this remove bias?} 


\begin{table}
	\centering
	\caption {Flixster: Movie (Action) \GB{Predicates/Features}. We collected 7
	attributes. }
	\label{tab:flixster}	
	\begin{scriptsize}
	\begin{tabular}{ | l | l |}    \hline	
		Attribute 	& \# of Predicates/Features \\ \hline \hline			
		Rating 	& 	3 \{1-6, 6-7, 7-10\}	  	\\ \hline
		Year 		& 	3  \{$<$1998, 1998-2002, 2002+\}	\\ \hline
		Genre 		& 	28  \{ex. Comedy\}	\\ \hline		
		Maturity Rating 		& 	94 \{ex. PG-13\} 		\\ \hline
		Director 		& 1239  		\\ \hline
		Actor 		& 	4364 		\\ \hline
		Writer 		& 	1404 		\\ \hline
	\end{tabular}
	\end{scriptsize}
\end{table}


\smallskip
\noindent
\textbf{Twitter.}
Twitter (\url{twitter.com}) is a well known microblogging site where
users post tweets, messages of up to 140 characters, that are broadcast
to users following them. Tweets can be retweeted by receiving users;
this rebroadcasts the tweet to users following the receiver. Thus,
action here is a user posting a tweet (or retweet). 

While collecting data, we focus on tweets that are retweeted, as
retweets are definite indications of flow of influence (or information). 
That is, tweeting is an action and retweeting is evidence of its 
propagation through the network.
%\GB{As such, we do not explicitly need the edges of the network
%(this being the follower graph)
%due to the presence of a retweet indicats that there exists a path from the tweet source user
%to the user retweeting it.}
Moreover, we restricted our data collection to tweets containing URLs,
as it allows us to compile rich action features, from the webpages
corresponding to the mentioned URLs.

We collected the tweet data using Twitter Streaming API, for 3 weeks
from Tue Jul 24 14:50:07 PDT 2012 to Tue Aug 14 14:57:30 PDT 2012. The
Streaming API permits tracking of specific users, that is, using this
API, we can collect tweets created by these users, and any retweets of
these tweets.  To select these ``source'' users, we exploit the Twitter
Search API. We did not provide any search term in the query, and the API
returned top-20 tweets according to Twitter's internal ranking. Queries
were sent every 5 seconds until a total of 10K source users were
collected. Once we had source users, we collected %the 
tweet data from \GB{the}
Streaming API, targeting these 10K users. In 3 weeks of data collection,
we accumulated 2.2M (source) tweets from these source users, which were retweeted
92.5M times by 11.8M other users. 

\eat{
\note{Laks: What are the edges? Do they correspond who retweeted whom? Sth else? } 
}

\smallskip
\noindent
\textit{Action Features:}
Tweets may contain user mentions, hashtags and URLs as features.
Usually, URLs are shortened by services like \url{bit.ly}. %that helps
%tweet size to be in 140 characters. 
Out of the 2.2M source tweets, 51\%
contained URLs. We focused on these tweets and their retweets. We were
able to expand 98\% of the URLs. To collect features, we 
%turned to
%Delicious (\url{http://delicious.com/}), an online service that enables
%sharing, storing, tagging and discovering web bookmarks. We 
queried
Delicious (\url{http://delicious.com/}) with URL hostnames and gathered Delicious tags. 
A total of 39K
unique URL tags were found from 28K unique URL hosts. After this
processing, we had 948K source tweets, which received 12.8M retweets. We
consider this sample in our analysis.

\smallskip 
\noindent 
\textbf{Influence Cube and Frequency Distribution of Followups.} From this data, we construct
influence cube $\C$ as described in \textsection\ref{sec:probdef}. That is, the
value in cell $(u,a,v)$ is set to 1 if there is a path from $u$ to $v$ in
the propagation graph corresponding to action $a$. For each user $u$, we then calculate 
the total number of followups, the distribution of which
is presented in Fig.~\ref{fig:dist_followups} (note that both the axes are in log scale). 
%As we expect, the distribution follows
%a power law function (note that both the axes are in log-log scale) indicating that 
%most users receive a few number of folloups, while a small set of influencers drive
%the number most followups. 
As expected, the distribution follows
a power law  in case of Flixster, with 
the power law exponent of  -1.326. 
On the other hand, the distribution in case of Twitter is not exactly power law. This is 
due to the bias in our data collection strategy that favors active users: recall that 
we collected 10K source users by exploiting Twitter Search API. We fit two 
piecewise functions -- the first with exponent -0.462 and the latter with exponent -1.04.
%\note{Laks: What's the purpose of this fitting? Where do we use it?} 
%\note{Amit: In the plots, please make the fonts bigger.}
%The power law exponent in case of Flixster is -1.326, while it is 

\begin{figure}[t]
%\vspace{-2mm} 
\centering
\begin{tabular}{cc}
\hspace{-4mm}\includegraphics[width=4.5cm]{flixsterFollowupHist.pdf}&
\hspace{-4mm}\includegraphics[width=4.5cm]{twitterFollowupHist.pdf}
\end{tabular}
%\vspace{-4mm}
\caption{Frequency distribution of number of followups in Flixster 
(left) and Twitter (right). Both axes are in log scale.\label{fig:dist_followups}} 
%\vspace{-2mm}
\end{figure}

exp.tex

The goals of our experimental analysis are manifold. Not only we are interested
in identifying influential users, that is, users with high number of followups,
we are also interested in exploring the distribution of their influence, from both
quantitative and qualitative angles. We achieve this by performing an exhaustive
analysis on two real-world datasets -- Flixster and Twitter. We next describe the datasets.

\subsection{Datasets}
\input{datasets}

\subsection{Qualitative Analysis}
\input{qualitative}

\subsection{Quantitative Analysis}
\input{quantitative}

intro.tex

\eat{	
Social influence occurs when one's actions are affected by one's social neighbors. While
the study of social influence has a long history in the fields of
sociology and marketing, it 
} 

The study of social influence has gained tremendous attention in the field of data
mining ever since the seminal paper of Kempe et al.~\cite{kempe03}
on the problem of 
influence maximization. A primary motivating application for influence
maximization as well as for other closely related
problems such as identifying community leaders~\cite{leaders},
trendsetters~\cite{trendsetters}, influential bloggers~\cite{agarwal08}
and microbloggers~\cite{twitterrank,cha10},
is viral marketing.
%where 
%
%One of the fundamental problems in the
%study of social influence is to identify influential users in a
%social network.
%since Kempe et al.~\cite{kempe03} published
%their, now well celebrated, seminal paper on the problem of influence maximization.
%The study of influence spread in social networks has attracted
%tremendous attention ever since Kempe et al.~\cite{kempe03} published
%their seminal paper on the problem of influence maximization.
%The primary motivation comes from the application of viral marketing where 
The objective in these problems is to identify influential users (also called
\emph{influencers} or \emph{seeds}) in a
social network 
%(called seed users) 
such that by convincing these users to perform a certain action (like
buying a new product), a large number of other users can be influenced to
follow the action.  The client of such an application is essentially a
\emph{marketer} who would 
%analyze the
%seed users and 
target these influencers for marketing a given new product, e.g.,
by providing free samples or discounts. 
%Once identified, these users are then presented to
%the marketing analyst for targeting. 
%In other words, the real aim of
%influence maximization problem is to recommend quality seed users to the
%marketer. 
It is natural that the marketer would like to analyze the influence
spread \cite{kempe03} or ``network value'' \cite{domingos01} of these influencers 
before actually committing resources
for targeting them. 
%For any influential seed user u, 
She would be interested in the answers to the
following questions: \begin{em}
Where exactly does the influence of an influencer
lie? How is it distributed?
%Which users are influenced by a seed users?
On what type of actions (or products\footnote{buying a product is 
an action.}) is an influencer influential? What are the
demographics of its followers? 
\end{em}   
However, the \emph{current approaches for 
identifying influencers}, and in particular, for selecting seed users for the problem of influence
maximization, \emph{largely work as a black box} \GB{in this respect. Just outputting a}
list of seed users (influencers), along with a scalar which is an estimate of the expected 
influence spread. The goal of this
paper is to open up this black box, address these questions and provide informative and 
crisp explanations for the 
influence distribution of influencers. 

%%%%%%%%%%%%%%%%%% 
%\input{table_example1.tex} 
%%%%%%%%%%%%%%%%%% 

Providing explanations to the marketer for influence spread of influencers can have
several benefits. First, it provides \emph{transparency} to the seed
selection algorithm. The marketer is made aware of why a certain user
is selected as a seed, where the user's influence lies, and on what type
of actions the user is influential. These are important analytics she 
may want to investigate before spending
resources on targeting that seed user. Second, it makes the seed selection algorithm
(and thus the system) \emph{scrutable}. The marketer would now be able
to tell the
system, if the explanations (and thus the algorithm) are wrong or are based
on incorrect assumptions, say using her own surveys or background knowledge.
If the explanations are correct and accurate, \GB{this} can increase the
marketer's \emph{trust} in the system and help her in making
good, informed decisions quicker. In other words,
accurate explanations may enhance \emph{effectiveness} and
\emph{efficiency} of the marketers, in making important marketing
decisions. 
Furthermore, such explanations allow room for 
\emph{flexibility} in the targeting process. Indeed, if the
marketer is not able to target \AG{some of the} seeds successfully, then she
knows what exactly the impact on ``coverage'' would be, and can make adequate
adjustments. For example, if a seed's influence was over young college 
students in CA on handheld devices, the marketer can look for an \GB{alternate} 
seed with close characteristics to cover that demographic. 
Overall, providing accurate and crisp explanations would increase the marketer's 
\emph{satisfaction}, and hence loyalty to the provider of seed selection service, 
\GB{as well as} \emph{confidence} in the seed selection algorithm.
In this paper, we specifically focus on providing explanations for
\emph{influencer validation}, that is, a marketer would be able to
analyze the demographics of the followers and the actions.


%Providing explanations to influence spreads to the marketer can have
%several benefits. First, it provides \emph{transparency} to the seed
%selection algorithm. The marketer would be aware of why a certain user
%is selected as a seed, which is an important analytics before spending
%resources on targeting that seed user. Second, it allows
%\emph{flexibility} to the targeting campaign.  For instance, if the
%marketer is not able to target one or more seeds successfully, then she
%knows that what exactly the impact would be, and can make adequate
%adjustments.  Moreover, if the explanation of a certain seed user is not
%convincing, the marketer can discard that seed and not target it.
%Finally, explanations can increase the \emph{credibility} of seed
%selection algorithm. If the explanations are irrelevant, that would
%imply the underlying algorithm is not adequate and hence, it won't be
%considered credible. On the other hand, if the explanations are relevant
%and valuable, they can immensely increase the credibility of t
%algorithm.

%In addition to the benefits to marketers, explanations can be helpful to
\GB{On} the industry side, companies like Klout\footnote{\url{www.klout.com}} and 
Peerindex\footnote{\url{www.peerindex.com}} %, which 
claim to provide users'
influence scores from their Social Media profiles (like Facebook and
Twitter). Both these companies provide ``topics'' over which the
users' influence is spread, in addition to influence scores. The 
explanations we propose offer a principled and comprehensive 
account of just how the influence of a seed user is distributed 
across \GB{the} user (i.e., follower) and action dimensions instead of an 
ad hoc ``influence score'' and ``topic''. 

The merit of providing explanations has been recognized before, in the
related fields of recommender systems (see Chapter 15 of \cite{handbook}
for a survey) and expert systems (see \cite{Lacave2004} for a review).
In these systems, the explanations are known to have benefits similar to
those mentioned above.  {\sl In the field of social influence analysis, to
the best of our knowledge, there has been no such systematic study}.  




%consider Flixster (\url{www.flixster.com}) where rating a movie is an
%action. A movie can have many attributes, e.g., genre, year,
%number\_of\_ratings, and similarly, users can have many attributes, e.g., 
%gender,
%age-group and occupation. The current influence maximization algorithms
%essentially output the seeds in the style: ``The influence spread of user $u$ 
%is
%70'' which is not as informative. 
%We are interested in the
%explanations of style -- 
%	``The influence
%	spread of user $u$ is 70, and the influence is spread as follows: a) Genre:
%	Horror, Gender: Male, Age-Group: 20-25, Influence Spread: 49 (70\%);
%	and b) Genre: Romance, Gender: Female, Occupation: Student,
%	Influence Spread 21 (30\%).''
%This example says that the total influence of user $u$ is 70, spread as
%49 (70\%) and 21 (30\%), across 2
%demographics, with the details of the demographics. In other words,
%there are two explanations, with the support of 70\% and 30\%,
%respectively. Clearly, these types
%of explanations are more informative and fruitful to the marketers.
%To be meaningful, the explanations should be accurate, detailed and
%noise-free. 

%While there has been no research study on providing explanations to
%influence spreads, 

\begin{table}
\input{table_flixster1stUser.tex} 
\end{table}

\smallskip
\noindent 
\textbf{A Motivating Example.} 
Consider a social network where users perform actions. For instance, in
Flixster\footnote{See \textsection\ref{sec:exp} for a description of the 
datasets.} (\url{www.flixster.com}), user actions correspond to rating
movies. A movie can have many attributes, e.g., genre, year of release,
length of the movie, rating value, and similarly, users can have many
attributes, e.g., gender, age-group and occupation.
Table~\ref{tab:flixster_firstUser} shows an example of the result from
our \GB{experimental} analysis on the real data of Flixster. In this
example, we analyze the influence of the top influencer in Flixster,
measured in terms of number of followups. For simplicity, we refer to
this user as Mike. Informally, a followup is defined as a follower
following up on a user's action. In the context of this example, the number
of followups of Mike is the number of times a follower of Mike rated a
movie, after he rated it.\footnote{We \GB{exactly define} followup in
\textsection\ref{sec:probdef}}

The table makes the following assertions. Mike has rated 3K movies and
has 106 active followers. In total, he has received 37.9K followups.
%that is, 12.6 followups on each movie he rated.
This is the overall picture of Mike's influence spread. Drilling down, the 
table shows six explanations describing a partial breakdown 
that covers a significant chunk of the influence mass, each explanation 
corresponding to a row. Each explanation 
is presented in terms of action and user features (first three columns). 
The explanations are heterogeneous: e.g., 
the first two explanations involve attributes maturity rating, genre, and user gender, 
whereas the next two involve the attributes user gender, genre, and movie length. 
% 
\eat{The influence is
described by 6 explanations (one explanation corresponds to one row),
and each explanation contains three features.} 

With just 6 crisp explanations, our algorithm is able to explain 56.3\%
of Mike's followups. As an example, 6.7K followups came from male
followers, on Mike's ratings on thriller  movies rated R. (movies
restricted to persons of age 17 or older).  Moreover, 2.3K followups
came from females on the same category of movies, suggesting that Mike
is quite influential on R-rated thriller movies. The Actions column
tells us that there are  708 such movies (thriller, rated R) that are
rated by Mike, while the Followers column tells us that out of 106
followers, 67 are males and 37 are females and 2 (= 106 - (67 + 37))
others did  not specify their gender. Other explanations reveal that
Mike is also influential on drama movies on males, and old (pre-1997)
comedy movies regardless of gender.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\eat{
\smallskip
\noindent 
\textbf{A Motivating Example.} 
Consider a social network where users perform actions.  For instance, in 
Twitter (\url{www.twitter.com}) user actions correspond to posting \emph{tweets}. 
A tweet can have many attributes, e.g., topic, category,
has\_image etc, and similarly, users can have many attributes, e.g.,
location, gender, age-group and occupation. Table~\ref{tbl:example} shows
an example of the kinds of explanations we envisage, for a hypothetical 
seed user $u$. 
\note{Amit, this hypothetical example is a placeholder, with instances to be 
replaced by real stuff found by our experiments.} 
The table makes the following assertions. 
User $u$ posted 200 tweets overall, and received 8000 retweets
(or \followups) between them. User $u$ was able to influence 6000 other users 
overall, i.e., each of them retweeted at least one of $u$'s tweets (directly 
or transitively). 
This is the overall picture of $u$'s influence spread. Drilling down, the 
table shows two explanations describing a partial breakdown 
that covers a significant chunk of the influence mass. Each explanation 
is presented in terms of action topics and user demographics. E.g., 
the first explanation ($k = 1$) says $u$ tweeted about (topic) Obama 
100 times and 700 Vancouver based females retweeted one or more of her 
tweets at least once. And between them, $u$ racked up 4900 followups 
for his Obama tweets. 
The second explanation ($k = 2$) says user $u$ tweeted about topic Camera 30 
times and 4000 male students retweeted $u$'s tweets at least once. Between 
them, $u$'s camera tweets received 2100 followups in all. 
}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


Notice, the entries in each of the numeric columns (Action/Followers Count
and Followups) do \emph{not} sum to their overall values. That is, in
general, the explanations provided do not necessarily completely cover
the entire influence spread of the seed user.  Each explanation consists
of a description involving follower (user) demographics and action
attributes (e.g., topic). It also comes equipped with three statistics
-- action count, follower count, and followups, with the meaning described 
above. It is possible that different explanations cover overlapping
demographics, e.g., females in Vancouver and young college students in
BC. 

There are several benefits to this style of explanations in terms of
affording simple inferences. First, we can deduce that if Mike (in the
example above) rates an arbitrary movie again, he is likely to
receive 37.9K/3K = 12.6 followups on average. Next,
we know on what kinds of movies Mike is influential. Thus, if a
marketer wants to advertise a horror movie, then perhaps Mike is not a
good seed, even though his influence is quite high. Moreover, if Mike
rates a thriller movie rated R, it is likely that it will attract
6.7K/708 = 9.5 followups, from male users on average. 
Clearly, these types
of explanations are very informative and valuable. 



%\eat{
%The
%table presents that a significant chunk of influence of $u$ can be
%described in two explanations, where each explanation is of length 3.
%An explanation may consists of attributes/demographics from both action and
%user dimensions. In addition to demographics of actions and users, we want 
%each explanation to be equipped with three statistics -- \followups,
%\actionscount and \userscount.

%The first explanation tells us that the user $u$ has tweeted 100 times
%about Obama (Topic is an attribute in action dimension), and received
%4900 \followups from female users in Vancouver (Gender and Location are
%user attributes). Moreover, total number of female users in Vancouver
%are 700. Similarly, the second explanation suggests us that the user $u$
%posted 30 tweets about Camera which attracted 2100 \followups from male
%students, the total population of which is 4000.
%} 


%There are several benefits to this style of explanations in terms of
%affording simple inferences. First, we can deduce that if $u$ performs
%an arbitrary action again, she is likely to receive 8000/200 = 40
%followups on an average.  Next, the two explanations provided cover a
%significant chunk of $u$'s influence: (4900+2100)/8000 = 87.5\% of all
%followups are explained with these two explanations.  
%\note{Laks: We say explanations can overlap, but then add up their followups. 
%Why is it justified?} 
%We also know that
%user $u$ is interested in tweeting about topics Obama and Camera. So, if
%a marketer wants to advertise about purses, then $u$ is not a good seed,
%even if her overall influence is quite high. Moreover, if $u$ tweets
%about Obama in the future, it is likely that the tweet will attract
%4900/100 = 49 followups, from female users in Vancouver.
%, which amounts to 49/700 = 7\% of the population in that demographic.
%Clearly, these types
%of explanations are very informative and valuable. 

Notice that a trivial answer to providing explanations is to describe
every single followup for a given influencer. This is undesirable since
such an explanation would be verbose and uninformative to the marketer
trying to make sense of the influencer's influence. We thus argue for
providing crisp or concise explanations that explain as much of the
influence spread (in terms of followups) of the influencer, as possible.  

%\note{The inferences above are likely to change when exp. results come in. 
%Also, I am dropping the our approach stuff below. We need a separate problem statement 
%section where the input an doutput will be made precise.} 


\smallskip
\noindent
In the literature, the \emph{network value} of a user \cite{domingos01, kempe03} is treated as 
a scalar, i.e., it's equated with the (expected) influence spread of the user. We
argue that in order to answer the above questions, we must revisit this
notion. Our thesis is that there is much more to the network value of a
user than just a number: it can be seen as a summary of the influence
distribution of the user, which describes how the influence is
distributed, over what kind of user demographics and on what type of
actions. In this paper, we formulate and attack the problem of how to
characterize the distribution of influence of a given seed user. In
particular, we make the following contributions. 

%\note{The list of contributions needs to be strengthened. What are we doing besides 
%formulating this problem, showing its hardness and providing a heuristic sol.? 
%Specifically, what are the experiments telling us?
%} 

\begin{itemize}
	\item We propose a novel problem of PROviding eXplanations for
		Influencers' validation (\probname) to describe network value of
		a given influencer. We outline several benefits of providing
		explanations. 
	\item We show that \probname is not only \NPhard to solve exactly,
		it is \NPhard to approximate within any reasonable factor.
		However, by exploiting properties of the objective function, we
		develop an intuitive greedy heuristic.
	\item We perform experimental analysis on two real datasets --
		Flixster and Twitter, by exploring the influence distributions
		of top influencers, from both qualitative and quantitative
		angles. 
	\item Performing qualitative analysis, we establish the validity 
		of our framework, while gaining insights into influence
		spread of influencers. On the other hand, with quantitative
		analysis, we show that our algorithm explains a significant amount
		of the influence spread with a small number of crisp
		explanations. We compare our algorithm with various baselines,
		and show that it is both effective and efficient.
\end{itemize}


The rest of the paper is organized as follows. Related work is discussed
in \textsection\ref{sec:related}. We formalize the problem in
\textsection\ref{sec:probdef} and develop our algorithm in
\textsection\ref{sec:algo}. The experimental analysis is presented in
\textsection\ref{sec:exp}, while 
\textsection\ref{sec:concl} summarizes the paper and discusses future work.

%Section 4 describes data collection and
%preprocessing. Section 5 details the experiments conducted and reviews
%results.  Section 6 concludes and assess what is still to be done.


justifications.tex
%Paper ID: DM803 
%Paper Password: p8033477

%\documentclass{sig-alternate}
\documentclass[10pt,conference,compsocconf]{IEEEtran}
%\documentclass[10pt,conference]{IEEEtran}

\usepackage{color}
\usepackage[show]{notes}
\usepackage{url}
\usepackage{amsmath,amssymb}
\usepackage{epsfig}
%\usepackage{euler}
\usepackage{algorithm}
%\usepackage[noend]{algorithmic}
\usepackage{multirow}
\usepackage{xspace}
\usepackage{subfigure}
\usepackage{wrapfig}

% added by shea
\usepackage{graphicx}
\usepackage{amssymb}
\usepackage{epstopdf}
%\usepackage{algorithm}% http://ctan.org/pkg/algorithm
%\usepackage{algpseudocode}% http://ctan.org/pkg/algorithmicx
\usepackage{listings}


% added by glenn for algorithms
\usepackage{algorithm}
\usepackage[noend]{algorithmic}
%\usepackage{times}
% table with adjustable line width
\usepackage{tabu}



\definecolor{Gray}{gray}{0.8}


\definecolor{Amit_color}{rgb}{0.2,0.2,0.8} 
%\newcommand{\AG}[1]{{\color{Amit_color}  #1}} % For 'notes' Amit
\newcommand{\AG}[1]{{#1}}
%\newcommand{\LL}[1]{{\color{red}  #1}} % For 'notes' Amit
\newcommand{\LL}[1]{{#1}}
\definecolor{Glenn_color}{rgb}{0,0.6,0} 
%\newcommand{\GB}[1]{{\color{Glenn_color}  #1}} % For 'notes' Glenn
\newcommand{\GB}[1]{{#1}}

%\newcommand{\AG}[1]{{#1}} % For 'notes' Amit


% to get Shea's TexShop program to use .eps instead of .pdf files:
% !TEX TS-program = latex

\renewcommand{\algorithmicrequire}{\textbf{Input:}}
\renewcommand{\algorithmicensure}{\textbf{Output:}}
\renewcommand{\algorithmiccomment}[1]{// #1}
\newcommand{\HRule}{\rule{\linewidth}{0.5mm}}


% Paragraphs
\newcommand{\spara}[1]{\smallskip\noindent{\bf #1}}
\newcommand{\mpara}[1]{\medskip\noindent{\bf #1}}
\newcommand{\para}[1]{\noindent{\bf #1}}

\newtheorem{definition}{Definition}
\newtheorem{proposition}{Proposition}
\newtheorem{property}{Property}
\newtheorem{theorem}{Theorem}
\newtheorem{corollary}{Corollary}
\newtheorem{claim}{Claim}
\newtheorem{example}{Example}
\newtheorem{lemma}{Lemma}
\newtheorem{problem}{Problem}
\newtheorem{assumption}{Assumption}


\DeclareMathOperator*{\argmin}{arg\,min}
\DeclareMathOperator*{\argmax}{arg\,max}
\newcommand{\Nin}{\ensuremath{N_{\mathrm{in}}}}
\newcommand{\Nout}{\ensuremath{N_{\mathrm{out}}}}
\newcommand{\din}{\ensuremath{d_{\mathrm{in}}}}
\newcommand{\dout}{\ensuremath{d_{\mathrm{out}}}}

\newcommand{\eat}[1]{}
\newcommand{\A}{\mathcal{A}}
\newcommand{\I}{\mathcal{I}}
\newcommand{\J}{\mathcal{J}}
\newcommand{\M}{\mathcal{M}}
%\newcommand{\F}{\mathcal{F}}
\newcommand{\C}{\mathcal{C}}
\newcommand{\E}{\mathcal{E}}
\newcommand{\calP}{\mathcal{P}} % set of predicates
\newcommand{\FeaturesMap}{\mbox{FeaturesMap}}

\newcommand{\B}{\mathcal{B}}
\newcommand{\X}{\mathcal{X}}
\renewcommand{\S}{\mathcal{S}}
\newcommand{\spc} { \hspace{2pt}}
\newcommand{\dc}{\gamma}
\newcommand{\tc}{\Gamma}
\newcommand{\pp}{\Upsilon}
\newcommand{\infl}{\textit{infl}}
\newcommand{\followups}{\textsc{Followups}\xspace}
\newcommand{\actionscount}{\textsc{Actions\_Count}\xspace}
\newcommand{\userscount}{\textsc{Users\_Count}\xspace}
\newcommand{\probname}{\textsc{Proxi}\xspace}
\newcommand{\NextExplanation}{\textsc{NextExplanation}\xspace}
\newcommand{\MineExplanations}{\textsc{MineExplanations}\xspace}
\newcommand{\FeatureCov}{\textsc{FeatureCov}\xspace}

\newcommand{\cov}{\sigma}
\newcommand{\NPhard}{NP-hard\xspace}
\newcommand{\NPHard}{NP-hard\xspace}

\newcommand{\flixster}{\textsc{Flixster}\xspace}
\newcommand{\twitter}{\textsc{Twitter}\xspace}
\newcommand{\random}{\textsc{Random}\xspace}
\newcommand{\greedy}{\textsc{Greedy}\xspace}
\newcommand{\mostpopular}{\textsc{Most-Popular}\xspace}
\newcommand{\exhaustive}{\textsc{Exhaustive}\xspace}

\newlength{\figwidth} 
\setlength{\figwidth}{0.32\textwidth} 
\newlength{\figthree} 
\setlength{\figthree}{0.325\textwidth} 
\newlength{\figthreeone} 
\setlength{\figthreeone}{0.31\textwidth} 
\newlength{\figfour} 
\setlength{\figfour}{0.18\textwidth} 
\newlength{\figfourone} 
\setlength{\figfourone}{0.23\textwidth} 



%\renewcommand{\bar}{\overline}

\begin{document}

%\title{Where is the Influence? \\Providing Explanations to Influence
%\title{Who do you Influence and on What? \\Providing Explanations for
%Influencer Validation}
%\title{Influence Explanation by Segment Identification} 
%\title{Influence Explanation by Market Segment Strength Identification} 

%\title{Network Value of Customer Revisited: Providing Explanations for 
%Influencer Validation} 

\title{Validating Network Value of Influencers by means of Explanations} 

%\author{Author names suppressed for blind review}

% \eat{
%\numberofauthors{1}
\author{
\begin{tabular}{cccc}
Glenn S. Bevilacqua$^\dag$ \hspace{2mm} & Shealen Clare$^\ddag$ \hspace{2mm} & Amit Goyal$^\dag$ \hspace{2mm} & Laks V. S. Lakshmanan$^\dag$ \\
\end{tabular}
\\$ $\\
\begin{tabular}{ccc}
%\affaddr{University of British Columbia} \\
%\affaddr{Vancouver, B.C., Canada} \\
University of British Columbia \\
Vancouver, B.C., Canada \\
{\sf $^\dag$\{lennson,goyal,laks\}@cs.ubc.ca, $^\ddag$shealen.clare@gmail.com} 
\end{tabular}
}%}

\eat{
\numberofauthors{4}

\author{
\alignauthor Glenn Bevilacqua\\
\affaddr{University of British Columbia}\\
\affaddr{Vancouver, BC, Canada}\\
\smallskip
\email{lennson@cs.ubc.ca}
\and
\alignauthor Shealen Clare\\
\affaddr{University of British Columbia}\\
\affaddr{Vancouver, BC, Canada}\\
\smallskip
\email{shealen.clare@gmail.com}
\linebreak
\and
\alignauthor Amit Goyal \\
\affaddr{University of British Columbia}\\
\affaddr{Vancouver, BC, Canada}\\
\smallskip
\email{goyal@cs.ubc.ca}
\and
\alignauthor Laks V. S. Lakshmanan \\
\affaddr{University of British Columbia}\\
\affaddr{Vancouver, BC, Canada}\\
\smallskip
\email{laks@cs.ubc.ca}
}
}

\maketitle \sloppy

\input{abstract}

\section{Introduction}
\label{sec:intro}
\input{intro}

%\section{Framework}
%\label{sec:approach}
%\input{approach}

\section{Related Work}
\label{sec:related}
\input{related}

%\section{Background and Problem Studied}
%\label{sec:background}
%\input{background} 

%\section{Can Seeding Make A Difference?} 
%\label{sec:seeding} 
%\input{seeding} 

\section{Problem Definition}
\label{sec:probdef}
\input{probdef}


%\section{Complexity of RecMax} 
%\label{sec:hardness} 
%\input{hardness} 

\section{Algorithm}
\label{sec:algo}
\input{algo}


%\section{Explanation Compacting}
%\label{sec:exCompact}
%\input{exCompact}

\section{Experiments}
\label{sec:exp}
\input{exp}

%\section{Case Study 1: Flixster}
%\label{sec:flixster}
%\input{flixster}

%\section{Case Study 2: Twitter}
%\label{sec:twitter}
%\input{twitter}

%\section{Data Sets}
%\label{sec:data}
%\input{data}


%\section{Experiments}
%\label{sec:exp}
%\input{exp}

\section{Conclusions and Future Work} 
\label{sec:concl} 
\input{concl} 


%\section{Appendix}
%\label{sec:appendix}
%\input{appendix}

\vspace*{-4pt}
\scriptsize
\bibliographystyle{abbrv} 
\bibliography{singlebib}  
\end{document}

probdef.tex

\GB{We consider a directed social graph, $G = (V,D)$ over a set of users $V$ 
where each arc $(u,v)\in D$ 
indicates that user $v$ follows user $u$,\footnote{Our ideas and 
algorithms easily extend to undirected graphs such as those corresponding 
to friendship links.} 
%In addition, consider
and a propagation log $\mathbb{L}$, %i.e. 
a set of triples $(u, a, t_u)$ signifying that user $u$ performed action $a$ at time $t_u$.}
When the action $a$ is clear from the context, by $t_u$ we mean the time at which 
user $u$ performed action $a$. 
We say an action $a$ is \emph{propagated} from
$u$ to $v$ if $(u,v) \in D$, and the log $\mathbb{L}$ cotains the tuples 
$(u,a,t_u)$ and $(v,a,t_v)$ for some $t_u$ and $t_v$, such that $t_u < t_v$. 
This defines a \emph{propagation graph} of $a$ as a directed graph $G(a)
= (V(a), D(a))$, with $V(a) = \{u \in V | \exists t_u: (u, a, t_u) \in
\mathbb{L}\}$ and $D(a) = \{(u,v) \in D | u \in V(a), v \in V(a), \mbox{
and } t_u < t_v\}$.  Define an \emph{influence cube} $\C$ over the
dimensions Users (as influencers), Actions and Users (as followers) as
follows: for a cell $(u, a, v)$, $\C(u,a,v) = 1$ if there exists a
(directed) path from $u$ to $v$ in $G(a)$, i.e., $v$ performed action
$a$ after $u$ did. All other cells have value $0$. 

Given a user $u$, by a \emph{followup} of u, we mean a cell $(u,a,v)$
for which $\C(u,a,v) = 1$.  The \emph{followup set} of $u$ is then the
set of followups of $u$: $\M_u = \{(u,a,v) \mid \C(u,a,v) = 1\}$. When
the user is understood from the context, we use $\M$ instead of $\M_u$.
We assume users are equipped with a set of features (e.g., age, location
etc), and similarly for actions (e.g., topic). Descriptions for followup
sets are derived from attributes by means of predicates of the form
$\texttt{A} = \texttt{val}$ where \texttt{A} is an attribute and 
\texttt{val} is a value from its domain. \LL{We assume numeric attributes are 
binned into appropriate intervals. Thus it suffices to consider 
only equality. 
E.g., year = pre-1997, maturity-rating = ``rated R'', and 
gender = female are
predicates/features.} {\em We use the terms predicates and features
interchangeably}.  Let $\calP$ be the set of all predicates. Consider a
cell $(u,a,v)$ in $\M_u$, the followup set of user $u$, and a predicate
$p \in \calP$, we say the cell satisfies the
predicate, $(u, a, v) \models p$, provided 
\eat{that the $p$ is derived from
the attribute-value of action $a$ or from user $v$. } 
either $p$ is a user predicate and user $u$ satisfies this predicate or 
$p$ is an action predicate  and action $a$ satisfies this predicate. 
% 
%Given a
%cell $(u,a,v) \in \M_u$ and a predicate $p \in \calP$ of the form
%$\texttt{A} \mbox{ op } \texttt{val}$, we say the cell satisfies the
%predicate, $(u, a, v) \models p$, provided $f$ is an action feature, the
%action $a$ has feature $f$ and $a.f \mbox{ op } val$ is true; or $f$ is
%a user feature, the user $v$ has feature $f$ and $u.f \mbox{ op } val$
%is true. 
%Let $\calP$ be the set of all predicates. Given a
%cell $(u,a,v) \in \M_u$ and a
%predicate $p \in \calP$ of the form $\texttt{A} \mbox{ op } \texttt{val}$, we say the cell satisfies
%the predicate, $(u, a, v) \models p$, provided $f$ is an action feature,
%the action $a$ has feature $f$ and $a.f \mbox{ op } val$ is true; or $f$
%is a user feature, the user $v$ has feature $f$ and $u.f \mbox{ op }
%val$ is true.  Here, $a.f$ ($u.f$) refers to the value of action $a$
%(resp., user $u$) for feature $f$. 
For a predicate $p$, we define $\M^p
= \{(u,a,v) \mid (u,a,v)\in\M \,\&\,(u,a,v) \models p\}$, i.e., the subset of followups
satisfying the predicate. We define an \emph{explanation} as a
conjunction of one or more (user and/or action) predicates. 
Given an explanation $E$, we define $\M^E = \bigcap_{p \in E} \M^{p}$.
%Given an
%explanation $E = \{p_1, \cdots , p_l\}$, we define $\M^E =
%\bigcap_{1\le i\le l} \M^{p_i}$, 
i.e., the set of followups satisfying
all the predicates in $E$. We define the \emph{coverage} of an
explanation to be $\cov(E) = |\M^E|$, i.e., the number of followups
satisfying $E$.  


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 
\eat{ 
Essentially, our problem takes as input an influence cube $\C: Users
\times Actions \times Users$. Each cell $(u, a, v) \in \C$ contains a boolean
value: it is 1 if $u$ performed an action $a$ and user $v$ followed it
up, and $v$ is socially connected to $u$. We next provide a way to
build the cube $\C$ from a commonly used data for social influence
analysis \cite{leaders, amit2010, goyal2012}: social graph and
propagation log.

Suppose we are given a directed social graph $G = (V,D)$ such that a
directed
edge $(u,v) \in D$ implies that user $v \in V$ follows user $u \in V$.
Thus, the influence (or information) flows from $u$ to $v$. Suppose we are also
given a propagation log $\mathbb{L}$ in which a tuple $(u, a, t_u) \in
\mathbb{L}$ implies that user $u$ performed action $a$ at time $t_u$.
Given such input, we say that an action $a$ is \emph{propagated} from
user $u$ to user $v$ if $(u,v) \in D$ and $t_v > t_u$. 
%That is, $u$ and
%$v$ are friends and $v$ follows up the the action after $u$.
This defines a
\emph{propagation graph} of $a$ as a directed graph $G(a) = (V(a),
D(a))$, with $V(a) = \{u \in V | (u, a, t_u) \in \mathbb{L}\}$ and $D(a)
= \{(u,v) \in D | u \in V(a), v \in V(a), t_v > t_u\}$. Now, we
can build the cube $\C$ as follows: we say that a cell $(u, a, v) \in \C$ is
1 if there exists a path from $u$ to $v$ in $G(a)$. All other cells have
value 0 in $\C$. 

Given a user $u$ of which we are interested in analyzing influence, we
define its \emph{followup set} $\M_u$ as the set of cells $(u, \cdot,
\cdot) \in \C$ whose value is 1. Hereforth, for the ease of exposition,
we drop the subscript $u$ from $\M_u$ and refer to it as $\M$. 


In addition to $\C$, we also take as input $\F$: the set of binary features, for both actions
and users. For each attribute-value pair (in action or user dimension), we construct a binary feature.
For instance, an attribute ``Gender'' in user dimension may assume two values -- Male and
Female. Correspondingly, we construct two features -- Gender\_Male and
Gender\_Female. A feature may be either ``absent'' or ``present''.  Let
$\F_v$ be the set of user features present for user $v$ and $\F_a$ be
the set of action features present for action $a$.  Then, the
features present for a cell $(u,a,v)$, is defined to be $\F_{(a,v)} =
\F_a \cup \F_v$. Furthermore, with $\M^f \subseteq \M$, we denote the
set of cells selected by the feature $f$. That is, $\M^f = \{(u,a,v) | f
\in \F_{(a,v)} \}$.

Our goal is to construct a set of $k$ explanations for a user's followup set, 
each of which is of
length at least $l$ such that these explanations cover as much influence
of $u$ as possible.  } 
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 


Our goal is to provide explanations for the followup set of a 
user (candidate influencer). On one hand, we would like each explanation 
to be as informative as possible. On the other, the total size of explanations 
should be concise or crisp so that a human (marketer) can quickly 
make sense of them. At the same time, between them, the explanations should 
cover as much ``influence mass'' as possible. We formalize these intuitions by 
insisting that each explanation should have length $\ge l$ and ask for a set 
of at most $k$ explanations $\E = \{E_1, ..., E_k\}$ such that the number of followups 
covered by these explanations is as large as possible. For a set of explanations 
$\E$, we extend coverage as follows: define $\M^{\E} = \bigcup_{E\in\E} \M^E$ and 
finally, define the \emph{coverage} of a set of explanations as 
$\cov(\E) = |\M^{\E}|$, i.e., the number of followps in $\M$ which satisfy 
at least one explanation in $\E$. That is,
\begin{align}
	\cov(\E) = |\M^{\E}| = | \bigcup_{E\in\E} \M^E | = |
	\bigcup_{E\in\E} \bigcap_{p \in E} \M^{p} |
\end{align}

%Consider again the example illustrated in Table
%\ref{tab:flixster_firstUser}. There, the parameters $k$ and $l$ are set
%to 6 and 3.

%\note{Laks: Revisit the (NEW) motivating example from Sec. 1 and illustrate a set of 
%two expanations of length $> 1$. } 

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\eat{ 
Intuitively, we wish each explanation to be as expressive as possible,
and thus we impose $l$ as the lower bound on the length of an explanation.
Moreover, we want to describe as much influence (or as many followups)
as possible with a small number of explanations. Hence, we set $k$ as
the upper bound on the number of explanations. 
With $E \subseteq 2^{\F}$, we denote a set of features that constitutes
one explanation. Similarly, with $\E \subseteq 2^{2^\F}$, we denote a 
set of
explanations. 
%Let $E \in \E$ be one explanation, which can also be
%viewed as a set of features. 
We use $\M^E \subseteq \M$ as the set
of the cells selected by features in $E$, as follows.
\begin{align}
\M^E = \bigcap_{f \in E} \M^f = \{(u,a,v) | \forall f \in E: f \in \F_{(a,v)} \}
\end{align}


%We let $\E \subseteq 2^{\F}$ denote a set of explanations. Our goal is to
%construct a set of $k$ explanations, each of which is of length at least
%$l$ such that these explanations cover as much influence of $u$ as
%possible. 
%We can denote each explanation with a set of features $F$. 
Moreover, we define $\cov(E) : 2^\F \rightarrow \mathbb{R}$ as the
\emph{coverage} of an explanation $E$. And similarly, we overload
$\cov(\cdot)$ and let $\cov(\E) :
2^{2^\F} \rightarrow \mathbb{R}$ denote the 
\emph{coverage} of explanations $\E$, for the user in the context $u$. 
\begin{align}\label{eq:cov}
\cov(\E) = | \M^\E | = | \bigcup_{E \in \E} \M^E |
\end{align}

where $\M^\E$ denote the set of cells selected by explanations $\E$. We
are now ready to define our problem \probname (PROviding eXpLanations) formally. 
} 
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 

\LL{Note the term coverage is defined for a single explanation as well as for a 
set of explanations. In discussing  
the properties of the coverage function,} \GB{we 
%would want to 
consider }
\LL{both $\sigma(E): 2^{\calP} \rightarrow \mathbb{R}$, coverage of a single explanation as a 
function of the features in the 
explanation, as well as 
$\sigma(\E): 2^{2^{\calP}} \rightarrow \mathbb{R}$, coverage of a set of explanations as a 
function of the explanations 
in the set $\E$. The notation and the context should make it clear.}

The main problem we study in this paper is \probname (PROviding eXplanations for
validating the network value of Influencers): 

\begin{problem}[\probname]\label{prob}
{\em
Given a user $u$, followup set $\M$, the available user and action
predicates $\calP$, and numbers $k$ and $l$, find a set of at most $k$
explanations $\E = \{E_1, ..., E_k\}$, where each explanation $E_i$ is a
conjunction of at least $l$ (user/action) predicates such that
$\cov(\E)$ is maximized.
}
\end{problem}

The lower bound $l$ on the size of each explanation captures the
intuition that explanations should be informative. The upper bound $k$
on the number of explanations captures the intuition that overall the
explanations should be crisp. At the same time, problem asks for the
influence mass covered (coverage) to be maximum.  


\subsection{Hardness of PROXI}
Not surprisingly, it turns out that \probname is \NPhard. Unfortunately
though, not only it is \NPhard to solve exactly, it is \NPhard to
approximate within any reasonable factor, even when $k=1$, which in
other words is the problem of generating one explanation
(Thm.~\ref{thm:nphardness}).  We establish
the hardness by exploiting its equivalence with the problem of
\emph{Maximum $l$-Subset Intersection} (MSI for short). However, to develop
intuitions for building our algorithm, we show some interesting
properties of the objective function $\cov(\E)$. In particular, we show
that the function $\cov(\E)$ is monotonically increasing and
submodular (Thm.~\ref{thm:sm1}), while the function $\cov(E)$ is
monotonically decreasing and supermodular (Thm.~\ref{thm:sm2}). We
exploit these results to develop our algorithm
(\textsection\ref{sec:algo}).
%It implies that if somehow we have a subroutine for MSI that outputs an optimal
%explanation of length $l$, then we can use this subroutine to
%approximate \probname within a factor of $(1-1/e)$, using a 
%greedy algorithm\footnote{Nemhauser et al.~\cite{submodular} showed that
%a greedy algorithm approximates the problem of maximizing monotone
%submodular functions within a factor of $(1-1/e)$. Later, it was shown
%that this approximation factor cannot be improved unless P=NP
%\cite{feige98}.}. Since we cannot have an optimal subroutine for MSI,
%we cannot guarantee any approximation factor. However, this insight
%suggests us that a reasonable heuristic to generate the set of
%explanations $\E$ would be to use the greedy algorithm
%(\textsection\ref{sec:algo}).


\begin{theorem}\label{thm:nphardness}
Problem \probname is \NPhard to solve exactly. Moreover, it cannot be
approximated within a factor of $0.5 n^{1 - 2\epsilon} + O(1 - 3 \epsilon)$ for any
$\epsilon > 0$, unless P=NP.
\end{theorem}

% http://www.ic.unicamp.br/~eduardo/publications/ipl12.pdf
\begin{proof} 
We prove the claim for the special case when $k=1$. In this 
case, the problem reduces to finding exactly one explanation $E$, of
length $l$ such
that $\cov(E)$ is maximized. Since $\cov(E)$
is defined as the intersection of sets $\M^p$ for all $p \in E$, the
problem is equivalent to \emph{Maximum $l$-Subset Intersection} (MSI)
Problem \cite{xavier2012, shieh2012}: Given a collection of sets $\S =
\{S_1, S_2, \ldots, S_m\}$ over a universe of elements $\mathcal{U} =
\{e_1, e_2, \ldots, e_n\}$,
the objective is to select (no less than) $l$ sets $\S' \subseteq \S$,
$\S' = \{S_{i_1}, S_{i_2}, \ldots, S_{i_l}\}$
such that its intersection size, $|S_{i_1} \cap S_{i_2} \cap \cdots S_{i_l}|$, is maximum.

It is easy to see that MSI is equivalent to \probname when $k=1$. An
element $e \in \mathcal{U}$ in MSI corresponds to a cell $(u,a,v)$ with
a value 1 in \probname. Similarly, a set $S$ corresponds to $\M^p$, the
set of cells selected by a predicate $p$. Furthermore, the objective is
equivalent -- select $l$ sets ($l$ predicates) such that the resulting
intersection size is maximum. The formal reduction from MSI to \probname 
and the other way around
is thus straightforward and we skip it for brevity.

It is well known that MSI is \NPhard, and is \NPhard to approximate it within a factor
a $0.5 n^{1 - 2 \epsilon} + O(1 - 3 \epsilon)$ \cite{shieh2012}. Given the equivalence 
between \probname and MSI, the theorem follows.
\end{proof}

%%%%%%%%%%%%%%%%%%%%% 
\eat{
\note{Laks: ${\cal E}*$ vs. ${\cal E}'$ issue needs to be fixed. Glenn: resolved}
}
%%%%%%%%%%%%%%%%%%%%% 

\begin{theorem}\label{thm:sm1}
The function $\cov(\E): 2^{2^{\calP}} \rightarrow \mathbb{R}$ is
monotonically increasing and submodular. That is, $\forall \E \subseteq
\E' \subseteq 2^{2^\calP} : \cov(\E) \le \cov(\E')$ and 
$ \cov(\E \cup \{E\}) - \cov(\E) \ge \cov(\E' \cup \{E\}) - \cov(\E')$.
\end{theorem}

\begin{proof}
First, we show that the objective function $\cov(\E)$ is monotonically
increasing. By definition of $\cov(\E)$, we have,
\begin{align*}
\cov(\E \cup \{E\}) - \cov(\E) = |\M^{\E} \cup \M^{E}| - |\M^{\E}|
\end{align*}

Clearly, $\M^{\E} \cup \M^{E}$ is a superset of $\M^\E$, the above
quantity is non-negative, implying that $\cov(\E)$ is monotonically
increasing.
Next, we show the property of submodularity. 
\begin{align*}
\cov(\E' \cup \{E\}) & - \cov(\E') = |\M^{\E'} \cup \M^{E}| - |\M^{\E'}|\\
% Step via \M^{\E'} being a subset of \M^{\E'} \cup \M^{E}
&= |(\M^{\E'} \cup \M^{E}) \setminus \M^{\E'}| \\ 
% Step via \M^{\E} being a subset of \M^{\E'}, so \M^{\E'} == \M^{\E} \cup \M^{\E'}
&= |(\M^{\E} \cup \M^{\E'} \cup \M^{E}) \setminus (\M^{\E} \cup \M^{\E'}) |  \\
% Step via splitting minus of union into two minuses and (\M^{\E} \cup \M^{\E'} \cup \M^{E}) \ \M^{\E'} == (\M^{\E} \cup \M^{E}) \ \M^{\E'}
&= |((\M^{\E} \cup \M^{E}) \setminus \M^{\E}) \setminus \M^{\E'} | 
\end{align*}

Since set subraction may only remove set elements,
\begin{align*}
\cov(\E' \cup \{E\})  - \cov(\E') &\le |(\M^{\E} \cup \M^{E}) \setminus \M^{\E} | \\
&\le \cov(\E \cup \{E\}) - \cov(\E)
\end{align*}

which is what we wanted to prove. 
\end{proof}

%%%%%%%%%%%%%%%%%%%%%%%%% 
\eat{
\note{Laks: For monotone non-increasing, isn't it obvious the more features you add 
the smaller the intersection? For submodularity, I wonder whether there is a need for 
$E^*$. Can't we prove it from first principles just using $E$ and $E'$ and $f\not\in E'$? 
The proof looks more complicated than it needs to be. Glenn: resolved} 
}

\begin{theorem}\label{thm:sm2}
The function $\cov(E): 2^\calP \rightarrow \mathbb{R}$ is monotonically decreasing and
supermodular. That is, $\forall E \subseteq
E' \subseteq 2^\calP : \cov(E) \ge \cov(E')$ and 
$ \cov(E \cup \{p\}) - \cov(E) \le \cov(E' \cup \{p\}) - \cov(E')$.
\end{theorem}

\begin{proof}
First, we show that the objective function $\cov(E)$ is monotonically
decreasing. By definition of $\cov(E)$, we have,
\begin{align*}
\cov(E \cup \{p\}) - \cov(E) = |\M^{E} \cap \M^{p}| - |\M^{E}|
\end{align*}

Clearly, $\M^{E} \cap \M^{p}$ is a subset of $\M^E$, the above
quantity is non-positive, implying that $\cov(E)$ is monotonically
decreasing.
We next show the property of supermodularity. 

\begin{align*}
\cov(E' \cup \{p\}) & - \cov(E') = - (|\M^{E'}| - |\M^{E'} \cap \M^{p}|)\\
% Step via \M^{E'} \cap \M^{f} being a subset of \M^{E'}
&= - |\M^{E'} \setminus (\M^{E'} \cap \M^{p})| \\
% Step via \M^{E'} being a subset of \M^{\E}, so \M^{\E'} == \M^{\E} \cup \M^{\E'}
&= - |(\M^{E} \cap \M^{E'}) \setminus (\M^{E} \cap \M^{E'} \cap \M^{p})|  \\
% Step via factoring out \M^{E'}
&= - |\M^{E'} \cap (\M^{E} \setminus (\M^{E} \cap \M^{p}))| 
\end{align*}

Since set intersect may only remove set elements,
\begin{align*}
\cov(E' \cup \{p\})  - \cov(E') &\ge - |(\M^{E} \setminus (\M^{E} \cap
\M^{p}) |\\
&\ge \cov(E \cup \{p\}) - \cov(E)
\end{align*}

which is what we wanted to prove. 
\end{proof}



%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%% BIG EAT

\eat{


\note{Amit: Notes above are written by me.}

The goal is the creation of detailed explanations by enssuring the use
of a sufficient number of user and action attributes while capturing a
substantial porition of the target user's influence. Given as input is a
followup set, $\M$, where $\M_u$ is the set of followups that correspond
to actions of the influencer $u$. A followup element, $(u,a,v)$, is
present in $\M_u$ if user $v$ followedup on $u$'s action $a$. Also
provided is a set of binary attributes, $\F$, for both actions and
followers. An attribute may be either ``absent'' or ``present''. Let
$\F_u$ be the set of user attributes present for user $u$ and $\F_a$ be
the set of action attributes present for action $a$. Then, the
attributes present for a followup element, $(u,a,v)$, is defined to be
$\F_{(a,v)} = \F_a \cup \F_v$. 

In construction of an explanation we are interested in finding user and
action attributes that select many of the followups contained in $\M_u$.
Each attribute selects a subset of the followups present in $\M_u$.  The
selected followups are those that have the attribute present.  Let
$\M_u^f$ be the subset of $\M_u$ selected by attribute $f \in \F$. An
explantion that makes use of a conjunction of attribute is more specific
but comes at the consequence of potentially reducing the followups
captured. We are interested in finding a set of attribute, $F \subset
\F$, of at least a certain size that retains the largest number of
followups contained $\M_u$ in their intersection.  Formally, we want to
maximize the \textit{coverage} of the attribute set, where the coverage
of a set of attribute with respect $\M_u$, denoted by $\cov(F; \M_u)$,
is defined to be cardinality of the set $\M_u^F$.

%Formally, we want to maximize the \textit{coverage} of the attribute set, where the coverage of a set of attribute with respect $\M_u$, denoted by $\cov(F; \M_u)$, is be defined as,

\begin{align}
\M_u^F = \bigcap_{f \in F} \M_u^f %\\
%\cov(F; \M_S) = cm(\M_S^F)
\end{align}

\begin{problem}
{\em
Given a user $u$, followup set $\M$, the available attributes and
their correspondence to users and actions $\F$, and a number $k$, find a
set of attributes $F \subset \F: |F| \ge k$ such that $|\M_u^F|$ is maximized.
}
\end{problem}

The coverage of $F$ is monotonic decreasing in the number of attributes in
$F$ due to the addition of an attributes results in one more set
intersection. Intersecting an additional set with the previous result
can only maintain all elements of the previous result or remove
elements. Furthermore, the coverage lost by the addition of a attributes is
reduced as other attributes are added. That is, coverage is
supermodular, statisfing the property: 
$f(A \cup {v}) - f(A) \le f(B \cup {v}) - f(B)$ where $A \subset B$.

\begin{proof}
Given an arbitary $\M_u$, for syntactic simplicity let this be $\M$, and some current set of attributes $F$ the addition of an arbitrary attribute $f$ results in the marginal change of,

{\setlength\arraycolsep{0.1em}
\begin{eqnarray}
\cov(F \cup {f}; \M) - \cov(F; \M) &=& -|\M^F \setminus (\M^F \cap \M^f)| \nonumber
%\cov(F \cup {f}; \M_S) - \cov(F; \M_S) &=& cm(\M_S^F \cap \M_S^f) - cm(\M_S^F) \nonumber \\
%&=& -(cm(\M_S^F) - cm(\M_S^F \cap \M_S^f)) \nonumber \\
%&=& -cm(\M_S^F - \M_S^F \cap \M_S^f) \nonumber
\end{eqnarray}
}

The equivalence holds due to $\M^F$ containing all elements of $\M^F \cap \M^f$.

Adding an arbitrary a set of attributes $F^{*}$, other than $f$, to the set $F$ to create a new attribute set $F' = F \cup F^{*}$.
Now, the addition of $f$ to $F'$ results in the marginal change of,

{\setlength\arraycolsep{0.1em}
\begin{eqnarray}
\cov(F' \cup {f}; \M) &-& \cov(F'; \M) = -|\M^{F'} \setminus (\M^{F'} \cap \M^f)| \nonumber \\
&=& -|(\M^F \cap \M^{F^{*}}) \setminus (\M^F \cap \M^{F^{*}} \cap \M^f)| \nonumber \\
&=& -|(\M^F \setminus (\M^F \cap \M^f)) \cap \M^{F^{*}}| \nonumber
%\cov(F' \cup {f}; \M_S) &-& \cov(F'; \M_S) = cm(\M_S^{F'} \cap \M_S^f) - cm(\M_S^{F'}) \nonumber \\
%&=& -cm(\M_S^{F'} - \M_S^{F'} \cap \M_S^f) \nonumber \\
%&=& -cm(\M_S^F \cap \M_S^{F^{*}} - \M_S^F \cap \M_S^{F^{*}} \cap \M_S^f) \nonumber \\
%&=& -cm((\M_S^F - \M_S^F \cap \M_S^f) \cap \M_S^{F^{*}}) \nonumber 
\end{eqnarray}
}
Since set intersection may only remove set elements,

\begin{align}
|\M^F \setminus (\M^F \cap \M^f)| \ge |(\M^F \setminus (\M^F \cap \M^f)) \cap \M^{F^{*}}| \nonumber 
\end{align}

Hence, region coverage is supermodular.
\end{proof}

The problem of maximizing a supermodular function with a cardinality constraint is known to be NP-hard. The negation ,$-\cov(\cdot)$,  converts from maximizing a supermodular function to an equivalent minimization of a submodular function problem. Minimizing a general submodular function under a cardinality constraint is known to be inapproximable within $O(\sqrt{n/\log{n}})$ \cite{submodularhardness}.

Furthermore, we are interested in finding not just one region but rather a set of regions, such that even with each block having high specificity (large $k$) the collection of regions still captures the bulk followups.  An explanation, $E \subset 2^{\F}$, then is a set of sets of attributes. The coverage of an explanation, $\cov(E; \M_u)$, is defined to be the cardinality of $\M_u^E$.

\begin{align}
\M_u^E = \bigcup_{F \in E} \M_u^F %\\
%\cov(E; \M_S) = cm(\M_S^E)
\end{align}

\begin{problem}
{\em
Given a user $u$, followup set $\M$, the available attributes and their correspondence to users and actions $\F$, and numbers $k$ and $l$, find a set of sets of attributes $E \subset 2^{\F}: |E| \le l$ where $\forall_{F \in E}: |F| \ge k$, such that $\cov(E; \M_u)$ is maximized.
}
\end{problem}

The coverage of $E$ is monotonic increasing in the number of sets of attributes in $E$ due to the addition of a set of attributes results in one more set union. The union of an additional set with the previous result can only maintain all elements of the previous result or add elements. Furthermore, the coverage gained by the addition of a set of attributes is reduced as other sets of attributes are added. That is, explanation coverage is submodular, statisfing the property: 
$f(A \cup {v}) - f(A) \ge f(B \cup {v}) - f(B)$ where $A \subset B$.

\begin{proof}
Given an arbitary $\M_u$, for syntactic simplicity let this be $\M$, and some current set of sets of attributes $E$ the addition of an arbitrary set of attributes $F$ results in the marginal change of,

{\setlength\arraycolsep{0.1em}
\begin{eqnarray}
\cov(E \cup {F}; \M) - \cov(E; \M) &=& |(\M^E \cup \M^F) \setminus \M^E| \nonumber
%\cov(E \cup {F}; \M_S) - \cov(E; \M_S) &=& cm(\M_S^E \cup \M_S^F) - cm(\M_S^E) \nonumber \\
%&=& cm(\M_S^E \cup \M_S^F - \M_S^E) \nonumber
\end{eqnarray}
}

The equivalence holds due to $\M_S^F$ containing all elements of $\M_S^F \cap \M_S^f$.

Adding arbitrary set of attributes other than $F$, $E^{*}$, to the set $E$ to create a new explanation $E' = E \cup E^{*}$.
The addition of $F$ to $E'$ results in the marginal change of,

{\setlength\arraycolsep{0.1em}
\begin{eqnarray}
\cov(E' \cup {F}; \M) &-& \cov(E'; \M) = |(\M^{E'} \cup \M^F) \setminus \M^{E'}| \nonumber \\
&=& |(\M^{E} \cup \M^{E^{*}} \cup \M^F) \setminus (\M^{E} \cup \M^{E^{*}})| \nonumber \\
&=& |((\M^{E} \cup \M^F) \setminus \M^{E}) \setminus \M^{E^{*}}| \nonumber 
%\cov(E' \cup {F}; \M_S) &-& \cov(E'; \M_S) = cm(\M_S^{E'} \cup \M_S^F) - cm(\M_S^{E'}) \nonumber \\
%&=& cm(\M_S^{E'} \cup \M_S^F - \M_S^{E'}) \nonumber \\
%&=& cm(\M_S^{E} \cup \M_S^{E^{*}} \cup \M_S^F - \M_S^{E} \cup \M_S^{E^{*}}) \nonumber \\
%&=& cm((\M_S^{E} \cup \M_S^F - \M_S^{E}) - \M_S^{E^{*}}) \nonumber 
\end{eqnarray}
}
Since set subraction may only remove set elements,

\begin{align}
|(\M^E \cup \M^F) \setminus \M^E| \ge |((\M^{E} \cup \M^F) \setminus \M^{E}) \setminus \M^{E^{*}}| \nonumber 
\end{align}

Hence, explanation coverage is submodular.
\end{proof}

While being known to be NP-hard maximization of a monotone submodular functions a greedy algorithm, repeatedly adding an element that gives the maximum marginal gain, approximates the optimal solution within a factor of $(1 - 1/e)$. If the internal problem of finding the optimal sets of attributes is resolved by an oracle the outer task of the selecting $l$ of these sets of attributes can provide an $(1 - 1/e)$ guarentee on the coverage of the explanation.

}
%Let $\M$ be the three dimensional influence cube $Users \times Actions
%\times Users$, such that $\M_u(a, v)$ represents the influence credit
%that is given to user $u$ for influencing user $v$ for action $a$. As
%the first problem statement, given a user $u$, we are interested in
%providing justification for the influence that $u$ possesses. We use
%$\M_u$ to represent the projection of the influence cube $\M$ on user
%$u$ in first dimension. 
%In other words, $\M_u$ represents the influence
%matrix containing actions that $u$ performs, such that $\M_u(a, v)$ is
%the influence credit given to $u$ for influencing $v$ on action $a$. 

%In addition, we assume we are given the set of features (in binary form)
%for both actions and users. Each feature can have only two values
%corresponding to whether the feature is ``absent'' or ``present''. 
%Let $F = \{f_1, f_2, \cdots\}$ be the set of features that are present.
%For a given user $u$, we are interested in finding the set of features
%$F$ such that these features explain the bulk mass of influence score
%that user $u$ has. In other words, we want to maximize the
%\textit{coverage} of the feature set, where coverage, denoted by $\cov$,
%can be defined as,
%\begin{align}
%\cov(F) = \sum_{(a,v)} M_u(a,v) \cdot I(a \mbox{ belongs to } F) \cdot
%I(v \mbox{ belongs to } F)
%\end{align}
%
%That is, coverage of a feature set $F$ is the sum of matrix that
%corresponds to feature set $F$. 
%Now, we formally define the problem statement.
%\begin{problem}
%{\em
%Given a user $u$, $\M_u$, feature sets on all actions and users, and a
%number $k$, find a set of features $S: |S| \ge k$ such that $\cov(S)$ is maximized.
%}
%\end{problem}

%It should be noted that as we expand the feature set $F$, the coverage
%decreases and hence, the function $\cov(\cdot)$ is a monotonically
%decreasing function. It also seems that the marginal loss should
%decrease in each iteration, and hence, it looks like the  function
%$\cov(\cdot)$ is supermodular. Thus, our problems looks very similar to
%supermodular function maximization, and thus, submodular function
%minimization.



qualitative.tex

Through qualitative analysis, we  mainly seek to validate our problem
settings, approach and algorithm. But we note the limitations imposed by
the public datasets available. In Twitter dataset, we know the identity
of the influencers. We can thus validate our approach by checking if the
distribution of influence is along the expected lines. On the other
hand, in Flixster dataset, we do not know the identity of the
influencers, but have the access to both user and action attributes.
Thus, in this case, we can examine the benefits of incorporating
followers' demographics (as we saw in the example shown in Table
\ref{tab:flixster_firstUser}).
%Thus, in this case, we can  do the checking at a high level.
%We begin by examining Flixster.


%\begin{table*}[t]
%\parbox{.48\linewidth}{
%\input{table_flixsterAttributes}
%}

%\begin{table*}[t]
%\parbox{.48\linewidth}{
%\input{table_flixster1stUser}
%}
%\end{table*}
%\hfill
\begin{table*}[t]
\parbox{.48\linewidth}{
\input{table_flixster2ndUser}
}
\parbox{.48\linewidth}{
\input{table_flixster3rdUser}
}
%\hfill
\end{table*}


\eat{
\begin{table}

\input{table_flixster1stUser}

\input{table_flixster2ndUser}

\input{table_flixster3rdUser}

\end{table}
}

%\input{table_flixster1stUser}
%\input{table_flixster2ndUser}

\noindent
\textbf{Formatting the Explanations.}
%\input{exCompact}
To avoid clutter, in the explanation tables, we do not mention the name
of each attribute, and instead show its required value directly.  For
instance, consider the example in Table \ref{tab:flixster_firstUser}.
Here, ``rated R'' indicates the feature ``maturity rating = rating R'' and ``thriller''
implies ``genre = thriller''. Similarly, we combine overlapping features
(or predicates) from various explanations, to allow us to visualize the
explanations in a tree structure. As an example, the features ``rated
R'' and ``thriller'' are present in the first two explanations. We order
the features in a manner that minimizes the repetition of the features
in the explanations table.

\noindent
\textbf{Flixster.} 
%
%\eat{
%\note{Laks: Please show flixster tables together and twitter tables togethr. they are 
%currently split. Be sure to mention the names of users (Mike, Kali, Julie) in the table that 
%concerns them. E.g., `` ... Top user (Mike) ...''} 
%}
We take the top-3 influencers measured in terms of the number of
followups they recieve,  and apply our algorithm to generate
explanations, for examining their influence distribution. The results
are presented in  Tables \ref{tab:flixster_firstUser},
\ref{tab:flixster_secondUser} and \ref{tab:flixster_thirdUser}. For
simplicity, we refer to the top-3 users as Mike, Kali, and Julie, even
though their identities in Flixster are unknown.  Table
\ref{tab:flixster} shows the complete set of movie features. For users,
we have the features corresponding to attributes gender and age. The
intent should be clear from the context. 

%Consider  user Mike (Table
%\ref{tab:flixster_firstUser}). As shown in the table, Mike has rated 3K movies and has 106 active
%followers (friends of Mike who have rated at least one movie after Mike). In
%total, he has received 37.9K followups, that is, 12.6 followups on each movie he
%rated. We run our algorithm to generate the explanations with parameter
%settings $k$ and $l$ as 3. 
%
%With just 6 crisp explanations, our algorithm is able to explain 56.3\% of Mike's 
%followups. As an example, 6.7K followups came from male followers, on Mike's 
%ratings on thriller  movies rated R. %(movies restricted to persons of
%age 17 or older). 
%Moreover, 2.3K followups came from females on the same
%category of movies, suggesting that Mike is quite influential on R-rated
%thriller movies. The Actions column tells us that there are  708 such movies
%(thriller, R rated) that are rated by Mike, while the Followers column tells us
%that out of 106 followers, 67 are males and 37 are females and 2 (= 106 - (67 + 37)) 
%others did  not
%specify their gender. Other explanations reveal that Mike is also influential on
%drama movies on males, and old (pre-1997) comedy movies regardless of gender.

While Table \ref{tab:flixster_firstUser} shows the explanations for the
most influential user (please see \textsection\ref{sec:intro} for more
details about this user), 
Tables \ref{tab:flixster_secondUser} and \ref{tab:flixster_thirdUser} show the
explanations for users who received second and third most number of followups, 
Kali and Julie, 
respectively. Kali has rated 2.8K movies and
received 27K followups from her 93 active followers. Julie has rated 1.8K movies
and received 23.5K followups from her 73 active followers. While Kali's
explanations cover 51.4\% of her followups, Julie's explanations cover 
68.7\% of her followups. 

Julie in particular
is influential on female users, with all her followups in the explanations
coming from female users. 
In fact, 63 among
73 of her followers are females. Finally, she is influential on all sorts of
movies (on female users), ranging from comedy, drama, thiller and action. This
implies that {\sl Julie might be a very good seed if the target market is females},
perhaps better than the top-2 users whose influence is distributed among both
males and females. This is the sort of insight that simply cannot be gained by 
viewing network values solely as a scalar!
A final remark about the explanations found is that they are heterogeneous, in that 
they involve a mix of user and action features. 


\noindent
\textbf{Twitter.} 
We next analyze the results from Twitter dataset. Recall that we have
user identities of key influencers in Twitter, which allows us to
validate whether the topics on which these influencers reported to be
influential by our algorithm are along the expected lines. This provides
us a nice strategy to validate our problem settings \GB{and approach}.
For instance, we expect  news accounts like New York Times (NYTimes) and
CNN to be influential on  topics like news, politics, media, etc, and
individuals like Tim O'Reilly to be influential on news on software,
tech, programming etc. Fortunately, we were able to generate a rich set
of topics for tweets by expanding their mentioned URLs. 

%\note{Laks: Check!, Glenn: checked} 
While we have the identity of the key influencers, for followers, 
we could not collect user
attributes due to demographic data not being available through the API.
Thus, our analysis is restricted to the action
attributes, which consist of tweet topics. We focus on explanations of four
influencers (Twitter accounts) -- New York Times, National Geographic, CNN Breaking News and
Tim O'Reilly, the results of which are presented in Tables \ref{tab:nytimes},
\ref{tab:cnn}, \ref{tab:timreilly} and \ref{tab:nationalgeo}.

\eat{
\begin{table}

\input{table_twitterNYTimes}

\input{table_twitterCNN}

\input{table_twitterTimReilly}

\input{table_twitterNationalGeo}

\end{table}
}

\begin{table*}[t]
\parbox{.5\linewidth}{
\input{table_twitterNYTimes}
}
%\hfill
\parbox{.5\linewidth}{
\input{table_twitterCNN}
}
\end{table*}

\begin{table*}[t]
\parbox{.5\linewidth}{
\input{table_twitterTimReilly}
}
%\hfill
\parbox{.5\linewidth}{
\input{table_twitterNationalGeo}
}
\end{table*}

%\input{table_twitterNYTimes}
%\input{table_twitterNationalGeo}
%\input{table_twitterCNN}
%\input{table_twitterTimReilly}

Consider the news accounts NYTimes and CNN first. As we expect, both
these accounts are influential on topics ``news'' and ``politics''. Moreover,
CNN is quite influential on topics like ``tv'' and ``breaking news'', which do
not appear in explanations of NYTimes. This makes sense as CNN is a
television news channel, while NYTimes is a newspaper. Another interesting
observation is that topics like ``religion'' and ``christianity'' appear in CNN
explanations (but not in NYTimes explanations) indicating CNN 
airs programs about religion. In the
sample we collected, CNN tweeted about religion and christianity only once, and
received 434 retweets -- much higher than the average of 56200/390 = 144
retweets per CNN tweet. Similarly, topics ``journalism'' and ``photos'' can be 
found in NYTimes explanations but not in CNN ones, while the topics ``business'' 
and ``politics'' can be found in both. 
Finally, it is interesting to note that these explanations
are able to cover almost all the followups -- 82.8\% for NYTimes and 99.8\% for
CNN, suggesting that these accounts are followed mostly because of their news,
politics, media etc, i.e., the topics represented in the explanations shown in 
these tables.


Next, in Table \ref{tab:timreilly}, we show the explanations of influence of Tim
O'Reilly, the founder of O'Reilly Media and a supporter of the free software and
open source movements. Topics like ``news, tech, media,
software, open source, programming, development, google'' etc.~emerge as the
topics of his influence, which agrees with our expectation. 
Finally, we explore the influence of the National
Geographic Channel in Table \ref{tab:nationalgeo}. This account is influential
on ``science, nature, geography travel'' etc, again consistent with our 
expectations. 


Above, we have seen that our algorithm outputs the features (topics) that we
expect these well known accounts to be influential on. These observations
clearly indicate that our problem settings and framework are valid and effective 
for the purpose of digging deep
into the influence spread of influencers and providing explanations.
\emph{When coupled with user features, as in the 
case of Flixster dataset, we are able to answer the questions we raised
in \textsection\ref{sec:intro}:
Where exactly does the influence of an influencer lie? How is it distributed? On
what type of actions is an influencer influential? What are the demographics of
its followers?} 



quantitative.tex


We next focus on evaluating our algorithm from a quantitative perspective 
and compare our algorithm with other algorithms, in
terms of the coverage achieved (the fraction of total followups), running time, 
and memory usage. 
%We conclude this section by showing the scalability of our
%algorithm.

%\smallskip
\noindent
\textbf{Algorithms Compared:} We compare our algorithm, which we refer to as 
\greedy, with the following baselines. 

\textsc{Random}: It selects the features randomly, with probability proportional to 
number of followups covered by each feature. 

\textsc{Most-Popular}: It orders the features by their popularity, i.e.,
number of followups they cover. Then, it picks the top $l$ features 
\GB{that
have yet to be picked 
to build an explanation, this is repeated $k$
times. }
It is an intuitive algorithm, as the features which cover most
followups can be seen as the representative set of features on which the
given influencer is influential. 

\eat{
\note{This doesn't say how the $kl$ features are packed off into 
$k$ explanations. The packaging could be good or bad in term sof coverage 
achieved.} 
}

\exhaustive: It generates one explanation at a time, by exhaustively trying all
possible combinations of features and picking the one that covers the maximum
number of followups (which are not covered by previous explanations). Note that
the number of possible combinations is \GB{${|\calP| \choose l}$}, where $l$ is the
number of features in one explanation. Thus, each explanation is an optimal one, 
i.e., the one with the maximum marginal coverage w.r.t. the previous set of 
explanations chosen. 
%however, since they are generated one at a time in the greedy fashion (we pick
%the best explanation at any step), this algorithm will provide us $(1-1/e)$
%approximation. 
Since the objective function \GB{$\cov: 2^{2^{\calP}} \rightarrow \mathbb{R}$}
is monotone non-decreasing and submodular
(see Thm.~\ref{thm:sm1}), %and it is known that the greedy algorithm that picks
%the best element (in this case, explanation) at every step 
the set of explanations obtained using this algorithm is an $(1-1/e)$-approximation 
to the optimal solution \cite{submodular}.

Thus, among the algorithms compared, algorithm \exhaustive provides the upper bound on 
the number of
followups that can be possibly covered by the explanations generated. Because of its 
exhaustive nature, we expect the algorithm to be quite slow. 

%\greedy: This is our algorithm as described in \textsection\ref{sec:algo}.

%\smallskip
Unless otherwise stated, on each dataset, we take top-100 influencers
with respect to number of followups they received. The algorithms are
then run on all of 100 influencers, and the median is picked as the
representative value for the comparison. We use median instead of mean,
as it is %a 
more robust against outliers.
 
%\note{Laks: Did you compute mean as well? Did you check to see if there
%were outliers?  Glenn: running time, especially for exhausive has some
%large outliers. Coverage has extreme cases, compete coverage and zero
%coverage} 

%\note{Laks: Should we say by ``coverage'' we mean ``relative coverage'' below?} 

%\smallskip
\noindent
\textbf{Coverage w.r.t.~change in \textit{k}}: Figure~\ref{fig:cov_k} shows the
variation in relative coverage achieved when $k$ is varied. Recall that $k$
denotes the number of explanations (table rows) generated. Relative
coverage is defined as the fraction of followups that are covered. The parameter
$l$ is fixed to 3 in Flixster and 5 in Twitter. As expected, the (relative)
coverage increases with $k$, but not at the same rate for all algorithms. 
Our algorithm \greedy consistently
performs just as well as
\exhaustive, while beating both \random and \mostpopular by huge margins, on
both the datasets. In fact, the performance of \greedy is almost indistinguishable from that of 
\exhaustive. For instance, on Flixster, with just 6 explanations, \greedy
is able to cover 0.57 fraction of followups, compared to the fraction 0.58 
achieved by \exhaustive. On the other hand, \mostpopular covers 0.25
fraction of followups and \random performs dismally, covering only 0.03
fraction of followups. Moreover, it is worth mentioning that the coverage
achieved quickly saturates (on Flickr only) for both \mostpopular and \random, 
implying that increasing
$k$ would not have helped achieve better coverage from these algorithms. 


In case of Twitter, as we can observe, the coverage achieved, is in general higher, with
\greedy covering up to 0.95 fraction of followups, again with 6 explanations. 
Recall, the longer an explanation (higher $l$) the smaller the coverage, in general. 
Despite this, the coverage achieved on Twitter with 6 longer explanations ($l=5$) 
is more than achieved on Flixster with 6 shorter explanations ($l=3$). 
This indicates that the influencers in Twitter are followed due to their niche.  
For
example, news accounts like CNN and New York Times are mostly followed on 
topics like ``news'' and ``politics'' as we saw above. Once again, \greedy and 
\exhaustive significantly outperform other baselines while their performance is 
very close. The relative coverage of \random seems to grow sharply as $k$ increases 
but at $k = 6$ it still performs poorly. The challenge is to cover as much as 
possible with as few but as detailed explanations as possible, and \greedy 
is found to rise to this challenge. 



\begin{figure}[t]
\vspace{-2mm} \centering
\begin{tabular}{cc}
\hspace{-4mm}\includegraphics[width=4.5cm]{flixsterCoverageWRTnumEx.pdf}&
\hspace{-4mm}\includegraphics[width=4.5cm]{twitterCoverageWRTnumExf5.pdf}
\end{tabular}
\vspace{-4mm}\caption{Coverage achieved from various algorithms w.r.t.~variation in $k$ in Flixster (left) and Twitter (right). 
$l=3$ in Flixster and $l=5$ in Twitter.\label{fig:cov_k}} \vspace{-2mm}
\end{figure}
\begin{figure}[t]
\vspace{-2mm} \centering
\begin{tabular}{cc}
\hspace{-4mm}\includegraphics[width=4.5cm]{flixsterCoverageWRTnumF.pdf}&
\hspace{-4mm}\includegraphics[width=4.5cm]{twitterCoverageWRTnumF.pdf}
\end{tabular}
\vspace{-4mm}\caption{Coverage achieved from various algorithms w.r.t.~variation in $l$ in Flixster (left) and Twitter (right). 
$k$ is fixed to 6.\label{fig:cov_l}} \vspace{-2mm}
\end{figure}


\noindent
\textbf{Coverage w.r.t.~change in \textit{l}}:
In Figure \ref{fig:cov_l}, we show the variation in relative coverage
when the parameter $l$, the number of features (table columns) per
explanation, is changed.  As expected,  coverage decreases with the
increase in $l$. Our \greedy algorithm continues to perform quite well.
For instance, on Flixster, it covers 0.31 fraction of followups,
compared to 0.05 and 0.00, the coverage achieved by \mostpopular and
\random, respectively at $l=4$. \exhaustive on the other hand, covers
0.34 fraction of followups.  We see a similar pattern in Twitter
dataset as well. When $l=5$, \greedy covers 0.92 fraction of followups
(same as 0.92 by \exhaustive), while the coverage from \mostpopular
and \random is 0.66 and 0.35. Notice that \exhaustive took too
long to complete for $l > 5$ on Twitter.


\noindent
\textbf{Running Times and Memory Usage.}
Fig.~\ref{fig:running_time_k} 
%and \ref{fig:running_time_l}
shows the
running time of various algorithms, on both datasets.
%, when $k$ and $l$
%are varied, respectively. 
As can be seen, our \greedy algorithm is an order of magnitude faster
than the optimal \exhaustive algorithm. For instance, on Flixster, when
$k=6$ and $l = 3$, while \greedy takes 26 ms to finish, \exhaustive
finishes in 3,748 ms, that is, it takes 144 times longer than \greedy.
The other algorithms -- \mostpopular and \random are faster than \greedy
as we foresaw earlier. They complete in 5 ms and 3 ms.
Similarly, on Twitter, when $k=6$ and $l = 5$, \exhaustive (finishes in 597 ms) is 18 times
slower than \greedy (finishes in 32.5 ms).  On the other hand,
\mostpopular and \random take just 15 ms and 27 ms, respectively. 


%\note{Laks: 1. It seems we are two order of magnitude or more faster than \exhaustive. 
%2. The above para should discuss all the running time plots. Why arbitrarily jump to Fig. 6? 
%Also, when giving times, be consistent and report times for all algorithms, for each dataset. I 
%did not edit this para and am leaving it to you to do it right.} 

%\smallskip
%\noindent
%\textbf{Memory Usage.}
%We show the memory usage by various algorithms in Figure~\ref{fig:memory_usage}.
%The interesting observation is that essentially, 
All the algorithms consume approximately the same amount of memory, up
to a maximum of 446 MB and 2.92 GB on Flixster and Twitter, respectivly.
This is because the memory usage primarily depends on the number of
features and the number of followups they cover. To be precise, \greedy
incurs additional space overhead on account of maintaining heaps of
features, but this additional overhead is under 1 MB, which is
negligible. 


%\smallskip
\noindent
\emph{In sum, our \greedy algorithm performs essentially as well as \exhaustive
algorithm in terms of coverage achieved, while being much more efficient in
running time.}

	
\begin{figure}
\vspace{-2mm} \centering
\begin{tabular}{cc}
\hspace{-4mm}\includegraphics[width=4.5cm]{flixsterRunningTimelogWRTk.pdf}&
\hspace{-4mm}\includegraphics[width=4.5cm]{twitterRunningTimelogWRTk.pdf}
\end{tabular}
\vspace{-4mm}\caption{Running time comparison for various algorithms on Flixster with $l$ = 3 (left) and Twitter with $l$ = 5 (right). 
\label{fig:running_time_k}} \vspace{-2mm}
\end{figure}

%\begin{figure}
%\vspace{-2mm} \centering
%\begin{tabular}{cc}
%\hspace{-4mm}\includegraphics[width=4.5cm]{images/flixster/flixsterRunningTime.pdf}&
%\hspace{-4mm}\includegraphics[width=4.5cm]{images/twitter/twitterRunningTime.pdf}
%\end{tabular}
%\vspace{-4mm}\caption{Running time comparison for various algorithms on Flixster (left) and Twitter (right) (k = 6 for both). 
%\label{fig:running_time_l}} \vspace{-2mm}
%\end{figure}


%\begin{figure}
%\vspace{-2mm} \centering
%\begin{tabular}{cc}
%\hspace{-4mm}\includegraphics[width=4.5cm]{images/flixster/flixsterRunningTimeWRTk.pdf}&
%\hspace{-4mm}\includegraphics[width=4.5cm]{images/twitter/twitterRunningTimeWRTk.pdf}
%\end{tabular}
%\vspace{-4mm}\caption{Running time comparison for various algorithms on Flixster with l = 3 (left) and Twitter with l = 5 (right). 
%\label{fig:running_time}} \vspace{-2mm}
%\end{figure}
		

related.tex

We summarize related work under three headings. \\ 
%\noindent
%\textbf{Identifying Influencers.}
\noindent 
{\bf Identifying Influencers.} Identifying influencers has been extensively studied as the problem of
influence maximization. The first work of this kind is due to 
%from a data mining perspective was first studied
%by
Domingos et al.~\cite{domingos01}. They refer to users' influence as \emph{network
value} and model it as the expected lift in profit due to influence
propagation. Thus, the network value of a customer is captured as a number.  
%, that is, the expected additional
%profit made due to users' influence in the social network.  
Later, Kempe
et al.~\cite{kempe03} formulated this as a discrete optimization
problem: select $k$ influencers in a given social network such that by
targeting them, the expected spread of the influence is maximized, assuming 
the propagation follows a diffusion model such as independent cascades or linear 
threshold or their variants. The
problem is \NPhard. However, the objective function satisfies the nice
properties of monotonicity and submodularity, under the diffusion models considered, 
allowing a simple greedy algorithm to provide a $(1-1/e-\epsilon)$-approximation 
to the optimal solution, for any $\epsilon > 0$
\cite{submodular}. 
\AG{Further exploiting these properties, Leskovec et al.~\cite{LeskovecKDD07} proposed a lazy forward optimization that dramatically improves the
efficiency of the greedy algorithm. The idea is that the marginal gain
of a node in the current iteration cannot be better than its
marginal gain in the previous iterations.}
Goyal et al.~\cite{goyal2012} proposed a direct data driven approach to social
influence maximization. They show this alternative approach is both accurate
(in predicting the influence spread) and is scalable, compared to the 
probabilistic approach of Kempe et al.~\cite{kempe03}. \AG{Their work also highlights the 
importance of validating the influence prediction and spread.}


Considerable work has been done on analyzing social influence on blogs
and micro-blogs. %, particularly on Twitter, perhaps due to easiness of
%collecting data from Twitter.  
Agarwal et al.~\cite{agarwal08}
investigate the problem of identifying influential bloggers in a
community.  They show the most influential bloggers are not
necessarily the most active. Gruhl et al.~\cite{Gruhl2004} analyze 
information diffusion in blogspace by characterizing the individuals and
the topics of their blog postings. %\cite{} 
%How do we differ from them, then?} 
In \cite{Gomez-RodriguezLK10}, the
authors look into the problem of inferring networks of diffusion and
influence in blogspace.
%On Twitter, 
Weng et al.~\cite{twitterrank} develop a topic sensitive Pagerank-like measure (called Twitterrank) for
ranking users based on their influence on given topics. 
Cha et al.~\cite{cha10} compare three different measures of influence
-- indegree (number of followers), retweets and user mentions, with regard to 
their ability to characterize influencers. They
observe that users who have a large number of followers are not
necessarily influential in terms of spawning off retweets or mentions. 
Romero et al.~\cite{romero2011} showed that the majority of users act as
passive information consumers and do not forward the content to the
network. 
%They proposed techniques to learn users' passivity. They argue
%that information about passivity of users in a network may be useful
%from the perspectives of viral marketing. 
Bakshy et al.~\cite{bakshy2011} find that the largest cascades tend to
be generated by users who have been influential in the past and who have
a large number of followers. 
%\note{Laks: Bakshy and Cha seem to contradict each other? Comments? 
%We need to say how we differ from them all, esp. Gruhl et al.} 



The problem of identifying influencers, and indeed influence maximization, 
is fundamentally different from our problem \probname. The objective of
\probname is to allow a human (or marketer) to (independently) validate
a given influencer, by generating human
readable, crisp explanations. The explanations consist of features from
action and user dimensions with relevant statistics and are generated in
a way such that they are able to cover the maximum amout influence, 
in terms of followups. 


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%% Topic Sensitive
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
Since our explanations are built of action and user features, works on 
topic-sensitive influence analysis
\cite{TangSWY09, Liu2010, twitterrank, trendsetters, Barbieri2012} and influence
based community detection \cite{leaders, Barbieri2013} are relevant and 
we survey these next. 

\noindent 
{\bf Topics.} 
Tang et al.~\cite{TangSWY09} introduce the problem of
topic-based social influence analysis. Given a social network and
a topic distribution for each user, the problem is to find
topic-specific subnetworks, and topic-specific influence weights
between members of the subnetworks. 
%They proposed a Topical
%Affinity Propagation (TAP) approach using a graphical
%probabilistic model. 
%They also deal with the efficiency problem by
%devising a distributed learning algorithm under the Map-reduce
%programming model. 
Liu et al.~\cite{Liu2010} propose a generative model which utilizes the
content and link information associated with each node (which can
be a user, or a document) in the network, to mine topic-level direct
influence. They use  Gibbs sampling  to estimate the
topic distribution and influence weights.
Weng et al.~\cite{twitterrank}, as described earlier, propose a topic
sensitive Pagerank-like measure to rank users of Twitter. 
In \cite{trendsetters}, the authors define \emph{trendsetters} as the
``early adopters'' who spread the new ideas or trends before they become
popular. They also propose a Pagerank-like measure to identify
trendsetters. Barbieri et al.~\cite{Barbieri2012} extend classical
propagation models like linear threshold and independent cascade
\cite{kempe03} to handle topic-awareness. Our problem is given a network, 
past information cascades in the form of an action log, 
and a seed node, we need to 
generate a compact explanation of the way the influence spread of 
the seed is distributed, which is not addressed by any of these works.

\noindent 
{\bf Communities.} 
Another related line of work is influence-based community detection
\cite{leaders, Barbieri2013}. Goyal et al.~\cite{leaders} define the
notion of ``tribe-leaders'' -- leaders (or influencers) who are followed
up by the same set of users, on several actions. They apply a pattern
mining framework to discover them. Barbieri et
al.~\cite{Barbieri2013} propose a generative model to detect
communities incorporating  information cascades. 


\GB{In} contrast \GB{to} the above mentioned papers, our goal is not to model 
topics or to detect communities, but to \emph{describe the influence
distribution of a given user}, by generating %crisp and informative
explanations consisting of interesting features from action
and user dimensions. 
\emph{To the best of our knowledge, this is the first research study to
provide explanations for the purpose of influencer validation.}


%Explanations - Recommender Systems (Chapter 15 of \cite{handbook}) and
%Experts Systems \cite{}.

%\smallskip
%\noindent
%\textbf{Providing Explanations.}

%In particular, they focused on two
%propagation models: linear threshold and independent cascade. 

table_flixster1stUser.tex

%\begin{table}
	\centering
	\caption{Mike: User with most followups. $k=6$, $l=3$.}
	\label{tab:flixster_firstUser}
	\begin{scriptsize}
	%\taburulecolor{Gray}
	\begin{tabu}{c c c | c c c }   	
		\multicolumn{3}{c|}{} 	&Actions&Followers&Followups\\	
		\multicolumn{3}{c|}{}   & (3.0k) & (106) & (37.9k)\\ \hline
		
		\multirow{2}{*}{rated R} & \multirow{2}{*}{thriller} & male	& 708 & 67 & 6.7k \\ \tabucline[1pt]{3-6}
		& & female & 708 & 37  & 2.3k\\ \tabucline[2pt]{1-6}
		
		\multirow{2}{*}{male}	& \multirow{2}{*}{drama} &len:long& 480 & 67 & 4.8k	\\ \tabucline[1pt]{3-6}
		& &len:med& 520 & 67	& 3.5k\\ \tabucline[2pt]{1-6}
		
		\multirow{2}{*}{pre-1997} & \multirow{2}{*}{comedy} &	male & 607 & 67 &  4.8k\\ \tabucline[1pt]{3-6}
		& & female  & 607 & 37 & 2.2k\\ \hline	
		\multicolumn{5}{r}{Total Coverage:} & 56.3\%\\
	\end{tabu}
	\end{scriptsize}
%\end{table}

table_flixster2ndUser.tex

%\begin{table}
	\centering
	\caption{Kali: User with 2nd most followups. $k=6$, $k=3$.}
	\begin{scriptsize}
	%\taburulecolor{Gray}
	\begin{tabu}{c c c | c c c }   	
		\multicolumn{3}{c|}{} 	& Actions	& Followers & Followups\\	
		\multicolumn{3}{c|}{}   & (2.8k) & (93)  & (27.0k)\\ \hline
		\multirow{4}{*}{female}	& comedy & pre-1997 & 550 & 62 & 2.8k	\\ \tabucline[2pt]{2-6}
		& thriller & action & 549 & 62 & 3.1k	\\ \tabucline[2pt]{2-6}
		& \multirow{2}{*}{drama} & len:long	& 475 & 62 & 2.8k\\ \tabucline[1pt]{3-6}
		& & len:med& 483 & 62 & 2.1k \\ \tabucline[3pt]{1-6}
		\multirow{2}{*}{male} & thriller &	rated:R & 687 & 28 &  2.6k\\ \tabucline[2pt]{2-6}
		& age:25-34 & pre-1997 & 1.4k & 13 & 2.3k \\ \hline	
		\multicolumn{5}{r}{Total Coverage:} & 51.4\%\\
	\end{tabu}
	
	\label{tab:flixster_secondUser}
	\end{scriptsize}
%\end{table}

table_flixster3rdUser.tex
%\begin{table}
	\centering
	\caption{Julie: User with 3rd most followups. $k=6$, $l=3$.}
	\begin{scriptsize}
	%\taburulecolor{Gray}
	\begin{tabu}{c c c | c c c }   	
		\multicolumn{3}{c|}{} 	&Actions&Followers&Followups\\	
		\multicolumn{3}{c|}{}   & (1.8k) & (73) &(23.5k)\\ \hline
		\multirow{6}{*}{female}	& \multirow{2}{*}{pre-1997} & comedy  & 401 & 63 & 4.3k	\\ \tabucline[1pt]{3-6}
		& & rat:7-10& 317 & 63	& 3.9k\\ \tabucline[2pt]{2-6}
		& \multirow{2}{*}{1998-2002} & comedy	 & 238 & 63 & 3.2k\\ \tabucline[1pt]{3-6}
		& & drama  & 222 & 63& 2.3k \\ \tabucline[2pt]{2-6}
		& rated:R & thriller  & 446 & 63 &  3.7k\\ \tabucline[2pt]{2-6}
		& PG-13 & action  & 228 & 63 & 3.0k\\ \hline	
		\multicolumn{5}{r}{Total Coverage:} & 68.7\%\\
	\end{tabu}
	\label{tab:flixster_thirdUser}
	\end{scriptsize}
%\end{table}

table_twitterCNN.tex
%\begin{table}
	\centering
	\caption{CNN breaking news. $k=6$, $l=3$.}
	\begin{scriptsize}
	%\taburulecolor{Gray}
	\begin{tabu}{c c c | c c }    
		\multicolumn{3}{c|}{} 	& Actions	& Followups\\ 
		\multicolumn{3}{c|}{}   & (390) & (56.2k)\\ \hline
		\multirow{6}{*}{news}	& \multirow{4}{*}{cnn} & politics  & 295 & 39.8k	\\ \tabucline[1pt]{3-6}
		& & business & 10 & 1.9k	\\ \tabucline[1pt]{3-6}
		& & breaking-news	 & 75 & 13.3k\\ \tabucline[2pt]{2-6}
		& media & tv  & 288 & 38.5k\\ \tabucline[2pt]{2-6}
		& religion & chistianity	 & 1 & 434\\ \tabucline[2pt]{2-6}
		& magazine & sport & 2 & 265 \\ \hline	
		\multicolumn{4}{r}{Total Coverage:} & 99.8\%\\
	\end{tabu}
	\label{tab:cnn}
	\end{scriptsize}
%\end{table}

table_twitterNYTimes.tex
%\begin{table}
	\centering
	\caption{New York Times. $k=6$, $l=4$.}
	\begin{scriptsize}
	%\taburulecolor{Gray}
	\begin{tabu}{c c c c | c c }    
		\multicolumn{4}{c|}{} 	& Followups & Actions	\\ 
		\multicolumn{4}{c|}{} 	&  (246) & (12.5k)\\ \hline	
		\multirow{6}{*}{news}	& \multirow{4}{*}{nytimes} & \multirow{2}{*}{business} & finance & 32	& 745\\ \tabucline[1pt]{4-6}
		& & & media  & 8 & 578	\\ \tabucline[2pt]{3-6}
		& & culture & media	 & 8 & 535 \\ \tabucline[2pt]{3-6}
		& &	journalism & photos  & 14 & 762\\ \tabucline[3pt]{2-6}
		& \multirow{2}{*}{politics} &	media & newspaper	 & 79 & 8.5k\\ \tabucline[2pt]{3-6}
		& & nyt & journalism  & 43 & 4.2k\\ \hline	
		\multicolumn{5}{r}{Total Coverage:} & 82.8\%\\
	\end{tabu}
	\label{tab:nytimes}
	\end{scriptsize}
%\end{table}

table_twitterNationalGeo.tex
%\begin{table}
	\centering
	\caption{National Geographic. $k=3$, $l=3$.}
	\begin{scriptsize}
	%\taburulecolor{Gray}
	\begin{tabu}{c c c | c c }    
		\multicolumn{3}{c|}{} 	& Actions	& Followups\\
		\multicolumn{3}{c|}{}   & (262) & (23.6k)\\ \hline
		science &	nature & geography  & 116 & 12.8k \\ \tabucline[2pt]{1-5}
		\multirow{2}{*}{travel} &	\multirow{2}{*}{national geographic} & magazine	 & 51 & 4.7k\\ \tabucline[1pt]{3-5}
		& & videos  & 38 & 2.3k\\ \hline	
		\multicolumn{4}{r}{Total Coverage:} & 84.1\%\\
	\end{tabu}
	\label{tab:nationalgeo}
	\end{scriptsize}
%\end{table}
table_twitterTimReilly.tex
%\begin{table}
	\centering
	\caption{Tim O'Reilly. $k=6$, $l=3$.}
	\begin{scriptsize}
	%\taburulecolor{Gray}
	\begin{tabu}{c c c | c c }    
		\multicolumn{3}{c|}{} 	& Actions	& Followups\\ 
		\multicolumn{3}{c|}{} 	& (115) & (3.0k) \\ \hline	
		\multirow{4}{*}{news}	& \multirow{2}{*}{tech} & software & 11	& 410 \\ \tabucline[1pt]{3-6}
		& & business  & 6	& 165\\ \tabucline[2pt]{2-6}
		& media & politics	 & 15 & 513\\ \tabucline[2pt]{2-6}
		& magazine & science & 3 & 113 \\ \tabucline[3pt]{1-6}
		development & programming & opensource	 & 2 & 471\\ \tabucline[3pt]{1-6}
		socialmedia & google & ping.fm  & 5 & 235\\ \hline	
		\multicolumn{4}{r}{Total Coverage:} & 63.4\%\\
	\end{tabu}
	\label{tab:timreilly}
	\end{scriptsize}
%\end{table}

justifications.bbl
\begin{thebibliography}{10}

\bibitem{agarwal08}
N.~Agarwal, H.~Liu, L.~Tang, and P.~S. Yu.
\newblock Identifying the influential bloggers in a community.
\newblock In {\em WSDM}, 2008.

\bibitem{bakshy2011}
E.~Bakshy, J.~M. Hofman, W.~A. Mason, and D.~J. Watts.
\newblock Everyone's an influencer: quantifying influence on twitter.
\newblock In {\em WSDM}, 2011.

\bibitem{Barbieri2012}
N.~Barbieri, F.~Bonchi, and G.~Manco.
\newblock Topic-aware social influence propagation models.
\newblock In {\em ICDM}, 2012.

\bibitem{Barbieri2013}
N.~Barbieri, F.~Bonchi, and G.~Manco.
\newblock Cascade-based community detection.
\newblock In {\em WSDM}, 2013.

\bibitem{cha10}
M.~Cha~et al.
\newblock {Measuring User Influence in Twitter: The Million Follower Fallacy}.
\newblock In {\em ICWSM}, 2010.

\bibitem{domingos01}
P.~Domingos and M.~Richardson.
\newblock Mining the network value of customers.
\newblock In {\em KDD}, 2001.

\bibitem{feige98}
U.~Feige.
\newblock A threshold of $\ln n$ for approximating set cover.
\newblock {\em J. ACM}, 45(4):634--652, 1998.

\bibitem{Gomez-RodriguezLK10}
M.~Gomez-Rodriguez, J.~Leskovec, and A.~Krause.
\newblock Inferring networks of diffusion and influence.
\newblock In {\em KDD}, 2010.

\bibitem{leaders}
A.~Goyal, F.~Bonchi, and L.~V.~S. Lakshmanan.
\newblock Discovering leaders from community actions.
\newblock In {\em CIKM}, 2008.

\bibitem{goyal2012}
A.~Goyal, F.~Bonchi, and L.~V.~S. Lakshmanan.
\newblock A data-based approach to social influence maximization.
\newblock {\em PVLDB}, 5(1), 2011.

\bibitem{Gruhl2004}
D.~Gruhl, R.~Guha, D.~Liben-Nowell, and A.~Tomkins.
\newblock Information diffusion through blogspace.
\newblock In {\em WWW}, 2004.

\bibitem{freqitemsetmining}
J.~Han, J.~Wang, Y.~Lu, and P.~Tzvetkov.
\newblock Mining top-k frequent closed patterns without minimum support.
\newblock In {\em ICDM}, pages 211--218, 2002.

\bibitem{Jamali10}
M.~Jamali and M.~Ester.
\newblock A matrix factorization technique with trust propagation for
  recommendation in social networks.
\newblock In {\em RecSys}, 2010.

\bibitem{kempe03}
D.~Kempe, J.~M. Kleinberg, and {\'E}.~Tardos.
\newblock Maximizing the spread of influence through a social network.
\newblock In {\em KDD}, 2003.

\bibitem{Lacave2004}
C.~Lacave and F.~J. Diez.
\newblock A review of explanation methods for heuristic expert systems.
\newblock {\em Knowl. Eng. Rev.}, 19(2), 2004.

\bibitem{LeskovecKDD07}
J.~Leskovec~et al.
\newblock Cost-effective outbreak detection in networks.
\newblock In {\em KDD}, 2007.

\bibitem{Liu2010}
L.~Liu, J.~Tang, J.~Han, M.~Jiang, and S.~Yang.
\newblock Mining topic-level influence in heterogeneous networks.
\newblock In {\em CIKM}, 2010.

\bibitem{submodular}
G.~L. Nemhauser, L.~A. Wolsey, and M.~L. Fisher.
\newblock An analysis of approximations for maximizing submodular set
  functions.
\newblock {\em Mathematical Programming}, 14(1):265--294, 1978.

\bibitem{handbook}
F.~Ricci, L.~Rokach, B.~Shapira, and P.~B. Kantor, editors.
\newblock {\em Recommender Systems Handbook}.
\newblock Springer, 2011.

\bibitem{romero2011}
D.~M. Romero, W.~Galuba, S.~Asur, and B.~A. Huberman.
\newblock Influence and passivity in social media.
\newblock In {\em WWW}, 2011.

\bibitem{trendsetters}
D.~Saez-Trumper, G.~Comarela, V.~Almeida, R.~Baeza-Yates, and F.~Benevenuto.
\newblock Finding trendsetters in information networks.
\newblock In {\em KDD}, 2012.

\bibitem{shieh2012}
M.~Shieh, S.~Tsai, and M.~Yang.
\newblock On the inapproximability of maximum intersection problems.
\newblock {\em Information Processing Letters}, 2012.

\bibitem{TangSWY09}
J.~Tang, J.~Sun, C.~Wang, and Z.~Yang.
\newblock Social influence analysis in large-scale networks.
\newblock In {\em KDD}, 2009.

\bibitem{twitterrank}
J.~Weng, E.-P. Lim, J.~Jiang, and Q.~He.
\newblock Twitterrank: finding topic-sensitive influential twitterers.
\newblock In {\em WSDM}, 2010.

\bibitem{xavier2012}
E.~Xavier.
\newblock A note on a maximum k-subset intersection problem.
\newblock {\em Information Processing Letters}, 2012.

\end{thebibliography}
