Att räkna frekvenserna av 3-, 4- och 5-node oriktade motiv (även kända som graflets) används i stor utsträckning för att förstå komplexa nätverk som sociala och biologiska nätverk. Det är dock en stor utmaning att beräkna dessa mätvärden för en stor graf på grund av den intensiva beräkningen. Trots de senaste försöken att räkna trianglar (t.ex. 3-node oriktade motivräkning) har liten uppmärksamhet ägnats åt att utveckla skalbara verktyg som kan användas för att karakterisera 4- och 5-node motiv. I denna uppsats utvecklar vi beräkningseffektiva metoder för att provta och räkna 4- och 5-node oriktade motiv. Våra metoder ger opartiska estimatorer av motivfrekvenser, och vi härleder enkla och exakta formler för varianserna av estimatorerna. Dessutom är våra metoder utformade för att passa vertex centrerade programmeringsmodeller, så att de enkelt kan appliceras på aktuella grafdatasystem som Pregel och GraphLab. Vi utför experiment på en mängd olika riktiga dataset, och experimentella resultat visar att våra metoder är flera storleksordningar snabbare än de senaste metoderna under samma skattningsfel.
Wang m.fl. REF utvecklar en provtagningsmetod för att uppskatta antalet 5-node oriktade motiv.
Moss: A Scalable Tool for Efficiently Sampling and Counting 4- and 5-Node Graphlets
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Computer Science']}