Teoretiska försök som hittills föreslagits för att beskriva vanliga perkoleringsprocesser på verkliga nätverk är beroende av den lokalt trädliknande ansatzen. En sådan approximation håller dock endast i begränsad utsträckning, eftersom verkliga grafer ofta kännetecknas av höga frekvenser av korta slingor. Vi presenterar här en teoretisk ram som kan övervinna en sådan begränsning för området perkolering. Vår metod är baserad på ett meddelande passerar algoritm som rabatterar redundanta vägar längs trianglar i grafen. Vi testar systematiskt metoden på 98 verkliga grafer och på syntetiska nätverk. Vi finner utmärkt exakthet i förutsägelsen av hela perkoleringsschemat, med betydande förbättring i förhållande till den förutsägelse som erhålls under den lokalt trädliknande approximationen. Restuella skillnader mellan teori och simuleringar beror inte på klusterbildning och kan tillskrivas förekomsten av slingor längre än tre kanter. Vi presenterar också en metod för att redovisa kluster i obligationsperkolering, men förbättringen med avseende på metoden baserad på den trädliknande approximationen är mycket mindre uppenbar. Perkoleringsprocesser används ofta för att studera motståndskraftsegenskaper hos verkliga nätverk [1] [2] [3], och spelar en grundläggande roll för förståelsen av spridningsfenomen i verkliga system [4, 5]. Perkolering har studerats intensivt i en mängd nätverksmodeller [6] [7] [8], inklusive glesa trädliknande grafer [2, 3, 9], samt generativa modeller för slumpmässiga nätverk med trianglar, klichéer eller godtyckliga subgrafer [10] [11] [11] [12] [13] [14] [15]. Dessa studier belyser grundläggande fysiska mekanismer av perkoleringsprocesser på komplexa nätverk topologier, men deras betydelse i analysen av perkolering på verkliga grafer är begränsad, eftersom topologin av enskilda verkliga nätverk ofta skiljer sig markant från den av slumpmässiga nätverk ensembler. Den senaste tidens arbeten har försökt övervinna en sådan allvarlig begränsning. Karrer m.fl. formulerat en ny metod som tar som indata den detaljerade topologiska strukturen i ett givet nätverk för att förutsäga värdet av perkoleringsstyrkan (och andra makroskopiska observerbara) som en funktion av obligationsaktivitetsannolikheten [16]. I synnerhet visade de att tröskelvärdet för obligationsperkolering för ett visst nät begränsas nedifrån av det ledande eigenvärdet för dess icke-backtracking-matris [17]. Ett tillvägagångssätt som bygger på samma logik användes också av Hamilton och Pryadko för att studera platsen percolation i isolerade nätverk [18], och av Radicchi i analysen av bindning och plats percolation modeller i ömsesidigt beroende nätverk [19]. Dessa metoder lider fortfarande av en grundläggande begränsning: de är baserade på lokalt trädliknande approximation [6] [7] [8], och som sådan de är potentiellt inte tillförlitliga för nätverk med icke försumbar densitet av trianglar, eller korta slingor i allmänhet [20, 21]. I detta dokument tar vi ett steg framåt genom att generalisera den strategi som utvecklats under [16, 18] för klustererade nätverk. Genom en systematisk analys av ett hundratal realtidsnätverk samt klustrade syntetiska, visar vi att vårt ramverk ger en utmärkt förutsägelse av hela fasdiagrammet för webbplatsens perkoleringsmodell. Dessutom lägger vi fram en strategi som också förbättrar förutsägelsen om obligationsperkoleringsfasens diagram (men på ett mindre tillfredsställande sätt) och förstår ursprunget till skillnaderna mellan de två fallen. Vi börjar vår analys från webbplatsen percolation modell. Vi antar att strukturen av ett nätverk med N noder och E kanter ges av en en-noll adjacency matris A (dvs. det generiska elementet A i,j = 1 om hörn i och j är anslutna, medan A i,j = 0 annars). Vi antar vidare att nätverket består av en enda ansluten komponent. I den vanliga webbplatsen percolation modell, varje nod är aktiv eller upptagen med sannolikhet p. Två aktiva noder tillhör samma kluster om det finns åtminstone en väg, passerar endast genom aktiva noder, som ansluter dem. För p = 0, inga noder är aktiva så att det inte finns några kluster. För p = 1, alla noder är aktiva och tillhör en enda kluster av storlek N. Som p varierar, nätverket genomgår en strukturell fas övergång, vid perkolationströskeln p c, vilket motsvarar uppkomsten av en omfattande kluster. Övergången kan övervakas genom den så kallade perkoleringsstyrkan S ∞, som definieras som den relativa storleken på den största klustret med avseende på nätverkets storlek. För p = 0, S ∞ = 0, för p = 1, S ∞ = 1. Målet med följande metod är att uppskatta det förväntade värdet av S ❌ över ett oändligt antal förverkliganden av perkolering modellen för varje givet värde av p. Sannolikheten s i att node i tillhör den största kluster kan beskrivas med ekvationen där N i är uppsättningen av grannar node i och t i→j kvantifierar sannolikheten att följa kanten (i, j), i riktning i → j, hittar vi en nod som tillhör den största kluster. Mängden t i→j kan tolkas som ett "mesarXiv:1602.07140v1 [fysik.soc-ph]
Radicchi m.fl. REF härleder också en alternativ matris av den icke-backtracking matrisen baserad på triangeln eliminering för att förbättra uppskattningen för platsen percolation tröskeln.
Beyond the locally tree-like approximation for percolation on real networks
{'venue': 'Phys. Rev. E 93, 030302 (2016)', 'journal': None, 'mag_field_of_study': ['Mathematics', 'Physics', 'Medicine']}