Abstrakt. Antalet trianglar är en beräknings dyrt grafstatistik som ofta används i komplexa nätverksanalyser (t.ex. transitivitetsförhållande), i olika slumpmässiga grafmodeller (t.ex. exponentiell slumpmässig grafmodell) och i viktiga tillämpningar i verkligheten såsom skräppostdetektering, avslöjande av den dolda tematiska strukturen på webben och länkrekommendation. Räkna trianglar i grafer med miljoner och miljarder kanter kräver algoritmer som körs snabbt, använda liten mängd utrymme, ge exakta uppskattningar av antalet trianglar och helst är parallelliserbara. I detta dokument presenterar vi en effektiv triangelräkningsalgoritm som kan anpassas till semistreamingmodellen [15]. Nyckelidén med vår algoritm är att kombinera provtagningsalgoritmen på [34, 35] och partitioneringen av uppsättningen hörn i en hög grad och en låg grad delmängd respektive som i [2], behandla varje uppsättning på lämpligt sätt. Vi får en körtid och en approximation (multiplikativ fel), där n är antalet hörn, m antalet kanter och  på det maximala antalet trianglar en kant finns. Dessutom visar vi hur denna algoritm kan anpassas till semistreamingmodellen med utrymmesanvändning O m 1/2 log n + m 3/2  på log n t på 2 och ett konstant antal pass (tre) över grafströmmen. Vi tillämpar våra metoder i olika nätverk med flera miljoner kanter och vi får utmärkta resultat. Slutligen föreslår vi en slumpmässig projektion baserad metod för triangelräkning och ger ett tillräckligt villkor för att få en uppskattning med låg varians.
En annan klassificering av triangelräkning är om en algoritm räknar ett exakt antal trianglar eller gör en approximation (t.ex. REF ).
Efficient Triangle Counting in Large Graphs via Degree-based Vertex Partitioning
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Computer Science', 'Mathematics', 'Physics']}