Stad: Stateful diffusion for linear time community detection
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
2019-01-182019-01-182019-03-28Bibliographically approved