基于三支決策的非重疊社團(tuán)劃分

方蓮娣,張燕平,陳潔 ,王倩倩,劉峰,王剛

(1.安徽大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院， 安徽 合肥 230601；2.安徽大學(xué) 計(jì)算機(jī)智能與信號(hào)處理教育部重點(diǎn)實(shí)驗(yàn)室，安徽 合肥 230601； 3.安徽大學(xué) 國際商學(xué)院，安徽 合肥 230601)

基于三支決策的非重疊社團(tuán)劃分

方蓮娣1,2,張燕平1,2,陳潔1,2,王倩倩3,劉峰1,2,王剛1,2

(1.安徽大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院， 安徽 合肥 230601；2.安徽大學(xué) 計(jì)算機(jī)智能與信號(hào)處理教育部重點(diǎn)實(shí)驗(yàn)室，安徽 合肥 230601； 3.安徽大學(xué) 國際商學(xué)院，安徽 合肥 230601)

基于三支決策理論，提出了一種基于三支決策的非重疊社團(tuán)劃分算法(N-TWD), 該方法將初始聚類形成的重疊社團(tuán)進(jìn)行二次劃分以形成最終的非重疊社團(tuán)。N-TWD算法首先利用層次聚類形成有重疊的社團(tuán)結(jié)構(gòu)，將兩個(gè)存在重疊的社團(tuán)的左邊社團(tuán)中非重疊部分定義為正域，右邊社團(tuán)中非重疊部分定義為負(fù)域，而兩個(gè)社團(tuán)的重疊部分定義為邊界域。然后，針對(duì)邊界域中的節(jié)點(diǎn)，分別計(jì)算邊界域中節(jié)點(diǎn)與正域和負(fù)域的社團(tuán)歸屬度BP、BN進(jìn)行二次劃分。對(duì)于二次劃分后仍然留在邊界域中的節(jié)點(diǎn)將利用投票的方法決定其最終歸屬，最終獲得非重疊的社團(tuán)結(jié)構(gòu)。本文選取4個(gè)經(jīng)典社交網(wǎng)絡(luò)數(shù)據(jù)集和1個(gè)真實(shí)世界數(shù)據(jù)集對(duì)N-TWD算法進(jìn)行了驗(yàn)證，相比較其他社團(tuán)劃分算法(GN、NFA、LPA、CACDA)，N-TWD時(shí)間復(fù)雜度較低，總體獲取的社團(tuán)模塊度值更高。

復(fù)雜網(wǎng)絡(luò)；社團(tuán)劃分；重疊節(jié)點(diǎn)；三支決策理論；粒化系數(shù)；層次聚類；社團(tuán)結(jié)構(gòu)；節(jié)點(diǎn)歸屬度

中文引用格式：方蓮娣,張燕平，陳潔，等. 基于三支決策的非重疊社團(tuán)劃分[J]. 智能系統(tǒng)學(xué)報(bào)， 2017, 12(3): 293-300.

英文引用格式：FANG Liandi， ZHANG Yanping， CHEN Jie， et al. Three-way decision based on non-overlapping community division[J]. CAAI transactions on intelligent systems, 2017, 12(3): 293-300.

在現(xiàn)實(shí)世界中，很多事物的聯(lián)系都是以網(wǎng)絡(luò)的形式存在的。例如，互聯(lián)網(wǎng)中的社交網(wǎng)絡(luò)，社會(huì)系統(tǒng)中的人際關(guān)系網(wǎng)，生態(tài)系統(tǒng)中的神經(jīng)元網(wǎng)和蛋白質(zhì)交互網(wǎng)。大量的研究表明，許多實(shí)際網(wǎng)絡(luò)中都存在著社團(tuán)結(jié)構(gòu)[1-2]。社團(tuán)將網(wǎng)絡(luò)中具有緊密聯(lián)系的事物劃分在一起，每個(gè)社團(tuán)內(nèi)部的節(jié)點(diǎn)之間連接相對(duì)緊密而社團(tuán)之間的連接比較稀疏[3]。研究網(wǎng)絡(luò)中的社團(tuán)結(jié)構(gòu)具有重要意義。如何有效地進(jìn)行社團(tuán)劃分，成為了社團(tuán)研究者們一直致力于研究的一個(gè)重要方向之一。近年來，許多學(xué)者分別從不同角度對(duì)社團(tuán)進(jìn)行劃分研究，其中著名的算法有Kernighan-Lin 算法[4]、譜平分法[5-6]和 GN算法[7]等。隨著研究的深入，人們發(fā)現(xiàn)在進(jìn)行社團(tuán)劃分時(shí)經(jīng)常會(huì)出現(xiàn)重疊部分，即一個(gè)節(jié)點(diǎn)被多個(gè)社團(tuán)包含。因?qū)嶋H需要將重疊節(jié)點(diǎn)劃分到單個(gè)社團(tuán)中，更有助于發(fā)現(xiàn)社團(tuán)內(nèi)存在的規(guī)律，并預(yù)測(cè)網(wǎng)絡(luò)的行為和功能[8]。因此，對(duì)于非重疊社團(tuán)劃分的研究，也是十分必要的。

