[發(fā)明專利]基于重疊點(diǎn)識(shí)別的網(wǎng)絡(luò)重疊社團(tuán)檢測(cè)方法

有效

• 申請(qǐng)?zhí)枺?/td>: 201310272890.7
• 申請(qǐng)日: 2013-07-02
• 公開(kāi)（公告）號(hào): CN103400299A
• 公開(kāi)（公告）日: 2013-11-20
• 發(fā)明（設(shè)計(jì)）人: 劉均;徐海鵬;董博;鄭慶華;馬天;賀歡;李冰
• 申請(qǐng)（專利權(quán)）人: 西安交通大學(xué)
• 主分類號(hào): G06Q50/00
• 分類號(hào): G06Q50/00
• 代理公司: 西安通大專利代理有限責(zé)任公司 61200
• 代理人: 朱海臨

1.一種基于重疊點(diǎn)識(shí)別的網(wǎng)絡(luò)重疊社團(tuán)檢測(cè)方法，其特征在于，包括如下步驟：

第一步，網(wǎng)絡(luò)社團(tuán)候選重疊點(diǎn)集合構(gòu)建：首先，對(duì)網(wǎng)絡(luò)進(jìn)行社團(tuán)劃分，得到網(wǎng)絡(luò)的非重疊社團(tuán)集合；其次，搜索連接兩個(gè)社團(tuán)之間的邊，社團(tuán)之間邊的頂點(diǎn)即社團(tuán)的邊界點(diǎn)，并據(jù)此求解出每個(gè)社團(tuán)的初始邊界點(diǎn)集合，對(duì)網(wǎng)絡(luò)中各社團(tuán)的初始邊界點(diǎn)集合求并集，得到網(wǎng)絡(luò)社團(tuán)的初始邊界點(diǎn)集合；再次，根據(jù)節(jié)點(diǎn)到關(guān)聯(lián)社團(tuán)的連接數(shù)與該節(jié)點(diǎn)在網(wǎng)絡(luò)中度的比值，計(jì)算社團(tuán)初始邊界點(diǎn)集合中每個(gè)節(jié)點(diǎn)到其關(guān)聯(lián)社團(tuán)的連接率，并將連接率達(dá)到檢測(cè)閾值的邊界點(diǎn)加入初始候選重疊點(diǎn)集合；

第二步，社團(tuán)重疊點(diǎn)識(shí)別：提出基于節(jié)點(diǎn)質(zhì)量函數(shù)重疊點(diǎn)判定規(guī)則，判定候選重疊點(diǎn)集合中的節(jié)點(diǎn)與節(jié)點(diǎn)潛在隸屬社團(tuán)的隸屬關(guān)系，識(shí)別出重疊點(diǎn)，并將重疊點(diǎn)加入到滿足重疊點(diǎn)判定規(guī)則的隸屬社團(tuán)中；將新產(chǎn)生的邊界點(diǎn)到其關(guān)聯(lián)社團(tuán)的連接率達(dá)到檢測(cè)閾值的節(jié)點(diǎn)加入候選重疊點(diǎn)集合；遞歸執(zhí)行第二步，直到候選重疊點(diǎn)集合不包含滿足重疊點(diǎn)判定規(guī)則的節(jié)點(diǎn)為止，得到網(wǎng)絡(luò)的重疊社團(tuán)集合；

第三步，網(wǎng)絡(luò)重疊社團(tuán)合并：對(duì)于第二步得到的網(wǎng)絡(luò)重疊社團(tuán)集合，計(jì)算每?jī)蓚€(gè)社團(tuán)間的社團(tuán)節(jié)點(diǎn)重疊率，將重疊率達(dá)到合并閾值的社團(tuán)進(jìn)行合并，從而得到最終的網(wǎng)絡(luò)重疊社團(tuán)劃分結(jié)果。

2.如權(quán)利要求1所述的基于重疊點(diǎn)識(shí)別的網(wǎng)絡(luò)重疊社團(tuán)檢測(cè)方法，其特征在于，所述第一步中：

對(duì)網(wǎng)絡(luò)進(jìn)行社團(tuán)劃分時(shí)，設(shè)網(wǎng)絡(luò)為G(V,E)，V表示節(jié)點(diǎn)集合，E表示邊的集合；使用GN算法對(duì)G(V,E)進(jìn)行社團(tuán)劃分，得到網(wǎng)絡(luò)初始的非重疊社團(tuán)集合P＝{C₁,C₂,...,C_i,...,C_k}，其中，1≤i,j≤k且i≠j，k表示社團(tuán)個(gè)數(shù)，C_i表示G(V,E)的第i個(gè)社團(tuán)；計(jì)算P中每個(gè)社團(tuán)的密度δ(C_i)，得到社團(tuán)密度記錄集合δ(C_i)計(jì)算如下：

δ(Ci)=|ECi||Ci|(|Ci|-1)---(1)]]>

|C_i|表示社團(tuán)中節(jié)點(diǎn)個(gè)數(shù)，表示G(V,E)中以C_i中節(jié)點(diǎn)為節(jié)點(diǎn)集合的子圖的邊數(shù)，ECi={(u,v)|u∈Ci,v∈Ci};]]>

所述社團(tuán)C_i的邊界點(diǎn)集合為：

border(Ci)={u|(u,v)∈E,u∈Ci,v∉Ci}---(2)]]>

對(duì)P中每個(gè)社團(tuán)的邊界點(diǎn)集合求并集，得到網(wǎng)絡(luò)的社團(tuán)初始邊界點(diǎn)集合B：

B=∪i=1kborder(Ci)={b1,b2,...,bj,...,bt}---(3)]]>

其中t表示邊界點(diǎn)個(gè)數(shù)，border(C_i)為社團(tuán)C_i的邊界點(diǎn)集合，b_j表示第j個(gè)邊界點(diǎn)；

對(duì)社團(tuán)初始邊界點(diǎn)集合B進(jìn)行篩選，計(jì)算集合B中邊界點(diǎn)b_j到其關(guān)聯(lián)社團(tuán)集合R_j中每個(gè)關(guān)聯(lián)社團(tuán)的社團(tuán)連接率r_jl；其中，邊界點(diǎn)b_j的關(guān)聯(lián)社團(tuán)集合R_j為：

Rj={Crelatel|∃v∈Crelatel,(bj,v)∈E,bj∉Crelatel,Crelatel∈P}---(4)]]>

邊界點(diǎn)b_j到關(guān)聯(lián)社團(tuán)的社團(tuán)連接率r_jl計(jì)算如下：

rjl=degCrelatel(bj)deg(bj),Crelatel∈Rj---(5)]]>

表示b_j到社團(tuán)的連接數(shù)，deg(b_j)表示b_j在網(wǎng)絡(luò)G(V,E)中的度；若r_jl大于等于檢測(cè)閾值φ，則將標(biāo)記為節(jié)點(diǎn)b_j的潛在隸屬社團(tuán)，記為并將該節(jié)點(diǎn)加入到候選重疊點(diǎn)集合CONS中。