Research On Community Structure And Related Problems

Many real-world complex systems in nature and society can be described by complex networks.Community structure can reveal hidden information and struc-ture properties of network,and help to understand the evolutionary mechanism of complex systems.Due to the dynamic nature of the network,the community struc-ture will evolve with the growth of the network scale.It is necessary to construct a mathematical evolutionary model to analyse and simulate dynamic properties of real-world community evolution.The community can be regarded as a small world network,and the research on multi-agent consensus problem in the small world network can provide the basis for community partition from the perspective of practical application.Meanwhile,with the emergency of big data,data col-lected from network platforms is incomplete.Based on current information,link prediction can predict missing and redundant data to reconstruct network.Link prediction can also provide new approach to the study of the evolution of network and communities.How to construct better algorithms to solve these problems has become a hot issue in statistical physics,applied mathematics and other fields.In this Ph.D.dissertation,we propose algorithms to identify community structure in complex networks.An evolutionary model of community structure is proposed,and its dynamic behaviors are analysed.We characterize quantitatively the sufficient condition of time-delayed multi-agent consensus problem in small-world network Moreover,we propose new link prediction algorithm and new indices to describe network structure.See below for detailsIn chapter 1 of this thesis,we introduce the research background and the recent research progress,and some notations are given as preliminary.We briefly introduce the main research work of this thesis.In chapter 2 of this thesis,we propose algorithms to identify non-overlapping and overlapping community structure.A new strategy for selecting a suit-able seed set is proposed,then it can be expanded to achieve local community partition of network by combining a personalized PageRank and random walk method.Our algorithm can also find the hierarchical community structure and small size community.It shows better effectiveness to identify commu-nity structure compared with other algorithms by experiments on real-world networks and computer generated networks.In chapter 3 of this thesis,we propose an evolutionary model of community based on preferential attachment principle.We analyse each community evolv-ing from small-world to scale-free and its dynamic behaviours,including the changes of modularity,epidemic spreading threshold and network entropy with time.We give the condition of modularity and epidemic spreading threshold to increase,and prove network entropy strictly increasing for each community evolution with time.We find it better to prevent the spreading of disease when the community evolves at a low evolutionary rate,and each community evolution process is a transition process from less vulnerable to susceptible to infection.The experimental simulations support our findings.In chapter 4 of this thesis,we give a mathematical rigorous estimation of the upper bound for the maximum degree of the small-world network as well as the upper and lower bound for the spectral radius with respect to the small-world network.These estimation characterize quantitatively the sufficient condition of time-delayed multi-agent consensus problem in small-world network.Addi-tional numerical simulation provides verification of analytical resultsIn chapter 5 of this thesis,new link prediction algorithm and indices to de-scribe network structure are proposed.A new algorithm based on common neighbors and distance is proposed to improve accuracy of link prediction.Our algorithm makes remarkable effect to predict the missing links between nodes with no common neighbors.Furthermore,based on common neighbors and Gini coefficient,we analyse that how network structure affects the accuracy of link prediction,and propose new indices to provide the reference for choice of link prediction algorithms.The statistical analysis reveals high correlation between new indices and Laplacian eigenvalue,clustering coefficient,degree heterogeneity,assortativity of network.A new method to predict missing links is proposed,which performs better prediction accuracy and robustness to the network structure.