The Research On The Formation Of Modularity During The Evolution Of A Scale-Free Network

A scale-free network is a class of complex network whose degree distribution follows a power law. Analyzing the evolution of a scale-free network and giving a proper formal description are hot issues in the research of complex network. BA model is currently most accepted model explaining the formation of scale-free networks. In short, the model simulates the evolution of network structures as a directed selection process. This conflicts with the fact that the structural formation of a network is a complex process affected by many factors without any explicit directions. In this paper, we try to develop an alternative model combining graph theory and game theory, and conclude that formation of complex networks are the results of both competitive and cooperative factors. The main work and contributions of this thesis are as follows:â…°) New algorithms are designed and implemented based on a novel perspective of analyzing the evolution process of a scale-free network. Using essentially the core concepts in the theory of Games on Graph, more than five factors such as'kin selection','direct reciprocity','indirect reciprocity','network reciprocity','group selection'are combined together to model the network evolution. Based on the analysis, the game algorithm based on evolutionary rules is designed and implemented using C++ language.â…±) Competition and cooperation are the internal reasons for the formation of a scale-free network based on our analysis and simulation. Firstly, several experiments are designed by choosing different game strategies and setting proper parameters to validate the rationality of our algorithms. The main conclusion is: it is the competition and cooperation and their complex interactions that would result in the scale-free structure of a network. We define external fitness as the ability to become successful whereas internal fitness would be the quality related to one's reputation and skill to interact with others. Our results thus shed light on the explanations of three intriguing details of network formations: 1) the player who becomes fitter externally would appear to also need to have higher internal fitness; 2) the one who cooperates with others while not affecting its own interests could in fact acquire both higher external and internal fitness; 3) if the one who has little external fitness to begin with, he could still become successful if he owns high un-deterministic. These observations suggest that nearly all of the scale-free networks might share similar underling mechanisms.