A Comparative Study of Graph Kernels and Clustering Algorithms

A Comparative Study of Graph Kernels and Clustering Algorithms

Riju Bhattacharya (National Institute of Technology, Raipur, India), Naresh Kumar Nagwani (National Institute of Technology, Raipur, India) and Sarsij Tripathi (Motilal Nehru National Institute of Technology, Allahabad, India)
DOI: 10.4018/IJMDEM.2021010103
OnDemand PDF Download:
No Current Special Offers


Graph kernels have evolved as a promising and popular method for graph clustering over the last decade. In this work, comparative study on the five standard graph kernel techniques for graph clustering has been performed. The graph kernels, namely vertex histogram kernel, shortest path kernel, graphlet kernel, k-step random walk kernel, and Weisfeiler-Lehman kernel have been compared for graph clustering. The clustering methods considered for the kernel comparison are hierarchical, k-means, model-based, fuzzy-based, and self-organizing map clustering techniques. The comparative study of kernel methods over the clustering techniques is performed on MUTAG benchmark dataset. Clustering performance is assessed with internal validation performance parameters such as connectivity, Dunn, and the silhouette index. Finally, the comparative analysis is done to facilitate researchers for selecting the appropriate kernel method for effective graph clustering. The proposed methodology elicits k-step random walk and shortest path kernel have performed best among all graph clustering approaches.
Article Preview

This section presents a detailed literature survey on graph kernels and clustering algorithms.

Complete Article List

Search this Journal:
Open Access Articles: Forthcoming
Volume 13: 4 Issues (2022): Forthcoming, Available for Pre-Order
Volume 12: 4 Issues (2021): 2 Released, 2 Forthcoming
Volume 11: 4 Issues (2020)
Volume 10: 4 Issues (2019)
Volume 9: 4 Issues (2018)
Volume 8: 4 Issues (2017)
Volume 7: 4 Issues (2016)
Volume 6: 4 Issues (2015)
Volume 5: 4 Issues (2014)
Volume 4: 4 Issues (2013)
Volume 3: 4 Issues (2012)
Volume 2: 4 Issues (2011)
Volume 1: 4 Issues (2010)
View Complete Journal Contents Listing