# Efficiency of Algorithms for Computing Influence and Information Spreading on Social Networks
## 2 Methods
### Algorithms
#### 2.2.2 Simple Contagion Algorithm  
The second algorithm (Algorithm 3) known as the _simple contagion_ (SC) algorithm models self-avoiding spreading. In self-avoiding spreading, paths must be non-intersecting. To avoid choosing a node which is already on the path, we must have the current path in memory, which slows down the computation significantly.  
The algorithm itself is a recursive depth-first search, which goes through all possible paths with a suitable length. The search starts from the given starting node \(s\) and recursively traverses to each neighbouring node. At any point, the current stack of recursive calls corresponds to the current path prefix. Provided there are no duplicate edges, each possible prefix is only seen once. All paths which have the current call stack as their prefix are constructed either in the current function call or in the subsequent recursive calls inside of it.  
Algorithm 3 uses the technique from Equation (3) for combining paths and meets the model's requirement that paths need to be combined at the end of their common prefix by, at each node, only constructing paths which first diverge at the node. Any pair of two differing paths has a specific node which corresponds to the end of the common prefix, which means that the procedure will, in fact, construct all possible paths--once and only once.  
Each call to the depth-first search function has its own probability array \(P\), which holds the probabilities spread to all other nodes. \(P_{i}\) denotes the probability of spreading from the current node to node \(i\). The values of \(P_{i}\) depend on the current depth and thus cannot be used for calculating spreading probabilities from other starting nodes. After the  
Figure 1: Network \(G\), and a tree of all paths ending at node \(A\) in network \(G\), with length at most 3, illustrating how paths are combined at their last common node. [15]  
probabilities for a node's neighbours are recursively computed, they are combined into the probability array of the current node.  
Note that were we to remove the self-avoiding restriction from line 9 of Algorithm 3, the algorithm would compute exactly the same values as the CC algorithm (Algorithm 2), but less efficiently. Another notable difference to the CC algorithm is that a single call to the SC algorithm (Algorithm 3) computes probabilities of spreading from a fixed start node \(s\), while a single call to the CC algorithm calculates the values for a fixed end node.  
It is well known that, in the worst case, there are \(\mathcal{O}(V^{L_{\max}})\) paths with a fixed starting node and at most \(L_{\max}\) edges in a network of \(V\) nodes. The search function in Algorithm 3 updates the spreading probability of all nodes after processing each neighbour, making the total time complexity of a single run \(\mathcal{O}(V^{L_{\max}}\cdot(V-1)\cdot V)=\mathcal{O}(V^{L_{\max}+2})\) as each node has at most \(|V|-1\) neighbours to process and there are \(|V|\) nodes with a probability to update. As before, this algorithm needs to be run \(|V|\) times, which increases the time complexity to fill the influence spreading matrix to \(\mathcal{O}(V^{L_{\max}+3})\). Both the SC algorithm and the original Algorithm 1 go through all spreading paths, but the fact that the SC algorithm does not store them in memory makes it significantly faster, more memory-efficient, and even usable in practice. It is scalable to large graphs with small values of \(L_{\max}\). As was the case with Algorithm 2, the \(|V|\) independent runs of this algorithm needed to fill the influence spreading matrix can be run in parallel to make computation more efficient. Combining the results of the runs is trivial, as each run corresponds to a single row in the final influence spreading matrix.