Studies On Community Structure Detection And Information Propagation Characteristics On Complex Networks

Complex network is an abstract presentation of complex systems in the form of network topology,where the nodes represent different individuals in the complex system and edges represent the interactions and relationships between individuals.Complex network can provide a global and comprehensive view of the underlying complex system.The researches on topological features and propagation characteristics of complex networks are very helpful to reveal common rules and properties in complex systems.Community structure is an important structure property of complex networks.Community structure has great practical significance since it usually corresponds to the function module or structural element of the complex system.For example,a community may correspond to a social organization in social networks,a discussion group in communication networks,or a functional protein complex in protein interaction network.Community structure can provide us a deep insight into the organization and function of complex network,and also has great influence on the dynamic properties and information propagation characteristics of complex network.Therefore,analyzing the community structure has become an important subject in the research field of complex network.Recently,community detection in complex networks has become a hot research topic at home and abroad.But the existing methods still have several drawbacks when tackling the problem of community detection.Firstly,most community detection methods use the modularity as the basic measure of community structure.However,some researches have found the resolution limit of modularity optimization,which may result in unreasonable and deficient community structure.Secondly,some researches have shown that the real-world networks often exhibit overlapping and hierarchical community structure.The overlapping property means that some nodes may belong to more than one community.The hierarchical property means that a larger community may consist of several smaller communities.In the presence of overlap and hierarchy,community structure is not simply a partition of the network,but a hierarchy of different covers for the network.However,the majority of community detection methods are only suitable for disjoint communities and not applicable to overlapping and hierarchical community structure.Thirdly,the scale of complex networks continuously increases with the explosive growth of information.Many real-world networks may contain thousands even millions of nodes and edges.This fact requires the community detection methods to be scalable and computational efficient.However,most existing community detection methods cannot satisfy the requirements of computational complexity for large-scale networks.Moreover,information propagation is also an important research subject in the field of complex network,which aims at revealing the properties and mechanism of information propagation process under specific network topology.As a common structural property of complex network that reflects the inhomogeneity of network topology,community structure does have some influence on the information propagation characteristics of the network.However,the researches on the information propagation characteristics of complex networks with community structure are still in a preliminary stage.By the above discussion,this dissertation systematically studies the mathematical model of community structure of complex networks.We propose some new methods for community detection in complex networks,and also present an effective influence maximization approach based on the influence analysis of community structure to the information propagation characteristics of complex network.The main works of this dissertation are listed as follows.First,this dissertation makes a thorough research on the basic theory of community structure,including the definition,topological structure and evaluation criteria.Second,in order to overcome the resolution limit of modularity optimization,this dissertation makes a pioneering attempt to introduce the cellular learning automata(CLA)theory into the community detection on complex networks and proposes a cellular learning automata based algorithm for discovering community structure.In the proposed method,the whole network is modeled as irregular cellular learning automata.Taking advantage of the evolution mechanism of cellular learning automata,the proposed method can impose some topological constraints to the communities when searching for the optimal modularity,which effectively solves the resolution limit of modularity optimization.Third,in order to identify overlapping communities in complex networks,this dissertation introduces the multi-objective optimization theory and proposes an overlapping community detection algorithm based on multi-objective evolutionary algorithm.In the proposed method,a new coding strategy for overlapping community structure is presented according to the topological features of edges in the network.Then,our method proposes two optimization objectives based on community fitness,which evaluate the compactness of overlapping community structure from different perspectives.At last,the proposed method formulates the problem of community detection as a multi-objective optimization problem and utilizes multi-objective genetic algorithm(MOGA)to solve this optimization problem and reveal the overlapping community structure in the network.Fourth,in order to identify hierarchical community structure in complex network,this dissertation proposes a community clustering algorithm based on label propagation by combing the techniques of hierarchical clustering and label propagation.This method identifies some specific cliques as the seeds of label propagation,and expands these seeds to reveal the lowest level of hierarchical community structure by multi-label propagation strategy.Then,on the basis of the lowest-level community structure,different pairs of communities are repeatedly merged according to specific similarity measure.Finally,a hierarchical tree of the communities in the network is built up.This proposed method exhibits near linear time complexity,which makes it applicable to large-scale networks.Finally,starting from the information propagation process,this dissertation makes an analysis on the relationship between the significance of community structure and information propagation characteristics of complex network under independent cascade model and linear threshold model.Moreover,on the basis of this analysis,this dissertation also proposes an influence maximization method based on label propagation to solve the influence maximization problem.This method uses the label propagation process to find the core nodes in different communities and takes these core nodes as the initial active nodes of information propagation.Extensive experimental results showed that the proposed method can effectively maximize the influence scope of information propagation.