Research On Three-way Decision Community Detection Based On Variable Granularity

In real life,there are all kinds of complex systems,and they can all be represented by different complex networks,such as the World Wide Web,social networks,and urban road transportation networks.In these complex networks,there is an important structural characteristic,that is the community structure.Community structure refers to the network is composed of multiple communities,the nodes within the community are closely connected and the nodes between the communities are sparsely connected.Mining the community structure in complex networks is of great significance for the research and analysis of complex networks.The community structure in a complex network can be divided into overlapping community structure and non-overlapping community structure according to whether the community contains overlapping nodes.Compared with the overlapping community structure,the non-overlapping community structure is more helpful in analyzing the potential laws and function of the network in some practical applications.Therefore,the discovery of non-overlapping community structure has important practical significance and application value.Since overlapping communities often appear in the process of community detection,it is necessary to effectively divide the overlapping parts of the community in order to obtain a non-overlapping community structure.Three-way decision(TWD)provides ideas for solving uncertain problems.It expands the traditional two-way decision theory.Compared with the traditional two-way decision,the three-way decision adds the third non-commitment decision(or delayed decision)as the decision-making behavior when the information is insufficient to make the acceptance or rejection decision.A discourse domain is divided into three parts: positive region,negative region,and boundary region according to three-way decision theory.The objects in the positive region take the acceptance decision,the objects in the negative region take the rejection decision,and the objects in the boundary region take the delayed decision.For the objects in the boundary region,the final decision is made after obtaining enough information.The decision-making method of the three-way decision is more in line with human decision-making models,which has a good applicability in real life,such as medical diagnosis,text classification,and email information filtering.In recent years,some non-overlapping community detection algorithms based on three-way decision have been proposed.This method has advantages in dealing with overlapping communities,but there are still two problems which are the merger of communities in the process of hierarchical clustering and the division of nodes in the boundary region.In order to solve these two problems,this dissertation proposes a three-way decision community detection method based on variable granularity.The main work of this dissertation is as follows:1.In order to solve the problem of merging communities in the process of hierarchical clustering,this dissertation proposes a community detection method(VGHC)based on variable granularity hierarchical clustering.This method first uses variable granular hierarchical clustering to build a hierarchical structure,and then selects the target layer based on the expanded modularity.According to the three-way decision theory,three definitions are made for overlapping communities in the target layer,that is,the non-overlapping part of the community is defined as a positive or negative region,and the overlapping part of the community is defined as a boundary region.Then the nodes in the boundary region are divided by using the local modularity optimization method,and finally the non-overlapping community detection is realized.Experimental results on public datasets show that this method can obtain better layering effect,and the quality of the obtained non-overlapping community structure is higher.2.In order to solve the problem of dividing the nodes in boundary region,this dissertation proposes a community detection method based on random walk boundary region processing.This method includes random walk and weighted random walk to effectively divide the boundary region part,respectively.They are the three-way decision community detection algorithm based on random walk(RW-TWD)and the three-way decision community detection algorithm based on weighted graph representation(WGR-TWD).For the RW-TWD algorithm,first the target layer is obtained according to the VGHC algorithm.Then,on the target layer,the three-way decision ideas are combined to divide the nodes in the boundary region by using the random walk algorithm to obtain the final non-overlapping community structure.For the WGR-TWD algorithm,first the target layer is obtained according to the VGHC algorithm,and then weights are added to the edges of the network according to the community division information of the target layer,and the weighted network is embedded to obtain a vector representation of all nodes in the network.On the target layer,the three-way decision ideas are combined to divide the nodes in the boundary region using cosine similarity to obtain a non-overlapping community structure.Experimental results show that the two proposed algorithms have achieved good performance.