Ändra sökning
RefereraExporteraLänk till posten
Permanent länk

Direktlänk
Referera
Referensformat
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Annat format
Fler format
Språk
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Annat språk
Fler språk
Utmatningsformat
  • html
  • text
  • asciidoc
  • rtf
Stad: Stateful Diffusion for Linear Time Community Detection
KTH, Skolan för elektroteknik och datavetenskap (EECS), Programvaruteknik och datorsystem, SCS.ORCID-id: 0000-0002-0264-8762
RISE SICS.
KTH, Skolan för elektroteknik och datavetenskap (EECS), Programvaruteknik och datorsystem, SCS.ORCID-id: 0000-0003-4516-7317
2018 (Engelska)Ingår i: 38th IEEE International Conference on Distributed Computing Systems, 2018Konferensbidrag, Publicerat paper (Refereegranskat)
Abstract [en]

Community detection is one of the preeminent topics in network analysis. Communities in real-world networks vary in their characteristics, such as their internal cohesion and size. Despite a large variety of methods proposed to detect communities so far, most of existing approaches fall into the category of global approaches. Specifically, these global approaches adapt their detection model focusing on approximating the global structure of the whole network, instead of performing approximation at the communities level. Global techniques tune their parameters to “one size fits all” model, so they are quite successful with extracting communities in homogeneous cases but suffer in heterogeneous community size distributions. In this paper, we present a stateful diffusion approach (Stad) for community detection that employs diffusion. Stad boosts diffusion with a conductance-based function that acts like a tuning parameter to control the diffusion speed. In contrast to existing diffusion mechanisms which operate with global and fixed speed, Stad introduces stateful diffusion to treat every community individually. Particularly, Stad controls the diffusion speed at node level, such that each node determines the diffusion speed associated with every possible community membership independently. Thus, Stad is able to extract communities more accurately in heterogeneous cases by dropping “one size fits all” model. Furthermore, Stad employs a vertex-centric approach which is fully decentralized and highly scalable, and requires no global knowledge. So as, Stad can be successfully applied in distributed environments, such as large-scale graph processing or decentralized machine learning. The results with both real-world and synthetic datasets show that Stad outperforms the state-of-the-art techniques, not only in the community size scale issue but also by achieving higher accuracy that is twice the accuracy achieved by the state-of-the-art techniques.

Ort, förlag, år, upplaga, sidor
2018.
Nyckelord [en]
Community Detection, Flow Models, Random Walks, Diffusion, Stateful Diffusion
Nationell ämneskategori
Datorsystem
Identifikatorer
URN: urn:nbn:se:kth:diva-231832DOI: 10.1109/ICDCS.2018.00107Scopus ID: 2-s2.0-85050963074OAI: oai:DiVA.org:kth-231832DiVA, id: diva2:1230180
Konferens
38th IEEE International Conference on Distributed Computing Systems, ICDCS 2018; Vienna University of Technology (TU Wien)Vienna; Austria; 2 July 2018 through 5 July 2018
Anmärkning

QC 20180703

Tillgänglig från: 2018-07-03 Skapad: 2018-07-03 Senast uppdaterad: 2018-10-30Bibliografiskt granskad

Open Access i DiVA

fulltext(3580 kB)96 nedladdningar
Filinformation
Filnamn FULLTEXT01.pdfFilstorlek 3580 kBChecksumma SHA-512
2968f13d1520944f4dc28bee5724f026ed7328785149f2934cf2c52ab6dd65ca306469e58a638be9def8482df67f902c2da2ebf5a9164ef3d4b6f733519def73
Typ fulltextMimetyp application/pdf

Övriga länkar

Förlagets fulltextScopus

Personposter BETA

Soliman, AmiraGirdzijauskas, Sarunas

Sök vidare i DiVA

Av författaren/redaktören
Soliman, AmiraGirdzijauskas, Sarunas
Av organisationen
Programvaruteknik och datorsystem, SCS
Datorsystem

Sök vidare utanför DiVA

GoogleGoogle Scholar
Totalt: 96 nedladdningar
Antalet nedladdningar är summan av nedladdningar för alla fulltexter. Det kan inkludera t.ex tidigare versioner som nu inte längre är tillgängliga.

doi
urn-nbn

Altmetricpoäng

doi
urn-nbn
Totalt: 165 träffar
RefereraExporteraLänk till posten
Permanent länk

Direktlänk
Referera
Referensformat
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Annat format
Fler format
Språk
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Annat språk
Fler språk
Utmatningsformat
  • html
  • text
  • asciidoc
  • rtf