{"entities":{"Q2012250":{"pageid":2022992,"ns":120,"title":"Item:Q2012250","lastrevid":57664689,"modified":"2026-03-31T20:23:51Z","type":"item","id":"Q2012250","labels":{"en":{"language":"en","value":"Cutoff for nonbacktracking random walks on sparse random graphs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 6754785"}},"aliases":{},"claims":{"P31":[{"mainsnak":{"snaktype":"value","property":"P31","hash":"fd5912e4dab4b881a8eb0eb27e7893fef55176ad","datavalue":{"value":{"entity-type":"item","numeric-id":56887,"id":"Q56887"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2012250$5AE405E8-2E35-4CBD-A28E-019D92028364","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"837c55cbb4093fcb3c92cbb43789af5786b3dc45","datavalue":{"value":{"text":"Cutoff for nonbacktracking random walks on sparse random graphs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q2012250$794DB2BE-2589-4C6B-B9FE-FDA348C9EABE","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"a492c4ca1d62244ef9b62659ad75dd533912b162","datavalue":{"value":"1372.60101","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2012250$6AF7C66F-3E7F-4848-B7FE-3C7EA6E3D63C","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"e96f9f143f60f0d630f84e117f8a9fb75f65a096","datavalue":{"value":"10.1214/16-AOP1100","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2012250$C88F2758-91FF-499F-9EFC-D83D6B5F9FE5","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"271875abe4ae0cb941bccba2c16fd8114581dbe9","datavalue":{"value":{"entity-type":"item","numeric-id":502866,"id":"Q502866"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2012250$3D9192DE-396C-4226-AC82-C0B40045C1D1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"10805d3400c51e153e79b4da914c84061746f113","datavalue":{"value":{"entity-type":"item","numeric-id":259577,"id":"Q259577"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2012250$AB20A51D-08C6-4D94-BF56-F2AC5C376846","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"c9d829dece3e2d330deed49a6cb836edc666e294","datavalue":{"value":{"entity-type":"item","numeric-id":107063,"id":"Q107063"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2012250$C2488A5B-F0F0-4832-AD80-BD5C78E6B8CF","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"c75f36686ff101691de5da09ae7135abb2a012b9","datavalue":{"value":{"time":"+2017-07-28T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q2012250$DF3EFFAE-F487-4AAB-AA82-C695C01F6EE7","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"092fcaf1863c6dba3fa33f391bcefc3b46c9a692","datavalue":{"value":"https://arxiv.org/abs/1504.02429","type":"string"},"datatype":"url"},"type":"statement","id":"Q2012250$C5611E5F-58B5-4EB5-81A6-B0E78904DFE8","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"db54d562a3d83ccaf18b662bf9eb5fb822cdd49d","datavalue":{"value":"Based on a given vertex set \\(V\\) and a function deg: \\(V\\to \\{2,3,\\ldots \\}\\) \\((N:=\\sum_{v\\in V}\\text{deg}(v))\\), one constructs a graph attaching deg(\\(v\\)) half-edges to each vertex \\(v\\in V\\)  \\[  \\mathcal{X}:=\\{(v,i):v\\in V,1\\leq i\\leq \\text{deg}(v)\\}.  \\]  One chooses a pairing \\(\\pi \\) on \\(V\\) and interprets every pair of matched half-edges \\(\\{x,\\pi (x)\\}\\) as an edge between the corresponding vertices. The nonbacktracking random walk (NBRW) is a discrete-time Markov chain where the transitions to the neighbouring vertices are possible with uniform distribution. The paper studies the sparse regime where the number \\(N\\) of half-edges diverges at a faster rate than the maximum degree. The main result states the NBRW shows the so-called cutoff phenomenon, the distance to equilibrium remains close to 1 for a long time and then drops to 0 over a much shorter time scale, the cutoff shape approaches the tail distribution of the standard nomal distribution.","type":"string"},"datatype":"string"},"type":"statement","id":"Q2012250$05479352-F531-4F43-9AFF-C25BE78397B3","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"f2f4187f96fe1f235cc10fef2a585d4f48ab9217","datavalue":{"value":{"entity-type":"item","numeric-id":592844,"id":"Q592844"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2012250$B78143B5-41B3-4309-926B-0922451ADCBE","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"1cdf15533e26fc0c4c2e22d28e655c364dfe77a6","datavalue":{"value":"60J10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2012250$EDB63312-2585-46ED-9D78-0D59FA55D10E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"e5b5126101ab4505674efcb5789319f63910d08f","datavalue":{"value":"05C81","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2012250$B928B638-5E0C-4893-A04E-150F24AC308A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"e52a86b600bbb05d9a7823bf91d423713b4b70ab","datavalue":{"value":"60G50","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2012250$9C354882-376A-49E1-BDFE-1754BB66837E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"4dd6b8847e09c706889ad9ef05dc0040f1c9f982","datavalue":{"value":"05C80","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2012250$1966B39A-6992-440C-9B61-A7053F48B31D","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"ca88135e036735ba855bcf0a8ead3f29358ee61b","datavalue":{"value":"6754785","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2012250$9B34528A-EDE9-4480-9272-B4A43991A543","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"52de7c482db54da68ab655f9186ae1cdf87630f3","datavalue":{"value":"cutoff","type":"string"},"datatype":"string"},"type":"statement","id":"Q2012250$30578DD0-5849-4905-BC26-EB38B42EAB02","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"3aff25cc82d788b16e86f5f24b9e5119fc52b742","datavalue":{"value":"nonbacktracking random walk","type":"string"},"datatype":"string"},"type":"statement","id":"Q2012250$8058A30F-C044-4252-9390-7D68E65372E1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"0e0446baf9c31d45b16691b35420e6e46c50f286","datavalue":{"value":"random graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q2012250$BB93C1A1-210C-46C7-9316-B1C9FF522BE6","rank":"normal"}],"P1460":[{"mainsnak":{"snaktype":"value","property":"P1460","hash":"57f7fea50d2ce1b39b695c4a1313582eed405e38","datavalue":{"value":{"entity-type":"item","numeric-id":5976449,"id":"Q5976449"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2012250$C3C3C8A4-A0B1-4BE2-BEF5-B52A9A0BDD0E","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"807ca431352e032b5ca1f112c7187219a2fce6e6","datavalue":{"value":"W2964318841","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2012250$0D95FCD4-1867-4718-8718-0204B4C9C8BD","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"7f2be15f968d1ad840f5dd2298b4d4685f3e831e","datavalue":{"value":{"entity-type":"item","numeric-id":2413249,"id":"Q2413249"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ab9c1245ea999a4d51f3acdb0649cc01968b2b8c","datavalue":{"value":{"amount":"+0.8241856098175049","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2012250$16632BD0-B227-4495-ABFA-7D7540621658","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"3afe2aa968c6d640436f36f0476c79a6b7b14148","datavalue":{"value":{"entity-type":"item","numeric-id":984454,"id":"Q984454"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"58710205f7d5d8da861a2f208cedd84fa278b417","datavalue":{"value":{"amount":"+0.8232262134552002","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2012250$80DB60C9-08D8-45E2-BDCE-D3528E019DE0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"40da6791ee7f946ded52a2c29ac2786c9df0ac84","datavalue":{"value":{"entity-type":"item","numeric-id":4608002,"id":"Q4608002"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"5fab75841e40edf44da6d9166594359f6da23dcb","datavalue":{"value":{"amount":"+0.8212546706199646","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2012250$F4C51683-FDD2-4670-BCBF-7DA585E846E1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"315f90ff600141a5dfb2e069401f543abac677d3","datavalue":{"value":{"entity-type":"item","numeric-id":2320396,"id":"Q2320396"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c401395bb22c58c0dd7f2f61299d9a261cb41e74","datavalue":{"value":{"amount":"+0.8210614919662476","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2012250$77E942CD-6C00-44DA-923C-B0E5CB843445","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"31141e6df4b849b0741a78f7e0639a7f9aa130fa","datavalue":{"value":{"entity-type":"item","numeric-id":2657925,"id":"Q2657925"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"31726a3e31b6748c2744eeadfc1c75161530d0cc","datavalue":{"value":{"amount":"+0.8183557987213135","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2012250$7F70756B-8059-4027-914E-24F64E9F9C43","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:2012250","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:2012250"}}}}}