# Efficiency of Algorithms for Computing Influence and Information Spreading on Social Networks
## 2 Methods  
### Influence Spreading Model  
In this section, we describe the influence spreading model [6] that is at the core of the presented algorithms. A similar model, called Independent Cascade Model, was presented by [PERSON] et al. [16] Our model may be viewed as a generalisation of the Independent Cascade Model, which does not allow self-intersecting paths or breakthrough influence. The model describes a form of diffusion in a social network, and it is based on assigning a spreading probability to each edge of the network. Diffusion starts from a specified starting node, and each node has one chance to spread influence to each of the neighbouring nodes with the probability specified by the assigned edge probabilities. We store all pairwise spreading probabilities in a two-dimensional _influence spreading matrix_\(C:V\times V\rightarrow\mathbb{R}\), where \(C(s,t)\) denotes the probability of spreading from the starting node \(s\) to the target node \(t\). The matrix elements are computed based on all possible paths between the corresponding pair of nodes. In other words, for computing \(C(s,t)\), we will combine the influence of all paths from node \(s\) to node \(t\). It is important to note that \(C(s,t)\) and \(C(t,s)\) will not always be equal as probabilities are assigned to each directed edge individually. Notice that paths between two nodes may have arbitrarily many nodes when we place no restrictions on them. Thus, to keep the set of paths finite, we need to limit path length. Let \(L_{\max}\) denote the maximum number of edges allowed on a path. In addition to edge-specific probabilities, Poisson distribution is used to model temporal spreading. It is applied as a factor to the probability of spreading through a path. The Poisson distribution is a discrete probability distribution that expresses the probability for a giving a number of events occurring in a fixed interval of time provided that these events take place with a known constant rate and independently of the time since the previous event. In this context, the Poisson process describes a process where spreading via successive links occurs randomly as a function of time [6]. The unconditional probability of temporal spreading at time \(T\) on a path of length \(L\) is given by  
\[\mathcal{P}(L)=1-\sum_{i=0}^{L-1}e^{-\lambda T}\frac{(\lambda T)^{i}}{i!},\ ( \mathcal{P}(0)=1), \tag{1}\]  
where \(\lambda\) is the intensity parameter of the Poisson distribution. \(\lambda\) and \(T\) are constants throughout the calculation. Here, the interpretation is that the spreading has advanced up to \(L\) or more links at time \(T\)[6]. When \(T\rightarrow\infty\), the values of \(\mathcal{P}(L)\) approach to one. Additionally, other path length-dependent distributions could be used to more accurately model the different kinds of real-world influence spreading. Now, we are ready to calculate the probability of a single spreading path. Let \(P(\mathcal{L})\) denote the probability of spreading through path \(\mathcal{L}\), starting from the first node and traversing the path through each edge until the end. \(P(\mathcal{L})\) is the product of corresponding edge probabilities and the Poisson distribution coefficient from Equation (1); that is,  
\[P(\mathcal{L})=\mathcal{P}(|E_{\mathcal{L}}|)\cdot\prod_{(u,v)\in E_{\mathcal{ L}}}w_{(u,v)}, \tag{2}\]  
where \(w_{(u,v)}\) denotes the spreading probability through the edge from \(u\) to \(v\), \(E_{\mathcal{L}}\) the set of edges on path \(\mathcal{L}\), and \(|E_{\mathcal{L}}|\) the size of the edge set; that is, the number of edges on the path [6]. To combine the probabilities of two different paths \(\mathcal{L}_{1}\) and \(\mathcal{L}_{2}\) between the same pair of nodes, we let \(\mathcal{L}_{3}\) denote the longest common prefix (LCP) of the paths. If there are no common nodes, i.e., \(\mathcal{L}_{3}\) is an empty path, we say that \(P(\mathcal{L}_{3})=1\). Otherwise, let us derive a formula for calculating \(P(\mathcal{L}_{3})\) from \(P(\mathcal{L}_{1})\) and \(P(\mathcal{L}_{2})\).