So let’s do an exercise here.

What’s my O()? The order of how many processing steps I’m doing?

It’s not too awfully hard to “guesstimate”.

***
EDIT: All numbers of operations below are wrong at least by a factor of 8, because where it says O(N^2) it should have said O(kN), where k is the average vertex degree of the network. With k=4.33 and N=38, I’m rounding to a factor of 8. And so I’m doing 8 times FEWER operations (order of magnitude) and so my number of cycles per base operations is about one order of magnitude higher (which is less surprising in my head, although I really don’t know…).

So there. It would seem I needed that coffee after all…

END EDIT.

***

 

 

Now the most basic operation is like so: Generate a random value between 0 and 1. Compare it to a value (Beta, or Mu, in the current version). If lower/bigger, do something (set infected or susceptible for next step).

The mu, you do once per infected node (say N), per time-step (t), per simulation (Sim), per individual (Ind), per generation (G.). How many nodes are infected in any time, for any individual? That’s the point, depends on so many things, it’s far-cry from easy to say. I’ll say it’s related mostly to the Beta and the number of nodes and edges…
Let’s remove the Beta (which is a parameter) and the worry of former-step situation, and go simplistic here (I’m looking for order of magnitude, not the exact number): O(N). I’m too tired to think it through any further.

The Beta, it’s not that simple: If infected, you don’t do it, no use. If NOT infected, you look at all its NEIGHBOURS, and for each infected, you see if you get the infection. Again, depends on the neighbours, current situation, which depends on the former time steps… Crazy. Again, maybe better call it O(N*(N-1)), which is obviously the worst case scenario (complete graph).

Now we have a base number, let’s call it O(N^2) for simplicity (we do beta or mu at each step, so I forget about mu altogether, it’s one lower order anyway). I KNOW, I’m off by quite a bit for sure, but that’s not an issue. Plus no one asks me for this, so there, I don’t care to go further into the details.

O(N^2) is one time-step.

Now let’s put more numbers to that, shall we?

Our example network has 38 nodes (N=38).

For each simulation, I run 50 time-steps (BUT! That number itself MUST be adapted to the network size! A big big network would require more time-steps!). And so, I’ll keep it simple and say t=2*N again. I know, again, I’m way off. It could very well be N^2 as well, I just don’t care (it’s Sunday morning… Be nice). 

For each individual, I run 50 different base scenarios. For the sake of not rounding up too much, I’ll call it 50. It’s not right: If I choose an initial prevalence of 20% of a small network with 38 nodes, to ensure each simulation considers different initial infections, the bigger the network, the more “original scenarios” I should try, and so if I were to be bragging about how much my laptop does in one night, I’d say N. But that wouldn’t be quite right either, because I could compensate with higher number of individuals or generations, and so I’ll take a constant, just because I want to. So say Sim=50.

Now, to cover more ground of the search space, the number of individuals should also be adapted to the number of nodes. After all, the complete search space, binary algorithm, for Beta and Mu for N individuals would be… 2^(2N) = 7.55e22, for N=38. (Don’t get me started about networks with 10,000 nodes…) That’s the search space. That’s the upper-bound for my simulator. That’s how many times I should run my simulator for perfection, the number of possible different individuals. That’s what a “perfect brute-force” would have to do. Mind you, that, but times the numbers from above, so it’s quite a bit of Sims runs… Which is why hopefully the GA helps, maybe not finding the BEST solution, but still doing a reasonable job while covering (hopefully) MUCH less ground (I should really hope so!).

OK, so, let’s keep going. Let’s say we want to have Ind=2N individuals per generations.

Finally (pfiu!), we do all the above for a few hundreds or thousands of generations (mutations won’t count for effort, although they’re important for effectiveness, and hence for efficiency…). For my small network, 100 individuals, I saw consistent progress in 1000 and up to 1500 generations.

Let’s call it 1000.

And here is why my apparently rather not-complex program uses 7 of my CPUs, and runs each Sim in C++ instead of R:

If I’m not completely off, I can guesstimate ONE CONFIGURATION to require roughly (for 38 nodes), in the ORDER OF:

(38^2)*(2*38)*50*(2*38)*1000 ~= 417,027,200,000 “operations” (aka 400 billion, if neither my math nor my English fail me).

If I’m not completely off (I might very well be, but again, Sunday morning here…): I’m doing 0.0000000000005 times the total of potential operations while finding (hopefully) reasonably good results (compared to optimum)… Hopefully, that’s a good gain (1.6 trillion times better, I think) compared to “simple brute force”. Thank you, Mr J. Holland, for coming up with Genetic Algorithms!

