[發(fā)明專(zhuān)利]一種基于相似性的社區(qū)檢測(cè)的方法

有效

• 申請(qǐng)?zhí)枺?/td>: 201810987366.0
• 申請(qǐng)日: 2018-08-28
• 公開(kāi)（公告）號(hào): CN109255433B
• 公開(kāi)（公告）日: 2021-10-29
• 發(fā)明（設(shè)計(jì)）人: 楊旭華;沈敏
• 申請(qǐng)（專(zhuān)利權(quán)）人: 浙江工業(yè)大學(xué)
• 主分類(lèi)號(hào): G06K9/62
• 分類(lèi)號(hào): G06K9/62;G06N3/04;G06Q50/00
• 代理公司: 杭州斯可睿專(zhuān)利事務(wù)所有限公司 33241
• 代理人: 王利強(qiáng)

一種基于相似性的社區(qū)檢測(cè)的方法，建立網(wǎng)絡(luò)模型,計(jì)算并記錄任意兩個(gè)節(jié)點(diǎn)的共同鄰居集合和聯(lián)合鄰居集合，計(jì)算網(wǎng)絡(luò)中任意一個(gè)節(jié)點(diǎn)的局部度數(shù)比和PageRank值,計(jì)算并記錄網(wǎng)絡(luò)中所有節(jié)點(diǎn)及其連邊的度數(shù)比聚類(lèi)值，找到所有節(jié)點(diǎn)對(duì)應(yīng)的度數(shù)比相似性最高的節(jié)點(diǎn)，計(jì)算并記錄網(wǎng)絡(luò)中所有節(jié)點(diǎn)及其連邊的PageRank中心性聚類(lèi)值，找到所有節(jié)點(diǎn)對(duì)應(yīng)的PageRank相似性最高的節(jié)點(diǎn)，將所有節(jié)點(diǎn)與其度數(shù)比相似性最高的節(jié)點(diǎn)劃入同一社團(tuán)，得到初始社區(qū)劃分，將每個(gè)節(jié)點(diǎn)與其PageRank相似性最高的節(jié)點(diǎn)所在的社區(qū)合并，得到最終的社區(qū)結(jié)構(gòu)。本發(fā)明有效利用了節(jié)點(diǎn)的相關(guān)性信息，準(zhǔn)確性較高，時(shí)間復(fù)雜度較低。

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

本發(fā)明涉及復(fù)雜網(wǎng)絡(luò)與社團(tuán)劃分領(lǐng)域，特別是指一種基于相似性的社區(qū)檢測(cè)的方法。

背景技術(shù)

隨著復(fù)雜網(wǎng)絡(luò)的小世界、無(wú)標(biāo)度特性的發(fā)現(xiàn)，結(jié)合非線(xiàn)性科學(xué)和近現(xiàn)代物理學(xué)的概念與理論，網(wǎng)絡(luò)科學(xué)的研究在網(wǎng)絡(luò)結(jié)構(gòu)、功能和性質(zhì)等方面得到了快速發(fā)展。但是，網(wǎng)絡(luò)科學(xué)中單一的指標(biāo)如度、介數(shù)等以及抽象的建模如拓?fù)?、加?quán)、博弈模型等，都不能很好地描述實(shí)際網(wǎng)絡(luò)的節(jié)點(diǎn)特性。而且，現(xiàn)實(shí)世界中的網(wǎng)絡(luò)節(jié)點(diǎn)數(shù)量多且復(fù)雜，節(jié)點(diǎn)自身和節(jié)點(diǎn)之間的關(guān)系很多會(huì)不斷變化，實(shí)際網(wǎng)絡(luò)中節(jié)點(diǎn)是演化的、動(dòng)態(tài)的，具有鮮明的主體性，不同的主體行為力體現(xiàn)了節(jié)點(diǎn)在網(wǎng)絡(luò)功能和行為中的所起到的不同作用。也就是說(shuō)，節(jié)點(diǎn)與節(jié)點(diǎn)通過(guò)連邊相互產(chǎn)生影響，這種局域影響性在網(wǎng)絡(luò)功能和行為中的研究必不可少?，F(xiàn)有的社團(tuán)劃分算法十分豐富，如基于模塊度優(yōu)化的Newman快速算法和CNM算法，基于譜分析的算法，基于標(biāo)簽傳播的算法，基于種子擴(kuò)散的算法，基于邊的社團(tuán)劃分算法等等。社團(tuán)劃分算法一般是根據(jù)拓?fù)浣Y(jié)構(gòu)來(lái)劃分，拓?fù)浣Y(jié)構(gòu)是對(duì)復(fù)雜網(wǎng)絡(luò)中的節(jié)點(diǎn)和連邊的最基礎(chǔ)的抽象。這種社團(tuán)劃分的方法沒(méi)有合理的思考節(jié)點(diǎn)本身在社團(tuán)形成過(guò)程中不可或缺的局域影響力。為網(wǎng)絡(luò)加入節(jié)點(diǎn)重要性，利用重要性的概念來(lái)定量刻畫(huà)節(jié)點(diǎn)間相互影響在形成社團(tuán)結(jié)構(gòu)時(shí)的作用，將可提高社團(tuán)劃分的質(zhì)量和可信度，使得社團(tuán)的物理意義更加明確，在網(wǎng)絡(luò)演化過(guò)程中的社團(tuán)變化特征更加準(zhǔn)確。

