Vi tar itu med problemet med att räkna antalet q k av k- cliques i storskaliga grafer, för alla konstant k ≥ 3. Clique counting är viktigt i en mängd olika tillämpningar, inklusive sociala nätverksanalys. Våra algoritmer gör det möjligt att beräkna q k för flera verkliga grafer och sprida ljus över dess tillväxthastighet som en funktion av k. Även för små värden av k, kan antalet q k av k-kluster vara i storleksordningen tiotals eller hundratals biljoner. Som k ökar, olika graf instanser visar olika beteenden: medan på vissa grafer q k+1 < q k, på andra riktmärken q k+1 q k, upp till två storleksordningar i våra observationer. Diagram med stark klicktillväxt är särskilt svåra exempel i praktiken. På grund av kliqueräkningsproblemets beräkningsintensiva natur nöjer vi oss med parallella lösningar inom ramen för MapReduce, som under de senaste åren har blivit en de facto-standard för batchbearbetning av massiva datamängder. Vi ger både teoretiska och experimentella bidrag. På teorisidan designar vi den första exakta skalbara algoritmen för att räkna (och lista) k-kluster i MapReduce. Vår algoritm använder O(m 3/2 ) totalt utrymme och O(m k/2 ) arbete, där m är antalet grafkanter. Detta matchar de mest kända gränserna för triangellistning när k = 3 och fungerar optimalt i värsta fall för alla k, samtidigt som kommunikationskostnaden är oberoende av k. Vi utformar också provtagningsbaserade estimatorer som dramatiskt kan minska drifttiden och utrymmeskraven för den exakta metoden, samtidigt som vi tillhandahåller mycket noggranna lösningar med hög sannolikhet. Vi bedömer därefter effektiviteten av olika klickräkningsmetoder genom en omfattande experimentell analys över Amazon EC2-plattformen, med beaktande av både våra algoritmer och deras toppmoderna konkurrenter. De experimentella resultaten belyser tydligt algoritmen för valet i olika scenarier och visar att vårt exakta tillvägagångssätt är det mest effektiva när antalet k-kluster är stort, graciöst skalning till icke-triviala värden av k även på kluster av liten/medelstor storlek. Våra approximationsalgoritmer uppnår extremt exakta uppskattningar och stora uppfarter, särskilt på de tuffaste instanserna för de exakta algoritmerna.
En algoritm för att beräkna den exakta räkningen av k-kluster har utvecklats i REF för MapReduce-ramverket.
Clique Counting in MapReduce: Algorithms and Experiments
{'venue': 'JEAL', 'journal': None, 'mag_field_of_study': ['Computer Science', 'Mathematics']}