對(duì)于非重疊社團(tuán)劃分的研究也引起了很多學(xué)者的關(guān)注和研究。Newman快速算法(newman fast algorithm,NFA)[9]依靠模塊度獲得最優(yōu)社團(tuán)結(jié)構(gòu)；Radicchi等[10]提出了自包含GN 算法(self-contained GN algorithm)，給出了強(qiáng)社團(tuán)和弱社團(tuán)結(jié)構(gòu)兩種量的定義，為如何確定社團(tuán)結(jié)構(gòu)提供了一種衡量標(biāo)準(zhǔn)；趙姝等[11]將粒計(jì)算思想引入到網(wǎng)絡(luò)的社團(tuán)劃分中，通過對(duì)網(wǎng)絡(luò)結(jié)構(gòu)的聚類粒化實(shí)現(xiàn)社團(tuán)劃分，其時(shí)間復(fù)雜度低、收斂速度快、精確度高，實(shí)現(xiàn)了時(shí)間復(fù)雜度與精確度之間的平衡。這些現(xiàn)有的非重疊社團(tuán)劃分算法從不同的角度和應(yīng)用層面對(duì)非重疊社團(tuán)的劃分進(jìn)行了研究，并取得了豐碩的研究成果。但這些算法對(duì)重疊部分處理時(shí)都只應(yīng)用了傳統(tǒng)的二支決策[12-13]方法，即根據(jù)已有的信息只做出接受或拒絕決策。但重疊部分的節(jié)點(diǎn)往往因?yàn)樾畔⒘坎粔驘o法決定其歸屬，才會(huì)出現(xiàn)在重疊部分，如果強(qiáng)制做出決策，可能影響最終非重疊社團(tuán)劃分的結(jié)果。三支決策對(duì)于處理那些不確定信息具有一定的實(shí)用性[14-19]。當(dāng)信息不足時(shí)，三支決策理論對(duì)不確定性問題首先做三分類，即正域、負(fù)域、邊界域；再通過進(jìn)一步觀察，獲得足夠的信息，將邊界域的對(duì)象進(jìn)行二次劃分，實(shí)現(xiàn)最終的二支決策。本文在文獻(xiàn)[11]的基礎(chǔ)上，引入三支決策思想[20]，改進(jìn)了對(duì)于重疊部分的處理方法，提出了一種基于三支決策的非重疊劃分算法(three-way decision based on non-overlapping community division，N-TWD)，以劃分出更合理的非重疊社團(tuán)。以劃分出更合理的非重疊社團(tuán)。該算法首先將兩個(gè)存在重疊部分的社團(tuán)的左邊社團(tuán)非重疊部分定義為正域，右邊社團(tuán)的非重疊部分定義為負(fù)域，而兩個(gè)社團(tuán)的重疊部分定義為邊界域，分別計(jì)算邊界域中的節(jié)點(diǎn)與正域和負(fù)域的社團(tuán)歸屬度BP、BN,依據(jù)兩者的差值進(jìn)行二次劃分。對(duì)于二次劃分后仍然留在邊界域中的節(jié)點(diǎn)將利用投票的方法決定其最終歸屬，最終獲得非重疊的社團(tuán)結(jié)構(gòu)。

N-TWD算法對(duì)于社團(tuán)重疊部分(邊界域)獲取了節(jié)點(diǎn)，與已明確劃分的社團(tuán)(正域/負(fù)域)之間的緊密關(guān)系依次進(jìn)行劃分，而不僅僅只根據(jù)鄰居數(shù)目進(jìn)行投票，更好地體現(xiàn)了節(jié)點(diǎn)的真實(shí)歸屬。本文采用4個(gè)真實(shí)的社交網(wǎng)絡(luò)數(shù)據(jù)集和1個(gè)真實(shí)數(shù)據(jù)集對(duì)N-TWD算法進(jìn)行了驗(yàn)證，實(shí)驗(yàn)結(jié)果證明了三支決策方法對(duì)部分重疊節(jié)點(diǎn)處理的可行性和有效性。

