Multi-attribute Undirected Weighted Graph Clustering Method Study

With the advance of social information and communication technology and the rapid development of network technology, information flow is too large, the amount of stored data is growing rapidly at an exponential rate, a widely used figure is the data structure, it is a good to express structural relationships between data objects. In the real world, many systems form the structure of the network graph, such as the Internet, World Wide Web, personal relationships, and scientists Collaboration and telephone network and so on. At the same time real-world network structure is used to describe the scale of the plan also has a larger growth trend. Currently the face of vast and infinite data, it is an urgent need from the data in the ocean to keep crude refined, through technical means of analysis are useful results.Graph clustering is a very interesting and challenging research topic in recent years has attracted extensive attention of many researchers, and applied to fields. The purpose of graph clustering is based on a variety of different standards to large-scale graph of the node split into different clusters, making a cluster of nodes in connection with the close connection nodes between different clusters sparse. Many existing graph clustering methods focus on the topology map so that each cluster to achieve a cohesive internal structure. But in the practical application of graph structure due to the heterogeneity of data sets, graph itself there are many potential information, as shown in the attribute information of the node weight between nodes of information and so on. With the graph structure increasingly large data sets and complex, only the information of the topology graph clustering difficult to get good results. In this paper, considering the graph for this topology, node properties, and the weights between nodes based on the proposed two new graph clustering method to solve the problem.1,Multi-attribute network graph structured agglomerative hierarchical clustering.Considering the way the topology graph and node attribute information, attribute information supplemented by the node topology graph to generate new clusters. First, in the original by adding more attribute nodes with the property method to enhance the closeness between nodes, while allowing non-connected graph into a connected graph; according to the direct neighbor nodes calculate the structural similarity of edge, in order to improve the new attribute node to add the contributions, we calculated an attribute node transition probability matrix, which are adjacent to the similarity between nodes. Initialize each node as a separate cluster, in accordance with the degree of acquaintance between the nodes descending order, visit each edge once, and gradually merge two nodes corresponding to edges, a bottom-up level of aggregation , where a given number of clusters k.In the real data set to test, and the current outstanding graphical clustering method, the experimental results show that the algorithm significantly improved the efficiency of clustering, and get better clustering results.2,Max-min distance measure based on the weighted network graph structured clustering method.Consider the graph of this method uniform topology and the weights between nodes. Our challenge is both to ensure greater weight with the two sides are not connected to separate, while making connections with the nodes within a cluster tightly. To this end we propose maximum and minimum distance metric based on the weighted network graph clustering method, normalized to the weight of each edge, to the range, calculated in accordance with the topology graph has a direct edge connecting node structural similarity, considering the graph topology and weight their contribution to the principle of minimal correlation to select a new cluster center, and the greatest correlation for pattern classification principle. Experimental results show that the method can be well balanced graph topology and the weights between nodes, the respective contributions, and get better clustering results.