Research On Mechanical Models And Vital Vertex Mining In Complex Networks

Networks can be seen everywhere in our life, with the continuous development of society,the concept of network has evolved into more complex virtual networks, such as Internet,from simple reality networks, such as highway networks and railway networks. People haveturned their survival world into the world of network, then a new field of study, namedcomplex network, has come out.Mechanical network modeling and vital vertex mining are two basic research braches inthe study of complex network. Series of studies, such as Network characteristics, are based onnetworks, the problems can not be analyzed and solved using the theory of complex networksfield before the real problem has been abstracted into a mechanisms model. The purpose ofmining important vertices is to seek the important vertex in a network, and this study is veryimportant to measure the network robustness. Only knew where the important vertex is,effective strategy can be applied to the network well, thereby useful network can be protectedand harmful networks can be destroyed, so that the network can be better used for human. Themain work of the thesis is as follows:(1) A swirl-shaped network model and a pinwheel-shaped network model are proposed.In order to understand how small world network gengerated, the reality phenomenon of swirland pinwheel rotation were studied, and construct two network models for analysis. In thisthesis, the way of deterministic construction is used to generate the two network models, andthe size of two networks is constantly increasing with the increase of the number of iterations.The network features’ analysis method in the field of complex network is used to analyze andsummarize four typical parameters of the proposed two models, such as degree distribution,clustering coefficient, diameter and average path length, and experimental verification hasbeen taken to show the correctness of all the conclusions.(2) An approximate flow betweenness algorithm and an activity algorithm are proposed.As the complexity of flow betweenness is so high, this paper proposed an approximate flowbetweenness by the analog information spread in the network. The algorithm uses the methodof analog information stream, where each node spread equalization information to its adjacentnodes, but itself does not retain the original information. After a certain number of timestransmission，all vertices will count the amount of contain information, and the importance of each node can be obtained. This algorithm and some other algorithms, such as the flowbetweenness algorithm, are all taken into two experimental networks, the effectiveness of thealgorithm is obtained by comparing the experimental results. In order to verify whether theclustering coefficient can be used for mining important vertices, the activity algorithm isproposed, which uses the analog information flow as well. The algorithm takes the product ofa vertex’s degree and its coefficient as the basis that how much information a vertex spreads toits adjacent vertex. How much information a vertex owns can be counted after a certain periodof time transmission to obtain each vertex’s importance. Experimental simulation has beentaken by using the algorithm and a variety of existing algorithms, the experimental resultsprove the correctness of the algorithm.