Research On Algorithms Of Community Structure Detection Based On Neighborhood

Community structure is a very important attribute. More and more scholars have been addicted to the studies of community structure detection algorithm from biology, sociology and other disciplines. Some methods have been proposed to discover community structure in complex network, but these algorithms have a lot of deficiency in aspect of time efficiency and accuracy. This paper proposed two novel algorithms based on the relationship between neighbors. The main content for this paper have been done as following:(1) Some single node partition effect assessments are given on the base of some community structure partition strategy:strong community structure node, weak community structure node, ambiguous community structure node and error-community structure node. The theoretical principle of these assessments are the definitions of strong community structure and weak community structure, which have great use for reference to a kind of partitioning to a network.(2) An advanced clique finding algorithm is proposed, which begins with the minimum-degree node, if there is a clique to found then delete corresponding edges related to the node; select the clique in descend order to compose community or add nodes into the community. Some simulations have been made on several real networks, and make an analysis about the obtained experiment results. The results display that our algorithm has a higher time efficiency and lower space resource demand than existing algorithms, and has better results on partitioning community structures.(3) A community structure detection algorithm based on dependence degree between nodes is proposed. Some dependence degrees are calculated including dependence degree between nodes and node, the dependence degree between node and community, and the conditional dependence degree between node and community. Besides, the detailed implementation process and some simulations for several real networks have been made; an analysis about the obtained experiment results have been given, this algorithm reaches a rather high standard on time complexity and has very good results on partitioning community structures.The research is jointly supported by the National Natural Science Foundation of China (Nos:61370145,61173183, and60973152), the Doctoral Program Foundation of Institution of Higher Education of China (No:20070141014), Program for Liaoning Excellent Talents in University (No:LR2012003), the National Natural Science Foundation of Liaoning province (No:20082165) and the Fundamental Research Funds for the Central Universities (No: DUT12JB06).