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
RISE - Research Institutes of Sweden, ICT, SICS.
RISE - Research Institutes of Sweden, ICT, SICS.
RISE - Research Institutes of Sweden, ICT, SICS.
2018 (English)In: Proceedings - International Conference on Distributed Computing Systems, Institute of Electrical and Electronics Engineers Inc. , 2018, p. 1074-1085Conference 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. %Furthermore, majority of existing techniques target extracting disjoint communities. 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
Institute of Electrical and Electronics Engineers Inc. , 2018. p. 1074-1085
Keywords [en]
Adaptive Random Walks, Decentralized Community Detection, Flow Models, Stateful Diffusion, Diffusion, Learning systems, Population dynamics, Community detection, Diffusion mechanisms, Distributed environments, Flow model, In-network analysis, Real-world networks, State-of-the-art techniques, Distributed computer systems
National Category
Electrical Engineering, Electronic Engineering, Information Engineering
Identifiers
URN: urn:nbn:se:ri:diva-37290DOI: 10.1109/ICDCS.2018.00107Scopus ID: 2-s2.0-85050963074ISBN: 9781538668719 (print)OAI: oai:DiVA.org:ri-37290DiVA, id: diva2:1280284
Conference
38th IEEE International Conference on Distributed Computing Systems, ICDCS 2018, 2 July 2018 through 5 July 2018
Available from: 2019-01-18 Created: 2019-01-18 Last updated: 2019-03-28Bibliographically approved

Open Access in DiVA

No full text in DiVA

Other links

Publisher's full textScopus
By organisation
SICS
Electrical Engineering, Electronic Engineering, Information Engineering

Search outside of DiVA

GoogleGoogle Scholar

doi
isbn
urn-nbn

Altmetric score

doi
isbn
urn-nbn
Total: 16 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