# A Generalized Framework for the Estimation of Edge Infection Probabilities
## 4 Evaluation
### Scalability  
We close the evaluation by investigating the scalability of the optimization method. Our interests here are the average number of iterations the method requires to produce a solution, the total running time (a parallel version of the algorithm was implemented in C++, and the results were computed on a PC with a 4-core i7-4770 3.4 GHz processor) and the relationship between the size of the task and the accuracy of the estimation.  
We examine four graphs in this section with \(1000,\ldots,4000\) nodes and \(1754,3752,5700\), \(7753\) edges and four infection scenarios from the previous section: \(33\%\) or \(10\%\) of the nodes are initially infected with an infection probability between 0 and 0.5 for the real-valued case and uniformly 1 for the binary case. Reference edge infection values were drawn from uniform random distributions between 0 and 0.25 and between 0 and 0.75. Both binary and real-valued two-observation infection scenarios were investigated. We only show results for the SIR \(\tau_{i}=2\) model; the performance of the other models was similar. Each of these tasks was computed ten times and the results were averaged. The variance of the results was minimal.  
Figure 5 shows the accuracy of the estimations, the average number of iterations and the running time for the above infection scenarios. The binary tasks remain much easier to solve than the real-valued tasks, requiring fewer iterations and less computational time to find a good estimation. The difference between the infection scenarios is also similar to that observed in the smaller examples, with larger infections being easier to predict. However, this depends on the ability of the graph to transfer infections (the reference edge values), as opposed to the fraction of initially infected vertices.  
Accuracy scaling can be seen in Figure 5a,b. The error of the estimation increases with the number of estimated values (edges), although the increase is significantly lower if the reference edge values are large. RMSE error values stay below 0.09 for all graphs if edge infections are large, but they are greater than 0.1 if infection values are small. Similar behavior can be observed in the binary case, where the classification is perfect if the transfer probabilities are large but remains below 1 if the edge values are small. The difference between scenarios with large and small edge infection probabilities can also be seen in Figure 5c,d, where the number of iterations required to find a good solution is much smaller if edge infection values are large. Finally, the running time of the tasks in minutes can be seen in Figure 5e,f. Depending on the size of the graph and the edge infection values, the tasks took one to eight hours on average to compute on the computer listed above.  
Figure 4: RMSE at different time steps of the infection process for the fully observed scenario in the SIR model. The error is shown for observations at \(T\): \(\{1\ldots 10\}\).  
Directly estimating the edge infection values in the GIIM is a difficult task, since the number of values to estimate, i.e., the number of edges, can be large, even for medium-sized graphs, posing a challenge for the optimization algorithm. In this section, we consider graphs with up to 4000 nodes and 7753 edges and show that estimation is possible on an average PC with acceptable accuracy and running time.  
There are multiple ways to speed up the method so that it can handle large networks. The time complexity of the optimization depends heavily on the time complexity of the infection model. A modified version of the CompleteSim infection heuristic [28] was used in this study, but other potentially faster heuristics are available in the literature [12; 28]. Another way to considerably speed up estimations is to assume that the edge infection values can be computed as functions of known vertex or edge attributes. In this case, only the coefficients of these functions have to be estimated, which are far less numerous than the number of edges in the graph.