Problemet med att hitta lokalt täta komponenter i en graf är en viktig primitiv i dataanalys, med omfattande tillämpningar från community mining till spam upptäckt och upptäckt av biologiska nätverksmoduler. I detta papper presenterar vi nya algoritmer för att hitta den tätaste subgrafen i den strömmande modellen. För alla > 0, våra algoritmer gör O(log 1+ n) passerar över inmatningen och hitta en subgraf vars densitet är garanterad att vara inom en faktor 2 (1 + ) av den optimala. Våra algoritmer är också lätt att parallellisera och vi illustrerar detta genom att förverkliga dem i MapReduce-modellen. Dessutom utför vi omfattande experimentell utvärdering av massiva verkliga grafer som visar prestanda och skalbarhet för våra algoritmer i praktiken.
Denna algoritm förbättrades av Bahmani et al. REF, som leder till en faktor 2 (1+ε) av den optimala i en MapReduce ram.
Densest Subgraph in Streaming and MapReduce
{'venue': 'PVLDB', 'journal': 'PVLDB', 'mag_field_of_study': ['Computer Science']}