Community Detection Method Based On Label Propagation Algorithm And Centrality

With the emergence of complex network and enlarging of practical application,the theoretical research of complex networks has been widely concerned.Community structure and centrality feature are typical structural features in complex networks,and community structure is defined as the vertex can naturally form different groups,and each group equals a community.Community has a high density of convergence nature,that is,vertexes within one community are more closely linked.Contrarily,vertexes within different communities are not.Community structure,an important structural feature of complex networks,almost corresponds to functional modules.By detecting the community structure of the network,we can find the functional unit of the network,study the correspondence between structure and function,and predict the function of the network by community structure.In addition,studies have shown that community usually indicates some features of nodes or whole network that has not been shown.Therefore,the research of community-detection method is of great significance in both theory and practical application.Researchers have proposed a large number of community-detection algorithms,but many algorithms have high time complexity and can not be effectively applied to larger networks.Aiming at this problem,we first combine the frequent itemsets with the LPA algorithm,and propose an improved algorithm LPAFI.Secondly,we proposes CG algorithms and CD algorithms based on the definition of local centrality.LPAFI: This method is deterministic community-detection method,proposed based on LPA and frequent itemsets.LPAFI,firstly,constructs the transaction database by running the LPA algorithm several times and treating each result as a transaction.And then the conditional frequent itemsets is found from the transaction database by mining the frequent itemsets.Secondly,by merging the frequent itemsets,the ‘core communit',the majority of the community,is got.Finally,single community,each node without ‘core community',with the core community are for merger to get the final community structure.The community-detection method based on the centrality: Considering the definition of community structure,this method proposed a local central definition,that is,the community is made up by the vertex and its neighbors,and the local centrality is the ratio of the number of internal sides to the total number of sides.The local centrality has an important feature that the vertex with the smaller center value is is often in the community ‘edge'.CG algorithm is a centrality-gain algorithm.Firstly,this algorithm is aimed at getting the maximum central value by removing the edge connected to the vertex repeatedly,which will divide the network into small community,and then finds unstable communities from a small community and divides them into smaller.Finally,the small community will be merged to get the final community structure;CD algorithm is a centrality-disturbance algorithm.Firstly,this algorithm finds vertex with less ‘contribution' and removes the edge between them continuously,which will divide the network into small community,and then finds unstable communities from a small community and divides them into smaller.Finally,the small community will be merged to get the final community structure.In order to verify the performance of the method proposed in this paper,the experiments were carried out on seven networks.The experimental results show that the method proposed in this paper can quickly detect the high quality community structure.