I detta papper studerar vi problemet med lokal triangel räkna i stora grafer. Nämligen, med tanke på en stor graf G = (V, E) vi vill uppskatta så exakt som möjligt antalet trianglar incident till varje nod v V i grafen. Problemet med att beräkna det globala antalet trianglar i en graf har övervägts tidigare, men enligt vår kunskap är detta det första papperet som tar upp problemet med lokal triangelräkning med fokus på effektivitetsfrågor som uppstår i massiva grafer. Fördelningen av det lokala antalet trianglar och den relaterade lokala klusterkoefficienten kan användas i många intressanta tillämpningar. Vi visar till exempel att de åtgärder vi beräknar kan bidra till att upptäcka förekomsten av skräppostaktivitet i storskaliga webbgrafer, samt tillhandahålla användbara funktioner för att bedöma innehållskvalitet i sociala nätverk. För att beräkna det lokala antalet trianglar föreslår vi två approximation algoritmer, som bygger på idén om min-wise oberoende permutationer ). Våra algoritmer fungerar på ett semi-streaming-sätt, med hjälp av O( och V) utrymme i huvudminnet och utföra O(log  och V) sekventiella skanningar över kanterna på grafen. Den första algoritmen som vi beskriver i det här dokumentet använder också O-utrymme i externt minne under beräkning, medan den andra algoritmen endast använder huvudminne. Vi presenterar såväl den teoretiska analysen som experimentella resultat i massiva grafer som visar den praktiska effektiviteten i vårt tillvägagångssätt.
Becchetti m.fl. REF löser det svårare problemet med att uppskatta antalet trianglar incident på varje nod.
Efficient semi-streaming algorithms for local triangle counting in massive graphs
{'venue': 'KDD', 'journal': None, 'mag_field_of_study': ['Computer Science']}