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 mönster är mycket utmanande, och det finns få praktiska resultat kända som kan skala till massiva storlekar. Ja, även en högstämd uppräkningskod tar mer än en dag på en graf med miljontals kanter. De flesta tidigare arbeten som körs för verkligt massiva grafer använder kluster och massiv parallellisering. Vi tillhandahåller en samplingsalgoritm som på ett tydligt och korrekt sätt approximerar frekvenserna för alla 4-vertex mönsters subgrafer. Vår algoritm är baserad på en ny teknik för 3-gångsprovtagning och ett speciellt beskärningsschema för att minska variansen i uppskattningar. Vi tillhandahåller teoretiska bevis för riktigheten av vår algoritm, och ger formella gränser för fel och förtroende för våra uppskattningar. Vi utför en detaljerad empirisk studie och visar att vår algoritm ger uppskattningar inom 1% relativ fel för alla submönster (över en stor klass av test grafer), samtidigt som order av magnitud snabbare än uppräkning och andra provtagning baserade algoritmer. Vår algoritm tar mindre än en minut (på en enda varumaskin) för att bearbeta ett socialt Orkut-nätverk med 300 miljoner kanter.
I REF, Jha et al. föreslog en algoritm som effektivt och effektivt approximerar frekvenserna för alla 4-vertex subgrafer genom provtagningsvägar av längd tre.
Path Sampling: A Fast and Provable Method for Estimating 4-Vertex Subgraph Counts
{'venue': "WWW '15", 'journal': None, 'mag_field_of_study': ['Mathematics', 'Computer Science']}