The Three-way Decision Based Community Detection

The community structure is an important topological characteristic of the complex network.It formed by the vertexes with similar interest and hobby,and the internal connections of community are intensive while the external connections are extensive.The study about community has great theoretical significance and practical application value.It not only can help to understand the formation mechanism and internal structure of complex network,but also can help to find the common preference and behavior about vertices.Community detection problem has become a research hotspot in the field of complex networks analysis.In recent years,researchers have done a lot of work on it and many community detection methods have been proposed.This paper mainly uses the three-way decision model to decide the vesting relationship between communities and then to detect the non-overlapping community and the overlapping community in the complex network.The main work is as follows:1)To define the vesting relationship between communities,and divided them into three types:completely belong relation,completely not belong relation and incompletely belong relation.The positive domain,negative domain and boundary domain of three-way decision can clearly describe those vesting relationship.This is,we use the positive domain,negative domain and boundary domain to reflect the completely belong relation,completely not belong relation and incompletely belong relation respectively.We define the similarity between vertices and the similarity between communities,and use the similarity between communities to quantify the conditional probability when two communities have the vesting relationship.2)We use the increment values of modularity Q function to reflect the inclusion ratio thresholds a and ?.That is,a is the maximum value of the increments of Q function,and ? is the minimum value of the increments of Q function,thus we can get the value of a and ? automatically.Based those,we propose the three-way decision based non-overlapping community detection algorithm(CD-TWD).This algorithm uses the three-way decision model to decide the vesting relationship between communities and then to detect community structure by merging from down to up the iteratively.When the vesting relationship between two communities is completely belong relation,then merge them;when the vesting relationship is completely not belong relation or incompletely belong relation,then do nothing.3)Based on the work of the before,when the similarity between communities is less than a and greater than ?,there exist some overlapping vertices between communities.We define the membership ratio between vertex and community,and propose the overlapping vertex detection algorithm(ONDA)to detect overlapping vertex.To detect overlapping community,we use the increment values of extended modularity EQ function to reflect the inclusion ratio thresholds a and ?.That is,a is the maximum value of the increments of EQ function,and ? is the minimum value of the increments of EQ function.Then we propose the three-way decision based overlapping community detection algorithm(OCD-TWD)to detect the overlapping community structure in complex network.