Research On Problems Of Role Based Community Detection And Community Evolution Prediction

Many real-world complex systems can be modeled as networks,such as epidemic networks,scientist collaboration networks,electric power transmission networks,metabolic networks,etc.A complex network is a topological abstraction composed of nodes and edges,in which nodes represent subjects in a complex system and edges represent relations or interactions between subjects.The community structure of a network is the tendency for nodes to be assembled into groups,or communities,which are densely connected inside and loosely connected with the rest of the network.Community detection,which aim to reveal hidden community structure in networks,have contributed to analysis of network structure,inference of network function,and optimization of network topology;It also provide guidance to identification,construction,and prediction of real-world network structrue.Generally speaking,it is the key of comprehensive insight into the organizational structures and functional behaviors of network structrue.Consequently,detecting hidden community structure in networks rapidly and accurately has attracted significant attention.And on the basis of detected community structure,using data mining approach to reveal intresting knowledge is another significant topic in both fields of research and application.In this dissertation,our work focuses on community detection and community evolution prediction,and our main contributions are as follows:(1)To improve the poor robustness and stability of label propagation algorithm,an improved algorithm named role-based label propagation algorithm(RLPA)is proposed.Label propagation algorithm is famous for its prominent speed,accurateness,and easy implementation of parallelism.While the algorithm has poor robustness and stability due to the introduced randomness.And for a network with weak community structure,label propagation algorithm may produce a giant community,which dominate a big part of the network,making the solution trivial.We analysis the influence of community-oriented role on the process of propagation,we define a metric related to the roles as the node preference,and introduces local indicator for the updating order,to improve the robustness,stability,and the performance in the network with weak community structure.The results of experiments on multiple artificial and real-world networks show that RLPA effectively improves the accuracy of detection and inherits the speed advantage of the original algorithm.(2)As a static community detection algorithm,role-based label propagation algorithm cannot derive the results with temporal smoothness in dynamic networks.In order to solve this problem,an evolution community detection algorithm role-based evolutionary label propagation algorithm(RELPA)are proposed.The community revolution in real-world dynamic networks are continuous;there should not be significant difference between community structures of sequencial network snapshots.Based on static community detection algorithm RLPA,our algorithm combined previous community structure information to improve the temporal smoothness,and introduced evolutionary structural differences information as the weight of contribution of previous local community structure information to improve the accuracy.The results of experiments show that the RELPA algorithm can quickly and accurately detect evolutionary communities in dynamic networks.(3)For community evolution prediction in dynamic networks,a method named multi-length evolution chains ensemble(MECE)was proposed.Previous approach cannot extract multi-scale(microscopic,mesoscopic,and macroscopic)topology information effectively,and cannot take advantage of temporal infomation contained by multiple-length evolution chains.Our approach extracted both multi-scale structural features,temporal features,and behavior features of the communities,and in consequence as input of a modified ensemble classifier for multiple-length evolution chains.The results of experiments show that the MECE algorithm can effectively predict the community evolution trend in dynamic networks.