基于局部相似度的社區(qū)檢測(cè)算法在大規(guī)模網(wǎng)絡(luò)中具有良好的性能。局部相似性指標(biāo)包括CN指數(shù)，Jaccard指數(shù)，HPI指數(shù)等。但是這些方法仍然存在一些挑戰(zhàn)，例如網(wǎng)絡(luò)邊緣的節(jié)點(diǎn)很容易被忽略。因此對(duì)于基于相似性的社區(qū)檢測(cè)算法的研究顯得非常必要。

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

為了克服現(xiàn)有社區(qū)檢測(cè)算法的獲取網(wǎng)絡(luò)全局信息困難、預(yù)測(cè)精度較低、時(shí)間復(fù)雜度較高的不足，本發(fā)明提出一種準(zhǔn)確性較高，時(shí)間復(fù)雜度較低的基于相似性的社區(qū)檢測(cè)的方法。

本發(fā)明解決其技術(shù)問(wèn)題所采用的技術(shù)方案是：

一種基于相似性的社區(qū)檢測(cè)的方法，包括如下步驟：

步驟一：構(gòu)建一個(gè)具有N個(gè)節(jié)點(diǎn)的無(wú)向網(wǎng)絡(luò)模型G(V,E),V為節(jié)點(diǎn)，E為連邊；

步驟二：任意選取兩個(gè)節(jié)點(diǎn)i和j，計(jì)算兩個(gè)節(jié)點(diǎn)的共同鄰居集合Int(i,j)＝(Γ_i∩Γ_j)和聯(lián)合鄰居集合Uni(i,j)＝(Γ_i∪Γ_j)，遍歷網(wǎng)絡(luò)中所有節(jié)點(diǎn)對(duì)，計(jì)算并記錄相應(yīng)節(jié)點(diǎn)對(duì)的共同鄰居集合和聯(lián)合鄰居集合；

步驟三：在網(wǎng)絡(luò)中任取一個(gè)節(jié)點(diǎn)i，計(jì)算該節(jié)點(diǎn)的局部度數(shù)比

其中D(i)表示節(jié)點(diǎn)i的度數(shù)，一個(gè)節(jié)點(diǎn)的度數(shù)為該節(jié)點(diǎn)的相連鄰居節(jié)點(diǎn)的數(shù)量，Γ(i)表示與節(jié)點(diǎn)i相連的所有鄰居節(jié)點(diǎn)并包括節(jié)點(diǎn)i，遍歷網(wǎng)絡(luò)，計(jì)算并記錄網(wǎng)絡(luò)中所有節(jié)點(diǎn)的局部度數(shù)比；

步驟四：計(jì)算網(wǎng)絡(luò)中包含每個(gè)節(jié)點(diǎn)的PageRank值的向量

x＝D(D-αA)^-1，