A Vertex-centric Markov Chain Algorithm for Network Clustering based on b-Coloring

Jianyi Lin, Corrado Mio

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

Abstract

The massive size and complexity of big datasets such as those coming from social, natural and sensor environments raise utmost challenges to unsupervised cluster analysis methods in terms of performance scalability in designing algorithms, also considering parallel and distributed networking context. To cope with these hindrances, the parallelization of clustering techniques, also benefiting from GPU-centered computation, can contribute to fill the gap in applicative areas such as optimization of network routing or management of large-scale IoT networks, thus enabling the extraction, processing and policy making relying on rich network information that are typically represented in the form of graphs. One established approach to clustering graphs is through the coloring techniques, and indeed, graph clustering and graph coloring can be viewed as tied. We devise a graph clustering technique based on a Markov Chain method aimed at b-coloring the data points, that works in efficient vertex-centric parallel manner and produces a valid clustering with reduced number of color classes. We assess our algorithm against synthetic data encapsulating group structure characteristics and present a brief convergence analysis of the method.

Original languageBritish English
Title of host publicationQ2SWinet 2020 - Proceedings of the 16th ACM Symposium on QoS and Security for Wireless and Mobile Networks
Pages89-93
Number of pages5
ISBN (Electronic)9781450381208
DOIs
StatePublished - 16 Nov 2020
Event19th ACM symposium on QoS and Security for Wireless and Mobile Networks, Q2SWinet 2020 - Alicante, Spain
Duration: 16 Nov 202020 Nov 2020

Publication series

NameQ2SWinet 2020 - Proceedings of the 16th ACM Symposium on QoS and Security for Wireless and Mobile Networks

Conference

Conference19th ACM symposium on QoS and Security for Wireless and Mobile Networks, Q2SWinet 2020
Country/TerritorySpain
CityAlicante
Period16/11/2020/11/20

Keywords

  • b-coloring
  • graph clustering
  • parallel algorithm
  • stochastic coloring

Fingerprint

Dive into the research topics of 'A Vertex-centric Markov Chain Algorithm for Network Clustering based on b-Coloring'. Together they form a unique fingerprint.

Cite this