Skip to main content
Erschienen in: Data Mining and Knowledge Discovery 5/2019

19.04.2019

FURL: Fixed-memory and uncertainty reducing local triangle counting for multigraph streams

verfasst von: Minsoo Jung, Yongsub Lim, Sunmin Lee, U. Kang

Erschienen in: Data Mining and Knowledge Discovery | Ausgabe 5/2019

Einloggen

Aktivieren Sie unsere intelligente Suche um passende Fachinhalte oder Patente zu finden.

search-config
loading …

Abstract

Given a multigraph stream (e.g., Facebook messages or network traffic) where duplicate edges arrive continuously, how can we accurately and memory-efficiently estimate local triangles for all nodes? Local triangle counting in a graph stream is one of the fundamental tasks in graph mining with important applications including anomaly detection, social role identification, community detection, etc. Many recent graph streams include duplicate edges, hence form multigraph streams: e.g., many network packets might have a same (source, destination) pair. Although there have been several local triangle counting methods for multigraph streams, they have problems in terms of accuracy and memory efficiency; furthermore, most methods support either binary or weighted counting, and thus cannot find anomalies whose detection requires both types of counting. In this paper, we propose FURL, a memory-efficient and accurate local triangle counting method for multigraph streams. FURL has two main advantages. First, FURL improves accuracy by (1) reducing the variance of its estimation via a regularization strategy, and (2) sampling more triangles than the state-of-the-art methods do, by using its memory space efficiently. Second, FURL finds anomalies which state-of-the-art methods cannot discover. Experimental results show that FURL outperforms state-of-the-art methods in terms of accuracy and memory efficiency. Thanks to FURL, we discover interesting anomalies from a Bitcoin network.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

Anhänge
Nur mit Berechtigung zugänglich
Literatur
Zurück zum Zitat Chou B, Suzuki E (2010) Discovering community-oriented roles of nodes in a social network. In: 12th international conference data warehousing and knowledge discovery (DAWAK), pp 52–64 Chou B, Suzuki E (2010) Discovering community-oriented roles of nodes in a social network. In: 12th international conference data warehousing and knowledge discovery (DAWAK), pp 52–64
Zurück zum Zitat Feller W (1968) An introduction to probability theory and its applications, vol 1. Wiley, LondonMATH Feller W (1968) An introduction to probability theory and its applications, vol 1. Wiley, LondonMATH
Zurück zum Zitat Jha M, Pinar A, Seshadhri C (2015) Counting triangles in real-world graph streams: dealing with repeated edges and time windows. In: 49th Asilomar conference on signals, systems, and computers (ACSSC), pp 1507–1514 Jha M, Pinar A, Seshadhri C (2015) Counting triangles in real-world graph streams: dealing with repeated edges and time windows. In: 49th Asilomar conference on signals, systems, and computers (ACSSC), pp 1507–1514
Zurück zum Zitat Kutzkov K, Pagh R (2013) On the streaming complexity of computing local clustering coefficients. In: Sixth ACM international conference on web search and data mining, (WSDM), pp 677–686 Kutzkov K, Pagh R (2013) On the streaming complexity of computing local clustering coefficients. In: Sixth ACM international conference on web search and data mining, (WSDM), pp 677–686
Zurück zum Zitat Lim Y, Kang U (2015) MASCOT: memory-efficient and accurate sampling for counting local triangles in graph streams. In: Proceedings of the 21th ACM SIGKDD international conference on knowledge discovery and data mining (KDD), pp 685–694 Lim Y, Kang U (2015) MASCOT: memory-efficient and accurate sampling for counting local triangles in graph streams. In: Proceedings of the 21th ACM SIGKDD international conference on knowledge discovery and data mining (KDD), pp 685–694
Zurück zum Zitat Milo R, Shen-Orr S, Itzkovitz S, Kashtan N, Chklovskii D, Alon U (2002) Network motifs: simple building blocks of complex networks. Science 298(5594):824–827CrossRef Milo R, Shen-Orr S, Itzkovitz S, Kashtan N, Chklovskii D, Alon U (2002) Network motifs: simple building blocks of complex networks. Science 298(5594):824–827CrossRef
Zurück zum Zitat Stefani LD, Epasto A, Riondato M, Upfal E (2016) Trièst: counting local and global triangles in fully-dynamic streams with fixed memory size. In: Proceedings of the 22nd ACM SIGKDD international conference on knowledge discovery and data mining (KDD), pp 825–834 Stefani LD, Epasto A, Riondato M, Upfal E (2016) Trièst: counting local and global triangles in fully-dynamic streams with fixed memory size. In: Proceedings of the 22nd ACM SIGKDD international conference on knowledge discovery and data mining (KDD), pp 825–834
Zurück zum Zitat Suri S, Vassilvitskii S (2011) Counting triangles and the curse of the last reducer. In: Proceedings of the 20th international conference on world wide web (WWW), pp 607–614 Suri S, Vassilvitskii S (2011) Counting triangles and the curse of the last reducer. In: Proceedings of the 20th international conference on world wide web (WWW), pp 607–614
Zurück zum Zitat Tsourakakis CE, Kang U, Miller GL, Faloutsos C (2009) DOULION: counting triangles in massive graphs with a coin. In: Proceedings of the 15th ACM SIGKDD international conference on knowledge discovery and data mining (KDD) vol. 1, 2009, pp 837–846 Tsourakakis CE, Kang U, Miller GL, Faloutsos C (2009) DOULION: counting triangles in massive graphs with a coin. In: Proceedings of the 15th ACM SIGKDD international conference on knowledge discovery and data mining (KDD) vol. 1, 2009, pp 837–846
Zurück zum Zitat Welser HT, Gleave E, Fisher D, Smith MA (2007) Visualizing the signatures of social roles in online discussion groups. J Soc Struct 8(2):1–32 Welser HT, Gleave E, Fisher D, Smith MA (2007) Visualizing the signatures of social roles in online discussion groups. J Soc Struct 8(2):1–32
Zurück zum Zitat Yang Z, Wilson C, Wang X, Gao T, Zhao BY, Dai Y (2011) Uncovering social network sybils in the wild. In: Proceedings of the 11th ACM SIGCOMM internet measurement conference, (IMC), pp 259–268 Yang Z, Wilson C, Wang X, Gao T, Zhao BY, Dai Y (2011) Uncovering social network sybils in the wild. In: Proceedings of the 11th ACM SIGCOMM internet measurement conference, (IMC), pp 259–268
Metadaten
Titel
FURL: Fixed-memory and uncertainty reducing local triangle counting for multigraph streams
verfasst von
Minsoo Jung
Yongsub Lim
Sunmin Lee
U. Kang
Publikationsdatum
19.04.2019
Verlag
Springer US
Erschienen in
Data Mining and Knowledge Discovery / Ausgabe 5/2019
Print ISSN: 1384-5810
Elektronische ISSN: 1573-756X
DOI
https://doi.org/10.1007/s10618-019-00630-6

Weitere Artikel der Ausgabe 5/2019

Data Mining and Knowledge Discovery 5/2019 Zur Ausgabe