# Recommending Links to Control Elections via Social Influence
## 3 Preliminaries  
### The Influence Maximization Problem  
The _Influence Maximization Problem_, introduced by [PERSON] et al. [21] in 2003, studies a social network, represented by a weighted directed graph \(G=(V,E,p)\), where the set of nodes \(V\) represent the users, the set of edges \(E\) represent social links between users, and the weight function \(p:V\times V\rightarrow[0,1]\) represents the influence between users. The goal is then to find a set of influential nodes of size \(B\) that can maximize the spread of information. The influence is defined based on the _information diffusion process_ among users.  
There are many different models to study these processes on graphs, one of the most used being the _Independent Cascade Model_ (ICM) [21]. Given a graph \(G=(V,E,p)\) and an initial set of nodes \(A_{0}\), usually referred as _seeds_, the diffusion process proceeds iteratively in a synchronous way along a discrete time-axis, starting from \(A_{0}\). Such set can be seen, for example, as the initial supporters of a product (or an opinion) that start to propagate it in a social network. Let \(A_{t}\subseteq V\) be the set of nodes active at time \(t\), then, for each node \(u\in A_{t}\setminus A_{t-1}\), a neighbor node \(v\) of \(u\) is activated at time \(t+1\) with probability \(p_{uv}\), independently, for each edge \((u,v)\in E\). Then, \(v\in A_{t+1}\) if and only if \(v\in A_{t}\) or one of the above independent events is realized. We say that the process has _quiesced_ at the first time \(\tilde{t}\) such that the set of active nodes would not change in the next round, i.e., time \(\tilde{t}\) is such that \(A_{\tilde{t}}=A_{\tilde{t}+1}\). We define the eventual set of active nodes as \(A:=A_{\tilde{t}}\). In this case, the goal is to maximize the set \(A\), i.e., the set of active nodes at the end of the process.  
[PERSON] et al. showed that the distribution of the set of active nodes \(A\) in the graph starting with \(A_{0}\) under the ICM process is equivalent to the distribution of reachable nodes from the same set \(A_{0}\) in the set of random graphs called _live-edge graphs_ (see Proof of Theorem 4.5 in [8]). A live-edge graph \(G^{\prime}=(V,E^{\prime})\) is built as follows: Given a graph \(G=(V,E,p)\), every edge \((u,v)\in E\) is selected to be inserted to \(E^{\prime}\) independently at random with a probability proportional to its weight \(p_{uv}\). This equivalent model allow them to provide two important results.  
First, they conjectured that evaluating the expected number of active nodes under ICM is #\(P\)-complete, which was later proved by [PERSON] et al. [22]. However, it can be efficiently approximated by using a polynomial number of live-edge graphs ([8], Proposition 4.1). Moreover, under the live-edge model, the problem of selecting the initial seed set of nodes in order to maximize the diffusion is _submodular_ (for a ground set \(N\), a function \(z:2^{N}\rightarrow\mathbb{R}\) is _submodular_ if for any two sets \(S,T\) such that \(S\subseteq T\subseteq N\) and for any element \(e\in N\setminus T\) it holds that \(z(S\cup\{e\})-z(S)\geq z(T\cup\{e\})-z(T)\)) [8]. Hence, exploiting a classical result [23], the influence maximization problem admits a \(1-1/e\) approximation using a simple greedy hill-climbing approach that, starting with an empty solution, for \(B\) iterations, selects the node that gives the maximal marginal gain on the objective function with respect the solution computed so far.