1 相關(guān)工作

1.1 三支決策理論

三支決策理論對(duì)于現(xiàn)實(shí)世界中的不確定信息決策問題的解決具有高效性，尤其對(duì)那些信息缺失、證據(jù)不充分或者不完整的情況。這時(shí)，由于信息不精確、不一致、不完整等原因，無法立即做出接受或拒絕的決策。于是，可以采用一種延遲決策或邊界決策，即不做任何承諾的決策。正常情況下，當(dāng)證據(jù)變得足夠或者完備時(shí)，就有可能進(jìn)一步做出正決策或負(fù)決策。

三支決策的主要思想是將整體分為3個(gè)獨(dú)立的部分：正域、負(fù)域、邊界域。對(duì)不同的部分采取不同的處理方法，為求解復(fù)雜問題提供了一種有效的策略與方法[15]。

當(dāng)前，三支決策的研究主要基于決策粗糙集，整個(gè)論域被劃分成3個(gè)部分，即正域(POS)、負(fù)域(NEG)和邊界域(BND)，分別代表著接受、拒絕和不承諾3種決策結(jié)果。決策粗糙集模型理論(decision-theoretic rough set model, DTRS)，是由姚一豫等在1990年提出[21-23]。它將概率粗糙集和最小風(fēng)險(xiǎn)貝葉斯決策結(jié)合起來，通過計(jì)算各類分類決策風(fēng)險(xiǎn)損失值，對(duì)正域(POS)、負(fù)域(NEG)和邊界域(BND)進(jìn)行劃分。假設(shè)有兩種狀態(tài)的集合Ω={X,X},X和X是互補(bǔ)關(guān)系的兩種狀態(tài)，即對(duì)象屬于X或者屬于X。由于分類結(jié)果有3個(gè)域，給定決策集A=(P,B,N)，其中P、B、N分別表示將對(duì)象劃分到正域、負(fù)域、邊界域的決策行為。由于采取不同決策行為會(huì)產(chǎn)生不同的損失，λPP、λBP、λNP分別代表當(dāng)x屬于X時(shí)，x被劃分到正域、負(fù)域、邊界域的損失；λPN、λBN、λNN則分別代表當(dāng)x不屬于X時(shí)，x被劃分到正域、負(fù)域、邊界域的損失。表1為對(duì)應(yīng)的決策損失矩陣。

表1 3種決策的損失矩陣

根據(jù)Bayes決策過程的推導(dǎo)，通過引入?yún)?shù)α、β可得到基于決策粗糙集的三支決策規(guī)則。

其中

1.2 重疊社團(tuán)中的3個(gè)域

本文基于三支決策的思想，實(shí)現(xiàn)對(duì)網(wǎng)絡(luò)的非重疊社團(tuán)結(jié)構(gòu)劃分。對(duì)于初始聚類?；螳@得重疊的社團(tuán)結(jié)構(gòu)定義如下。

1)正域 (POS)：左邊社團(tuán)的非重疊節(jié)點(diǎn)。

2)負(fù)域 (NEG)：右邊社團(tuán)的非重疊節(jié)點(diǎn)。

3)邊界域 (BND)：重疊部分的節(jié)點(diǎn)。

其中，正域與負(fù)域僅僅為相對(duì)的概念，也可將邊界域的左邊定義為負(fù)域，右邊定義為正域。本文為敘述方便，只將左邊稱為正域，右邊稱為負(fù)域。

圖1 重疊社團(tuán)3個(gè)域的劃分Fig.1 The division of three domains in overlapping community

1.3 社團(tuán)評(píng)價(jià)標(biāo)準(zhǔn)

本文采用與文獻(xiàn)[11]相同的聚類?；枷脒M(jìn)行初始社團(tuán)劃分，形成重疊的社團(tuán)結(jié)構(gòu)。算法中以?；禂?shù)為閾值控制合成過程，并選取模塊度函數(shù)Q對(duì)劃分結(jié)果進(jìn)行評(píng)價(jià)，現(xiàn)將?；禂?shù)和模塊度概念介紹如下。

