[發(fā)明專(zhuān)利]一種基于動(dòng)態(tài)同步模型的社區(qū)檢測(cè)方法

有效

• 申請(qǐng)?zhí)枺?/td>: 201410717471.4
• 申請(qǐng)日: 2014-11-28
• 公開(kāi)（公告）號(hào): CN104346481B
• 公開(kāi)（公告）日: 2018-01-16
• 發(fā)明（設(shè)計(jì)）人: 董學(xué)文;楊超;盛立杰;王超;姚青松;李興華;曾勇;姜奇
• 申請(qǐng)（專(zhuān)利權(quán)）人: 西安電子科技大學(xué)
• 主分類(lèi)號(hào): G06F17/30
• 分類(lèi)號(hào): G06F17/30;G06Q50/00
• 代理公司: 西安通大專(zhuān)利代理有限責(zé)任公司61200
• 代理人: 徐文權(quán)

技術(shù)領(lǐng)域

本發(fā)明屬于網(wǎng)絡(luò)數(shù)據(jù)挖掘領(lǐng)域，具體涉及一種基于動(dòng)態(tài)同步模型的社區(qū)檢測(cè)方法。

背景技術(shù)

數(shù)據(jù)挖掘(Data Mining)是指從大量數(shù)據(jù)中提取隱含的、未知的、有潛在應(yīng)用價(jià)值的信息或模式的過(guò)程。聚類(lèi)是數(shù)據(jù)挖掘領(lǐng)域中一種重要的分析技術(shù)，根據(jù)數(shù)據(jù)之間在預(yù)先制定的屬性上的相似性聚集成簇。聚類(lèi)的目標(biāo)是將有限個(gè)未知標(biāo)簽的數(shù)據(jù)劃分成有限個(gè)離散數(shù)據(jù)集合的形式,它沒(méi)有可供學(xué)習(xí)訓(xùn)練的數(shù)據(jù),可用的只有數(shù)據(jù)點(diǎn)本身的特征和可計(jì)算數(shù)據(jù)點(diǎn)之間相似關(guān)系的相似性度量規(guī)則，因此選擇合適的相似性度量規(guī)則是非常重要的環(huán)節(jié)。常用的相似性度量包括歐氏距離、馬氏距離、核距離、海明威距離等。

在過(guò)去十年中，數(shù)據(jù)聚類(lèi)吸引了研究人員的廣泛關(guān)注，并提出一系列的聚類(lèi)算法。這些算法可以分為如下幾類(lèi)：基于劃分的聚類(lèi)算法、基于密度的聚類(lèi)算法，基于層次的聚類(lèi)算法，基于模型的聚類(lèi)算法等等。基于劃分的聚類(lèi)方法直接將數(shù)據(jù)空間中的一組數(shù)據(jù)劃分為不相連的一組子空間數(shù)據(jù)。基于層次的聚類(lèi)方法是另外一種比較成熟的聚類(lèi)方法。在初始狀態(tài)時(shí)每個(gè)樣本都是作為一個(gè)類(lèi)存在的,將距離最近的兩個(gè)類(lèi)合并成一個(gè)類(lèi),重復(fù)迭代直至所有的類(lèi)都?xì)w為一類(lèi)；或者初始狀態(tài)時(shí)所有的樣本點(diǎn)是屬于同一個(gè)類(lèi)的,逐漸細(xì)分為越來(lái)越小的類(lèi),最終每個(gè)類(lèi)中只含有一個(gè)樣本。基于密度的聚類(lèi)方法是一種專(zhuān)門(mén)針對(duì)密度數(shù)據(jù)提出的聚類(lèi)方法,該方法使用數(shù)據(jù)點(diǎn)的密度特征作為聚類(lèi)特征,將具有相似密度特征的樣本歸為一類(lèi)。基于模型的方法為每個(gè)簇假定了一個(gè)模型，尋找數(shù)據(jù)對(duì)給定模型的最佳擬合。基于模型的算法可能性通過(guò)構(gòu)建反映數(shù)據(jù)點(diǎn)空間分布的密度函數(shù)來(lái)定位聚類(lèi)。

傳統(tǒng)的基于kuramoto模型的社區(qū)檢測(cè)算法——SYN算法——首先對(duì)網(wǎng)絡(luò)節(jié)點(diǎn)進(jìn)行預(yù)處理：使用節(jié)點(diǎn)間的結(jié)構(gòu)相似度描述鏈接密度，并利用OPTICS算法，將各節(jié)點(diǎn)進(jìn)行排序，排序結(jié)果為一個(gè)一維坐標(biāo)序列，同時(shí)保證鏈接密度大的節(jié)點(diǎn)距離較近。然后進(jìn)行同步聚類(lèi)：將每個(gè)對(duì)象與其ε–鄰域內(nèi)進(jìn)行同步調(diào)整，對(duì)調(diào)整坐標(biāo)后的所有節(jié)點(diǎn)重新進(jìn)行社團(tuán)劃分，將距離小于ε的節(jié)點(diǎn)判定為同一個(gè)社團(tuán)。得到社團(tuán)劃分結(jié)果后，計(jì)算其模塊度。在不斷增加鄰域半徑ε值的同步過(guò)程中，得到一系列聚類(lèi)結(jié)果，選擇其中模塊度最大的作為最優(yōu)聚類(lèi)結(jié)果。

