A Distance-based Spectral Clustering Approach With Applications To Network Community Detection

The rapid development of mobile Internet has led to the increasing popularity of many online social networks and their related applications,which makes social networks play an increasingly important role in disseminating news and gathering public opinions.After observing and studying,we find that there are many communities with similar members in the real social network,but how to find these communities is a problem worthy of study.Spectral clustering is an important unsupervised learning approach to many object partitioning and pattern analysis problems.In order to solve the network community detection problem,we present our work on a novel spectral clustering algorithm that groups a collection of objects using the spectrum of the pairwise distance matrix.It is proven that if the points in a metric space can be associated with a well defined distance,the pairwise distance matrix is almost negative definite,which implies that its eigenvectors for the most significant negative eigenvalues can be used to approximate the solution to a quadratic binary partition problem.In addition,we define the quality measures for the one dimensional partitioning of the eigenvectors,which are further applied to evaluate the partitioning results for the data points projected into the space spanned by the selected eigenvectors.Since the Lanczos iterative algorithm may be revised to finding the eigenvalues efficiently in a distributed way,we adapted this algorithm to the network community detection problem using a decentralized multi-agent framework.The performance of the proposed approach was tested using different datasets,for example,the artificial data set,the UCI Iris dataset,the image segmentation dataset,and the Karate club dataset,and the experiments showed that it was able to enhance the effectiveness of clustering.When the algorithm is applied to the community discovery problem,the topology of the network is not known,and the requirements of user privacy protection are met.The correct and effective result can be obtained by the fast convergence speed.