I en graf, en gemenskap kan löst definieras som en grupp av noder som är närmare kopplade till varandra än till resten av grafen. Även om det finns en mängd olika mått som kan användas för att ange kvaliteten på en viss gemenskap, är ett vanligt tema att flöden tenderar att stanna inom samhällen. Vi förväntar oss därför att cyklerna ska spela en viktig roll för att upptäcka människor i samhället. För oriktade grafer har betydelsen av trianglar - en oriktad 3-cykel - varit känd under en lång tid och kan användas för att förbättra samhällets upptäckt. I riktade grafer är situationen mer nyanserad. Den minsta cykeln är helt enkelt två noder med en ömsesidig anslutning, och med hjälp av information om återvändo har visat sig förbättra samhällets upptäckt. Vår nya idé är baserad på de fyra typer av riktade trianglar som innehåller cykler. För att identifiera samhällen i riktade nätverk föreslår vi därför ett oriktat system för kantviktning baserat på vilken typ av riktade trianglar som kanterna är inblandade i. Vi föreslår också ett nytt mått på kvaliteten på de samhällen som bygger på antalet 3-cykler som är uppdelade mellan olika samhällen. För att visa effekten av vår nya viktning, använder vi standard METIS diagram partitionering verktyg för att bestämma samhällen och visa experimentellt att de resulterande samhällen resulterar i färre 3-cykler skärs. Omfattningen av effekten varierar mellan en minskning på 10 och 50 procent, och vi finner också bevis för att detta viktningssystem förbättrar en uppgift där man känner till rimliga grundsanningar. Nyckelord: community detektering, riktade nätverk, trianglar, ömsesidighet, 3-cykler Många olika system kan ses som komplexa nätverk som består av objekt (nodes) och anslutningar mellan dem (länkar eller kanter). Under de senaste årtiondena har studien av sådana nätverk blivit viktig inom många discipliner [5, 6, 9, 23], och ett återkommande forskningstema är att hitta samhällen eller moduler inom dessa nätverk. Dessa samhällen avslöjar viktiga strukturer som är dolda i nätverksdata. Hittills har merparten av arbetet med att upptäcka människor i samhället fokuserat på oriktade nätverk (se undersökningen [10]), men på senare tid har mer forskning fokuserat på riktade nätverk (se undersökningen [20] ). I den vanligaste inställningen, en gemenskap är en grupp av noder som är närmare kopplade till varandra än till resten av nätverket. Metoder för gemenskapstilldelning använder endast nätets topologiska egenskaper om man inte känner till ytterligare information om nätverkets komponenter, och därför används ofta anslutning mellan noderna ensamma för att fastställa mått som mäter de tilldelade gruppernas "kvalitet". Gemensamma kvalitetsmått mäter (i) densiteten av länkar inom en grupp (modulitet) [21], (ii) antalet skärkanter i förhållande till gruppens storlek (ledning), (iii) den stationära fördelningen av en slumpmässig gång inom nätverket (LinkRank) [17], (iv) och sannolikheten för en (riktad) länk mellan två noder [33]. De flesta av dessa kvalitetsåtgärder har naturliga utvidgningar till vägda nätverk, i vilket fall uttryck som "antal kanter" ersätts med "total kantvikt" istället. I vårt papper föreslår vi ett enkelt viktningsschema som omvandlar en riktad graf till en viktad oriktad graf. Denna modell gör det möjligt för oss att utnyttja rikedomen och komplexiteten hos befintliga metoder för att hitta samhällen i oriktade grafer. I synnerhet har olika system utvecklats för att optimera dessa fyra typer av konnektivitetsmått, se bland annat [4, 12, 13, 22, 24, 32]. Vårt särskilda viktningssystem bygger på att utvidga tanken att information inom "goda" samhällen kan delas inom en gemenskap lättare än mellan samhällen. Eftersom information kan flöda längs kanter, kan korta (direkta) vägar och (direkta) cykler ses som viktiga i funktionen av samhällen inom nätverk. Till exempel, en kort väg mellan två noder indikerar att information kan resa mellan dem snabbt-eller kan resa snabbt
Till exempel Klymko et al. REF tillämpar trianglar information för att upptäcka gemenskap i riktade nätverk.
Using Triangles to Improve Community Detection in Directed Networks
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Computer Science', 'Physics']}