Community Detecting Methods Based On Given Partition In Complex Networks

Complex systems are everywhere around us.For the study of complex systems,a variety of efforts have been devoted and many theories have been established,among which the field of complex networks begun to rise at the end of the twentieth century is one of the attempts.A complex network is an abstraction of a complex system,in which two keys,the individuals and the interactions between them,are captured.This abstraction benefits us in the following three aspects:it simplifies the systems,reduces the complexity and dimension;it describes the systems in mathematical language of graph theory and it provides a intuitive picture;it provides a unified framework for the study of different systems.Complex networks,though are simplifications of complex systems,are still com-plex,which requires us to reduce the dimension further and to observe them from dif-ferent sides.Observing and describing complex networks from different perspectives,different properties can be found,such as scale-free property and small-world property.And it is from large-scale perspective that the emphasis of this thesis,the community structure,describes complex networks.Community structure is an important structure of complex networks.The impor-tance is summarized in this thesis,which includes:it conduces to the understanding of the organizing principle of complex networks,it emerges on a variety of real networks,it is a link between the structure and function of networks,it is helpful to identify other structures,it has a significant effect on the dynamics of the network,it provides a spe-cific perspective to observe the networks,and it provides a verification platform for some algorithms.However,for many real networks,the network data is not accompanied by the community structure,which requires us to detect the hidden community structure.For the detection,several methods have been established,among which the modularity-based methods and statistical inference are mainly introduced in this thesis.In order to evaluate their performance,those methods are usually tested against synthetic bench-mark networks and real-world networks each of which has a reference partition.In real-world networks,the reference partitions are given by domain experts based on ad-ditional information of the networks,which can be recovered by many detecting algo-rithms.These partitions are called to be expert partitions,which are usually regarded as the ground-truth of the community structure in the networks.If the expert partitions can be reliably recovered,an algorithm is considered successful.Despite the wide use of expert partitions in evaluating community detection algorithms,the evaluation of the expert partitions themselves has attracted few attention.In this thesis,a new concept about the relation between community structure and expert partition,completeness,which represents whether a partition that is either anno-tated by experts or given by a community detection algorithm,carries complete infor-mation about community structure in the network,is proposed.In order to determine the completeness,a new measure to community structure,exclusive modularity,is de-fined,and a mathematically principled method based on cavity method of statistical physics is developed.The results demonstrate that the expert partition in karate club network is complete.While in the famous political blogs network,the expert partition is surprisingly incomplete,showing that there are other information hidden by the ex-pert partition,and indicating that the relation between expert partition and community structure in real-world networks needs to be re-examined.As a by-product,the applica-tions of the method include detecting hidden structures,finding hierarchical structures without removing edges,and obtaining low-dimensional embedding of networkOn the above work,the expert partition is excluded from the network,but some-times,the non-topo logical properties of nodes may conduce to the detection of commu-nity structure.Based on the known properties,the modularity-like objective function is defined in this thesis,which is a linear combination of classic modularity and condi-tional entropy.Moreover,two works in other fields rather than community structure are intro-duced.One is epidemic spreading in complex networks based on behavioural responses,in which a epidemic spreading model accompany with behavioural responses in com-plex networks is established.Via the percolation method under mean-field approxima-tion,the theoretical formulas for the epidemic threshold as well as the prevalence of epidemic are derived,which are in good agreement with the simulations.The other is about dynamics traffic light strategy in urban traffic model,in which two strategies are proposed,one of which performs much better than the classic alternating one.