Community Detection Algorithm Based On The Linear Spectral Statistics

Community detection is an important subject in networks,whose applications are in a diverse set of areas,ranging from detection communities in social and biological networks to identifying deadbeat in financial credit.Community detecting in a network has received much attention from statistics,physics and computer science.However,the clustering algorithms used in the past are often limited by the known number of communities k.In this paper,we will learn k automatically in a graph by using a hypothesis test.Every community in a graph generated from a stochastic block model can be considered as an ER graph,therefore the null hypothesis is that a network is generated from an ER graph.To establish a connection between the ER graph and the Wigner matrix,we will prove the central limit theorem of the linear spectral statistics of the adjancy matrix of ER random gragh,and ues the linmiting distribution of linear spectral statistics as statistics for hypothesis testing to determine whether the network is an ER graph.We will propose two hierarchical clustering algorithms based on motif spectral clustering algorithm and the hypothesis testing algorithm.The difficulty is mainly discussed in the following two aspects.The first difficulty is to prove that the linear spectral statistics of the normalized adjacency matrix of the ER graph converge weakly to Gaussian distribution.The other difficulty is how to build k unknown clustering algorithm based on hypothesis testing algorithm of the linear spectral statistics.