Vi studerar problemet med grafpartitionering, eller klusterbildning, i glesa nätverk med tidigare information om kluster. Specifikt, vi antar att för en bråkdel ρ av noderna de verkliga kluster uppdrag är kända i förväg. Detta kan förstås som en halvövervakad version av klusterbildning, i motsats till oövervakad klusterbildning där den enda tillgängliga informationen är grafstrukturen. I det oövervakade fallet är det känt att det finns en tröskel för den inter-cluster-anslutning över vilken kluster inte kan upptäckas. Här studerar vi effekten av tidigare information om detektionströskeln och visar att även minimala [men generiska] värden på ρ > 0 förskjuter tröskeln nedåt till dess lägsta möjliga värde. För viktade grafer visar vi att en liten semi-övervakning kan användas för en icke-trivial definition av samhällen. Diagramdelning är ett viktigt problem med ett brett spektrum av tillämpningar inom kretsdesign, samhällsvetenskap, datautvinning m.m. I samband med analys av sociala nätverk är detta problem mer känt som community detection, där gemenskapen löst definieras som en grupp av noder så att länktätheten inom gruppen är högre än mellan olika grupper. Många verkliga nätverk har en välhanterlig samhällsstruktur [1], och mycket ny forskning har fokuserat på att utveckla metoder för att upptäcka i samhället (se [2] för en översyn). Ett gemensamt kännetecken för många av dessa metoder är förekomsten av en tröskel i samverkan mellan samhällen bortom vilken samhällen inte kan upptäckas [3, 4]. Detta problem har studerats genom att formulera gemenskapsdetektionen som en minimering av en viss Potts-Ising Hamiltonian [4, 5]. Det har visat sig att grafen partitionering problemet verkligen kännetecknas av en fas övergång från detekterbara till odetekterbara system som man ökar kopplingen styrka mellan kluster [4]. De flesta arbeten hittills har betraktat oövervakad version av klusterbildning, där den enda tillgängliga informationen är grafstrukturen. I många situationer kan man dock ha ytterligare information om eventuella klustertilldelningar av vissa noder. Denna version av problemet har väckt intresse för maskininlärning gemenskapen, i samband med grafbaserade halvövervakade lärande och klassificering (se [6] för en nyligen genomförd undersökning). I denna inställning, antar man att förutom grafstrukturen, har man också viss tidigare information om kluster-medlemskap av en uppsättning noder [7, 8]. Vårt syfte är att presentera en teoretisk analys av den halvövervakade versionen av gemenskapens detekteringsproblem för enkla, bi-community nätverk, och att avslöja nya scenarier för detektering av samhället underlättas av semi-övervakning. Förlaga. Betrakta en Erdös-Rényi graf: varje par av noder är kopplad med sannolikhet α/N, där N är antalet noder i graferna. Varje länk ges en vikt J > 0. Föreställ dig nu ett par av en sådan identisk Erdös-Rényi graf, som modellerar två kluster (kommuner). Förutom intra-cluster J-länkar är varje nod i en graf kopplad med sannolikhet γ/N med noder i den andra grafen. Var och en av dessa inter-cluster länkar ges en vikt K > 0. För tydlighetens skull antas både J och K vara heltalsnummer. Denna planterade bisektionsgraf modell kommer att användas för att studera prestandan hos kluster detektionsmetoden, som placerar en Ising spinn på varje nod och låter dessa spins interagera via nätverkslänkarna [4, 5] : där vi har gjort bi-cluster typ av nätverket explicit genom att införa separata spin variabler s i = ±1 ochs i = ±1 (i = 1,..., N) för två kluster. Här J ij och J ij är identiska och självständigt fördelade slumpvariabler som antar noll med sannolikhet 1 − α N och J > 0 med sannolikhet α N. Likaså, K ij identiska och oberoende är lika med noll med sannolikhet 1 − γ N och till K > 0 med sannolikhet γ N. För att genomdriva equipment, Hamiltonian (1) kommer att studeras under begränsningen Således, att upptäcka tecknet på en given spin s i vid noll temperatur (så att utesluta alla termiska fluktuationer) kan vi dra slutsatsen vilken kluster motsvarande nod hör: alla spins som har lika tecken tillhör samma kluster. Felsannolikheten p e för klustertilldelningen är där m är (enkel-kluster) magnetisering,. .. T =0 är nolltemperatur Gibbs-medelvärdet, d.v.s. Genomsnittet för alla konfigurationer av snurrar som i termodynamiskt begränsar den minimala energi som ges av (1, 2), och där [. ..] av är genomsnittet över bi-grafstrukturen, dvs. över {J ij}, {J ij} och {K ij}. Som antyds av själv-genomsnitt funktionen, i stället för att ta [. ..] av, Vi kan utvärdera s i T =0 på den mest sannolika bi-graf struktur(er).
Allahverdyan m.fl. REF studerade problemet med halvövervakad grafklustring genom att integrera kända klusteruppdrag för en bråkdel av noderna.
Community Detection with and without Prior Information
{'venue': 'Europhysics Letters 90, p.18002, 2010', 'journal': None, 'mag_field_of_study': ['Computer Science', 'Physics', 'Biology']}