[發明專利]一種多關系社交網絡的社團劃分方法

在審

• 申請號: 201710579247.7
• 申請日: 2017-07-17
• 公開（公告）號: CN107545509A
• 公開（公告）日: 2018-01-05
• 發明（設計）人: 劉雪芳;李國偉;楊清海
• 申請（專利權）人: 西安電子科技大學;西安中電科西電科大雷達技術協同創新研究院有限公司
• 主分類號: G06Q50/00
• 分類號: G06Q50/00;G06K9/62
• 代理公司: 西安長和專利代理有限公司61227
• 代理人: 黃偉洪

技術領域

本發明屬于計算機應用技術領域，尤其涉及一種多關系社交網絡的社團劃分方法。

背景技術

在社交網絡中人與人之間的聯系往往是多種多樣的，把這種包含多種社交關系的網絡稱為多關系社交網絡，在現實生活中是普遍存在的。在多關系社交網絡中，網絡中的節點往往存在聚類的現象，把這種聚類當中的每一個簇叫做一個社團。Tang等人發表的文章“Uncovering Groups via Heterogeneous Interaction Analysis”中研究了多關系網絡的社團劃分問題，然而在社團劃分時未考慮各個關系之間的權重問題。多關系社交網絡社團劃分的關鍵在于如何考慮每一維度關系對社團劃分的影響。本發明提出用具體數據來確定各個關系權重的思想，一切由數據決定。另外，目前存在的采用張量分解進行多關系社交網絡社團劃分的方法復雜度高，而且性能不好。

綜上所述，現有技術存在的問題是：在確定各個關系之間的權重時，缺少理論指導，多關系社交網絡區別于單關系社交網絡主要在于各個關系對于社團成型的貢獻是不一樣的，分析各個關系的權重是多關系社交網絡社團劃分的關鍵問題。利用傳統的HOOI(High Order Orthogonal Iteration)方法進行張量分解的社團劃分方法復雜度高，不適合大規模社交網絡。

發明內容

針對現有技術存在的問題，本發明提供了一種多關系社交網絡的社團劃分方法。

本發明是這樣實現的，一種多關系社交網絡的社團劃分方法，所述多關系社交網絡的社團劃分方法包括以下步驟：

首先將原始網絡數據轉化為相似度張量，接著建立分析模型；

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

最后利用聚類分析方法得到社團的劃分結果。

進一步，所述多關系社交網絡的社團劃分方法利用譜聚類的思想建立多關系社交網絡社團劃分的譜聚類方法，譜聚類的具體包括：

對于任意的單關系網絡G＝(V,E)，節點的數量為N，W是存儲網絡數據的鄰接矩陣，D是一個對角陣，它的元素是節點度的數量；其中L＝D-W稱作拉普拉斯矩陣，而且標準化的拉普拉斯矩陣表示如下：

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

其中，I是單位矩陣，S_N是稱作標準化的相似矩陣；S_N和L_Ncut具有相同的特征向量，而且特征值滿足對于多關系網絡，對每一種維度計算相似度矩陣，根據譜聚類的方法可以建立如下的分析模型：

s.t. U^TU＝I

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

s.t. U^TU＝I

其中，表示二范數算子；通過對問題的求解得到U矩陣，通過對U矩陣進行聚類分析得到社團的劃分結果。

進一步，所述多關系社交網絡的社團劃分方法具體包括以下步驟：

步驟一，原始網絡數據轉化為相似度張量，并建立優化問題；

步驟二，相似度張量的分解，采用張量分解的方法對相似度張量進行分解，在實際應用中根據不同的需求選擇具體的張量分解方法；

步驟三，聚類分析，對于得到的U矩陣進行聚類分析，得到社團的劃分結果。

進一步，所述步驟一具體包括：

(1)多關系網絡以不同的觀測維度可以得到類似于單關系網絡對象的相似度矩陣，所有K個觀察角度可以得到K個相似度矩陣，相似度張量的生成過程是將K個相似度矩陣疊加在一起，每種關系矩陣構成張量；

(2)在多關系網絡中，每種關系對網絡聚類的貢獻或影響是不一樣的，每種關系對網絡聚類的影響由數據決定，每種關系對網絡聚類的權重朝著網絡聚類結果更明顯的方向調整；

進一步，參照單目標關系網絡的譜聚類優化問題建立多關系網絡的譜聚類分析模型：

其中，w_k為每個維度上的權重因子，對于K種關系的權重，歸一化處理，建立多關系的譜聚類問題。

進一步，所述步驟二具體包括：

(a)用Tucker分解來分解張量，對得到的相似度張量，采用Tucker分解來解決原始問題，如下式：