?；禂?shù)f(C) 是判斷是否對(duì)社團(tuán)進(jìn)行聚類粒化的一個(gè)標(biāo)準(zhǔn)，其公式如下：

?；禂?shù)

式中：Ci,Cj?C,BND=Ci∩Cj,POS=Ci-BND,NEG=Cj-BND;C是粒化到當(dāng)前的粒集合;?BND」表示兩個(gè)粒集合中相同節(jié)點(diǎn)的個(gè)數(shù)；?POS+NEG+BND」表示正域、負(fù)域和邊界域中所有不同節(jié)點(diǎn)的個(gè)數(shù)。

模塊度函數(shù)Q[24]模塊度函數(shù)Q是由Newman和Girvan提出的，在社交網(wǎng)絡(luò)中，它是衡量一個(gè)非重疊社團(tuán)劃分好壞的量化指標(biāo)。目前，模塊度函數(shù)Q作為社團(tuán)劃分評(píng)價(jià)標(biāo)準(zhǔn)已經(jīng)被廣泛使用。其定義如下：

2 基于三支決策的非重疊社團(tuán)劃分算法

三支決策模型根據(jù)正域、負(fù)域和邊界域獲取決策規(guī)則，在處理模糊性、不完整性數(shù)據(jù)時(shí)，可以給出不承諾規(guī)則，能夠降低誤判[25],提高決策正確性。對(duì)于社團(tuán)劃分，邊界域的存在是暫時(shí)的，隨著獲取信息的增多，對(duì)邊界域中對(duì)象的認(rèn)識(shí)更加細(xì)化，最終的劃分必須是明確的，即正域和負(fù)域。為了劃分邊界域中節(jié)點(diǎn)的歸屬問題，本文基于三支決策理論，計(jì)算邊界域節(jié)點(diǎn)的社團(tuán)歸屬度，增加新的信息進(jìn)行二次決策，提出一種基于三支決策的非重疊社團(tuán)劃分算法。

2.1 節(jié)點(diǎn)相似度與社團(tuán)歸屬度

為了評(píng)價(jià)邊界域中的節(jié)點(diǎn)與正域、負(fù)域間的歸屬關(guān)系，給出如下定義。

定義2 邊界域中節(jié)點(diǎn)v與正域、負(fù)域間的歸屬度。由于邊界域節(jié)點(diǎn)與正域(負(fù)域)間的歸屬度反映了該域節(jié)點(diǎn)與正域(負(fù)域)連接的緊密程度，歸屬度越大，說明它們之間連接越緊密，更有可能被劃分到正域(負(fù)域)中。邊界域中節(jié)點(diǎn)與正域、負(fù)域之間的歸屬度分別表示為

根據(jù)式(11)～(13)可將邊界域參數(shù)映射到[0,1]區(qū)間。將邊界域中的節(jié)點(diǎn)進(jìn)一步劃分到正域或負(fù)域中。如圖2所示，通過分別計(jì)算邊界域中節(jié)點(diǎn)9、10與正域(負(fù)域)的歸屬度及其差值，即

BP9=0.11,BN9=0.05;

BP9-BN9=0.11-0.05=0.06;

BN9-BP9=0.05-0.11=-0.06;

BP10=0.12,BN10=0.09;

BP10-BN10=0.12-0.09=0.03;

BN10-BP10=0.09-0.12=-0.03;

圖2 計(jì)算歸屬度后3個(gè)域的劃分Fig.2 The division of three domains after calculation of belonging degree

2.2 算法流程描述

算法1 N-TWD算法。

2)計(jì)算邊界域中節(jié)點(diǎn)與正域、負(fù)域中的社團(tuán)的歸屬度BP和BN：

end while

3)在2)完成后，對(duì)于仍然留在邊界域中的節(jié)點(diǎn)進(jìn)行投票處理：

3 實(shí)驗(yàn)分析

3.1 基準(zhǔn)數(shù)據(jù)實(shí)驗(yàn)

為了驗(yàn)證N-TWD算法的有效性和可行性，本文采用了4個(gè)典型社交網(wǎng)絡(luò)數(shù)據(jù)集作為測(cè)試數(shù)據(jù)集，分別是著名的空手道俱樂部網(wǎng)絡(luò)(Zachary’s karate club)、足球聯(lián)盟網(wǎng)絡(luò)(American college football)、海豚網(wǎng)絡(luò)(dolphin social network) 和悲慘世界網(wǎng)絡(luò)(lesmis)。實(shí)驗(yàn)數(shù)據(jù)集的基本信息如表2。

