Research On Non-overlapping Community Division Based On Three-way Decision Theory

Many relationships in reality can be abstracted as different network forms such as social networks,collaboration networks,and technological networks and so on.Community structure is one of the most important structural feature in complex networks.Communities are formed by the nodes with similar functions or attributes,and the connections of inner-communities are closer while between which they are sparser.The process of dividing the nodes which have the close connection into together depending on relationship between nodes in the whole network is called community detection.According to whether all nodes belong to more than one community situation,the style of communities which have been divided can be classified into two categories of non-overlapping communities and overlapping communities.In specific application scenarios,non-overlapping communities are more helpful to reveal abundant hidden information and predict the functional properties and behaviors of the networks,such as product recommendation in E-commerce and precise delivery of the advertisement and so on.However,in the process of community detection,it is always emerge the overlapping communities.Therefore,how to divide the overlapping nodes into a single community to achieve non-overlapping communities has important application values and widespread prospects.Theory of three-way decisions(3WD)is an extension of the classic two-way decisions(2WD),with the different from the two-way decisions of acceptance or rejection,a third way of decision which named non-commitment is added,that is to say,the way of non-commitment will be chosen when people can't make a decision at once because of insufficient information,and it also can be called as deferment.In the theory of three-way decisions,the objects classified into the positive regions make decision of acceptance;the objects classified into the negative regions make decision of rejection;the objects classified into the boundary regions means that more detailed observations are needed to make the final decision,in other word,decision of deferment.Decision of deferment will achieve the final two-way decisions by introducing more detailed information to achieve second classification for the objects in the boundary regions,and make decision of acceptance or rejection further.The three-way decisions are one of the most commonly used strategies in dealing with practical decision-making problems in real life and are similar to the human's real decision cognition.Nowadays,it has been widely applied in many subjects and fields,especially suitable for the analysis and discrimination of uncertain and incomplete information,and such problems can be better analyzed and resolved by introducing decision of deferment.At present,many community detection algorithms have achieved nonoverlapping community detection from different perspectives and applied at different levels,and have also acquired some research achievements.In this dissertation,the non-overlapping communities obtained by the method of hierarchical granulation community detection.However,there are overlapping communities in the process of hierarchical granulation community detection,and the emergence of overlapping communities are due to the current overlapping node information is not enough to decide their attribution.Hence,the theory of three-way decisions theory is introduced into nonoverlapping community detection to deal with overlapping nodes problem.The main work of this dissertation is as follows:1.Firstly,in this dissertation briefly summarizes the significance,the domestic and international research status of non-overlapping community detection algorithms,and focuses on the analysis for the advantages and the existing problems in obtaining community structures based on hierarchical granulation.Then,we briefly summarize the proposition,the development and the application of the three-way decisions theory.And the significance of introducing the three-way decisions theory into the hierarchical granulation community detection to obtain the non-overlapping community structure is given.2.In order to solve the overlapping nodes in the process of hierarchical granulation,a Three-way Decisions Community Detection Algorithm based on the Degree of Belonging(DB-TWD)is proposed in this dissertation to get non-overlapping communities structure.The three-way decisions theory are introduced into the study of community detection in the algorithm.For the overlapping community's structure which appeared in the process of hierarchical clustering algorithm,the nodes in the non-overlapping parts of the community of the left side between two communities with overlapping parts were defined as positive regions,the nodes in its right as the negative regions and nodes in overlapping parts as boundary regions.Then,the belonging degree BP,BN between the positive region and negative region can be calculated respectively with the nodes in the boundary regions to achieve three-way division.After further division,the belonging of the rest nodes in the boundary region will be determined by voting to get non-overlapping community structure finally.The experiment results demonstrate that the proposed algorithm has better performance in dividing community and can get a higher modularity comparing with state-of-the-art algorithms.3.For solving the problems of initial nodes loosely connected by DB-TWD algorithm,we present a Three-way Decisions Community Detection Algorithm based on Local Sub-community Information(LSI-TWD)to detect community structure by using the local information of the nodes.In the strategy of initialization,sub-communities are constructed by the node v and v's neighbors which are reachable to each other.The structure information of the initial granules are fully taken into consideration so that the nodes in the same sub-communities which obtained by the initialization of local information are linked more closely and more conformable to reality.Then,based on the algorithm of hierarchical granulation community detection,overlapping nodes are divided by combining the theory of three-way decisions to get the non-overlapping communities which structure are more reasonable and the modularity are higher.