Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
Stad: Stateful Diffusion for Linear Time Community Detection
KTH, School of Electrical Engineering and Computer Science (EECS), Software and Computer systems, SCS. Royal Institute of Technology (KTH).ORCID iD: 0000-0002-0264-8762
RISE SICS.
KTH, School of Electrical Engineering and Computer Science (EECS), Software and Computer systems, SCS. Royal Institute of Technology (KTH).ORCID iD: 0000-0003-4516-7317
2018 (English)In: 38th IEEE International Conference on Distributed Computing Systems, 2018Conference paper, Published paper (Refereed)
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.

Place, publisher, year, edition, pages
2018.
Keywords [en]
Community Detection, Flow Models, Random Walks, Diffusion, Stateful Diffusion
National Category
Computer Systems
Identifiers
URN: urn:nbn:se:kth:diva-231832DOI: 10.1109/ICDCS.2018.00107OAI: oai:DiVA.org:kth-231832DiVA, id: diva2:1230180
Conference
ICDCS 2018
Note

QC 20180703

Available from: 2018-07-03 Created: 2018-07-03 Last updated: 2018-07-03Bibliographically approved

Open Access in DiVA

fulltext(3580 kB)8 downloads
File information
File name FULLTEXT01.pdfFile size 3580 kBChecksum SHA-512
2968f13d1520944f4dc28bee5724f026ed7328785149f2934cf2c52ab6dd65ca306469e58a638be9def8482df67f902c2da2ebf5a9164ef3d4b6f733519def73
Type fulltextMimetype application/pdf

Other links

Publisher's full text

Search in DiVA

By author/editor
Soliman, AmiraGirdzijauskas, Sarunas
By organisation
Software and Computer systems, SCS
Computer Systems

Search outside of DiVA

GoogleGoogle Scholar
Total: 8 downloads
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

doi
urn-nbn

Altmetric score

doi
urn-nbn
Total: 18 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf