Quantify The Information And Complexity Of Complex Networks

Network science is an emerging cross-science which has emerged since this century,involving physics,information science,mathematics,computer science,control science,and social science.It characterizes complex systems in nature and society through networks,and explores the relationship between the structure and function of networks,so as to understand the various macroscopic phenomena presented by complex systems and the self-organizing mechanism behind them.In the study of this grand scientific problem,viewing complex networks from the perspective of information is an important research method to solve many problems.In particular,exploring the amount of information contained in the network itself,the differences between networks,and the complexity of networks can help us better understand the root causes of complex network topology and dynamic behavior to some extent.At present,seeking an effective measure of network information and structural complexity is still an important unsolved problem in the scientific community.On the one hand,looking at network systems from the information perspective and constructing measures which contain the global information of networks are not only the key issues of the system information theory,but also the expansion of the nature of complex network structures and the research basis for network differences.On the other hand,what is complexity,complex systems and how to measure the complexity of complex networks and other issues have not yet been resolved.The two problems are interlinked and mixed together.The purpose of this study is to find an entropy measure that can effectively reflect the characteristics of the global structure of networks and then characterize the global information of networks,and use this entropy measure to construct a measure that can accurately quantify the complexity of the global structure of networks.To this end,we carry out the following research work:The first task is to quantify the information of complex networks.Our research group put forward the concept of the communicability sequence entropy and studied the difference of network structures with it in the previous study.To explore whether the communicability sequence entropy has the ability to quantify the global information of networks,a series of studies were carried out.The influence of the topology structure of synthetic networks on the communicability sequence entropy is first studied.The results show that networks with strong heterogeneity,large degree-degree correlation coefficient and intermediate number of community structures all have relatively smaller communicability sequence entropy.Secondly,by studying the communicability sequence entropy of some real networks and their corresponding randomized network models,we can get that the higher the order of the randomized network model is,the lower the communicability sequence entropy is and the closer it is to the original real network.These results show that the communicability sequence entropy is sensitive to the basic topology of networks,and tends to decreases with the increase of the order degree of networks.This further proves that the communicability sequence entropy can effectively characterize the characteristics of the network global topology and has the ability to quantify the global information of networks.The second task is to quantify the complexity of complex network structures.This paper presents a statistical measure that can characterize the complexity of networks from a global perspective,which consists of the product of two items: One is the communicability sequence entropy that describes the global information of networks;The second is Jensen-Shannon divergence which characterizes the difference between the target network and the random network,which is constructed based on the communicability sequence entropy and describes the degree to which the target network is far from equilibrium.In order to verify the validity and accuracy of this measure,a series of studies were carried out.The influence of the topology structure of the synthetic network on the complexity measure is first studied.The results show that networks with strong heterogeneity,strong degree-degree correlation and intermediate number of community structures have relatively high complexity measures.In particular,this paper studies the complexity of weighted synthetic networks,and the results show that weighted networks have higher complexity than networks without weights.Finally,the complexity of real networks and their corresponding randomized network models are studied.The results show that the complexity of the randomized network model is a monotonically increasing function of its order,and the ones of real networks are larger complexity-values compared to all corresponding randomized network models.These research results show that the complexity measure proposed in this paper has a sensitive dependence on the change of the basic topology of networks,and has a positive correlation with the external constraints of networks.It strongly demonstrates that the complexity measure based on the communicability sequence entropy can accurately characterize the network complexity of the global structure.In a word,this paper studies the complex network from the perspective of information science and uses the idea of quantum statistical physics to find an effective measure for the quantification of the global information of complex networks and the representation of its complexity.These studies can not only promote people's further understanding of complex network structures,but also provide the reference for design and optimization of network structures.