Empirical Setup

For all the experiments, we fixed the worm strategy such that each infected node, in each round, sends out the worm to $\beta$ unique nodes selected uniformly at random, and we fixed the alert strategy according to Algorithm 1. We note that the worm strategy we used in these experiments is not necessarily the best possible worm strategy, but we selected this strategy for concreteness. We stress that our theoretical results hold for any worm strategy.

We performed experiments on two kinds of networks. For the first network, we use a random $d$-regular directed graph as the overlay network. Our $d$ regular directed random graph was created on the lines of the standard configuration model. We have an array of nodes id's containing $d$ stubs each for every one of the $n$ node id's. This $nd$ size array is in increasing order. We take a random permutation of this array and map the corresponding elements of the first array and the permuted array to get a $d$-regular directed graph. We ignore self loops and multi-edges in this implementation. We call this network a random network

For the second network we make use of the pairwise independent hash functions described in the book by Mitzenmacher Upfal on Probability and Computing. In this model, node id $i$ maps to $(ai + b)$ mod $n$, where $n$ is a prime and $0<a\leq n-1$, $0\leq b \leq n-1$. We find 50 distinct values of $a$ chosen uniformly at random between $1$ and $n-1$. We find 50 values of $b$ chosen uniformly at random between 0 and $n-1$. This gives us 50 pairwise independent hash functions which map a node $i$ to 50 other nodes in the network. We call this network a pseudo-random network.

The relative advantage in the implementation of the pseudo-random network over the random network is in not having to store explicitly the graph in the memory. We compute the neighbors of a node in real time when we need to access them. The implementation of the default mod function was computationally intensive. To make this operation more efficient we store $2^i$ mod $p$, $0<i<\log_2{p}$ in one preprocessing step and access the stored values throughout the simulation. All multiplications between integers is reduced to multiplications between powers of two. For the rest of this section we give sizes of the network in this network model in terms of the largest power of two smaller than the prime number representing the actual size of the network. In our experiments we use hash table primes given here

There are several possible strategies for resolving the status of a node that gets both a worm message and an alert message in the same round and is neither infected nor alerted before that round. In our theoretical analysis, we assumed that if a node receives just one worm message it becomes infected. However, in our experiments, we used the somewhat more relaxed and realistic assumption that the probability that the node gets infected equals the number of worm messages received divided by the total number of messages received, and that the probability the node becomes alerted is $1$ minus this quantity. We note that this assumption is equivalent to assuming that the messages all arrive in the node's message queue according to some random permutation.

Our first experiment measured the fraction of nodes saved when we varied both $\alpha$ and $n$. In our second experiment we measured the fraction of nodes alerted and infected at each round of the algorithm. To further explore the role of $\alpha$ in our model, in our third experiment, we measured the fraction of nodes saved as $\alpha$ varies. In this experiment we ensure that the $\tau$ value is always adjusted so that the number of nodes which can be alerted due to a false alert is always $10^4$. So $\tau=\lfloor\log_{\alpha}{10^4}\rfloor$.