[發(fā)明專利]基于社交網(wǎng)絡(luò)節(jié)點(diǎn)雙標(biāo)簽傳播算法的社區(qū)結(jié)構(gòu)劃分方法

在審

• 申請(qǐng)?zhí)枺?/td>: 201911293324.8
• 申請(qǐng)日: 2019-12-16
• 公開（公告）號(hào): CN110956553A
• 公開（公告）日: 2020-04-03
• 發(fā)明（設(shè)計(jì)）人: 鄭文鋒;楊波;尹超;劉珊;曾慶川
• 申請(qǐng)（專利權(quán)）人: 電子科技大學(xué)
• 主分類號(hào): G06Q50/00
• 分類號(hào): G06Q50/00;G06F16/901
• 代理公司: 成都行之專利代理事務(wù)所(普通合伙) 51220
• 代理人: 溫利平

1.一種基于社交網(wǎng)絡(luò)節(jié)點(diǎn)雙標(biāo)簽傳播算法的社區(qū)結(jié)構(gòu)劃分方法，其特征在于，包括以下步驟：

(1)、構(gòu)造社交網(wǎng)絡(luò)圖；

讀取社交網(wǎng)絡(luò)數(shù)據(jù)，構(gòu)造以社交網(wǎng)絡(luò)用戶為節(jié)點(diǎn)，用戶間關(guān)系為邊的社交網(wǎng)絡(luò)圖；

(2)、分配節(jié)點(diǎn)標(biāo)簽及隸屬度初始化；

在社交網(wǎng)絡(luò)圖中，為每個(gè)節(jié)點(diǎn)分配兩個(gè)標(biāo)簽并設(shè)置其隸屬度值為

(3)、利用K-shell算法計(jì)算各個(gè)節(jié)點(diǎn)的權(quán)值；

(4)、通過迭代更新方式實(shí)現(xiàn)社交網(wǎng)絡(luò)節(jié)點(diǎn)的雙標(biāo)簽傳播；

(4.1)、初始迭代次數(shù)k＝1，最大迭代次數(shù)K；設(shè)置所有節(jié)點(diǎn)對(duì)應(yīng)標(biāo)簽在傳播過程中未發(fā)生變化的百分占比閾值為P；

(4.2)、隨機(jī)遍歷社交網(wǎng)絡(luò)圖中的所有節(jié)點(diǎn)，并按照節(jié)點(diǎn)節(jié)點(diǎn)雙標(biāo)簽傳播規(guī)則進(jìn)行節(jié)點(diǎn)雙標(biāo)簽更新，具體更新過程為：

(4.2.1)、隨機(jī)選取未更新節(jié)點(diǎn)V_i；

(4.2.2)、對(duì)節(jié)點(diǎn)V_i的所有鄰居節(jié)點(diǎn)應(yīng)用雙標(biāo)簽傳播規(guī)則；

計(jì)算節(jié)點(diǎn)V_i從鄰居節(jié)點(diǎn)接收到各個(gè)標(biāo)簽的強(qiáng)度；

其中，表示節(jié)點(diǎn)V_i接收到所有具有標(biāo)簽名為L(zhǎng)的鄰居節(jié)點(diǎn)的總強(qiáng)度值，N^L(V_i)表示與節(jié)點(diǎn)V_i相連接的具有標(biāo)簽名L的鄰居節(jié)點(diǎn)集合，K_U表示鄰居節(jié)點(diǎn)U的權(quán)值，表示標(biāo)簽名L在鄰居節(jié)點(diǎn)U中的隸屬度值；

(4.2.3)、更新節(jié)點(diǎn)V_i的標(biāo)簽；

(4.2.4)、按照步驟(4.2.1)-(4.2.3)的方法，將社交網(wǎng)絡(luò)圖中的所有未更新的節(jié)點(diǎn)進(jìn)行雙標(biāo)簽更新；

(4.3)、通過本輪迭代后，統(tǒng)計(jì)標(biāo)簽名未發(fā)生變化的節(jié)點(diǎn)的百分占比，然后比較該百分占比是否大于預(yù)設(shè)閾值P，如果百分占比大于P或當(dāng)前迭代次數(shù)達(dá)到最大迭代次數(shù)K，則迭代停止，然后進(jìn)入步驟(5)；否則，令k＝k+1，再返回至步驟(4.2)，進(jìn)行下一輪迭代；

(5)、獲得社交網(wǎng)絡(luò)的社區(qū)結(jié)構(gòu)

把具有相同標(biāo)簽的節(jié)點(diǎn)劃分為同一社區(qū)，從而獲得社交網(wǎng)絡(luò)的社區(qū)結(jié)構(gòu)。

2.根據(jù)權(quán)利要求1所述的一種基于社交網(wǎng)絡(luò)節(jié)點(diǎn)雙標(biāo)簽傳播算法的社區(qū)結(jié)構(gòu)劃分方法，其特征在于，所述的更新節(jié)點(diǎn)V_i的標(biāo)簽的具體過程為：

在節(jié)點(diǎn)V_i接收到所有標(biāo)簽中，選取兩個(gè)強(qiáng)度最大的標(biāo)簽為節(jié)點(diǎn)V_i的新標(biāo)簽，并對(duì)其更新；

設(shè)選取的兩個(gè)最大的強(qiáng)度值分別為那么節(jié)點(diǎn)V_i的兩個(gè)新標(biāo)簽的隸屬度更新為：