Research And Applications Of Weighted Property Graph Clustering Algorithm Based On DNA Computing

Graph is an effective means of describing and solving problems.Clustering is the process of grouping data into several clusters.Clustering analysis problems generally can be transformed into graph clustering problems for reducing the complexity.Graph clustering algorithms express relationships between objects using weighted graph,and achieve the clustering goal by means of dividing nodes into several sub-graph. With sustained advancing of social informationization,scale of the graph which is used to describe real world shot up,followed by computing complexity of graph clustering problem increasing exponentially. So electronic computer is hard to solve these similar problems.The basic principle of DNA computing can be summarized as follows. Firstly taking coded DNA sequences as carriers,map the pending issue to certain DNA molecules;Then generate the solution space by biochemistry reactions with the actions of biological enzyme;Finally,get computing results through various molecular techniques.DNA computing is a new computing pattern with high degree of parallelism.Therefore,the speed of graph clustering would be sharply increased if DNA computing can be used for solving graph clustering problems.The existing graph clustering algorithms focus more on how to cluster objects reasonably.After cluster formation stage,they usually take the center node as cluster head.But in a real world application,the choices of cluster head often need to consider the factors such as influence of each nodes.Regarding of this kind of problems,this paper introduces a property graph whose nodes and edges are both weighted.And the weight of node represents influence value while the weight of edge is the similarity between nodes.To solve the clustering problem of this kind of graph,we propose a clustering algorithm based on the minimum spanning tree.Meanwhile we give the corresponding coherent DNA computing method,and design an improved encoding method which encode the weight of node and edge into the same DNA strand.After biology operations,the test tube will show the clustering result and the information of cluster head.We analysis the complexity of our algorithm and then apply it to the clustering problem of WSN.We give the routing mechanism and the simulation results which verifies the algorithm validity.This application provides an effective and novel method for optimized energy saving of network cluster problem.