Vi presenterar två utrymme avgränsade slumpmässiga provtagning algoritmer som beräknar en approximation av antalet trianglar i en oriktad graf ges som en ström av kanter. Vår första algoritm gör inga antaganden om kanterna i strömmen. Den använder utrymme som är omvänt relaterat till förhållandet mellan antalet trianglar och antalet tripletter med minst en kant i den inducerade subgrafen, och konstant förväntad uppdateringstid per kant. Vår andra algoritm är utformad för incidensströmmar (alla kanter incident till samma vertex visas i följd). Den använder utrymme som är omvänt relaterat till förhållandet mellan antalet trianglar och längd 2 banor i grafen och förväntad uppdateringstid O(log  och V) · (1 + s ·..v)), där s är utrymmeskravet för algoritmen. Dessa resultat förbättras betydligt jämfört med tidigare arbete [20, 8]. Eftersom utrymmets komplexitet endast beror på strukturen av inmatningsgrafen och inte på antalet noder, våra algoritmer skala mycket väl med ökande grafstorlek och så de ger ett grundläggande verktyg för att analysera strukturen av stora grafer. De har många tillämpningar, till exempel i upptäckten av webbgemenskaper, computa- * Detta arbete stöddes delvis av EU inom det sjätte ramprogrammet under kontrakt 001907 "Dynamiskt utvecklande, stora skalan informationssystem" (DELIS) * En del av detta arbete gjordes medan författaren var post-doc på Universitá degli Studi di Roma "La Sapienza" † En del av detta arbete gjordes medan författaren besökte tillstånd att göra digitala eller hårda kopior av hela eller en del av detta arbete för personligt eller klassrum användning beviljas utan avgift, förutsatt att kopior inte görs eller distribueras för vinst eller kommersiella fördelar och att kopior bär detta meddelande och den fullständiga citeringen på första sidan. För att kopiera på annat sätt, för att återpublicera, för att posta på servrar eller för att omfördela till listor, krävs tidigare specifik behörighet och/eller avgift. Utveckling av kluster och transitivitetskoefficient och upptäckt av frekventa mönster i stora grafer. Vi har implementerat både algoritmer och utvärderat deras prestanda på nätverk från olika applikationsområden. Storleken på de berörda graferna varierade från cirka 8, 000 noder och 40, 000 kanter till 135 miljoner noder och mer än 1 miljard kanter. För båda algoritmerna utför vi experiment med parameter s = 1, 000, 10, 000, 100, 000, 1, 000, 000 för att utvärdera körtid och approximationsgaranti. Båda algoritmerna verkar vara tidseffektiva för dessa provstorlekar. Den första algoritmens approximativa kvalitet varierade avsevärt och även för s = 1 000 000 hade vi mer än 10 procents avvikelse för mer än hälften av fallen. Den andra algoritmen utfördes mycket bättre och även för s = 10 000 hade vi en genomsnittlig avvikelse på mindre än 6% (tog över alla utom det största fall där vi inte kunde beräkna antalet trianglar exakt).
Senare, Buriol et al. REF förbättrar utrymmets komplexitet och per-edge-tid O(s)(sε, ε)mn/τ(G)).
Counting triangles in data streams
{'venue': "PODS '06", 'journal': None, 'mag_field_of_study': ['Mathematics', 'Computer Science']}