[發(fā)明專(zhuān)利]面向網(wǎng)絡(luò)的重疊社區(qū)發(fā)現(xiàn)方法

在審

• 申請(qǐng)?zhí)枺?/td>: 201310277647.4
• 申請(qǐng)日: 2013-07-03
• 公開(kāi)（公告）號(hào): CN103425737A
• 公開(kāi)（公告）日: 2013-12-04
• 發(fā)明（設(shè)計(jì)）人: 呂林濤;楊維維;孫飛龍;譚芳
• 申請(qǐng)（專(zhuān)利權(quán)）人: 西安理工大學(xué)
• 主分類(lèi)號(hào): G06F17/30
• 分類(lèi)號(hào): G06F17/30
• 代理公司: 西安弘理專(zhuān)利事務(wù)所 61214
• 代理人: 李娜

1.面向網(wǎng)絡(luò)的重疊社區(qū)發(fā)現(xiàn)方法，其特征在于，通過(guò)非重疊社區(qū)劃分的的結(jié)果初始化網(wǎng)絡(luò)的節(jié)點(diǎn)，然后采用基于模糊合作博弈的方法求社區(qū)之間的重疊點(diǎn)，實(shí)現(xiàn)網(wǎng)絡(luò)的重疊社區(qū)劃分，具體步驟如下：

步驟1、選取非重疊社區(qū)發(fā)現(xiàn)方法進(jìn)行社區(qū)劃分,不包含社區(qū)的重疊點(diǎn)；

步驟2、重新確定隸屬函數(shù)，計(jì)算節(jié)點(diǎn)屬于每個(gè)社區(qū)的隸屬度；

步驟3、重新確定收益函數(shù)，計(jì)算節(jié)點(diǎn)加入到社區(qū)后的社區(qū)的收益；

步驟4、根據(jù)計(jì)算的節(jié)點(diǎn)的隸屬度、節(jié)點(diǎn)加入社區(qū)后社區(qū)的收益求社區(qū)的重疊點(diǎn)，實(shí)現(xiàn)網(wǎng)絡(luò)的重疊社區(qū)劃分。

2.如權(quán)利要求1所述的面向網(wǎng)絡(luò)的重疊社區(qū)發(fā)現(xiàn)方法，其特征在于，

步驟2中，對(duì)每個(gè)和節(jié)點(diǎn)i相連的社團(tuán)C，這個(gè)節(jié)點(diǎn)加入到社團(tuán)C的隸屬函數(shù)可以表示為：

membershipc(i)=Σm<nshort_distmn(i)/short_distmn---(1)]]>

式中，m、n分別表示社區(qū)C中兩個(gè)不相同的節(jié)點(diǎn)，short_dist_mn表示節(jié)點(diǎn)m和節(jié)點(diǎn)n之間的最短路徑數(shù)，表示節(jié)點(diǎn)m和節(jié)點(diǎn)n之間經(jīng)過(guò)節(jié)點(diǎn)i的最短路徑數(shù)；在具有n個(gè)節(jié)點(diǎn)的社區(qū)中，對(duì)于給定的節(jié)點(diǎn)i來(lái)說(shuō)，最為極端的情況是任意兩個(gè)其他節(jié)點(diǎn)之間的最短路徑均經(jīng)過(guò)節(jié)點(diǎn)i，那么此時(shí)，該節(jié)點(diǎn)的membership_C(i)達(dá)到最大值(n-1)(n-2)/2.因此，歸一化的membership_C(i)可以定義為：

membership_C(i)＝membership_C(i)/[(n-1)(n-2)/2]??????（2）

3.如權(quán)利要求1或2所述的面向網(wǎng)絡(luò)的重疊社區(qū)發(fā)現(xiàn)方法，其特征在于，步驟3中，通過(guò)EQ函數(shù)來(lái)作為節(jié)點(diǎn)加入到社區(qū)后網(wǎng)絡(luò)的總體收益，EQ值越大，表明網(wǎng)絡(luò)的整體收益越大，那么，收益函數(shù)定義為:

revenge(C)＝EQ????????????????（3）

節(jié)點(diǎn)i加入社區(qū)后社區(qū)C的收益變化為：

Δrevenge(C)＝ΔEQ?????（4）

其中，EQ函數(shù)表示如下：

EQ=12mΣi|C|Σv∈Ci,w∈Ci1OvOw[Avw-kvkw2m]---(5)]]>

該公式含義為，給定一個(gè)網(wǎng)絡(luò)G，允許一個(gè)網(wǎng)絡(luò)節(jié)點(diǎn)可以同時(shí)屬于多個(gè)社區(qū)，O_v為節(jié)點(diǎn)所屬社區(qū)的個(gè)數(shù)，m為網(wǎng)絡(luò)中的邊數(shù)，|C?為總社區(qū)的個(gè)數(shù)，k_i和k_j分別為節(jié)點(diǎn)i和節(jié)點(diǎn)j的度，A_vw為網(wǎng)絡(luò)鄰接矩陣中，如果節(jié)點(diǎn)v和節(jié)點(diǎn)w之間有邊相連接，A_vw＝1，否則A_vw＝0。