表2 實(shí)驗(yàn)數(shù)據(jù)集的基本信息

在N-TWD算法中，?；瘏?shù)λ、邊界域參數(shù)γ的取值對(duì)算法的最終結(jié)果有一定的影響。參數(shù)λ作為粒化系數(shù)，控制著初始社團(tuán)粒度，對(duì)于最終的社團(tuán)劃分好壞有一定的影響。若λ為1，則任意兩粒子都不滿足粒化條件，算法無法進(jìn)行粒化操作迭代，直接按投票法獲得最終的社團(tuán)結(jié)構(gòu)；若λ為0，則任意兩粒子之間均可進(jìn)行粒化操作，迭代后所得到的粒子包含了所有網(wǎng)絡(luò)的節(jié)點(diǎn)，即該網(wǎng)絡(luò)可視為一個(gè)社團(tuán)。參數(shù)γ作為邊界域參數(shù)，它的大小決定投票和歸屬度這兩種方法對(duì)邊界域中節(jié)點(diǎn)處理的多少。γ為1時(shí)，則邊界域中的節(jié)點(diǎn)采用全投票法，等同于文獻(xiàn)[11]所提算法；γ為0時(shí)，則邊界域中的節(jié)點(diǎn)采用全歸屬度方法處理。圖3給出了在不同數(shù)據(jù)集上γ取得最優(yōu)值時(shí)Q值隨參數(shù)λ值變化的關(guān)系圖。其中，γ=1表示完全采用投票處理邊界域中的節(jié)點(diǎn)；γ=0表示完全使用歸屬度處理邊界域中的節(jié)點(diǎn)；γ≠0表示對(duì)邊界域中的節(jié)點(diǎn)先采用歸屬度處理后，對(duì)于仍留在邊界域中的節(jié)點(diǎn)采用投票法處理。從圖3中(a)、(b)、(d)明顯可以看出，隨著λ的增大,折線λ≠0基本都在折線λ=0和γ=1上方。圖3中(c)圖,由于dolphin數(shù)據(jù)集自身網(wǎng)絡(luò)特別稀疏，在層次聚類粒化的過程中獲得的重疊部分較少，所以使用本算法劃分后效果不明顯?？傮w上，即當(dāng)γ≠0時(shí)，在4個(gè)數(shù)據(jù)集上社團(tuán)劃分評(píng)價(jià)指標(biāo)Q的值都基本優(yōu)于γ=0和γ=1時(shí)的值，此時(shí)劃分后的社團(tuán)內(nèi)部聯(lián)系比較緊密，說明采用三支決策的方法對(duì)邊界域中重疊節(jié)點(diǎn)進(jìn)行二步?jīng)Q策對(duì)社團(tuán)劃分有明顯的作用，使社團(tuán)劃分更加合理。

(a)karate數(shù)據(jù)集

(b)football數(shù)據(jù)集

(c)dolphin數(shù)據(jù)集

(d)lesmis數(shù)據(jù)集圖3 Q值與λ值關(guān)系圖 Fig.3 The connection between λ and Q

圖4 γ值與Q值關(guān)系圖Fig.4 The connection between γ and Q

作者將本文算法與其他相關(guān)社團(tuán)劃分算法(GN、NFA、LPA、CACDA)在4個(gè)真實(shí)的網(wǎng)絡(luò)數(shù)據(jù)集上的模塊度Q值進(jìn)行了對(duì)比，實(shí)驗(yàn)結(jié)果如表3所示。其中，GN[7]為經(jīng)典的分裂式層次社團(tuán)挖掘算法,NFA[9]為Newman快速算法，是基于模塊度優(yōu)化的凝聚式社團(tuán)挖掘算法,LPA[27]為快速標(biāo)簽傳播算法,CACDA[11]為基于鄰接?；纳鐖F(tuán)發(fā)現(xiàn)算法。

表3 數(shù)據(jù)集中不同算法Q值的比較Table 3 Comparison of Q by different algorithm in datasets

