Många metoder har föreslagits för gemenskapsdetektering i nätverk, men de flesta av dem tar inte hänsyn till ytterligare information om de noder som ofta är tillgängliga i praktiken. I detta dokument föreslår vi ett nytt gemensamt detekteringskriterium för gemenskapen som använder både nätkantsinformation och nodfunktioner för att upptäcka samhällsstrukturer. En fördel vår metod har jämfört med befintliga gemensamma detektionsmetoder är flexibiliteten i att lära sig effekterna av olika egenskaper som kan skilja sig åt mellan olika samhällen. En annan fördel är flexibiliteten när det gäller att välja hur stor påverkan funktionsinformationen har på samhällen. Metoden är asymptotiskt konsekvent under blockmodellen med ytterligare antaganden om funktionen distributioner, och fungerar bra på simulerade och verkliga nätverk. Gemenskapens upptäckt är ett grundläggande problem i nätverksanalysen, som i stor utsträckning studerats inom ett antal områden – se (1) och (2) för några exempel på tillämpningar. Ett antal metoder för att upptäcka gemenskaper bygger på probabilistiska modeller för nätverk med samhällen, såsom den stokastiska blockmodellen (3), den gradkorrigerade stokastiska blockmodellen (4) och den latenta faktormodellen (5). Andra metoder fungerar genom att optimera ett kriterium som mäter styrkan i samhällsstrukturen i någon mening, ofta genom spektral approximationer. Exempel är normaliserade snitt (6), modularitet (7, 8) och många varianter av spektralkluster, t.ex. (9). Många av de befintliga metoderna upptäcker samhällen som endast bygger på nätadjakensmatrisen. Vi har dock ofta ytterligare information om noderna (node funktioner), och ibland även kanter, till exempel (10), (11) och (12). I många nätverk är distributionen av nodfunktioner korrelerad med samhällsstrukturen (13), och därför är en naturlig fråga om vi kan förbättra samhällets upptäckt genom att använda nodfunktionerna. Flera generativa modeller för gemensamt modellering av kanterna och funktionerna har föreslagits, däribland modellen för slumpmässiga nätverkseffekter (14), modellen med inbäddade funktioner (15), den latenta variabla modellen (16), den diskriminerande metoden (17), modellen med latent flergruppsdiagram (18), modellen med sociala cirklar för egonätverk (13), samhällena från kantstruktur och nodattribut (CESNA)-modellen (19), modellen med Bayesian Graph Clustering (BAGC) (20) och modellen med aktuella samhällen och personligt intresse (TCPI) (22). De flesta av dessa modeller är utformade för specifika funktionstyper, och deras effektivitet beror i hög grad på att modellspecifikationen är korrekt. Modellfria metoder omfattar viktade kombinationer av nätverket och likheter (23; 24), brytning av attributstrukturer (25), simulerad glödgning av kluster (26) och komprimerat informationsflöde (27). De flesta metoder i denna kategori använder alla funktioner på samma sätt utan att avgöra vilka som påverkar gemenskapsstrukturen och vilka som inte gör det, och saknar flexibilitet i hur man balanserar nätverksinformationen med den information som kommer från dess nodfunktioner, som inte alltid håller med. Inklusive irrelevanta nod funktioner kan bara skada community upptäckt genom att lägga till i buller, medan välja funktioner som själva kluster kraftigt kanske inte motsvarar funktioner som korrelerar med den samhällsstruktur som finns i adjacency matrisen. I detta dokument föreslår vi ett nytt gemensamt detekteringskriterium för gemenskapen som använder både nätverksadjacensmatrisen och nodfunktionerna. Tanken är att genom att korrekt väga kanter enligt funktionen likheter på sina slutnoder, stärker vi gemenskapens struktur i nätverket vilket gör det lättare att upptäcka. I stället för att använda alla tillgängliga funktioner på samma sätt lär vi oss vilka funktioner som är mest användbara för att identifiera samhällsstrukturen från data. Intuitivt söker vår metod en överenskommelse mellan kluster som föreslås av två datakällor, adjacensmatrisen och nodfunktionerna. Numeriska experiment på simulerade och verkliga nätverk visar att vår metod fungerar bra jämfört med metoder som använder antingen Vår metod är utformad för att leta efter olika samhällsstruktur, det vill säga den typ av samhällen där noder är mer benägna att ansluta till varandra om de tillhör samma gemenskap, och därmed finns det fler kanter inom samhällen än mellan. Detta är en mycket vanlig intuitiv definition av samhällen som ingår i många kriterier för att upptäcka samhällen, t.ex. modularitet (8). Vårt mål är att använda ett sådant community detektionskriterium baserat enbart på adjakensmatrisen, och lägga till funktionsbaserade kantvikter för att förbättra detektionen. Det finns flera kriterier enbart för adjacensmatrisen, men att ha ett enkelt kriterium linjärt i adjacensmatrisen gör optimeringen mycket mer möjlig i vår speciella situation, och vi föreslår ett nytt kriterium som visar sig fungera särskilt bra för våra syften. Låt A beteckna adjacencymatrisen med A ij = 0 om det inte finns någon kant mellan noderna i och j, och annars A ij > 0 som kan vara antingen 1 för oviktade nätverk eller kanten vikt för viktade nätverk. Det community detektionskriterium vi börjar från är en mycket enkel analog av modularitet, som ska maximeras över alla möjliga etikettuppdrag e: ( 1.1) Här e är vektorn för nodetiketter, med e i = k om node i tillhör gemenskap k, för k = 1,..., K, E k = {i : e i = k}, och E k  på är antalet noder i gemenskap k. Vi antar att varje nod tillhör exakt en gemenskap, och antalet samhällen K är fast och känd. Omskalning av  och k är utformad för att utesluta triviala lösningar som sätter alla noder i samma gemenskap, och α > 0 är en inställningsparameter. När α = 2, kriteriet är ungefär summan av kanttätheter inom samhällen, och när α = 1, kriteriet är summan av genomsnittliga "inom gemenskapen" grader, som båda intuitivt representerar gemenskapens struktur. Detta kriterium kan visas vara konsekvent enligt den stokastiska blockmodellen genom att kontrollera villkoren för den allmänna teorin i (28). Den idealiska användningen av funktioner med detta kriterium skulle vara att använda dem för att höja kanterna inom samhällen och längs kanterna mellan dem, vilket förbättrar samhällsstrukturen i det observerade nätverket och gör det lättare att upptäcka. Men nodfunktioner kanske inte helt korreleras med samhällsstruktur, olika samhällen kan drivas av olika funktioner, som påpekades av (13), och funktioner själva kan vara bullriga. Därför måste vi lära oss hur olika funktioner påverkar samhällena och balansera själva nätverkets roller och dess funktioner. Låt f i betecknar den p-dimensionella egenskapen vektor av node i. Vi föreslår ett gemensamt community detektionskriterium (JCDC), där α är en inställning parameter som i (1.1), β k R p är den koefficient vektor som definierar inverkan av olika egenskaper på kth gemenskapen, och β := {β 1,. .., β K }...., β K................................................................................... Kriteriet maximeras sedan över både e och β. Med en annan β k för varje k kan vi lära oss de roller olika funktioner kan spela i olika samhällen. Balansen mellan informationen från A och F:= {f 1,. .., f n } kontrolleras av w n, en annan inställning parameter som i allmänhet kan bero på n. För enkelhetens skull, vi modellerar kanten vikt W (f i, f j, β k ; w n ) som en funktion av noden funktioner f i och f j via en p-dimensionell vektor av deras likhet åtgärder ij =  ska (f i, f j ). Valet av likhetsåtgärder i  ska bero på vilken typ av f i (t.ex. om egenskaperna är numeriska eller kategoriska) och bestäms från fall till fall; den enda viktiga egenskapen är att  ska tilldela högre värden till funktioner som är mer likartade. Observera att detta trivialt tillåter införandet av egg funktioner samt nod funktioner, så länge de omvandlas till någon form av likhet. För att eliminera potentiella skillnader i enheter och skalor, standardiserar vi alla ij längs varje funktionsdimension. Slutligen, funktionen W bör öka 2 i ij, β, som kan ses som "total likhet" mellan noder, och för optimeringsändamål är det bekvämt att ta W att vara konkava. Här använder vi den exponentiella funktionen, Man kan använda andra funktioner av liknande former, till exempel logit exponentiella funktionen, som vi fann empiriskt att utföra på liknande sätt. Kriteriet för gemensam detektering av samhället måste optimeras över både samhällsuppdragen e och funktionsparametrarna β. Med hjälp av blockkoordinater optimerar vi JCDC genom att växelvis optimera över etiketterna med fasta parametrar och över parametrarna med fasta etiketter, och itererar tills konvergens. När parametrarna β är fasta kan alla kantvikter w ijk's behandlas som kända konstanter. Det är omöjligt att söka över alla n K möjliga etikettuppdrag, och som många andra community detektionsmetoder, förlitar vi oss på en girig etikett byta algoritm för att optimera över e, specifikt, tabu sökningen (29), som uppdaterar etiketten på en nod i taget. Eftersom vårt kriterium innebär antalet noder i varje gemenskap  på E k  på, inga enkla spektral approximationer finns tillgängliga. Lyckligtvis tillåter vår metod en enkel lokal ungefärlig uppdatering som inte kräver omräkning av hela kriteriet. För en given nod i övervägd för etikettbyte, kommer algoritmen tilldela det till gemenskap k snarare än l om där S kk är dubbelt så stor som den totala eggvikten i gemenskap k, och S iùk är summan av eggvikter mellan nod i och alla noder i E k. När  till E k  och  på E l är stora, kan vi ignorera +1 i nämnaren, och (2.1) blir 2) som möjliggör en "lokal" uppdatering för etiketten nod i utan att beräkna hela kriteriet. Detta belyser också effekten av stämparametern α: när α = 1, kan de två sidorna av (2.2) betraktas som genomsnittliga vikter för alla kanter som förbinder nod i med samhällen E k respektive E l. Sedan tilldelar vår metod node i till det samhälle som den har starkast kontakt med. När α = 1, den vänstra sidan av (2.2) multipliceras med en faktor (t.ex. Antag att "E k" är större än "E l"; att sedan välja 0 < α < 1 anger en preferens för att tilldela en nod till den större gemenskapen, medan α > 1 gynnar mindre samhällen. En detaljerad numerisk undersökning av α:s roll finns i det kompletterande materialet. De kantvikter som ingår i (2.2) beror på stämparametern w n. När β = 0 är alla vikter lika med w n − 1. Å andra sidan w ijk ≤ w n för alla värden av β. Därför är w n /(w n − 1) den maximala mängd med vilken vår metod kan omväga en kant. När w n är stor, w n /(w n − 1)  till 1, och därmed informationen från nätverkets struktur dominerar. När w n är nära 1 är förhållandet stort och de funktionsdrivna eggvikterna har stort genomslag. Se Kompletterande Material för mer information om valet av w n. Medan stämparametern w n kontrollerar mängden påverkan funktioner kan ha på gemenskap upptäckt, det påverkar inte de uppskattade parametrarna β för en fast gemenskap uppdrag. Detta är lätt att se från omgruppering termer i (1.2): där funktionen g inte beror på w n. Observera att termen som innehåller w n inte beror på β.  Eftersom vi valde en konkava kantvikt funktion (1.3), för en given gemenskap uppdrag e gemensamma kriteriet är en konkava funktion av β k, och det är enkelt att optimera över β k av lutning stigning. β k:s roll är att kontrollera inverkan av olika funktioner på varje gemenskap. Man kan visa genom en Taylor-serie typ expansion runt den maximala (detaljer utelämnas) och även observera empiriskt att för vår metod, de uppskattade β k's korreleras med funktionen likheter mellan noder i gemenskap k. Med andra ord, vår metod tenderar att producera en stor uppskattad β ( ) k för en funktion med höga likhetsvärden ∂ ( ) ij's för i, j  på E k. Men i det extrema fallet, den optimala β ( ) k kan vara +∞ om alla ∂ ( ) ij's är positiva i samhället k eller −∞ om alla ∂ ( ) ij's är negativa (återkalla att likheter är standardiserade, så detta kan inte hända i alla samhällen). För att undvika dessa extrema lösningar subtraherar vi en straffterm λ β 1 från kriteriet (1.2) samtidigt som vi optimerar över β. Vi använder ett mycket litet värde av λ (λ = 10 −5 överallt i papperet) som skyddar mot numeriskt instabila lösningar men har mycket liten effekt på andra uppskattade koefficienter. Det föreslagna JCDC-kriteriet (1.2) är inte modellbaserat, utan enligt vissa modeller är det asymptotiskt konsekvent. Vi överväger inställningen där nätverket A och funktionerna F genereras oberoende av en stokastisk blockmodell respektive en jämnt avgränsad distribution. Låt P(A ij = 1) = ρ n P cicj där ρ n är en faktor som styr den totala kanten densitet och c = (c 1,. .., c n ) är vektorn för sanna etiketter. Anta följande regelbundenhet villkor hålla: 1. Det finns globala konstanter M- och M-β, sådana att ij 2 ≤ M- och β k 2 ≤ M-β för alla k, och inställningsparametern w n uppfyller log w n > M-M-β. Villkor 1 anger att knutpunktens likheter är jämnt avgränsade. Detta är ett milt tillstånd i många applikationer eftersom nodfunktionerna ofta själva är jämnt avgränsade. I praktiken, för numerisk stabilitet kan användaren vill standardisera nod funktioner och kassera enskilda funktioner med mycket låg varians, innan man beräknar motsvarande likheter. Villkor 2 garanterar att samhällen inte försvinner asymptotiskt. Villkor 3 tvingar fram diverseitet. Eftersom de uppskattade etiketterna e är endast definierade upp till en godtycklig permutation av samhällen, mäter vi avtalet betwee e och c genom d(e, c) = min σ till P K 1 n n i=1 1 / 6 (e i ) = c i ), där P K är uppsättningen av alla permutationer av {1,..., K}. Teoret 1 (Sammanhängighet för JCDC). Under förhållanden 1, 2 och 3, om nρ n → ∞, w n ρ n → ∞, och parametern α uppfyller då har vi, för varje fast δ > 0, Beviset ges i det kompletterande materialet. Vi jämför JCDC med tre representativa referensmetoder som använder både adjakens matris och noden funktioner: CASC (Covariate Assisted Spectral Clustering, (24)), CESNA (Kommunities from Edge 4 Structure and Node Attribut, (19))) och BAGC (BAyesian Graph Clustering, (20) ). Dessutom inkluderar vi också två standardmetoder som använder antingen nätverket adjacency ensam (SC, spektral klustering på Laplacian legaliserade med en liten konstant τ = 1e - 7, som i (21)), eller nod funktioner ensam (KM, Kmeans utförs på p-dimensionell nod funktion vektorer, med 10 slumpmässiga initiala utgångsvärden). Vi skapar nätverk med n = 150 noder och K = 2 samhällen i storlek 100 och 50 från den gradkorrigerade stokastiska blockmodellen enligt följande. Kanterna genereras oberoende med sannolikhet i j p om noder i och j är i samma gemenskap, och r på j p om noder i och j är i olika samhällen. Vi sätter p = 0,1 och varierar r från 0,25 till 0,75. Vi ställer in 5% av noderna i varje gemenskap till att vara "hub" noder med gradkorrigeringsparametern i = 10, och för de återstående noderna som är inställda i = 1. Alla resulterande produkter har en tröskel på 0,99 för att säkerställa att det inte finns några sannolikhetsvärden över 1. Dessa inställningar resulterar i den genomsnittliga förväntade nodgraden från 22 till 29. För varje nod i genererar vi p = 2 funktioner, med en "signal" funktion relaterad till gemenskapens struktur och en "buller" funktion vars fördelning är densamma för alla noder. Den "signal" funktionen följer fördelningen N (μ, 1) för noder i gemenskap 1 och N (−μ, 1) för noder i gemenskap 2, med μ varierar från 0,5 till 2 (större μ motsvarar starkare signal). För användning med CESNA, som bara tillåter kategoriska nodfunktioner, diskretiserar vi de kontinuerliga nodfunktionerna genom att partitionera den verkliga linjen till 20 bins med hjälp av 0,05, 0,1,..., 0,95-th quantiles. För JCDC, baserat på studien av inställningsparametrarna i det kompletterande materialet, använder vi α = 1 och jämför två värden av w n, w n = 1,5 och w n = 5. Slutligen mäts överenskommelsen mellan de uppskattade samhällena och de verkliga gemenskapsmärkena genom normaliserad ömsesidig information, en åtgärd som vanligen används i nätverkslitteraturen och som sträcker sig mellan 0 (slumpmässig gissning) och 1 (perfekt överenskommelse). För varje konfiguration upprepar vi experimenten 30 gånger och registrerar den genomsnittliga NMI över 30 replikeringar. Figur 1 visar värmekartorna för genomsnittlig NMI för alla metoder under dessa inställningar, som en funktion av r och μ. Som man kan förvänta sig påverkas prestandan för spektral klustring (c), som endast använder nätverksinformationen, endast av r (den större r är, desto svårare problemet), och prestandan för K-medel (d), som endast använder funktionerna, påverkas bara av μ (den större μ är, desto lättare problemet). JCDC kan dra nytta av både nätverks- och funktionsinformation genom att uppskatta koefficienterna β från data, och dess prestanda försämras endast när ingen av dem är informativ. De informativa funktionerna är mer användbara med ett större värde av w (a), och omvänt oinformativa funktioner påverkar perfomance något mer med ett lägre värde av w (b), men denna effekt är inte stark. CASC (e) verkar ärva den skarpa fasövergången från spektral klustring, som utgör grunden för CASC; den skarpa övergången beror kanske på olika samhällsstorlekar och navnoder, som båda är utmanande för spektral klustring; CESNA (f) och BAGC (g) inte presterar lika bra totalt, med BAGC ofta kluster alla nav noder i en gemenskap. Denna förordning träder i kraft den tjugonde dagen efter det att den har offentliggjorts i Europeiska unionens officiella tidning.
Till exempel föreslår Ref gemensamma kriterier för detektering av gemenskapen, som kan ses som en ändring av modularitetspoäng för nätverk med attribut.
Community Detection in Networks with Node Features
{'venue': 'Electronic Journal of Statistics, Volume 10, Number 2 (2016), 3153-3178', 'journal': None, 'mag_field_of_study': ['Mathematics', 'Computer Science', 'Physics']}