Study On Analysis Of Complex Network Topology

With the advancement of the information technology represented by the Internet,we have entered a network era.Most real-world systems can be modeled as networks,such as the World Wide Web,the road map,the airlines,the inter-personal relationship,the very large-scale integrated circuits,and the electric grid.Even the synonym relationship in linguistics can be depicted as a network.Obviously,it is greatly significant to analyze these networks.On the one hand,a property that seems to be common to many networks is community structure:the division of network nodes into communities within which the connections are dense,but between which they are sparser.As nodes belonging to a tight-knit community are more likely to share some characters,community detection is potentially very useful.On the other hand,the assessment the importance of nodes in networks has kept people's attentions for years.It has many applications such as the immunization strategy for computer networks and populations.Many attempts to tackle the community detection problem have been proposed in recent years.This thesis presents a new algorithm based on genetic algorithm,clustering and bi-partitioning strategy.It is illustrated through cases of both computer-generated and real-world networks that our algorithm is excellent in accuracy as well as efficiency.As for the problem of nodes evaluation,sociologists have suggested the criteria of degree,closeness and vertex betweenness;scholars from the system science have created the theory of core and coritivity;experts in the field of informaties have brought forward the famous PageRank and HITS algorithm.Based on the meaningful information hidden behind the identified communities,the proposed approach in this thesis could determine the role of a vertex in its community.And it also provides a solution for graph reduction.