表3給出了N-TWD算法與其他相關(guān)算法劃分后最優(yōu)的模塊度值的對(duì)比實(shí)驗(yàn)結(jié)果。從表3中可以看出，本文提出的算法N-TWD在karate和lesmis、football上都獲得了最高的模塊度值，在dolphin上也獲得了較高的模塊度值。CACDA 在football上獲得了最高的模塊度值，但沒能在其他網(wǎng)絡(luò)上獲取較高的模塊度值。由于本文算法和CACDA算法的主要開銷在于進(jìn)行?；?，需要遍歷鄰接矩陣的每行(每列)，其時(shí)間復(fù)雜度均為O(n2)。GN雖然在數(shù)據(jù)集dolphin上取得最高的Q值，但是它的時(shí)間復(fù)雜度是這5種算法中最高的，為O(n3)。NFA雖然在dolphin獲得了第2高模塊度值，但由于NFA本身是貪婪尋優(yōu)算法，所以可以獲得很高的模塊度算法，且NFA需要非常多的時(shí)間進(jìn)行迭代，其時(shí)間復(fù)雜度為O((m+n)n)。LPA的線性復(fù)雜度為O(m+n)。從表3中可以看出，本文提出的算法相比其他4個(gè)算法，時(shí)間復(fù)雜度較低，獲取的社團(tuán)模塊度值總體上更高，總體性能更優(yōu)。

3.2 應(yīng)用數(shù)據(jù)實(shí)驗(yàn)

為了進(jìn)一步驗(yàn)證本文所提出的N-TWD算法的有效性，本文以某市移動(dòng)通信的實(shí)際應(yīng)用數(shù)據(jù)為例進(jìn)行實(shí)驗(yàn)。實(shí)驗(yàn)數(shù)據(jù)根據(jù)通信基站間是否有信號(hào)切換確定兩基站節(jié)點(diǎn)間是否存在邊來構(gòu)建網(wǎng)絡(luò)模型。構(gòu)建的無權(quán)無向網(wǎng)絡(luò)如圖5所示，其中包含3 644個(gè)頂點(diǎn)，6 976條邊。

圖5 無權(quán)無向網(wǎng)絡(luò)Fig.5 A unweighted and undirected network

將圖5所示的網(wǎng)絡(luò)采用本文N-TWD算法進(jìn)行社團(tuán)劃分，圖6給出了在真實(shí)數(shù)據(jù)集上Q值與λ值的關(guān)系圖。從圖6可以看出，在真實(shí)數(shù)據(jù)集網(wǎng)絡(luò)中，對(duì)于劃分到邊界域中的重疊節(jié)點(diǎn)，采用本算法進(jìn)行社團(tuán)劃分依然具有有效性。圖6中虛折線表示N-TWD算法處理后社團(tuán)模塊度的變化趨勢(shì)，正方形實(shí)折線和圓形實(shí)折線分別表示僅采用投票和僅采用歸屬度處理情況下的模塊度變化趨勢(shì)。圖6中隨著λ的變化，γ取得最優(yōu)值時(shí)(γ=0.03)能比投票(γ=0.2)和歸屬度方法(γ=0)直接決策取得更高Q值，采用和文獻(xiàn)[11]相同的干擾模型評(píng)價(jià)可以得到更優(yōu)的頻點(diǎn)干擾值。表明在N-TWD算法劃分下可以更真實(shí)地體現(xiàn)應(yīng)用數(shù)據(jù)集中的網(wǎng)絡(luò)結(jié)構(gòu)特征。

圖6 真實(shí)數(shù)據(jù)集中Q值與λ值關(guān)系圖Fig.6 The connection between λ and Q of true dataset

4 結(jié)束語

本文將三支決策的思想應(yīng)用于非重疊社團(tuán)劃分，提出了一種基于三支決策的非重疊社團(tuán)劃分算法(N-TWD)，旨在解決社團(tuán)劃分過程中出現(xiàn)的節(jié)點(diǎn)重疊部分。本文算法基于三支決策的思想，對(duì)于社團(tuán)重疊部分(邊界域)通過計(jì)算節(jié)點(diǎn)與明確社團(tuán)(正域/負(fù)域)間的歸屬度，再對(duì)重疊節(jié)點(diǎn)的具體歸屬進(jìn)行二次決策，從而進(jìn)行三分類，即正域、負(fù)域、待處理(仍留在邊界域)，對(duì)于待處理部分采取鄰居節(jié)點(diǎn)投票法進(jìn)行再一次決策，最終將其準(zhǔn)確劃分到正域或負(fù)域中。與其他算法相比，本文算法隨著決策步驟的增加，對(duì)邊界域中樣本的歸屬認(rèn)知更加細(xì)化，時(shí)間復(fù)雜度總體較低，且獲取了更高的Q值，劃分后的社團(tuán)結(jié)構(gòu)聯(lián)系比較緊密，說明邊界域中的重疊節(jié)點(diǎn)得到了更為穩(wěn)定的劃分。下一步將會(huì)基于網(wǎng)絡(luò)的局部信息，進(jìn)一步改進(jìn)初始重疊社團(tuán)的獲取方法。

