Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Kendrick Simulator can not work in large population scale free network #76

Open
thanhbka85dn opened this issue Aug 21, 2018 · 4 comments

Comments

@thanhbka85dn
Copy link
Contributor

thanhbka85dn commented Aug 21, 2018

Implementing Bansal's idea for Kendrick simulator works well in scale-free network with SMALL population.
I run the test case with 100 individuals and it prints a nice graph:

image

But as trying larger population, such as 1000 or 10000 individuals, the simulator leaks memory and not responding at all.

I will take care of this case.

@thanhbka85dn thanhbka85dn changed the title Kendrick Simulator can not work well in scale free network with large population Kendrick Simulator can not work in scale free network with large population Aug 21, 2018
@thanhbka85dn
Copy link
Contributor Author

After fixing, now IBM Simulator can work with 1000 individuals of Scale-free network (k mean degree is 10), but it still takes too long to finish (about 1 hour)

image

@thanhbka85dn
Copy link
Contributor Author

thanhbka85dn commented Aug 22, 2018

In case 10000 individuals, I reduce the maximum of time to 10 days and change the step to 0.5; the simulator takes 2 hours to complete the graph:

image

@thanhbka85dn
Copy link
Contributor Author

thanhbka85dn commented Aug 23, 2018

I have fixed this issue, the main problem is - I guess - the time complexity of saveCompartmentsValueAtTime: O(N*N) - order N square.
As looking at the current version of this method:

image

model population compartment keysAndValuesDo will loop N times (N is number of compartment). In case 10000 individuals and three status #(S, I, R), N = 10000 x 3 = 30000.
The timeSeriesOutputs detect will loop n times with n ranges from 1 to N.
We have: 1 + 2 + ... + N = N*(N+1)/2 about N*N/2 times. If N = 30000, the simulator has no choice but to loop 450 million times. The situation will become worse as epidemiologist uses other compartments (like ages, genders, countries...).

Therefore, I suggest the code above is replaced by:

image

Assuming that (model population compartments) at: (e compartment) requires a constant time, the new version will take O(N) because timeSeriesOutputs do loops N times.

Last but not least, I increase the step of simulator to 0.5 (instead of 0.1), and it takes about 3 hours to finish.

image

Finally, I got this result:

image

@thanhbka85dn thanhbka85dn changed the title Kendrick Simulator can not work in scale free network with large population Kendrick Simulator can not work in large population scale free network Aug 23, 2018
@SergeStinckwich
Copy link
Collaborator

Integrate code from : master...thanhbka85dn:master

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

No branches or pull requests

2 participants