Vi studerar problemet med att återvinna en känd klusterstruktur i ett glest nätverk, även känt som det planterade delningsproblemet, med hjälp av statistisk mekanik. Vi finner en skarp övergång från oåtervinnbar till återvinningsbar struktur som en funktion av separationen av kluster. För multivariata data har sådana övergångar observerats ofta, men alltid som en funktion av antalet datapunkter, dvs. Med tanke på en tillräckligt stor datamängd, kan två punktmoln alltid erkännas som olika kluster, så länge deras separation är icke-noll. Däremot, för de glesa nätverk som studeras här, förblir en klusterstruktur omöjlig att upptäcka även i ett oändligt stort nätverk om en kritisk separation inte överskrids. Vi ger analytiska formler för denna kritiska separation som en funktion av graden av distributionen av nätet och beräkna formen av recoverabilitytransition. Våra resultat har implikationer för oövervakat lärande och datautvinning i relationella databaser och ger gränser för den uppnåeliga prestandan hos grafklusteralgoritmer. PAC-nummer: 89,75. Hc,05.50.+q,64.60.Cn Inom någon vetenskapsgren börjar ofta undersökande dataanalys med klusterbildning. Om man antar att uppgifterna är hopsamlade, är en naturlig fråga om man över huvud taget kan hoppas på att återvinna den underliggande strukturen av data från ett begränsat antal prover [1]. Denna fråga har studerats ingående av fysiker i följande sammanhang: Med tanke på αN-data från en känd sannolikhetsfördelning som bildar kluster i ett N-dimensionellt utrymme (t.ex. en blandning av Gaussians), kan vi återställa parametrarna för sannolikhetsfördelningen från den givna data ensam och kan vi märka datapunkterna korrekt som tillhör en av punktmolnen? Det svar som har getts är i allmänhet ja. För varje icke-noll separation av kluster i ett flerdimensionellt utrymme kan man lära sig parametrarna för den underliggande fördelningen om bara antalet datapunkter är tillräckligt stort, dvs. Man observerar en övergång från oåtervinnbar till återvinningsbar struktur som en funktion av α [2, 3, 4, 5]. I detta bidrag studerar vi problemet med att återvinna en känd klusterstruktur i nätverk. Detta problem har på senare tid fått stor uppmärksamhet under termen "community detection" [6, 7, 8, 9] i forskningen om de komplexa nätverkens topologi. Om kluster är alla lika stora, är detta problem känt som "planterade partition problem" i datavetenskap där det mest studerade fallet är planterade bisektion problem där alla noder i nätverket är medlemmar i en av endast två kluster. Varje par av noder från samma kluster är ansluten med sannolikhet p, medan varje par noder från olika kluster är ansluten med sannolikhet r < p. Som ett exempel, Onsjö och Watanabe ger en algoritm som bevisligen återvinner den planterade lösningen med sannolikhet > 1 − δ om p − r = ∂(N −1/2 log(N/δ)) [10]. Andra författare presenterar olika algoritmer med liknande gränser [11, 12]. Återigen, om datamängden, dvs. antalet noder N, är tillräckligt stor, de två kluster kan återvinnas oavsett styrkan i deras separation (p − r). Ovanstående bundna gäller endast täta nätverk där det genomsnittliga antalet anslutningar per nod k växer linjärt med antalet noder i nätverket. De flesta verkliga nätverk på vilka kluster utförs är dock glesa och har länkdensiteter i storleksordningen 1/N, i vilket fall ovanstående bundna är meningslösa [13, 14]. Den genomsnittliga konnektiviteten för glesa nät ökar inte i takt med systemets storlek. Tänk till exempel på den globala webben: dubblering av antalet webbsidor kommer inte att leda till att antalet länkar fördubblas en enda sida listor eller tar emot i genomsnitt. Vi kommer att visa att för glesa nätverk, en fördefinierad klusterstruktur förblir oåtervinnbar även i gränsen för oändliga N, Om sannolikheten för en intra-kluster länk inte överstiger ett kritiskt värde p c där beror på graden distribution p (k). Vi kommer att beräkna p c in och formen av övergången analytiskt som en funktion av p (k). Vi överväger särskilt problemet med att återställa den fördefinierade klusterstrukturen i oändligt stora glesa nät för vilka en gradfördelning p(k) ges och samma i alla kluster. Den genomsnittliga konnektiviteten per nod k antas vara ändlig. Vi parameteriserar den planterade klusterstrukturen i nätverket genom antalet kluster q och sannolikheten p i att en given kant ligger inom en av q lika stora kluster. Varje nod i bär ett index s i  till {1,..., q} som anger den kluster som den tillhör genom design. För p in = 1/q kan den fördefinierade klusterstrukturen inte återvinnas per definition, medan för p in = 1 återhämtning är trivialt eftersom vårt nätverk består av q frånkopplade delar. Med tanke på ett sådant nätverk är vi intresserade av att hitta en partition, dvs. en tilldelning av index σ i  ska {1,..., q} till nätverkets N-noder, t.ex. för att maximera noggrannheten A = i σ si,σi /N för att återvinna den planterade lösningen. Eftersom vi inte kan anta kunskap om p i, Det bästa möjliga tillvägagångssättet är att hitta en partition
Reichardt och Leone Ref ansåg att de glesa nät där dessa gränser är meningslösa eftersom både p out och p i skala med nätstorleken.
(Un)detectable cluster structure in sparse networks
{'venue': 'Phys. Rev. Lett. 101, 078701 (2008)', 'journal': None, 'mag_field_of_study': ['Physics', 'Medicine']}