[1]SHEN H, CHENG X, CAI K, et al. Detect overlapping and hierarchical community structure in networks[J]. Physica a: statistical mechanics and its applications, 2009, 388(8): 1706-1712.

[2]LIU Y, PAN L, JIA X, et al. Three-way decision based overlapping community detection[C]//Rough Sets and Knowledge Technology. Springer, Berlin , 2013: 279-290.

[3]柯望. 基于層次?；纳鐖F(tuán)發(fā)現(xiàn)方法研究[D]. 合肥： 安徽大學(xué), 2016. KE Wang. Reach on community detection algorithm based on Hierarchical Granulation[D]. Hefei: Anhui University, 2016.

[4]KERNIGHAN B W, LIN S. An efficient heuristic procedure for partitioning graphs[J]. The bell system technical journal, 1970, 49(2): 291-307.

[5]ZHANG Y P, WANG Y. Detecting communities using spectral bisection method based on normal matrix[J]. Computer engineering and applications, 2006, 46(27): 43-45.

[6]POTHEN A, SIMON H D, LIOU K P. Partitioning sparse matrices with eigenvectors of graphs[J]. SIAM journal on matrix analysis and applications, 1990, 11(3): 430-452.

[7]GIRVAN M, NEWMAN M E J. Community structure in social and biological networks[J]. Proceedings of the national academy of sciences, 2002, 99(12): 7821-7826.

[8]金弟, 楊博, 劉杰,等. 復(fù)雜網(wǎng)絡(luò)簇結(jié)構(gòu)探測(cè)——基于隨機(jī)游走的蟻群算法[J]. 軟件學(xué)報(bào), 2012, 23(3):451-464. JIN Di ,YANG Bo ,LIU Jie, et al. Ant colony optimization based on random walk for community detection in complex networks [J]. Journal of software, 2012, 23(3): 451-464.

[9]NEWMAN M E J. Fast algorithm for detecting community structure in networks [J]. Physical review E, 2004, 69(6): 066133.

[10]RADICCHI F, CASTELLANO C, CECCONI F, et al. Defining and identifying communities in networks [J]. Proceedings of the national academy of sciences of the United States of America, 2004, 101(9): 2658-2663.

[11]趙姝, 柯望, 陳潔, 等. 基于聚類?；纳鐖F(tuán)發(fā)現(xiàn)算法[J]. 計(jì)算機(jī)應(yīng)用, 2014, 34(10): 2812-2815. ZHAO Shu, KE Wang, CHEN Jie, et al. Community detection algorithm based on clustering granulation[J]. Journal of computer applications, 2014, 34(10): 2812-2815.

[12]YAO Y Y. Three-way decisions with probabilistic rough sets [J]. Information sciences, 2010, 180(3): 341-353.

[13]YAO Y. Two semantic issues in a probabilistic rough set model [J]. Fundamental informaticae, 2011, 108(3/4): 249-265.

[14]賈修一, 商琳, 周獻(xiàn)中,等. 三支決策理論與應(yīng)用[M]. 南京：南京大學(xué)出版社, 2012.

[15]于洪, 王國胤, 李天瑞，等. 三支決策:復(fù)雜問題求解方法與實(shí)踐[M]. 北京：科學(xué)出版社，2015.

[16]YU H, ZHANG C, WANG G. A tree-based incremental overlapping clustering method using the three-way decision theory[J]. Knowledge-based systems, 2016, 91:189-203.

[17]YU H, WANG Y, JIAO P. A three-way decisions approach to density-based overlapping clustering [M]. Berlin Heidelberg:Springer, 2014: 92-109.

[18]YU H, ZHANG C, HU F. An Incremental Clustering Approach Based on Three-Way Decisions[C]//Rough Sets and Current Trends in Computing.Springer,Berlin Heidelberg,2014,8536: 152-159.

[19]LIU Y, PAN L, JIA X, et al. Three-way decision based overlapping community detection[C]//Rough Sets and Knowledge Technology, 2013,8171: 279-290.

[20]YAO Y. An Outline of a theory of three-way decisions[C]//Rough Sets and Currnet Trends in Computing. Berlin Heidelberg:Springer, 2012: 1-17.

