Randomization algorithms for large sparse networks

dc.contributorAalto-yliopistofi
dc.contributorAalto Universityen
dc.contributor.authorPuolamäki, Kaien_US
dc.contributor.authorHenelius, Andreasen_US
dc.contributor.authorUkkonen, Anttien_US
dc.contributor.departmentDepartment of Computer Scienceen
dc.contributor.groupauthorHelsinki Institute for Information Technology (HIIT)en
dc.date.accessioned2019-07-30T07:20:21Z
dc.date.available2019-07-30T07:20:21Z
dc.date.issued2019-05-30en_US
dc.description.abstractIn many domains it is necessary to generate surrogate networks, e.g., for hypothesis testing of different properties of a network. Generating surrogate networks typically requires that different properties of the network are preserved, e.g., edges may not be added or deleted and edge weights may be restricted to certain intervals. In this paper we present an efficient property-preserving Markov chain Monte Carlo method termed CycleSampler for generating surrogate networks in which (1) edge weights are constrained to intervals and vertex strengths are preserved exactly, and (2) edge and vertex strengths are both constrained to intervals. These two types of constraints cover a wide variety of practical use cases. The method is applicable to both undirected and directed graphs. We empirically demonstrate the efficiency of the CycleSampler method on real-world data sets. We provide an implementation of CycleSampler in R, with parts implemented in C.en
dc.description.versionPeer revieweden
dc.format.extent15
dc.format.extent1-15
dc.format.mimetypeapplication/pdfen_US
dc.identifier.citationPuolamäki, K, Henelius, A & Ukkonen, A 2019, ' Randomization algorithms for large sparse networks ', Physical Review E, vol. 99, no. 5, 053311, pp. 1-15 . https://doi.org/10.1103/PhysRevE.99.053311en
dc.identifier.doi10.1103/PhysRevE.99.053311en_US
dc.identifier.issn2470-0045
dc.identifier.issn2470-0053
dc.identifier.otherPURE UUID: cfdc389c-54f5-4179-bc5a-c1b4c6b8eeaeen_US
dc.identifier.otherPURE ITEMURL: https://research.aalto.fi/en/publications/cfdc389c-54f5-4179-bc5a-c1b4c6b8eeaeen_US
dc.identifier.otherPURE LINK: http://www.scopus.com/inward/record.url?scp=85066427308&partnerID=8YFLogxKen_US
dc.identifier.otherPURE FILEURL: https://research.aalto.fi/files/35132752/PhysRevE.99.053311.pdfen_US
dc.identifier.urihttps://aaltodoc.aalto.fi/handle/123456789/39505
dc.identifier.urnURN:NBN:fi:aalto-201907304560
dc.language.isoenen
dc.publisherAmerican Physical Society
dc.relation.ispartofseriesPhysical Review Een
dc.relation.ispartofseriesVolume 99, issue 5en
dc.rightsopenAccessen
dc.titleRandomization algorithms for large sparse networksen
dc.typeA1 Alkuperäisartikkeli tieteellisessä aikakauslehdessäfi
dc.type.versionpublishedVersion

Files