Maximal klickräkning är ett grundläggande problem i grafteorin och har viktiga tillämpningar inom många områden såsom social nätverksanalys och bioinformatik. Problemet studeras ingående, men de bästa befintliga algoritmerna kräver minne utrymme linjär i storleken på inmatningskurvan. Detta har blivit en allvarlig oro med tanke på den massiva volymen av dagens snabbt växande nät. Vi föreslår en allmän ram för att utforma externa-minnesalgoritmer för maximal klickräkning i stora grafer. Den allmänna ramen gör det möjligt att bearbeta maximal clique-räkning rekursivt i små subgrafer av indatagrafen, vilket möjliggör in-minne beräkning av maximal cliques utan den kostsamma slumpmässiga diskåtkomst. Vi bevisar att den uppsättning kliquer som erhålls genom rekursiv lokal beräkning är både korrekt (dvs globalt maximal) och komplett. Den del som ska behandlas varje gång definieras utifrån en uppsättning basvertikaler som kan väljas flexibelt för att uppnå olika syften. Vi diskuterar valet av bas hörn för att fullt ut utnyttja det tillgängliga minnet för att minimera I / O kostnad i statiska grafer, och för uppdatering underhåll i dynamiska grafer. Vi tillämpar också vårt ramverk för att designa en extern-minnesalgoritm för maximal klickberäkning i en stor graf.
Externa minnesalgoritmer för maximal klickräkning har beaktats i REF.
Finding maximal cliques in massive networks
{'venue': 'TODS', 'journal': None, 'mag_field_of_study': ['Computer Science']}