{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,3]],"date-time":"2025-12-03T17:37:30Z","timestamp":1764783450030,"version":"3.41.0"},"reference-count":25,"publisher":"Association for Computing Machinery (ACM)","license":[{"start":{"date-parts":[[2011,5,1]],"date-time":"2011-05-01T00:00:00Z","timestamp":1304208000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100004963","name":"Seventh Framework Programme","doi-asserted-by":"publisher","award":["231200"],"award-info":[{"award-number":["231200"]}],"id":[{"id":"10.13039\/501100004963","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001665","name":"Agence Nationale de la Recherche","doi-asserted-by":"publisher","award":["\u201cWebfluence\u201d #ANR-08-SYSC-009"],"award-info":[{"award-number":["\u201cWebfluence\u201d #ANR-08-SYSC-009"]}],"id":[{"id":"10.13039\/501100001665","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["ACM J. Exp. Algorithmics"],"published-print":{"date-parts":[[2011,5]]},"abstract":"<jats:p>\n            The generation of random graphs using edge swaps provides a reliable method to draw uniformly random samples of sets of graphs respecting some simple constraints (e.g., degree distributions). However, in general, it is not necessarily possible to access all graphs obeying some given constraints through a classical switching procedure calling on pairs of edges. Therefore, we propose to get around this issue by generalizing this classical approach through the use of higher-order edge switches. This method, which we denote by \u201c\n            <jats:italic>k<\/jats:italic>\n            -edge switching,\u201d makes it possible to progressively improve the covered portion of a set of constrained graphs, thereby providing an increasing, asymptotically certain confidence on the statistical representativeness of the obtained sample.\n          <\/jats:p>","DOI":"10.1145\/1963190.2063515","type":"journal-article","created":{"date-parts":[[2012,10,15]],"date-time":"2012-10-15T19:22:23Z","timestamp":1350328943000},"source":"Crossref","is-referenced-by-count":13,"title":["Generating constrained random graphs using multiple edge switches"],"prefix":"10.1145","volume":"16","author":[{"given":"Lionel","family":"Tabourier","sequence":"first","affiliation":[{"name":"SPEC (CEA Saclay), CREA (CNRS\/Ecole Polytechnique), ISC-PIF"}]},{"given":"Camille","family":"Roth","sequence":"additional","affiliation":[{"name":"CAMS (CNRS\/EHESS), CREA (CNRS\/Ecole Polytechnique), ISC-PIF"}]},{"given":"Jean-Philippe","family":"Cointet","sequence":"additional","affiliation":[{"name":"INRA SenS (IFRIS\/UPEMLV), CREA (CNRS\/Ecole Polytechnique), ISC-PIF"}]}],"member":"320","published-online":{"date-parts":[[2011,12,28]]},"reference":[{"doi-asserted-by":"publisher","key":"e_1_2_1_1_1","DOI":"10.1038\/43601"},{"doi-asserted-by":"publisher","key":"e_1_2_1_2_1","DOI":"10.1103\/PhysRevE.72.056708"},{"unstructured":"Bansal S. Khandelwal S. and Meyers L. 2008. Evolving Clustered Random Networks. Arxiv preprint cs.DM\/0808.0509.  Bansal S. Khandelwal S. and Meyers L. 2008. Evolving Clustered Random Networks. Arxiv preprint cs.DM\/0808.0509.","key":"e_1_2_1_3_1"},{"doi-asserted-by":"publisher","key":"e_1_2_1_4_1","DOI":"10.1016\/0097-3165(78)90059-6"},{"unstructured":"Colbourn C. 1977. Graph Generation. University of Waterloo Waterloo Ontario.  Colbourn C. 1977. Graph Generation. University of Waterloo Waterloo Ontario.","key":"e_1_2_1_5_1"},{"doi-asserted-by":"publisher","key":"e_1_2_1_6_1","DOI":"10.1007\/s10955-009-9821-2"},{"doi-asserted-by":"publisher","key":"e_1_2_1_7_1","DOI":"10.1017\/S0963548306007978"},{"key":"e_1_2_1_8_1","first-page":"385","article-title":"Graphic sequences and graphic polynomials: A report","volume":"1","author":"Eggleton R.","year":"1973","unstructured":"Eggleton , R. 1973 . Graphic sequences and graphic polynomials: A report . In Infinite and Finite Sets 1 , 385 -- 392 . Eggleton, R. 1973. Graphic sequences and graphic polynomials: A report. In Infinite and Finite Sets 1, 385--392.","journal-title":"Infinite and Finite Sets"},{"doi-asserted-by":"publisher","key":"e_1_2_1_9_1","DOI":"10.1109\/FOCS.2006.5"},{"volume-title":"Proceedings of the 5th Workshop on Algorithm Engineering and Experiments (ALENEX). SIAM","author":"Gkantsidis C.","unstructured":"Gkantsidis , C. , Mihail , M. , and Zegura , E . 2003. The markov chain simulation method for generating connected power law random graphs . In Proceedings of the 5th Workshop on Algorithm Engineering and Experiments (ALENEX). SIAM , Philadelphia. Gkantsidis, C., Mihail, M., and Zegura, E. 2003. The markov chain simulation method for generating connected power law random graphs. In Proceedings of the 5th Workshop on Algorithm Engineering and Experiments (ALENEX). SIAM, Philadelphia.","key":"e_1_2_1_10_1"},{"doi-asserted-by":"publisher","key":"e_1_2_1_11_1","DOI":"10.1007\/978-3-540-30536-1_15"},{"unstructured":"Guruswami V. 2000. Rapidly mixing markov chains: A comparison of techniques. MIT Laboratory for Computer Science. cs.washington.edu\/homes\/venkat\/pubs\/papers.html.  Guruswami V. 2000. Rapidly mixing markov chains: A comparison of techniques. MIT Laboratory for Computer Science. cs.washington.edu\/homes\/venkat\/pubs\/papers.html.","key":"e_1_2_1_12_1"},{"volume-title":"Proceedings of the 8th Annual ACM-SIAM Symposium on Discrete algorithms. SIAM","author":"Kannan R.","unstructured":"Kannan , R. , Tetali , P. , and Vempala , S . 1997. Simple Markov-chain algorithms for generating bipartite graphs and tournaments . In Proceedings of the 8th Annual ACM-SIAM Symposium on Discrete algorithms. SIAM , Philadelphia, 193--200. Kannan, R., Tetali, P., and Vempala, S. 1997. Simple Markov-chain algorithms for generating bipartite graphs and tournaments. In Proceedings of the 8th Annual ACM-SIAM Symposium on Discrete algorithms. SIAM, Philadelphia, 193--200.","key":"e_1_2_1_13_1"},{"doi-asserted-by":"publisher","key":"e_1_2_1_14_1","DOI":"10.1145\/1159913.1159930"},{"doi-asserted-by":"publisher","key":"e_1_2_1_15_1","DOI":"10.1890\/03-0101"},{"unstructured":"Milo R. Kashtan N. Itzkovitz S. Newman M. and Alon U. 2003. On the uniform generation of random graphs with prescribed degree sequences. Arxiv preprint cond-mat\/0312.028.  Milo R. Kashtan N. Itzkovitz S. Newman M. and Alon U. 2003. On the uniform generation of random graphs with prescribed degree sequences. Arxiv preprint cond-mat\/0312.028.","key":"e_1_2_1_16_1"},{"key":"e_1_2_1_17_1","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1073\/pnas.0307545100","article-title":"Coauthorship networks and patterns of scientific collaboration","volume":"101","author":"Newman M.","year":"2004","unstructured":"Newman , M. 2004 . Coauthorship networks and patterns of scientific collaboration . In Proc. Nat. Acad. Sciences 101, Suppl 1 , 5200. Newman, M. 2004. Coauthorship networks and patterns of scientific collaboration. In Proc. Nat. Acad. Sciences 101, Suppl 1, 5200.","journal-title":"Proc. Nat. Acad. Sciences"},{"doi-asserted-by":"publisher","key":"e_1_2_1_18_1","DOI":"10.1016\/j.neunet.2005.07.009"},{"unstructured":"Rao A. Jana R. and Bandyopadhyay S. 1996. A Markov chain Monte Carlo method for generating random (0 1)-matrices with given marginals. Sankhy&abar; Indian J. Statistics Series A 225--242.  Rao A. Jana R. and Bandyopadhyay S. 1996. A Markov chain Monte Carlo method for generating random (0 1)-matrices with given marginals. Sankhy&abar; Indian J. Statistics Series A 225--242.","key":"e_1_2_1_19_1"},{"doi-asserted-by":"publisher","key":"e_1_2_1_20_1","DOI":"10.1016\/S0378-8733(00)00026-5"},{"volume-title":"Algorithms for Random Generation and Counting: A Markov Chain Approach","author":"Sinclair A.","unstructured":"Sinclair , A. 1993. Algorithms for Random Generation and Counting: A Markov Chain Approach . Springer , Berlin . Sinclair, A. 1993. Algorithms for Random Generation and Counting: A Markov Chain Approach. Springer, Berlin.","key":"e_1_2_1_21_1"},{"unstructured":"Stauffer A. and Barbosa V. 2005. A study of the edge-switching Markov-chain method for the generation of random graphs. Arxiv preprint cs.DM\/0512.105.  Stauffer A. and Barbosa V. 2005. A study of the edge-switching Markov-chain method for the generation of random graphs. Arxiv preprint cs.DM\/0512.105.","key":"e_1_2_1_22_1"},{"key":"e_1_2_1_23_1","first-page":"314","article-title":"Constrained switchings in graphs","volume":"8","author":"Taylor R.","year":"1980","unstructured":"Taylor , R. 1980 . Constrained switchings in graphs . Comb. Math. 8 , 314 -- 336 . Taylor, R. 1980. Constrained switchings in graphs. Comb. Math. 8, 314--336.","journal-title":"Comb. Math."},{"doi-asserted-by":"publisher","key":"e_1_2_1_24_1","DOI":"10.1137\/0603011"},{"doi-asserted-by":"publisher","key":"e_1_2_1_25_1","DOI":"10.1007\/11533719_45"}],"container-title":["ACM Journal of Experimental Algorithmics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1963190.2063515","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1963190.2063515","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T20:26:02Z","timestamp":1750278362000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1963190.2063515"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011,5]]},"references-count":25,"alternative-id":["10.1145\/1963190.2063515"],"URL":"https:\/\/doi.org\/10.1145\/1963190.2063515","relation":{},"ISSN":["1084-6654","1084-6654"],"issn-type":[{"type":"print","value":"1084-6654"},{"type":"electronic","value":"1084-6654"}],"subject":[],"published":{"date-parts":[[2011,5]]}}}