[發(fā)明專利]基于拓?fù)涮匦缘膹?fù)雜網(wǎng)絡(luò)社團(tuán)發(fā)現(xiàn)方法

有效

• 申請(qǐng)?zhí)枺?/td>: 201410037855.1
• 申請(qǐng)日: 2014-01-27
• 公開（公告）號(hào): CN103810260B
• 公開（公告）日: 2017-06-20
• 發(fā)明（設(shè)計(jì)）人: 周紅芳;段文聰;王心怡;何馨依;郭杰;張國榮
• 申請(qǐng)（專利權(quán)）人: 西安理工大學(xué)
• 主分類號(hào): G06F17/30
• 分類號(hào): G06F17/30
• 代理公司: 西安弘理專利事務(wù)所61214
• 代理人: 李娜

1.基于拓?fù)涮匦缘膹?fù)雜網(wǎng)絡(luò)社團(tuán)發(fā)現(xiàn)方法，其特征在于，包括：

步驟1，初始化；將網(wǎng)絡(luò)中的每個(gè)節(jié)點(diǎn)作為一個(gè)獨(dú)立的社團(tuán)，如果網(wǎng)絡(luò)中有n個(gè)節(jié)點(diǎn)，那么就有n個(gè)初始化社團(tuán)，各個(gè)節(jié)點(diǎn)的關(guān)鍵性為0，歸屬度取決于邊連接強(qiáng)度；

所述歸屬度，是節(jié)點(diǎn)劃分的判斷標(biāo)準(zhǔn)，即節(jié)點(diǎn)與各個(gè)社團(tuán)之間的關(guān)系；歸屬度計(jì)算公式如下：

$A(i,g)=\underset{j\∈g}{\mathrm{\Σ}}\left(\right(1+s_{ij})\·(1+\frac{c_j}{r}\left)\right)---\left(1\right)$

其中A(i,g)就代表節(jié)點(diǎn)i與社團(tuán)g的歸屬度，s_ij代表節(jié)點(diǎn)i與社團(tuán)g中節(jié)點(diǎn)j的邊連接強(qiáng)度，c_j代表節(jié)點(diǎn)j在社團(tuán)g中的關(guān)鍵性，r為系數(shù)；

步驟2，計(jì)算邊連接強(qiáng)度；計(jì)算所有相連節(jié)點(diǎn)之間的邊連接強(qiáng)度，也就是計(jì)算有邊相連的兩個(gè)節(jié)點(diǎn)所構(gòu)成的三角形的個(gè)數(shù)；

步驟3，迭代；依順序?qū)Ω鞴?jié)點(diǎn)進(jìn)行以下操作：首先，將一個(gè)節(jié)點(diǎn)從其所在社團(tuán)刪除，計(jì)算該節(jié)點(diǎn)與各個(gè)社團(tuán)的歸屬度，將節(jié)點(diǎn)劃分到歸屬度最大的社團(tuán)；

步驟3中，節(jié)點(diǎn)被劃分到新的社團(tuán)之后，與其相連的節(jié)點(diǎn)的中心程度可能會(huì)發(fā)生改變，需要重新計(jì)算它們的關(guān)鍵性，即能構(gòu)成的三角形的個(gè)數(shù)；之后，對(duì)下一個(gè)節(jié)點(diǎn)進(jìn)行同樣的操作；當(dāng)遍歷完所有的節(jié)點(diǎn)，一次迭代結(jié)束；經(jīng)過多次迭代，各節(jié)點(diǎn)的歸屬將不再發(fā)生變化，算法終止。

2.如權(quán)利要求1所述的基于拓?fù)涮匦缘膹?fù)雜網(wǎng)絡(luò)社團(tuán)發(fā)現(xiàn)方法，其特征在于，所述邊連接強(qiáng)度，是用來衡量?jī)蓚€(gè)相連節(jié)點(diǎn)之間的相似度，用s_ij來表示節(jié)點(diǎn)i與節(jié)點(diǎn)j之間的邊連接強(qiáng)度，s_ij等于在網(wǎng)路中包含節(jié)點(diǎn)i與節(jié)點(diǎn)j所組成的三角形的個(gè)數(shù)。

3.如權(quán)利要求1所述的基于拓?fù)涮匦缘膹?fù)雜網(wǎng)絡(luò)社團(tuán)發(fā)現(xiàn)方法，其特征在于，所述關(guān)鍵性，是衡量節(jié)點(diǎn)在其所屬社團(tuán)中的重要程度，用c_j來表示節(jié)點(diǎn)j在其所屬社團(tuán)中的關(guān)鍵性，c_j等于在節(jié)點(diǎn)j所屬社團(tuán)中包含節(jié)點(diǎn)j的三角形的個(gè)數(shù)。