Study On Measure And Topology Properties Of Some Complex Networks

Complex networks and systems extensively exist in nature and society, including proteininteraction network, personal relationships network, scientific collaboration network, trafficnetwork and the internet and so on. Scholars in different fields research complex networksbecause they often have big scales, large quantities, wide ranges and dynamic evolutions.Both the theoretic research and the applied one of complex network are very attractive andchallenging, and they also have a broad application prospects. Governments around the worldattach great importance to the research of complex network, and have invested a lot ofmanpower and material resources. In the unremitting efforts of scholars, there have been lotsof research achievements of complex network. New research directions and application fieldsare still developed. On the basis of some introduction to the theoretical foundation andgeneral research status of complex network, the present dissertation studies several measureand topology properties of complex network, obtaining some research achievements. Theresearch of measure property is based on resistance distance. Resistance distance is regardedas similarity measurement between any two nodes of a network, and then some relatedapplications are explored. Because all studies are carried out on networks and inevitablyinvolve the network topology structures, some topology properties are studied from anotherpoint, such as community structure, scale-free characteristics. Specifically, the main researchwork and contribution of this dissertation are summarized as follows.1. A new network model with the degree Sequence of geometric Sequence is proposed. Thenetwork model is theoretically proved to be a scale-free network, the power exponent ofwhich is simultaneously obtained. The degree sequence of the network model is a geometricsequence, the first term of which is a positive integer, and common ratio q of which is apositive integer greater than1. The length of the degree sequence is l. The number of nodeswithk idegree is b^n-i+1, and the power exponent is logqb, where b is also a positive integer,and n=l-1. In the network model, the geometric sequence is used to determine networkparameters, such as power exponent, the minimum degree and the number of nodes.Subsequently, related properties of the network are analyzed. Then, the topology structure ofthe network is found to vary with the change of degree sequence length. However, thescale-free property of it is always the same. Finally, some instances are employed to illustratethe network model. The illustrations show that the network model may exhibit differentnetwork structures. 2. Resistance distance is reviewed briefly in the view of complex network, thetransformation of a general network into an electrical network is given, and all computingmethods, application and properties of resistance distance are discussed. Meanwhile, it isproved that resistance is distance. The relationship between resistance distance and randomwalk is explored, and a famous property of resistance distance is introduced. The property isthe theoretical basis of many related applications.3. By applying the above resistance distance and its properties, a new spectral clusteringalgorithm is proposed, in which resistance distance is used to measure the similarity of dataobjects. The basic flow and general principle of spectral clustering algorithm are analyzed,and a few similarity measures in spectral clustering algorithm are discussed, then resistancedistance is applied to spectral clustering. The theoretical analysis shows that the proposedalgorithm can be applied to clustering data for distinct tasks, and the experiments show itsvalidity.4. An algorithm of discovery community structures is designed based on resistance distanceat first. According to the properties of small world and scale-free, each community has somecenter nodes with the larger degree. The proposed algorithm decides center nodes ofcommunities by using both the resistance distance and degrees of nodes; whereafter comparesthe resistance distance in between other nodes and center nodes for clustering the network.The algorithm uses the measure property of resistance distance. On the basis of the algorithm,an improved algorithm is brought forward. The second algorithm initially marks all nodes as“unvisited”, and then searches these unvisited nodes and seeks some so-called strongstructures made up of a center node with a maximal degree and most of its neighbors, andmarks them as “visited”. Subsequently the “unvisited” nodes are assigned to different strongstructures according to some criteria. At last the existing strong structures are perhapsoptimized and then different communities generate. The experiment results show that the twoalgorithms are stable, reliable and accurate.5. Based on the above resistance distance and its properties also, a new centrality measureis put forward to evaluate the importance of nodes. The resistance distance centrality of anode is considered as a function of the reciprocal of the sum of resistance distance betweenthe node and all the others. Resistance distance centrality brings into correspondence withinformation centrality in fact. In addition, the differences are discussed between the resistancedistance centrality and classical centrality measures. To evaluate the accuracy of the proposedcentrality measure, some tests are presented on artificial and real-world network data sets. The experiment results demonstrate the discriminative power of the proposed measure, especiallyon regular graphs.