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.

Lin, J., Mio, C., A Vertex-centric Markov Chain Algorithm for Network Clustering based on b-Coloring, in Q2SWinet 2020 - Proceedings of the 16th ACM Symposium on QoS and Security for Wireless and Mobile Networks, (esp, 2016-11-16), Association for Computing Machinery, Inc, New York 2020: 89-93. [10.1145/3416013.3426459] [http://hdl.handle.net/10807/177942]

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

Lin, Jianyi
;
2020

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.
2020
Inglese
Q2SWinet 2020 - Proceedings of the 16th ACM Symposium on QoS and Security for Wireless and Mobile Networks
19th ACM symposium on QoS and Security for Wireless and Mobile Networks, Q2SWinet 2020
esp
16-nov-2016
20-nov-2020
9781450381208
Association for Computing Machinery, Inc
Lin, J., Mio, C., A Vertex-centric Markov Chain Algorithm for Network Clustering based on b-Coloring, in Q2SWinet 2020 - Proceedings of the 16th ACM Symposium on QoS and Security for Wireless and Mobile Networks, (esp, 2016-11-16), Association for Computing Machinery, Inc, New York 2020: 89-93. [10.1145/3416013.3426459] [http://hdl.handle.net/10807/177942]
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/10807/177942
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 1
  • ???jsp.display-item.citation.isi??? ND
social impact