Research On The K-means Clustering Algorithm Based On Attribute Augumented Graph

Community structure is one of the common topological characteristics of social networks.Community detection has become a fundamental problem in the research field of socialnetworks. The clustering algorithm is an important way to find community structure. Theclustering analysis technique has been widely studied in the past many years, one of theclustering algorithm is k-menas clustering algorithm, which is the most classical. Because ofsimple thinking and short time complexity , k-means is wide studied and applied. Especiallythe k-means algorithm is scalable and high efficient in large-scale database.In the real network, there is topological structure between datas, and there are specialproperties too. Many existing clustering methods mainly focus on the topological structure,but largely ignore the data properties, which are often important in the clustering algorithm.The topological structure and properties of data play an important role on the clusteringanalysis.In this paper, we analyze the important of topological structure and properties in theclustering algorithm, then impore the K-means clustering algorithm. We propose a newclustering algorithm (SAK). The main contributions of this paper are summarized below:(1) We use graph model to said real network. In accordance with the practicality of thereal network, we add the properties characteristic of the node as a node in the graph, and addthe edges in accordance with the relationship between the nodes and the attribute. Then theattribute augment graph is constituted. A random walk model is used to measure the vertexcloseness through the topological structure and properties based on the attribute augmentgraph.(2)We propose a weight self-adjustment method. In the iterative process of clusteringalgorithm, the weight of edges and the vertex closeness is updated too. The different attriburewill play different role in the clustering algorithm. The change will make the measurement ofsimilarity become more practical and accurate. (3) The k-means clustering algorithm based on the attribute augument graph is putforward. The clustering algorithm change the method of randomly selecting the initialclustering centers on the k-means clustering algorithm. The density function method is used toselect the initial clustering centers. We use two real network to verify the clustering algorithm.