The Reseach Of Complex Network Structure And Information Flow Control

Researchers often pay much attention to network control in network information science. With the development of science and information technology, various users with a variety of hardware and software join complex systems and involve in the development and evolution of the system, to constitute large-scale complex networks. How to outline the structure of complex network, as well as how to use the structural properties of the network to control the information flow, have become a very hot topic in complex network field.In network structure research field, people often focuses their attention on how to find communities of network, which means allocating every node to one community(or more communities), to make the network structure and the function of every node clearly. On the basis of clear network structure, network flow can be divided into two categories: one is positive flow and the other is negative flow. In general, people always hope the positive flow can be spread faster and farther in network, and the negative flow can be controlled as soon as possible. Hence, the network control theory was proposed. It can be done from two aspects to control network flow: control information source and control key nodes for dissemination of information. Controlling information source can help people to manage information distribution from source, and controlling key nodes for dissemination of information plays an important role to ensure information flow direction is the hope of people.This thesis can be divided into two parts. The first part is to study the structure of the network. Combining the structural characteristics of network, some community discovery algorithms were proposed. By using those algorithms into some synthetic and real network, it has verified that those algorithms have good performance to find communities in network. The second part is to study the control method of information flow in network. Information source localization can provide a method to find the source of information, and key nodes finding makes people to know which node is important in network. The study of network structure is the basis of network flow control research, and the study of network flow control is an extension of the research of network structure.The main contents of this thesis are as follows:(1) The study of structural properties of complex networks. It proposed a community discovery algorithm based on node similarity. In complex networks, the basic idea of community finding is to allocate nodes with the same or similar attributes to the same group, to make the link which is between nodes of the same group is close and the link which is between nodes of the different group is loose. Based on this idea, this thesis proposed a method to measure the similarity of node pairs, and assign nodes into the same community with the same or similar attributes. In this thesis, it measure the degree of node local similarity by correlation neighbor relationship, then measure the degree of node global similarity by mix indexs, finally combine the local indicators and global indicators to propose a community discovery algorithm. Experimental results show that the proposed algorithm can reflect the topology of complex network, and has theoretical reference value on community reseach.(2) The study of Label Propagation Algorithm(LPA). It is proposed a community finding algorithm based on the fusion clustering. Because of the complexity and dynamic characteristics of complex network, it is nature to find an algorithm with light, flexible and low time complexity property to find communities in network. The label propagation algorithm does not require a priori knowledge with near-linear time complexity, so it is suitable for community discovery in large-scale complex network. In this thesis, the fusion clustering overcomes the problem of instability caused by label propagation algorithm. Experimental results show that integration fusion clustering into label propagation algorithm can improve the stability of the community results.(3) The study of the influence of sequence of nodes to the results of communities. It proposed a community finding algorithm based on node sorting. A lot of empirical evidence shows that if the node which locates in the center of the community is considered firstly, it leads to stable community results; but if the node which locates at the edge of the community is considered firstly, the community results will random. In this thesis, it used a method to sort node, and proposed an algorithm to divide network based on nodes sorting. Experimental results show that the nodes sorting can solve the problem of instability in label propagation algorithm.(4) The study of constant community. Combining fusion clustering, it proposed an algorithm to find constant communities in network. Constant community is a very special structure in network, and it can be used to measure the degree of tightness of the network. Constant community consists by a series of nodes which always be allocated into the same community whatever how the network topology changes. Based on the characteristics of the constant community, it proposed an algorithm to discovery constant community based on fusion clustering, and it has important implications for the research of network structure.(5) The study of reachability for nodes. It proposed an algorithm to locate information source based on the reachability of nodes. In network, information can spread from edge of network. Hence, more edges exist between a node and other nodes, easier information can spread from this node to other nodes, and the reachability of this node is better. In this thesis, according to the number of path between a node and other nodes, it proposed an algorithm to find information source based on the reachability of nodes. Experimental results show that this method not only can avoid the time complexity caused by maximum likelihood estimation, but also can overcome inaccurate estimating of hop number in accessibility.(6) The study of how local properties and global properties to impact on the importance of node. It proposed an algorithm to measure the importance of nodes based on m hop neighbor’s information. A lot of empirical evidence show that the degree of node importance is not only relate with the local properties of nodes, but also relate with global properties as well as the position of nodes in the network. In this thesis, combining with local, global and position properties of nodes, it proposed an algorithm to measure the importance of nodes, to get the sequence of importance of nodes. Experimental results show that the mixd method can reflect the degree of importance of nodes accurately, and can get accurate nodes importance sequence.The main contents of this thesis are study network structure and control information flow. This work provide theoretical and practical basis for the study of complex network.