{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,27]],"date-time":"2025-06-27T12:44:19Z","timestamp":1751028259419,"version":"3.41.0"},"reference-count":44,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2019,4,18]],"date-time":"2019-04-18T00:00:00Z","timestamp":1555545600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"Singapore National Research Foundation under its Campus for Research Excellence And Technological Enterprise (CREATE) program"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Model. Comput. Simul."],"published-print":{"date-parts":[[2019,4,30]]},"abstract":"<jats:p>Social contact network (SCN) models the daily contacts between people in real life. It consists of agents and locations. When agents visit a location at the same time, the social interactions can be established among them. Simulations over SCN have been employed to study social dynamics such as disease spread among population. Because of the scale of SCN and the execution time requirement, the simulations are usually run in parallel. However, a challenge to the parallel simulation is that the structure of SCN is naturally skewed with a few hub locations that have far more visitors than others. These hub locations can cause load imbalance and heavy communication between partitions, which therefore impact the simulation performance. This article proposes a comprehensive solution to address this challenge. First, the hub locations are decomposed into small locations, so that SCN can be divided into partitions with better balanced workloads. Second, the agents are decomposed to exploit data locality, so that the overall communication across partitions can be greatly reduced. Third, two enhanced execution mechanisms are designed for locations and agents, respectively, to improve simulation parallelism. To evaluate the efficiency of the proposed solution, an epidemic simulation was developed and extensive experiments were conducted on two computer clusters using three SCN datasets with different scales. The results demonstrate that our approach can significantly improve the execution performance of the simulation.<\/jats:p>","DOI":"10.1145\/3265749","type":"journal-article","created":{"date-parts":[[2019,4,19]],"date-time":"2019-04-19T16:56:23Z","timestamp":1555692983000},"page":"1-25","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":5,"title":["Efficient Parallel Simulation over Large-scale Social Contact Networks"],"prefix":"10.1145","volume":"29","author":[{"given":"Yulin","family":"Wu","sequence":"first","affiliation":[{"name":"Nanyang Technological University, Nanyang Avenue, Singapore"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Wentong","family":"Cai","sequence":"additional","affiliation":[{"name":"Nanyang Technological University, Nanyang Avenue, Singapore"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Zengxiang","family":"Li","sequence":"additional","affiliation":[{"name":"Institute of High Performance Computing (A*STAR), Connexis North, Singapore"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Wen Jun","family":"Tan","sequence":"additional","affiliation":[{"name":"Nanyang Technological University, Nanyang Avenue, Singapore"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Xiangting","family":"Hou","sequence":"additional","affiliation":[{"name":"Nanyang Technological University, Nanyang Avenue, Singapore"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2019,4,18]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.5555\/1898953.1899055"},{"volume-title":"Proceedings of the 2014 Winter Simulation Conference. IEEE, 2750--2761","author":"Alt Aj","key":"e_1_2_1_2_1","unstructured":"Aj Alt and Philip A. Wilsey . 2014. Profile driven partitioning of parallel simulation models . In Proceedings of the 2014 Winter Simulation Conference. IEEE, 2750--2761 . Aj Alt and Philip A. Wilsey. 2014. Profile driven partitioning of parallel simulation models. In Proceedings of the 2014 Winter Simulation Conference. IEEE, 2750--2761."},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1109\/CSE.2009.240"},{"key":"e_1_2_1_4_1","volume-title":"Emergence of scaling in random networks. science 286, 5439","author":"Barab\u00e1si Albert-L\u00e1szl\u00f3","year":"1999","unstructured":"Albert-L\u00e1szl\u00f3 Barab\u00e1si and R\u00e9ka Albert . 1999. Emergence of scaling in random networks. science 286, 5439 ( 1999 ), 509--512. Albert-L\u00e1szl\u00f3 Barab\u00e1si and R\u00e9ka Albert. 1999. Emergence of scaling in random networks. science 286, 5439 (1999), 509--512."},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0378-4371(00)00018-2"},{"volume-title":"Proceedings of the 2008 ACM\/IEEE Conference on Supercomputing. ACM, Article 37","author":"Barrett Christopher L.","key":"e_1_2_1_6_1","unstructured":"Christopher L. Barrett , Keith R. Bisset , Stephen G. Eubank , Xizhou Feng , and Madhav V. Marathe . 2008. EpiSimdemics: An efficient algorithm for simulating the spread of infectious disease over large realistic social networks . In Proceedings of the 2008 ACM\/IEEE Conference on Supercomputing. ACM, Article 37 . Christopher L. Barrett, Keith R. Bisset, Stephen G. Eubank, Xizhou Feng, and Madhav V. Marathe. 2008. EpiSimdemics: An efficient algorithm for simulating the spread of infectious disease over large realistic social networks. In Proceedings of the 2008 ACM\/IEEE Conference on Supercomputing. ACM, Article 37."},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1038\/scientificamerican0305-54"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1109\/CCGRID.2017.141"},{"key":"e_1_2_1_9_1","unstructured":"K. Bisset K. Atkins C. L. Barrett R. Beckman S. Eubank A. Marathe M. Marathe H. S. Mortveit P. Stretz and V. A. Kumar. 2006. Synthetic Data Products for Societal Infrastructures and Proto-populations: Data Set 1.0. Technical Report. NDSSL Technical Report.  K. Bisset K. Atkins C. L. Barrett R. Beckman S. Eubank A. Marathe M. Marathe H. S. Mortveit P. Stretz and V. A. Kumar. 2006. Synthetic Data Products for Societal Infrastructures and Proto-populations: Data Set 1.0. Technical Report. NDSSL Technical Report."},{"volume-title":"Proceedings of the 2011 Winter Simulation Conference. IEEE, 2938--2952","author":"Bisset Keith","key":"e_1_2_1_10_1","unstructured":"Keith Bisset , Jiangzhuo Chen , Chris J. Kuhlman , V. S. Kumar , and Madhav V. Marathe . 2011. Interaction-based HPC modeling of social, biological, and economic contagions over large networks . In Proceedings of the 2011 Winter Simulation Conference. IEEE, 2938--2952 . Keith Bisset, Jiangzhuo Chen, Chris J. Kuhlman, V. S. Kumar, and Madhav V. Marathe. 2011. Interaction-based HPC modeling of social, biological, and economic contagions over large networks. In Proceedings of the 2011 Winter Simulation Conference. IEEE, 2938--2952."},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/2501602"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/1542275.1542336"},{"key":"e_1_2_1_13_1","volume-title":"Network analysis in the social sciences. Science 323, 5916","author":"Borgatti Stephen P.","year":"2009","unstructured":"Stephen P. Borgatti , Ajay Mehra , Daniel J. Brass , and Giuseppe Labianca . 2009. Network analysis in the social sciences. Science 323, 5916 ( 2009 ), 892--895. Stephen P. Borgatti, Ajay Mehra, Daniel J. Brass, and Giuseppe Labianca. 2009. Network analysis in the social sciences. Science 323, 5916 (2009), 892--895."},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1177\/0037549712462620"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.4108\/ICST.SIMUTOOLS2009.5672"},{"key":"e_1_2_1_16_1","article-title":"Network based models of infectious disease spread","volume":"58","author":"Eubank Stephen","year":"2005","unstructured":"Stephen Eubank . 2005 . Network based models of infectious disease spread . Jpn. J. Infect. Dis. 58 , 6 (2005), S. Stephen Eubank. 2005. Network based models of infectious disease spread. Jpn. J. Infect. Dis. 58, 6 (2005), S.","journal-title":"Jpn. J. Infect. Dis."},{"key":"e_1_2_1_17_1","volume-title":"Modelling disease outbreaks in realistic urban social networks. Nature 429, 6988","author":"Eubank Stephen","year":"2004","unstructured":"Stephen Eubank , Hasan Guclu , V. S. Anil Kumar , Madhav V. Marathe , Aravind Srinivasan , Zoltan Toroczkai , and Nan Wang . 2004. Modelling disease outbreaks in realistic urban social networks. Nature 429, 6988 ( 2004 ), 180--184. Stephen Eubank, Hasan Guclu, V. S. Anil Kumar, Madhav V. Marathe, Aravind Srinivasan, Zoltan Toroczkai, and Nan Wang. 2004. Modelling disease outbreaks in realistic urban social networks. Nature 429, 6988 (2004), 180--184."},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/2866577"},{"key":"e_1_2_1_19_1","volume-title":"Eddy","author":"Gallagher Shannon","year":"2017","unstructured":"Shannon Gallagher , Lee Richardson , Samuel L. Ventura , and William F . Eddy . 2017 . SPEW : Synthetic populations and ecosystems of the world. Arxiv preprint Arxiv :1701.02383 (2017). Shannon Gallagher, Lee Richardson, Samuel L. Ventura, and William F. Eddy. 2017. SPEW: Synthetic populations and ecosystems of the world. Arxiv preprint Arxiv:1701.02383 (2017)."},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1177\/0037549714531061"},{"key":"e_1_2_1_21_1","volume-title":"Proceedings of the 10th USENIX Conference on Operating Systems Design and Implementation (OSDI\u201912)","author":"Gonzalez Joseph E.","year":"2012","unstructured":"Joseph E. Gonzalez , Yucheng Low , Haijie Gu , Danny Bickson , and Carlos Guestrin . 2012 . PowerGraph: Distributed graph-parallel computation on natural graphs . In Proceedings of the 10th USENIX Conference on Operating Systems Design and Implementation (OSDI\u201912) . USENIX Association, 17--30. Joseph E. Gonzalez, Yucheng Low, Haijie Gu, Danny Bickson, and Carlos Guestrin. 2012. PowerGraph: Distributed graph-parallel computation on natural graphs. In Proceedings of the 10th USENIX Conference on Operating Systems Design and Implementation (OSDI\u201912). USENIX Association, 17--30."},{"issue":"940","key":"e_1_2_1_22_1","first-page":"1","article-title":"FRED (A framework for reconstructing epidemic dynamics): an open-source software system for modeling infectious diseases and control strategies using census-based populations","volume":"13","author":"Grefenstette John J.","year":"2013","unstructured":"John J. Grefenstette , Shawn T. Brown , Roni Rosenfeld , Jay DePasse , Nathan T. B. Stone , Phillip C. Cooley , William D. Wheaton , Alona Fyshe , David D. Galloway , Anuroop Sriram , 2013 . FRED (A framework for reconstructing epidemic dynamics): an open-source software system for modeling infectious diseases and control strategies using census-based populations . BMC Publ. Health 13 940 , 1 (2013), 1 -- 14 . John J. Grefenstette, Shawn T. Brown, Roni Rosenfeld, Jay DePasse, Nathan T. B. Stone, Phillip C. Cooley, William D. Wheaton, Alona Fyshe, David D. Galloway, Anuroop Sriram, et al. 2013. FRED (A framework for reconstructing epidemic dynamics): an open-source software system for modeling infectious diseases and control strategies using census-based populations. BMC Publ. Health 13:940, 1 (2013), 1--14.","journal-title":"BMC Publ. Health"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1080\/13658810701349037"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1109\/DS-RT.2010.10"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.procs.2012.04.031"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF00163027"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1097\/PHH.0b013e31829398eb"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.5555\/1304060.1304517"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1109\/DS-RT.2016.17"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1109\/IPDPS.2013.72"},{"volume-title":"Proceedings of the IEEE International Conference on Computing Communication Technologies, Research, Innovation, and Vision for the Future (RIVF\u201916)","author":"Petkova A.","key":"e_1_2_1_31_1","unstructured":"A. Petkova , C. Hughes , N. Deo , and M. Dimitrov . 2016. Accelerating the distributed simulations of agent-based models using community detection . In Proceedings of the IEEE International Conference on Computing Communication Technologies, Research, Innovation, and Vision for the Future (RIVF\u201916) . IEEE, 25--30. A. Petkova, C. Hughes, N. Deo, and M. Dimitrov. 2016. Accelerating the distributed simulations of agent-based models using community detection. In Proceedings of the IEEE International Conference on Computing Communication Technologies, Research, Innovation, and Vision for the Future (RIVF\u201916). IEEE, 25--30."},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/2486092.2486115"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1093\/bioinformatics\/bth436"},{"volume-title":"Proceedings of the 2014 International Conference on Autonomous Agents and Multi-agent Systems. International Foundation for Autonomous Agents and Multiagent Systems, 1173--1176","author":"Swarup Samarth","key":"e_1_2_1_34_1","unstructured":"Samarth Swarup , Stephen G. Eubank , and Madhav V. Marathe . 2014. Computational epidemiology as a challenge domain for multiagent systems . In Proceedings of the 2014 International Conference on Autonomous Agents and Multi-agent Systems. International Foundation for Autonomous Agents and Multiagent Systems, 1173--1176 . Samarth Swarup, Stephen G. Eubank, and Madhav V. Marathe. 2014. Computational epidemiology as a challenge domain for multiagent systems. In Proceedings of the 2014 International Conference on Autonomous Agents and Multi-agent Systems. International Foundation for Autonomous Agents and Multiagent Systems, 1173--1176."},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.5555\/2022297.2022313"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/3064911.3064934"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.artmed.2015.06.003"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.5555\/2693848.2694282"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1109\/IPDPS.2014.83"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1088\/1367-2630\/12\/2\/023015"},{"key":"e_1_2_1_41_1","volume-title":"Proceedings of the Conference on Summer Computer Simulation. Society for Computer Simulation International, 1--8.","author":"Zhang Mingxin","year":"2015","unstructured":"Mingxin Zhang , Rongqing Meng , and Alexander Verbraeck . 2015 b. Including public transportation into a large-scale agent-based model for epidemic prediction and control . In Proceedings of the Conference on Summer Computer Simulation. Society for Computer Simulation International, 1--8. Mingxin Zhang, Rongqing Meng, and Alexander Verbraeck. 2015b. Including public transportation into a large-scale agent-based model for epidemic prediction and control. In Proceedings of the Conference on Summer Computer Simulation. Society for Computer Simulation International, 1--8."},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1109\/TCC.2014.2328594"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1109\/TETC.2015.2398353"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1145\/2038916.2038936"}],"container-title":["ACM Transactions on Modeling and Computer Simulation"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3265749","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3265749","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T01:39:49Z","timestamp":1750210789000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3265749"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,4,18]]},"references-count":44,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2019,4,30]]}},"alternative-id":["10.1145\/3265749"],"URL":"https:\/\/doi.org\/10.1145\/3265749","relation":{},"ISSN":["1049-3301","1558-1195"],"issn-type":[{"type":"print","value":"1049-3301"},{"type":"electronic","value":"1558-1195"}],"subject":[],"published":{"date-parts":[[2019,4,18]]},"assertion":[{"value":"2017-11-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2018-08-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2019-04-18","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}