[發(fā)明專利]一種多關(guān)系社交網(wǎng)絡(luò)的社團(tuán)劃分方法

在審

• 申請(qǐng)?zhí)枺?/td>: 201710579247.7
• 申請(qǐng)日: 2017-07-17
• 公開(kāi)（公告）號(hào): CN107545509A
• 公開(kāi)（公告）日: 2018-01-05
• 發(fā)明（設(shè)計(jì)）人: 劉雪芳;李國(guó)偉;楊清海
• 申請(qǐng)（專利權(quán)）人: 西安電子科技大學(xué);西安中電科西電科大雷達(dá)技術(shù)協(xié)同創(chuàng)新研究院有限公司
• 主分類號(hào): G06Q50/00
• 分類號(hào): G06Q50/00;G06K9/62
• 代理公司: 西安長(zhǎng)和專利代理有限公司61227
• 代理人: 黃偉洪

1.一種多關(guān)系社交網(wǎng)絡(luò)的社團(tuán)劃分方法，其特征在于，所述多關(guān)系社交網(wǎng)絡(luò)的社團(tuán)劃分方法包括以下步驟：

首先將原始網(wǎng)絡(luò)數(shù)據(jù)轉(zhuǎn)化為相似度張量，接著建立分析模型；

然后利用張量分解方法得到張量的分解結(jié)果；

最后利用聚類分析方法得到社團(tuán)的劃分結(jié)果。

2.如權(quán)利要求1所述的多關(guān)系社交網(wǎng)絡(luò)的社團(tuán)劃分方法，其特征在于，所述多關(guān)系社交網(wǎng)絡(luò)的社團(tuán)劃分方法利用譜聚類的思想建立多關(guān)系社交網(wǎng)絡(luò)社團(tuán)劃分的譜聚類方法，譜聚類的具體包括：

對(duì)于任意的單關(guān)系網(wǎng)絡(luò)G＝(V,E)，節(jié)點(diǎn)的數(shù)量為N，W是存儲(chǔ)網(wǎng)絡(luò)數(shù)據(jù)的鄰接矩陣，D是一個(gè)對(duì)角陣，它的元素是節(jié)點(diǎn)度的數(shù)量；其中L＝D-W稱作拉普拉斯矩陣，而且標(biāo)準(zhǔn)化的拉普拉斯矩陣表示如下：

L_Ncut＝D^-1/2LD^-1/2＝I-S_N；

其中，I是單位矩陣，S_N是稱作標(biāo)準(zhǔn)化的相似矩陣；S_N和L_Ncut具有相同的特征向量，而且特征值滿足對(duì)于多關(guān)系網(wǎng)絡(luò)，對(duì)每一種維度計(jì)算相似度矩陣，根據(jù)譜聚類的方法可以建立如下的分析模型：

其中，trace(·)算子是求矩陣的跡，是松弛分配矩陣，M為社團(tuán)數(shù)量。由于S_N是半正定矩陣，問(wèn)題轉(zhuǎn)化為Frobenius范數(shù)分析模型：

其中，表示二范數(shù)算子；通過(guò)對(duì)問(wèn)題的求解得到U矩陣，通過(guò)對(duì)U矩陣進(jìn)行聚類分析得到社團(tuán)的劃分結(jié)果。

3.如權(quán)利要求1所述的多關(guān)系社交網(wǎng)絡(luò)的社團(tuán)劃分方法，其特征在于，所述多關(guān)系社交網(wǎng)絡(luò)的社團(tuán)劃分方法具體包括以下步驟：

步驟一，原始網(wǎng)絡(luò)數(shù)據(jù)轉(zhuǎn)化為相似度張量，并建立優(yōu)化問(wèn)題；

步驟二，相似度張量的分解，采用張量分解的方法對(duì)相似度張量進(jìn)行分解，在實(shí)際應(yīng)用中根據(jù)不同的需求選擇具體的張量分解方法；

步驟三，聚類分析，對(duì)于得到的U矩陣進(jìn)行聚類分析，得到社團(tuán)的劃分結(jié)果。

4.如權(quán)利要求3所述的多關(guān)系社交網(wǎng)絡(luò)的社團(tuán)劃分方法，其特征在于，所述步驟一具體包括：

(1)多關(guān)系網(wǎng)絡(luò)以不同的觀測(cè)維度可以得到類似于單關(guān)系網(wǎng)絡(luò)對(duì)象的相似度矩陣，所有K個(gè)觀察角度可以得到K個(gè)相似度矩陣，相似度張量的生成過(guò)程是將K個(gè)相似度矩陣疊加在一起，每種關(guān)系矩陣構(gòu)成張量；

(2)在多關(guān)系網(wǎng)絡(luò)中，每種關(guān)系對(duì)網(wǎng)絡(luò)聚類的貢獻(xiàn)或影響是不一樣的，每種關(guān)系對(duì)網(wǎng)絡(luò)聚類的影響由數(shù)據(jù)決定，每種關(guān)系對(duì)網(wǎng)絡(luò)聚類的權(quán)重朝著網(wǎng)絡(luò)聚類結(jié)果更明顯的方向調(diào)整。

5.如權(quán)利要求4所述的多關(guān)系社交網(wǎng)絡(luò)的社團(tuán)劃分方法，其特征在于，參照單目標(biāo)關(guān)系網(wǎng)絡(luò)的譜聚類優(yōu)化問(wèn)題建立多關(guān)系網(wǎng)絡(luò)的譜聚類分析模型：

其中，w_k為每個(gè)維度上的權(quán)重因子，對(duì)于K種關(guān)系的權(quán)重，歸一化處理，建立多關(guān)系的譜聚類問(wèn)題。

6.如權(quán)利要求3所述的多關(guān)系社交網(wǎng)絡(luò)的社團(tuán)劃分方法，其特征在于，所述步驟二具體包括：

(a)用Tucker分解來(lái)分解張量，對(duì)得到的相似度張量，采用Tucker分解來(lái)解決原始問(wèn)題，如下式：

分別表示張量與U^T進(jìn)行模1乘積、與U^T進(jìn)行模2乘積、與W^T進(jìn)行模3乘積；

(b)對(duì)于Tucker分解的方法，如下式：

7.一種應(yīng)用權(quán)利要求1～6任意一項(xiàng)所述多關(guān)系社交網(wǎng)絡(luò)的社團(tuán)劃分方法的社交網(wǎng)絡(luò)。