傳統(tǒng)的基于kuramoto模型的SYN算法在對(duì)鏈接密度的描述不夠精確，計(jì)算出結(jié)構(gòu)相似度數(shù)值區(qū)間狹窄，不能有效反映網(wǎng)絡(luò)鏈接密度差異。同時(shí)利用kuramoto模型進(jìn)行局部同步時(shí)僅考慮ε–鄰域內(nèi)同步，未考慮關(guān)系密切的其他節(jié)點(diǎn)。另外在同步處理之后，沒(méi)有對(duì)微小社區(qū)進(jìn)行后續(xù)處理，導(dǎo)致大量微小社區(qū)存在并使得社區(qū)檢測(cè)結(jié)果不夠準(zhǔn)確。

發(fā)明內(nèi)容

本發(fā)明的目的在于針對(duì)現(xiàn)有技術(shù)存在的缺陷和不足，提供一種基于動(dòng)態(tài)同步模型的社區(qū)檢測(cè)方法，該方法能夠?qū)︽溄用芏冗M(jìn)行精確的描述，并有效反映網(wǎng)絡(luò)鏈接密度的差異。

為實(shí)現(xiàn)上述目的，本發(fā)明采用以下技術(shù)方案：包括以下步驟：

步驟A，構(gòu)造網(wǎng)絡(luò)圖：讀取網(wǎng)絡(luò)數(shù)據(jù)，構(gòu)造以用戶(hù)為節(jié)點(diǎn)，用戶(hù)關(guān)系為邊的網(wǎng)絡(luò)圖；

步驟B，網(wǎng)絡(luò)矢量化：將步驟A所得網(wǎng)絡(luò)圖中各節(jié)點(diǎn)通過(guò)OPTICS算法進(jìn)行矢量化，將網(wǎng)絡(luò)中各節(jié)點(diǎn)映射到一個(gè)一維坐標(biāo)序列中，為后續(xù)的同步聚類(lèi)做準(zhǔn)備，具體步驟為：

步驟B1，首先對(duì)網(wǎng)絡(luò)利用節(jié)點(diǎn)相似性描述網(wǎng)絡(luò)中鏈接密度，計(jì)算各邊(x，y)的節(jié)點(diǎn)相似度，定義

；其中τ(x)表示節(jié)點(diǎn)x的鄰域，包含x和x的鄰居節(jié)點(diǎn),τ(y)表示節(jié)點(diǎn)y的鄰域，包含y和y的鄰居節(jié)點(diǎn)；degree(x)表示節(jié)點(diǎn)x的度，degree(y)表示節(jié)點(diǎn)y的度；

步驟B2，利用節(jié)點(diǎn)相似度定義和OPTICS算法，獲得節(jié)點(diǎn)序列；

步驟B3，根據(jù)獲得的節(jié)點(diǎn)序列，將網(wǎng)絡(luò)中的每個(gè)節(jié)點(diǎn)平均映射到區(qū)間[0，1)上，每個(gè)節(jié)點(diǎn)對(duì)應(yīng)一個(gè)一維坐標(biāo)，即實(shí)現(xiàn)整個(gè)網(wǎng)絡(luò)的矢量化；

步驟C，執(zhí)行同步聚類(lèi)：設(shè)置初始同步參數(shù)ε，確定同步范圍，每個(gè)節(jié)點(diǎn)在其同步范圍內(nèi)進(jìn)行同步聚類(lèi)，直至達(dá)到全局同步，根據(jù)同步坐標(biāo)位置進(jìn)行社區(qū)劃分，并計(jì)算該社區(qū)劃分的模塊度；不斷增加同步半徑，執(zhí)行同步聚類(lèi)，直至同步半徑覆蓋所有節(jié)點(diǎn)。

進(jìn)一步的，步驟C所述同步聚類(lèi)和社區(qū)劃分包括如下步驟：

步驟C1，初始化同步參數(shù)ε值為ε₀，計(jì)算各節(jié)點(diǎn)x的ε–鄰域集合N_ε(x)和密切節(jié)點(diǎn)集合Close(x)，將兩個(gè)集合進(jìn)行合并組成節(jié)點(diǎn)x的同步范圍R_ε(x)；

N_ε(x)＝{y∈X|dist(y,x)≤ε}