[發(fā)明專利]一種社交網(wǎng)絡(luò)重疊社區(qū)發(fā)現(xiàn)系統(tǒng)及其方法

有效

• 申請(qǐng)?zhí)枺?/td>: 201410436259.0
• 申請(qǐng)日: 2014-08-29
• 公開（公告）號(hào): CN104166731B
• 公開（公告）日: 2017-11-17
• 發(fā)明（設(shè)計(jì)）人: 張卓;游煌斌;張學(xué)武;范新南;李敏;付懷勇
• 申請(qǐng)（專利權(quán)）人: 河海大學(xué)常州校區(qū)
• 主分類號(hào): G06F17/30
• 分類號(hào): G06F17/30
• 代理公司: 南京縱橫知識(shí)產(chǎn)權(quán)代理有限公司32224
• 代理人: 董建林,耿英

1.一種社交網(wǎng)絡(luò)重疊社區(qū)發(fā)現(xiàn)方法，其特征在于，包括以下步驟：

(1)采集實(shí)際網(wǎng)絡(luò)數(shù)據(jù)，以鄰接矩陣的形式存儲(chǔ)原始網(wǎng)絡(luò)信息；

(2)采用非重疊社區(qū)發(fā)現(xiàn)方法對(duì)網(wǎng)絡(luò)進(jìn)行處理，得到非重疊社區(qū)；

(3)在步驟(2)中得到的非重疊社區(qū)基礎(chǔ)上，通過計(jì)算社區(qū)中節(jié)點(diǎn)與其他社區(qū)的隸屬度，判斷是否應(yīng)將該節(jié)點(diǎn)加入對(duì)應(yīng)社區(qū)，從而得到重疊節(jié)點(diǎn)，也發(fā)現(xiàn)網(wǎng)絡(luò)中的重疊社區(qū)；

第(2)步中，在非重疊社區(qū)發(fā)現(xiàn)方法確定何時(shí)結(jié)束社區(qū)劃分是通過模塊度Q達(dá)到最大值完成的，

Q=12mΣc∈CΣu,v∈Vδcuδcv(Auv-kukv2m)]]>

其中A_uv是鄰接矩陣，m是網(wǎng)絡(luò)總邊數(shù)，V是所有節(jié)點(diǎn)的集合，C表示所有社區(qū)的集合，k_u和k_v分別是節(jié)點(diǎn)u和v的度；δ_cu表示節(jié)點(diǎn)u是否屬于社區(qū)c，屬于的話該值為1，反之為0；

第(3)步中，通過第(2)得到非重疊社區(qū)之后，計(jì)算社區(qū)中節(jié)點(diǎn)與其他社區(qū)的隸屬度，隸屬度的求取如下：

B(u,c)=Σv∈ceuvΣv∈Veuv]]>

e_uv表示連接節(jié)點(diǎn)u和v的邊，當(dāng)e_uv＝1時(shí)，表示節(jié)點(diǎn)u和v相連，當(dāng)e_uv＝0時(shí)，表示兩節(jié)點(diǎn)沒有連接，隸屬度反應(yīng)了節(jié)點(diǎn)u與社區(qū)c之間的緊密關(guān)系；判斷將節(jié)點(diǎn)添加到社區(qū)之后整個(gè)網(wǎng)絡(luò)的模塊度Q值是否大于初始時(shí)的整個(gè)網(wǎng)絡(luò)的模塊度Q₀值，大于則將節(jié)點(diǎn)添加至該社區(qū)，反之，保持社區(qū)不變；

Q₀值計(jì)算公式：

Q0=12mΣc∈CΣu,v∈VB(u,c)B(v,c)(Auv-kukv2m)]]>

其中A_uv是鄰接矩陣，m是網(wǎng)絡(luò)總邊數(shù)，C表示所有社區(qū)的集合，V是所有節(jié)點(diǎn)的集合，k_u和k_v分別是節(jié)點(diǎn)u和v的度，B(u,c)和B(v,c)分別是節(jié)點(diǎn)u和v與社區(qū)c之間的隸屬度；通過計(jì)算社區(qū)中節(jié)點(diǎn)與其他社區(qū)間的隸屬度，同時(shí)在一定條件下比較Q₀值，決定是否將節(jié)點(diǎn)添加至對(duì)應(yīng)社區(qū)；一個(gè)節(jié)點(diǎn)屬于多個(gè)社區(qū)，則認(rèn)為該節(jié)點(diǎn)為重疊節(jié)點(diǎn)，而具有重疊節(jié)點(diǎn)的社區(qū)則是重疊社區(qū)。