# Efficiency of Algorithms for Computing Influence and Information Spreading on Social Networks
## 4 Discussion  
Diffusion in various kinds of real-world situations often requires its own type of model. Some phenomena can be modelled effectively with analytical models, while others cannot. Sometimes simulation is the only option if no efficient analytical model exists or has been discovered. Generally speaking, simulation of diffusion turns out to be slow, in which case  
Figure 5: Betweenness values in the Dutch Student network (see Figure 6) with \(L_{\text{max}}\rightarrow\infty\), \(\lambda=1\), \(T\rightarrow\infty\), and \(w_{(u,v)}=0.5\) for all \((u,v)\in E\). Values are calculated from the influence spreading matrix according to Equation (6). Values are expressed as percentages as our definition of betweenness centrality (Equation (6)) corresponds to the relative change in cohesion (Equation (7)). The higher the percentage, the more important the node.  
Figure 6: The depicted network was constructed based on data collected by [PERSON] [26]. It is a longitudinal friendship network among 32 Dutch students. Its small size and unique structure make it a great example network for our centrality and betweenness measures. Note that there are three unconnected nodes numbered 5, 12, and 18. They were left out of Figures 3–5 as they do not provide any significant results.  
analytical models--like our efficient one--should be preferred instead. Our model has many applications and a lot of possibilities for future research. For example, the model allows the use of any path length-dependent probability distribution. It is also possible to alter the edges' probabilities based on the distance from the original spreader. Even empirical distributions could be used to model real-world phenomena.  
Computation of self-avoiding spreading requires information about the current spreading path, which makes the analytical computation of influence spreading using self-avoiding models inefficient. However, using simulation, asymptotically more efficient models with the same accuracy have been previously developed [5]. Furthermore, there are some features which naturally lead to simulation. One of them is controlling breakthrough infections. If we want to, say, assign a probability for breakthrough infections, we need to store the state of each node to determine whether a node is already infected or not. A large amount of possible states makes any analytical model inefficient, and we are, thus, left with simulation models.  
Unlike other diffusion models, our model has a clear physical interpretation as all measures are based on influence spreading probabilities. The pairwise spreading probabilities found in the influence spreading matrix naturally lead to the interpretation of the centrality measures from Equations (4) and (5) as expected values. These can, in turn, be used as a measure in Equation (6) for calculating betweenness centrality values. A probability-based approach also allows the use of well-known probability distributions, like the Poisson distribution in Equation (1).  
Our path-based approach has several unique characteristics not found in other models. To start with, it allows us to efficiently limit the spreading to the neighbourhood of a node. This makes it possible to study and compare a node's importance in different-sized communities surrounding it. Furthermore, our model takes all possible paths into account, which means that the complete structure of the network is reflected in the spreading probabilities, and by extension in the betweenness centrality values from Equation (6). This is in contrast to the more common _geodesic-based centrality_[27], which only takes the shortest paths between pairs of nodes into account. Moreover, if we increase \(L_{\text{max}}\) enough, the resulting probabilities describe the global structure of the network. In summary, the model scales naturally from analysing the local structure of a network to analysing its global structure.