Att räkna frekvensen av små subgrafer är en grundläggande teknik i nätverksanalyser inom olika områden, särskilt inom bioinformatik och sociala nätverk. Det speciella fallet med triangelräkning har fått mycket uppmärksamhet. Att få resultat för 4-vertex eller 5-vertex mönster är mycket utmanande, och det finns få praktiska resultat kända som kan skala till massiva storlekar. Vi introducerar ett algoritmiskt ramverk som kan användas för att räkna alla små mönster i en graf och tillämpa detta ramverk för att beräkna exakta värden för alla 5-vertex subgraphs. Vårt ramverk är byggt på att skära ett mönster i mindre, och med hjälp av antalet mindre mönster för att få större antal. Dessutom utnyttjar vi gradorienteringar i grafen för att minska körtiden ännu mer. Dessa metoder undviker den kombinatoriska explosion som typiska subgraph räkna algoritmer ansikte. Vi bevisar att det räcker att räkna bara fyra specifika subgrafer (tre av dem har mindre än 5 hörn) för att exakt räkna alla 5-vertex mönster. Vi utför omfattande empiriska experiment på en mängd olika verkliga grafer. Vi kan beräkna antalet grafer med tiotals miljoner kanter på några minuter på en varumaskin. Såvitt vi vet är detta den första praktiska algoritmen för att räkna 5-vertex mönster som körs på denna skala. En språngbräda till vår huvudalgoritm är en snabb metod för att räkna alla 4-vertex mönster. Denna algoritm är typiskt tio gånger snabbare än den toppmoderna 4-vertex räknare.
Pinar-SeshadhriVishal utformade ESCAPE-algoritmen för praktisk (totalt) 5-vertex subgraph counting REF.
ESCAPE: Efficiently Counting All 5-Vertex Subgraphs
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Computer Science']}