Vi presenterar k-Flipper, en graf transformationsalgoritm som omvandlar regelbundna oriktade grafer. Med tanke på en stig på k + 2 kanter byter den ut den sista hörnen på stigen. Den här operationen bevarar per definition regelbundenhet och konnektivitet. Vi visar att varje regelbundet ansluten graf kan nås genom en serie av dessa operationer för alla k ≥ 1. Vi använder en randomiserad version, kallad Random k-Flipper, för att skapa slumpmässiga regelbundna anslutna oriktade grafer som kan fungera som en ryggrad för peer-to-peer nätverk. Vi bevisar för de- 2 log 1/ ) omvandlar någon graf till en expander graf med hög sannolikhet, dvs.. 1−n −.(1).............................................................................................. Random 1-flippern är symmetrisk, dvs. Omvandlingsannolikheten från någon märkt d-regelbunden graf G till G är lika med de från G till G. Från detta och nåbarhet egenskapen drar vi slutsatsen att i gränsen en serie slumpmässiga 1-flipper operationer konvergerar mot en enhetlig sannolikhetsfördelning över alla anslutna märkta d-regelbundna grafer. För grad d  en (1) växer med grafens storlek innebär detta att iterativt tillämpa random 1-flipper omvandlar någon given graf till en expander asymptotiskt nästan säkert. Vi använder dessa operationer som en underhållsoperation för ett peer-to-peer-nätverk baserat på slumpmässiga regelbundna uppkopplade grafer som ger hög robusthet och återhämtar sig från degenererade nätverksstrukturer genom att kontinuerligt tillämpa dessa slumpmässiga graftransformationer. För detta beskriver vi hur nätverksoperationer för att ansluta och lämna nätverket kan utformas och hur sammanfallande grafomvandlingar kan hanteras.
Inledningsvis har Mahlmann och Schindelhauer föreslagit Random k-Flipper REF, en graf transformationsalgoritm som skapar slumpmässiga regelbundet anslutna oriktade grafer, asymptotiskt nästan säkert enhetlig.
Peer-to-peer networks based on random transformations of connected regular undirected graphs
{'venue': "SPAA '05", 'journal': None, 'mag_field_of_study': ['Computer Science']}