Efficient Gillespie algorithms for spreading phenomena in large and heterogeneous higher-order networks

Efficient Gillespie algorithms for spreading phenomena in large and heterogeneous higher-order networks | Research Square window.SnipcartSettings = { analytics: { enabled: false } }; (function() { var accessVector = localStorage.getItem('access_vector') || ''; window.dataLayer = window.dataLayer || []; if (accessVector) { window.dataLayer.push({ user: { profile: { profileInfo: { snid: accessVector } } } }); } })(); (function(w,d,s,l,i){w[l]=w[l]||[];w[l].push({'gtm.start':new Date().getTime(),event:'gtm.js'});var f=d.getElementsByTagName(s)[0],j=d.createElement(s),dl=l!='dataLayer'?'&l='+l:'';j.async=true;j.src='https://www.googletagmanager.com/gtm.js?id='+i+dl;f.parentNode.insertBefore(j,f);})(window,document,'script','dataLayer','GTM-K279D39R'); Browse Preprints In Review Journals COVID-19 Preprints AJE Video Bytes Research Tools Research Promotion AJE Professional Editing AJE Rubriq About Preprint Platform In Review Editorial Policies Our Team Advisory Board Help Center Sign In Submit a Preprint Cite Share Download PDF Article Efficient Gillespie algorithms for spreading phenomena in large and heterogeneous higher-order networks Silvio Ferreira, Hugo Maia, Wesley Cota, Yamir Moreno This is a preprint; it has not been peer reviewed by a journal. https://doi.org/ 10.21203/rs.3.rs-8225160/v1 This work is licensed under a CC BY 4.0 License Status: Under Review Version 1 posted You are reading this latest preprint version Abstract Higher-order interactions, where groups of nodes interact collectively rather than pairwise, are central to many complex systems, from neural and ecological networks to social contagion. However, simulating dynamical processes on such higher-order structures remains computationally challenging due to the combinatorial growth of possible interactions. Here, we develop efficient and statistically exact Gillespie algorithms for Markovian spreading dynamics on large and heterogeneous hypergraphs. By incorporating phantom processes $-$events that advance time without altering the system’s state$-$, we drastically reduce the computational complexity of standard algorithms (O(N 2 )), achieving near-linear scaling with system size (O(N)). Using the susceptible–infected–susceptible model with critical mass thresholds as a benchmark, we show that the optimized algorithms outperform standard approaches by several orders of magnitude, enabling simulations of networks with millions of nodes and broad heterogeneity in both degree and interaction order. These results establish a general framework for scalable, continuous-time simulations of higher-order contagion and related dynamical processes. Physical sciences/Physics/Statistical physics, thermodynamics and nonlinear dynamics/Complex networks Physical sciences/Physics/Biological physics Full Text Additional Declarations There is NO Competing Interest. Cite Share Download PDF Status: Under Review Version 1 posted You are reading this latest preprint version Research Square lets you share your work early, gain feedback from the community, and start making changes to your manuscript prior to peer review in a journal. As a division of Research Square Company, we’re committed to making research communication faster, fairer, and more useful. We do this by developing innovative software and high quality services for the global research community. Our growing team is made up of researchers and industry professionals working together to solve the most critical problems facing scientific publishing. Also discoverable on Platform About Our Team In Review Editorial Policies Advisory Board Help Center Resources Author Services Accessibility API Access RSS feed Manage Cookie Preferences © Research Square 2026 | ISSN 2693-5015 (online) Privacy Policy Terms of Service Do Not Sell My Personal Information {"props":{"pageProps":{"initialData":{"identity":"rs-8225160","acceptedTermsAndConditions":true,"allowDirectSubmit":false,"archivedVersions":[],"articleType":"Article","associatedPublications":[],"authors":[{"id":557230273,"identity":"43805da0-e221-47c6-a910-457dc369c728","order_by":0,"name":"Silvio Ferreira","email":"data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAAZAAAAAyAQMAAABI0h/eAAAABlBMVEX///8AAABVwtN+AAAACXBIWXMAAA7EAAAOxAGVKw4bAAAAtUlEQVRIie3PMQrCMBTG8fcIZLRrnLzCg4LgbVJygA4uHRwihXZ09STSMRLolAN0koAncHO0tTr73ATzX7K8H3wBSKV+MSEsaJCQAUZAyyI4k6UVxCTvM3JcsmqxUbFalPlgpMLu8pmQH4kOcnN6krBlEIE1FY2k9VB6wkYzhtUvkh+N4BHwuI8TIWUwsghNZPwLqXDFWATOsIN353vVU9YacLeOM2yunx8+ANh9cZtKpVJ/1wOF1jW2Rrj4ygAAAABJRU5ErkJggg==","orcid":"https://orcid.org/0000-0001-7159-2769","institution":"Universidade Federal de Viçosa","correspondingAuthor":true,"prefix":"","firstName":"Silvio","middleName":"","lastName":"Ferreira","suffix":""},{"id":557230274,"identity":"80e22a12-4f70-4e40-9b3a-e1805d75d4ba","order_by":1,"name":"Hugo Maia","email":"","orcid":"","institution":"Universidade Federal de Viçosa","correspondingAuthor":false,"prefix":"","firstName":"Hugo","middleName":"","lastName":"Maia","suffix":""},{"id":557230275,"identity":"0f1b2549-c143-4be3-9106-238aa879e5f9","order_by":2,"name":"Wesley Cota","email":"","orcid":"https://orcid.org/0000-0002-8582-1531","institution":"Universidade Federal de Viçosa","correspondingAuthor":false,"prefix":"","firstName":"Wesley","middleName":"","lastName":"Cota","suffix":""},{"id":557230276,"identity":"ba03ada2-e13c-4a2d-a553-468e53596e07","order_by":3,"name":"Yamir Moreno","email":"","orcid":"https://orcid.org/0000-0002-0895-1893","institution":"University of Zaragoza","correspondingAuthor":false,"prefix":"","firstName":"Yamir","middleName":"","lastName":"Moreno","suffix":""}],"badges":[],"createdAt":"2025-11-27 22:15:20","currentVersionCode":1,"declarations":"","doi":"10.21203/rs.3.rs-8225160/v1","doiUrl":"https://doi.org/10.21203/rs.3.rs-8225160/v1","draftVersion":[],"editorialEvents":[],"editorialNote":"","failedWorkflow":false,"files":[{"id":97844617,"identity":"cf8e4cf6-9a63-4d23-8169-de1e28f271da","added_by":"auto","created_at":"2025-12-10 05:04:29","extension":"pdf","order_by":0,"title":"","display":"","copyAsset":false,"role":"acdc-reference","size":1351857,"visible":true,"origin":"","legend":"","description":"","filename":"ManuscriptNC.pdf","url":"https://assets-eu.researchsquare.com/files/rs-8225160/v1/3b8abaf9c1ddbfcd8b5e31ad.pdf"},{"id":97844616,"identity":"b81f6d6f-233f-4e69-83da-a354c795dcf0","added_by":"auto","created_at":"2025-12-10 05:04:29","extension":"json","order_by":1,"title":"","display":"","copyAsset":false,"role":"acdc-reference","size":5622,"visible":true,"origin":"","legend":"","description":"","filename":"NCOMMS2596335.json","url":"https://assets-eu.researchsquare.com/files/rs-8225160/v1/d327c00671e0d464cd9b3b8d.json"},{"id":97897445,"identity":"7daaa603-0378-45a5-8525-5d9dcc3df528","added_by":"auto","created_at":"2025-12-10 15:37:49","extension":"pdf","order_by":1,"title":"","display":"","copyAsset":false,"role":"manuscript-pdf","size":688814,"visible":true,"origin":"","legend":"Article File","description":"","filename":"ManuscriptNC.pdf","url":"https://assets-eu.researchsquare.com/files/rs-8225160/v1_covered_d84779f9-7f5a-445b-9315-e2cfff6b25f1.pdf"}],"financialInterests":"There is \u003cb\u003eNO\u003c/b\u003e Competing Interest.","formattedTitle":"Efficient Gillespie algorithms for spreading phenomena in large and heterogeneous higher-order networks","fulltext":[],"fulltextSource":"","fullText":"","funders":[],"hasAdminPriorityOnWorkflow":false,"hasManuscriptDocX":false,"hasOptedInToPreprint":true,"hasPassedJournalQc":"","hasAnyPriority":true,"hideJournal":false,"highlight":"","institution":"","isAcceptedByJournal":false,"isAuthorSuppliedPdf":true,"isDeskRejected":"","isHiddenFromSearch":false,"isInQc":false,"isInWorkflow":false,"isPdf":true,"isPdfUpToDate":true,"isWithdrawnOrRetracted":false,"journal":{"display":true,"email":"[email protected]","identity":"nature-portfolio","isNatureJournal":true,"hasQc":false,"allowDirectSubmit":false,"externalIdentity":"","sideBox":"","snPcode":"","submissionUrl":"","title":"Nature Portfolio","twitterHandle":"","acdcEnabled":false,"dfaEnabled":false,"editorialSystem":"ejp","reportingPortfolio":"","inReviewEnabled":true,"inReviewRevisionsEnabled":false},"keywords":"","lastPublishedDoi":"10.21203/rs.3.rs-8225160/v1","lastPublishedDoiUrl":"https://doi.org/10.21203/rs.3.rs-8225160/v1","license":{"name":"CC BY 4.0","url":"https://creativecommons.org/licenses/by/4.0/"},"manuscriptAbstract":"Higher-order interactions, where groups of nodes interact collectively rather than pairwise, are central to many complex systems, from neural and ecological networks to social contagion. However, simulating dynamical processes on such higher-order structures remains computationally challenging due to the combinatorial growth of possible interactions. Here, we develop efficient and statistically exact Gillespie algorithms for Markovian spreading dynamics on large and heterogeneous hypergraphs. By incorporating phantom processes $-$events that advance time without altering the system’s state$-$, we drastically reduce the computational complexity of standard algorithms (O(N\u003csup\u003e2\u003c/sup\u003e)), achieving near-linear scaling with system size (O(N)). Using the susceptible–infected–susceptible model with critical mass thresholds as a benchmark, we show that the optimized algorithms outperform standard approaches by several orders of magnitude, enabling simulations of networks with millions of nodes and broad heterogeneity in both degree and interaction order. These results establish a general framework for scalable, continuous-time simulations of higher-order contagion and related dynamical processes.","manuscriptTitle":"Efficient Gillespie algorithms for spreading phenomena in large and heterogeneous higher-order networks","msid":"","msnumber":"","nonDraftVersions":[{"code":1,"date":"2025-12-10 05:04:24","doi":"10.21203/rs.3.rs-8225160/v1","editorialEvents":[],"status":"published","journal":{"display":true,"email":"[email protected]","identity":"nature-communications","isNatureJournal":true,"hasQc":false,"allowDirectSubmit":false,"externalIdentity":"NCOMMS","sideBox":"Learn more about [Nature Communications](http://www.nature.com/ncomms/)","snPcode":"","submissionUrl":"https://mts-ncomms.nature.com/","title":"Nature Communications","twitterHandle":"","acdcEnabled":true,"dfaEnabled":true,"editorialSystem":"ejp","reportingPortfolio":"Nature Communications","inReviewEnabled":true,"inReviewRevisionsEnabled":false}}],"origin":"","ownerIdentity":"6ee8542b-1fe5-4f1d-925f-9a133b3885c0","owner":[],"postedDate":"December 10th, 2025","published":true,"recentEditorialEvents":[],"rejectedJournal":[],"revision":"","amendment":"","status":"under-review","subjectAreas":[{"id":59306012,"name":"Physical sciences/Physics/Statistical physics, thermodynamics and nonlinear dynamics/Complex networks"},{"id":59306013,"name":"Physical sciences/Physics/Biological physics"}],"tags":[],"updatedAt":"2026-04-15T17:20:19+00:00","versionOfRecord":[],"versionCreatedAt":"2025-12-10 05:04:24","video":"","vorDoi":"","vorDoiUrl":"","workflowStages":[]},"version":"v1","identity":"rs-8225160","journalConfig":"researchsquare"},"__N_SSP":true},"page":"/article/[identity]/[[...version]]","query":{"redirect":"/article/rs-8225160","identity":"rs-8225160","version":["v1"]},"buildId":"8U1c8b4HqxoKbykW_rLl7","isFallback":false,"isExperimentalCompile":false,"dynamicIds":[84888],"gssp":true,"scriptLoader":[]}