Then again

And of course, I want to test different Beta, Mu and Budgets (for the current version of the simulator, that is), so say the above, times (if I’m being VERY exhaustive) one thousand?

Now I’ve tried with fixed Mu, 3 levels of base Beta and 8 different Budgets and (let’s say) it took say 1h (NOT quite, I’m rounding everything, I just wasn’t staying looking at the screen the whole time – And ALTHOUGH I HAVE THE EXACT NUMBER somewhere… I haven’t opened my program yet today…), on 7 “cores” (obviating some overhead, that is irrelevant here):

So 400 billion * (3*8) / (7*3600) ~= 400000000 operations per second (again, one “operation” involves generated a pseudo-random number, etc.).

 And is that good? I don’t have a clue :D:D:D:D

But then again, if I lookup up some numbers about Macbook M1 chips (and I’ve got no active refrigeration, it’s not the highest end, but I like it, and let’s forget that altogether), it appears we’re talking roughly 3.2GHz per thread or core?

3200000000 / 400000000 = 8 cycles per “operation” (WT…!?!)

WOWOOOOOOWWWW! I mean, SURELY I’m WAY OFF somewhere, and surely I’m actually doing MUCH FEWER operations per unit of time… Maybe it was 2h per run after all?… But then I hope I’m within (say) two orders of magnitudes, and IF SO, that means… 80-800 cycles per operation – I would be VERY OK with that: I’d be using my laptop PRETTY GOOD.

YES, I know… Maybe I should re-do the numbers with a cup of coffee… BUT NOT TODAY.

Now remember: That’s for a SMALL 38-nodes network!!! And things should GROW EXPONENTIALLY with the number of nodes, so that means that if I want to do this at scale…

When does Apple release the “M3 SUPER ULTRA DUPER MAX” with 3 times as many CPUs? (Kiddin’… Or am I? Yes, no, I am, of course… But am I though? 😀 Nah, the ROI for the MSc dissertation paper isn’t quite there… If I had to somehow leverage this at work though…).

Although maybe… I should look at the “Neural Engine”, the GPU (i’ve tested some things that way, but not really gotten anywhere incredibly useful…), or (to keep it simple with less re-work… because those two options would cost me a whole lot of effort…) much easier: Go Cloud-based, rent a gazillion CPUs to run things in parallel (right now I’m doing 7 with parallel processing for 100 individuals, but really for 30 (I optimize things a bit), so with 30 CPUs, I could run things 4x faster… And I could set things up to run in parallel for each config, so I can in theory parallelize the thing easily 1000 times more) for just a little bit of time… It’s just, I have 7 CPUs at hand (8, but I keep one free for anything else to avoid contention), and that’ll have to do for now. Call it “edge computing”, that’s fashionable…

 

Well I don’t know, it’s all “guesstimates”, just ballpark numbers, to reassure me in that I’ve done a reasonable work at making things “fast”. I’m pretty sure I scr**ed up in any number of places in the above, but well, let’s just say: This my little project requires a bit of processing, if we are to expect anything of value out of it…

Side note: I personally care about not wasting unnecessary power where/when possible… So in my head, I’m assuming some day this could amount to great savings for any numbers of very large Companies out there (or well their CYS Depts), which in turn would mean much much less CO2 than what I’m wasting on trying to create the “product” in the first place… If one in a million such “projects” people are working on out there could have some positive impact on energy waste, who knows, maybe it’s all worth it?

Other value for the project

The whole thing comes from the theory world of epidemiology. Who knows, like, with more time, thought and energy, this could even be of value for human networks, not only computer networks. I’m sorry I’m specialised in IT and Cybersecurity: I’m no medical doctor, and so I don’t feel entitled to dive into that topic as much (although, well, to a point, numbers are numbers, and we’re all self-designated experts in a post-COVID world, but still… It would feel a bit irresponsible…). On the other hand, MDs probably need help from IT people, so maybe it’s not crazy that I would look into it…

I can’t do it all (a friend once told me I “shouldn’t aim for knowing everything about everything, that it was too stressing and impossible anyway”…), so that will definitely go to “future work”.

But I just felt it was important to mention: This could be valuable to others out there… I hope so, anyway!

One week off

That’s right, I’m taking the week off of this whole thing. No coding, and although I most certainly won’t manage to not “think” about it, I’ll try to keep it at a minimum, get back some lost sleep hours, and at most take some notes on paper for upcoming work.

Let’s see if I can stick to that “plan” for a week… (Who am I kidding?)