# Efficiency of Algorithms for Computing Influence and Information Spreading on Social Networks
## 2 Methods
### Algorithms
#### 2.2.1 Complex Contagion Algorithm  
First, we describe an efficient algorithm for modelling _complex contagion_ (CC). In the case of complex contagion, self-intersecting paths are allowed. Algorithm 2 solves this problem for a fixed target node \(t\). To fill the influence spreading matrix, the procedure needs to be run \(|V|\) times, once with each node as the target node. As mentioned, \(L_{\max}\) represents the maximum path length, that is, the number of edges on a path. Two important factors contribute to the algorithm's efficiency. Firstly, no restrictions, other than the maximum path length, are posed on paths. A spreading path may, for example, self-intersect. This means that we do not need to have the current path in memory in order to select the next node. Instead, it suffices to store the latest node and the length of the path. This allows us to save memory by grouping multiple paths together and combining their probabilities during the computation, rather than storing all individual paths until the end. Secondly, nodes have no state; that is, they are neither influenced nor uninfluenced. This means that we need not store the state of each node in memory nor do we need to process a great number of possible states individually. ```
1:\(\triangleright\) Computes the spreading probabilities from each node to node \(t\) in network \(G\). 2:procedureProbabilities(\(t\), \(G=(V,E,w)\))
3:\(\triangleright\) Network \(G\) contains a node set, an edge set and the spreading probabilities for each edge
4:\(P_{L}(i)\gets 0.0\), for all \(i\in V\), \(0\leq L\leq L_{\max}\)\(\triangleright\) Initialise the probability array
5:\(P_{L_{\max}}(t)\leftarrow\mathcal{P}(L_{\max})\)
6:for\(L=L_{\max}-1\)\(\dots\)\(0\)do\(\triangleright\) Iterate \(L\) from \(L_{\max}-1\) to \(0\)
7:\(P_{L}(t)\leftarrow\mathcal{P}(L)\)\(\triangleright\) Start new paths from \(t\) with \(L\) nodes left
8:for\((u,v)\in E\)do\(\triangleright\) Iterate all edges
9:\(p\gets P_{L+1}(v)\cdot w_{(u,v)}\)\(\triangleright\) Extend paths ending at \(v\) with node \(u\)
10:\(P_{L}(u)\gets P_{L}(u)+p-\dfrac{P_{L}(u)\cdot p}{\mathcal{P}(L)}\)\(\triangleright\) Combine probabilities (Equation (3))
11:endfor
12:endfor
13:\(\triangleright\) Now, the spreading probabilities from \(i\) to \(t\) are found in \(P_{0}(i)\), for all \(i\in V\). 14:endprocedure
```  
**Algorithm 2** The Complex Contagion algorithm  
```
1:\(\triangleright\) Computes the spreading probabilities from \(s\) to each node in network \(G\). 2:procedureProbabilities(\(s\), \(G=(V,E,w)\))
3:\(\triangleright\) The DFS function takes the current node and recursion depth as parameters
4:functionDepth-First-Search(Node, Depth)
5:\(P_{n}\gets 0.0\), \(n\in V\)\(\triangleright\) Create a probability array of size \(|V|\)
6:\(P_{\text{Node}}\leftarrow\mathcal{P}(\text{Depth})\)
7:if Depth \(<L_{\max}\)then
8:for each neighbor \(u\) of Node do
9:if\(u\) not on current path then
10:\(p\leftarrow\) Depth-First-Search(\(u\), Depth + 1)
11:for each \(n\in V\)do
12:\(p_{n}\gets p_{n}\cdot w_{\text{Node},u}\)
13:\(P_{n}\gets P_{n}+p_{n}-\dfrac{P_{n}\cdot p_{n}}{\mathcal{P}(\text{Depth})}\)\(\triangleright\) Combine probabilities (Equation (3))
14:endfor
15:endif
16:endfor
17:endif
18:return\(P\)
19:endfunction
20:returnDepth-First-Search(\(s\), \(0\))\(\triangleright\) Start the recursive search from \(s\)
21:endprocedure
```  
**Algorithm 3** The Simple Contagion Algorithm  
The algorithm works backwards, building paths starting from the target node \(t\), which is the last node on all paths. The backwards computation ensures that all pairs of paths are combined at the latest possible node as required by the model. The node, at which a pair of paths is combined, is the one where the paths diverge from each other for the first time. Spreading probabilities are stored in a two-dimensional array \(P\), where \(P_{L}(i)\) corresponds to all paths with latest node \(i\) and \(L\) nodes missing.