Application Research On Graph Mining Based On Structure And Attribute

As a technology to discover useful knowledge from data, the graph clustering methodsaccept more attentions. The most of the existing graph clustering methods are based on graphtopology or attributes. However, both structures and attributes may need to be taken intoaccount. Therefore, the existing graph clustering methods have some problems such as themodel is not accurate, the clustering results are not satisfied and the algorithm is inefficiently.In order to solve the problems, this paper will study in the following areas:Firstly, we propose a weighted graph with attribute model. In the model, the verticesrepresent data objects, the edges represent relationships and vertex attributes represent thecharacteristics of data objects. According to the relations of the data and the degree of theimportance of the different attribute, a set of different weights were set to the structural edgesand the attributes respectively. The graph model can reflect applications more realistically.Secondly, based on the problem mentioned above, an efficient graph clustering method,SACA (Structural and Attributed Clustering Approach), based on structure and attribute isproposed.1) A weighted graph with attribute model is proposed in this paper. In the model,different weights are assigned to the structure edges and the attributes.2) A method to unifythe structure and attribute similarity is proposed and then the similarity of the trcutures andattributes can be computed unified.3) A random walk similarity is proposed to measure thesimilarity between the structures and attributes vertices of the graph.4) Following the AffinityPropagation clustering algorithm, SACA clustering method aims at clustering the graph andthe vertices in the same cluster are density connected and the attributes are homogeneous;however the vertices in different clusters are loosely connected and the attribute areheterogeneous.Finally, the extensive experiment was performed to evaluate the performance ofproposed clustering algorithm SACA on real datasets. The results of the experiment showSACA graph clustering method is more effective and efficient in effect and time complexitythan the existing graph clustering algorithms.