Investigation Of Spectral Graph Theory For Graph Clustering And Community Detection

Abstract

This study investigates how graph grouping and community detection can be accomplished using spectral graph theory. The eigenvalues and eigenvectors of a graph's adjacency or Laplacian matrix are used by spectral graph theory to uncover structural characteristics and underlying patterns. Data analysis and network science core objectives include clustering and community discovery, which seek to locate communities of connected nodes in a graph. Spectral graph theory offers important insights into the structure and connection patterns of the network by examining its spectrum. This study explores numerous spectral clustering
algorithms and evaluates how well they identify communities inside various kinds of graphs, including normalised cuts, spectral embedding, and modularity optimisation. It also investigates how spectral graph clustering algorithms perform in relation to graph
characteristics like sparsity and size. The findings of this study advance knowledge of spectral graph theory and its practical application to graph clustering and community detection problems. For more precise community discovery, the suggested method makes use of a probability matrix and an enhanced spectral clustering algorithm. The approach first builds a probability matrix by using the Markov chain to determine the transition probabilities between nodes. The mean probability matrix is then used to create a similarity graph. The NCut goal function is then optimised to accomplish community detection. On both synthetic and actual networks, comparisons are made between the proposed algorithm and existing techniques like SC, WT, FG, FluidC, and SCRW to assess its efficacy. The suggested
technique produces more precise community detection and demonstrates higher overall clustering performance, according to experimental data.