# Efficiency of Algorithms for Computing Influence and Information Spreading on Social Networks
## 3 Case Study Results  
In this section, we provide examples of how the model and its applications function in practice. We also provide insight into the effects of the maximum path length \(L_{\text{max}}\) and how much it can be limited. As mentioned, from a computational point of view, it is ideal to limit path length as much as possible in order to make the program run faster. Because the probability of spreading through a path decreases exponentially with respect to path length, the spreading probabilities eventually converge. Values in the influence spreading matrix approach the converged ones rather quickly, and after a point, increases in path length cause unnoticeable differences in the final probabilities. In the case of the _Facebook network_ (see Figure 2) from the SNAP dataset [25], a dense graph of 4039 nodes and 88,234 edges, \(L_{\text{max}}=31\) is the first value with which all out-centrality values differ by less than ten percent from the converged ones. At \(L_{\text{max}}=41\), the values differ by less than a percent, and at \(L_{\text{max}}=50\), by less than 0.1%. The Facebook network used here is an example of a relatively large and dense network, which increases the amount of CC paths. In a more typical, sparser network, even smaller values of \(L_{\text{max}}\) are required to achieve the same precision. The CC algorithm runs efficiently for networks with up to 100,000 nodes. See Table 1 for running times in real-world social networks. However, if large networks are studied, the \(|V|\times|V|\)-sized influence spreading matrix grows too large to keep in computer memory. In this case, it is possible to replace it with two arrays of size \(|V|\), used to directly store the in- and out-centrality sums corresponding to each node without calculating them from the influence spreading matrix after the computation has finished. This makes the memory complexity of computing all in- and out-centrality values \(\mathcal{O}(V)\). \begin{table}
\begin{tabular}{c c c c} \hline \hline
**Network** & **\#Nodes** & **\#Edges** & **Running Time** \\ \hline ArXiv collaboration network (ca-GrQc) & 5242 & 14,496 & 29.2 s \\ Facebook network (ego-Facebook) & 4039 & 88,234 & 37.5 s \\ Twitter network (ego-Twitter) & 81,306 & 1,768,149 & 3.5 h \\ Google+ network (ego-Gplus) & 107,614 & 13,673,453 & 50.7 h \\ \hline \hline \end{tabular}
\end{table} 
Table 1: Running times for various real-world social networks from the SNAP dataset [25] using the CC algorithm (Algorithm 2). All values were calculated with \(L_{\text{max}}=50\) on a workstation with two Intel Xeon X5690 processors. Figure 2: Relative difference in out-centrality values with different path lengths when compared to the values with \(L_{\text{max}}\to\infty\) in the Facebook network [25] calculated with the CC model (Algorithm 2) when \(w_{(u\psi)}=0.1\) for all \((u,\psi)\in E\), \(\lambda=1\), and \(T\to\infty\). By relative difference, we mean the largest relative difference in a node’s out-centrality value when compared to the converged value, i.e., those with \(L_{\text{max}}\to\infty\). Note that the y-axis is logarithmic and that the curve is nearly linear after the start, which means that precision grows exponentially with respect to path length. Figures 3-5 illustrate different applications of our model, influence spreading probabilities, out-centrality and betweenness centrality, respectively. Notice that as centrality values are calculated from the influence spreading probabilities, betweenness centrality values are calculated from centrality values. These measures, thus, form layers of abstractions on top of each other. The depicted values are calculated in the Dutch student network (see Figure 6) with all edge weights set to 0.5, i.e., \(w_{(u,v)}=0.5\) for all \((u,v)\in E\), where \(E\) denotes the edge set of the graph. Figure 3 depicts probabilities of spreading from node 1 to all other nodes. It includes a comparison between two values of \(L_{\text{max}}\), the maximum number of edges allowed on a path.