Detecting Communities In Complex Networks Based On Propagation Dynamics

Network science has brought significant advances to our understanding of various complex systems in real life.Real-world networks exhibit substantial non-trivial topolog-ical features such as heavy-tailed degree distributions,high clustering coefficients,assor-tativity or disassortativity among vertices,community structure,and hierarchical organi-zation.Community structure,one of the most prominent features of complex networks,is defined as the organization of nodes in groups,with many connections within groups and comparatively few connections between groups.Detecting community structure is of great significance in disciplines such as sociology,biology and computer science,which has attracted the attention of many different fields.This dissertation first introduces the basic concepts and detection methods of commu-nity detection,then discusses the significance of clustering and how methods should be tested and compared to each other,as well as the applications of community detection to real-world networks,by studying three kinds of methods based on diffusion process.Three innovative research results are as follows.1.We proposed a new community detection method named LPAf based on random walk and coding compression on networks.The central idea of LPAf is that if a network has a strong community structure,the average description length of the random walk will be greatly reduced if the nodes are encoded hierarchically according to the community structure.The average description length is a function of network partitioning.Given the network,the better division,the shorter average description length.By minimizing the av-erage description length during the label propagation process,communities can be detected accurately and effectively.We tested LPAf on both real-world and synthetic networks,and compared it to serveral other widely used methods,which indicates that LPAf has strong robustness,high accuracy and low time complexity.2.We proposed a multiresolution algorithm,MLPA,based on the idea that communi-ties could be detected from subnetworks by comparing the internal and external cohesion of each subnetwork.In our method,similar nodes are frstly gathered into meta-communities,which might or might not be merged through a multilevel label propagation process ac-cording to certain criterion.MLPA requires neither any priori information of communities nor optimization of any objective function.Experimental results on both synthetic and real-world networks show that,MLPA performs quite well and converges extremely fast,compared to several other popular algorithms.By tuning a resolution parameter,we can also observe communities at different scales,so this could reveal the hierarchical structure of the network.To further explore the effectiveness of MLPA,we applied it to the E-Coli transcriptional regulatory network,and found that all the identifed modules have strong structural and functional coherence.3.We proposed an efficient dynamic community detection method based on local diffusion dynamics.Many real-world networks are evolving.Previous methods treated the network as a static one which is derived from aggregating data during a long period of time,which may result in the loss of evolutionary information of the network and its communities.If one would like to monitor the communities of a network in real time,the static methods are usually time-consuming as they have to compute the whole community decomposition even if a very small modification of the network occurs,especially when the network evolves rapidly.In order to detect and monitor communities in dynamic net-works,we proposed a parameter-free and adaptive label propagation algorithm(ALPA).Unlike the traditional methods by re-computig the whole community decomposition after each modification of the network,ALPA takes into account the information of historical communities and updates its solution according to network modifications via a local label propagation process,which generally affects only a small portion of the network.This makes it respond to network changes at a low computational cost.We tested ALPA on both synthetic and real-world networks,which shows that it can sucessfully identify and track the dynamic communities.Moreover,compared to other methods,ALPA has higher accuracy and lower time complexity.