Graph Partition Defined By The Roads To Sub-heart And Calculating The Number Of Crossing Edge In Classified Graph

In the era of data, under the explosion of information, graph as an important information carrier, gets more and more attention from researchers. How to represent graph data visually and analysis it has become a research hot spot. In order to better understand the structure of graph and measure the layout of graph, in this paper we use multidisciplinary approaches, including the path analysis in graph theory, the line segment intersection in computational geometry and computer simulation methods. The main study topics are the graph partition and the crossing number problem. The main conclusions and innovation are in the following three aspects:(1) The Graph Partition. Based on the idea that the sub-class center node has greater power to control other nodes in the same subclass, several concepts including the sub-class center node, the up pathway and the centripetal pathway, are defined. By using those concepts, a new algorithm called the Toward to Sub-heart Roads Defining Network Clustering Algorithm is presented. The new algorithm can help us to finish the community division of the network nodes. Several experiments show that this algorithm plays better performance than some traditional algorithms.(2) The Number of Edge Crossing in Classified Graph. When calculating the number of edge crossing, we make full use of the given node classification information of the classified graph divided the edges into two categories and calculate the crossing number separately. If the number of edges between the classes is small, our algorithm increases the efficiency of computing time.(3)The Generation of Artificial Graph. According to the scale-free feature theory and graph structure analysis, we divided the generation process of artificial graph to two steps:the span of sub-graph and sub-graph connect. In the span of sub-graph section, we focus on the edge build that nodes tend to be connected to a node which has a high degree. In the sub-graph connect section, two probability rules are used:a node is chosen with high probability as a end of an edge between two sub-graphs if the node locates on the border; An end of cross sub-graphs edge has greater probability to get more edges. Our artificial graph generation algorithm based on the structure of graph can generate the graph satisfying the needs of user and shows good simulation effect.