[21]YAO Y Y, WONG S K M. A decision theoretic framework for approximating concepts [J]. International journal of man-machine studies, 1992, 37(6): 793-809.

[22]JIA X, TANG Z, LIAO W, et al. On an optimization representation of decision-theoretic rough set model[J]. International journal of approximate reasoning, 2014, 55(1):156-166.

[23]QIAN Y, ZHANG H, SANG Y, et al. Multi-granulation decision-theoretic rough sets[J]. International journal of approximate reasoning, 2014, 55(1): 225-237.

[24]NEWMAN M E J, GIRVAN M. Finding and evaluating community structure in networks[J]. Physical review E, 2004, 69(2): 026113.

[25]賈修一, 李偉湋, 商琳,等. 一種自適應(yīng)求三枝決策中決策閾值的算法[J]. 電子學(xué)報(bào), 2011, 39(11):2520-2525.

JIA Xiuyi, LI Weiwei, SHANG Lin，et al. An adaptive learning parameters algorithm in three-way decision-throretic rough set model[J]. Chinese journal of electronics, 2011, 39(11): 2520-2525

[26]LEICHT E A, HOLME P, NEWMAN M E J. Vertex similarity in networks[J]. Physical review E, 2006, 73(2): 026120.

[27]RAGHAVAN U N, Albert R, Kumara S. Near linear time algorithm to detect community structures in large-scale networks [J]. Physical reviewe, 2007, 76(3): 036106.

方蓮娣, 女 , 1992年生，碩士研究生, 主要研究領(lǐng)域?yàn)槿Q策和機(jī)器學(xué)習(xí)。

張燕平, 女 ，1962年生，教授，博士, 主要研究方向?yàn)榱Ｓ?jì)算、智能計(jì)算、機(jī)器學(xué)習(xí)。獲發(fā)明專利2項(xiàng)，發(fā)表學(xué)術(shù)論文80余篇。

陳潔, 女 , 1982年生， 副教授, 博士，主要研究方向?yàn)橹悄苡?jì)算、機(jī)器學(xué)習(xí)、三支決策。發(fā)表學(xué)術(shù)論文10余篇。

Three-way decision based on non-overlapping community division

FANG Liandi1, 2， ZHANG Yanping1, 2， CHEN Jie1, 2， WANG Qianqian3， LIU Feng1, 2， WANG Gang1, 2

(1.School of Computer Science and Technology, Anhui University, Hefei 230601, China; 2.Key Laboratory of Intelligent Computing and Signal Processing of Ministry of Education, Anhui University, Hefei 230601, China; 3.School of Business, Anhui University, Hefei 230601, China)

This paper proposes an algorithm called N-TWD based on the theory of three-way decision, which can further divide overlapping communities formed by the initial clustering into non-overlapping communities. First, it utilizes a hierarchical clustering algorithm to get an overlapping community structure. 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. Then, the nodes on its right are denoted as the negative region, and nodes in the overlapping parts are denoted as the boundary region. The degree of belonging (BP,BN) between the positive and negative regions was calculated using the nodes in the boundary region. Moreover, a further division was done based on the degree of belonging. After division, the belonging of the rest nodes in the boundary region would be determined by voting to ultimately get a non-overlapping community structure. The experimental results for four classical social networks and one real-world data-set indicate that the proposed algorithm has a lower time complexity and gets a higher modularity value than other community division algorithms (GN, NFA, LPA, CACDA).

complex network; community division; overlapping node; three-way decision; granulation coefficient; hierarchical clustering；community structure; node belonging degree

10.11992/tis.201705013

http://kns.cnki.net/kcms/detail/23.1538.TP.20170705.1656.006.html

2017-05-12. 網(wǎng)絡(luò)出版日期：2017-07-05.

國家“863”計(jì)劃項(xiàng)目(2015AA124102)；國家自然科學(xué)基金項(xiàng)目(61673020，61602003，61402006); 安徽省自然科學(xué)基金項(xiàng)目(1508085MF113，1708085QF156，1708085QF143，1708085MF163); 安徽省高等學(xué)校省級(jí)自然科學(xué)基金重點(diǎn)項(xiàng)目(KJ2013A016,KJ2016A016); 教育部人文社科青年基金項(xiàng)目(14YJC860020).

張燕平.E-mail :zhangyp2@gmail.com.

TP301

A

1673-4785(2017)03-0293-08