[發(fā)明專(zhuān)利]一種社交網(wǎng)絡(luò)中的多標(biāo)簽傳播重疊社區(qū)發(fā)現(xiàn)方法

有效

• 申請(qǐng)?zhí)枺?/td>: 201410034425.4
• 申請(qǐng)日: 2014-01-24
• 公開(kāi)（公告）號(hào): CN103729475B
• 公開(kāi)（公告）日: 2016-10-26
• 發(fā)明（設(shè)計(jì)）人: 陳羽中;陳國(guó)龍;郭文忠;施松
• 申請(qǐng)（專(zhuān)利權(quán)）人: 福州大學(xué)
• 主分類(lèi)號(hào): G06F17/30
• 分類(lèi)號(hào): G06F17/30
• 代理公司: 福州元?jiǎng)?chuàng)專(zhuān)利商標(biāo)代理有限公司 35100
• 代理人: 蔡學(xué)俊

1.一種社交網(wǎng)絡(luò)中的多標(biāo)簽傳播重疊社區(qū)發(fā)現(xiàn)方法，其特征在于，所述方法包括以下步驟：

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

步驟B：初步社區(qū)劃分：根據(jù)社交網(wǎng)絡(luò)圖，采用綜合考慮節(jié)點(diǎn)中心度以及標(biāo)簽度分布約束的標(biāo)簽傳播方法進(jìn)行社區(qū)發(fā)現(xiàn)，獲得非重疊社區(qū)結(jié)構(gòu)；

步驟C：節(jié)點(diǎn)層級(jí)標(biāo)記：根據(jù)初步社區(qū)劃分獲得的非重疊社區(qū)結(jié)構(gòu)以及節(jié)點(diǎn)在所屬社區(qū)的中心度值，標(biāo)記節(jié)點(diǎn)所屬的層級(jí)；

步驟D：重疊社區(qū)細(xì)化：根據(jù)節(jié)點(diǎn)所屬的層級(jí)，計(jì)算不同層級(jí)節(jié)點(diǎn)之間的標(biāo)簽傳播增益，并利用多標(biāo)簽傳播進(jìn)行重疊節(jié)點(diǎn)挖掘，得到社交網(wǎng)絡(luò)的重疊社區(qū)結(jié)構(gòu)。

2.根據(jù)權(quán)利要求1所述的一種社交網(wǎng)絡(luò)中的多標(biāo)簽傳播重疊社區(qū)發(fā)現(xiàn)方法，其特征在于，所述步驟B中，社交網(wǎng)絡(luò)的初步社區(qū)劃分具體包括以下步驟：

步驟B1：根據(jù)社交網(wǎng)絡(luò)圖，進(jìn)行節(jié)點(diǎn)標(biāo)簽初始化，為社交網(wǎng)絡(luò)圖中的每個(gè)節(jié)點(diǎn)分配一個(gè)全局唯一的標(biāo)簽號(hào)；

步驟B2：根據(jù)標(biāo)簽更新規(guī)則，對(duì)社交網(wǎng)絡(luò)圖中的每個(gè)節(jié)點(diǎn)進(jìn)行標(biāo)簽更新，同時(shí)根據(jù)鄰居節(jié)點(diǎn)信息更新節(jié)點(diǎn)的中心度值，反復(fù)迭代，直到滿(mǎn)足迭代終止條件；

步驟B3：根據(jù)迭代終止時(shí)節(jié)點(diǎn)所分配的標(biāo)簽，將具有相同標(biāo)簽的節(jié)點(diǎn)歸屬到同一社區(qū)，輸出非重疊社區(qū)結(jié)構(gòu)。

3.根據(jù)權(quán)利要求2所述的一種社交網(wǎng)絡(luò)中的多標(biāo)簽傳播重疊社區(qū)發(fā)現(xiàn)方法，其特征在于，所述步驟B2中，綜合考慮了節(jié)點(diǎn)中心度與標(biāo)簽度分布差異約束條件，進(jìn)行標(biāo)簽更新，標(biāo)簽更新規(guī)則為：

其中表示進(jìn)行標(biāo)簽更新后節(jié)點(diǎn)v選擇的標(biāo)簽，N^l(v)表示與節(jié)點(diǎn)v具有相同標(biāo)簽號(hào)的鄰居節(jié)點(diǎn)集合，m為一參數(shù)，k_v為節(jié)點(diǎn)v的度大小，K_l為標(biāo)簽度的大小，表示屬于標(biāo)簽l的各個(gè)節(jié)點(diǎn)的度大小的總和，定義為：

V為社交網(wǎng)絡(luò)圖的節(jié)點(diǎn)集合，為克羅內(nèi)克函數(shù)，定義為：

p_u為節(jié)點(diǎn)中心度，表示節(jié)點(diǎn)u處于社區(qū)內(nèi)部的中心程度，p_u值越大表示節(jié)點(diǎn)越處于社區(qū)的中心位置，在社區(qū)發(fā)現(xiàn)的迭代過(guò)程中，社區(qū)歸屬越穩(wěn)定；在標(biāo)簽更新的迭代過(guò)程中，每個(gè)節(jié)點(diǎn)u的中心度p_u基于節(jié)點(diǎn)u的所有鄰居集合中與其具有同樣標(biāo)簽的各個(gè)節(jié)點(diǎn)對(duì)其中心度值的貢獻(xiàn)總和進(jìn)行同步的迭代更新，節(jié)點(diǎn)中心度p_u定義為

其中l表示節(jié)點(diǎn)v的當(dāng)前標(biāo)簽號(hào)，N^l(u)表示與節(jié)點(diǎn)u具有相同標(biāo)簽號(hào)的鄰居集合，表示節(jié)點(diǎn)u的鄰居中標(biāo)簽號(hào)為l的節(jié)點(diǎn)個(gè)數(shù)；

迭代終止條件為標(biāo)簽數(shù)目不再發(fā)生變化終止迭代。

4.根據(jù)權(quán)利要求2所述的一種社交網(wǎng)絡(luò)中的多標(biāo)簽重疊社區(qū)發(fā)現(xiàn)方法，其特征在于，所述步驟C中，所述節(jié)點(diǎn)的層級(jí)定義為兩級(jí)：核心層級(jí)與邊界層級(jí)，用于層級(jí)劃分的方法包括顯式層級(jí)劃分和模糊層級(jí)劃分；

顯式層級(jí)劃分的節(jié)點(diǎn)層級(jí)映射函數(shù)定義為：

其中H(v)表示節(jié)點(diǎn)v所劃分的層級(jí)，Boundary=1表示邊界層級(jí)，Core=2表示核心層級(jí)，pMax_l、pMin_l分別表示各個(gè)社區(qū)內(nèi)部節(jié)點(diǎn)中心度的最大值和最小值，r為閾值參數(shù)，取值范圍為0.5~0.8；

模糊層級(jí)劃分的節(jié)點(diǎn)層級(jí)映射函數(shù)定義為：

其中p_v為節(jié)點(diǎn)v的中心度值。