[發明專利]多維網絡基于介數中心度進行網絡分析的方法

在審

• 申請號: 201410403859.7
• 申請日: 2014-08-15
• 公開（公告）號: CN104168158A
• 公開（公告）日: 2014-11-26
• 發明（設計）人: 王朝坤;王萌;楊建祥
• 申請（專利權）人: 清華大學
• 主分類號: H04L12/26
• 分類號: H04L12/26;H04L12/24
• 代理公司: 北京匯信合知識產權代理有限公司 11335
• 代理人: 王詠雯

技術領域

本發明涉及計算機社交網絡技術領域，特別是涉及一種多維網絡基于介數中心度進行網絡分析的方法。

背景技術

隨著社交網絡等現實社會中存在的復雜網絡的發展，網絡中的關系不再僅僅表現為單一的連接關系，網絡的個體之間可能具有多重不同類型的關系，傳統的基于單一連接結構的網絡分析已不能全面地反映網絡的特性。此外，隨著網絡規模的不斷增大，對于網絡分析時效性要求的不斷提高，傳統的靜態網絡分析方法已經不符合現今網絡分析技術的發展趨勢。在網絡分析中，需要尋找承擔了重要溝通作用的個體，這些個體能夠很好的將其他個體聯系起來，在消息傳播過程中處于關鍵位置。而介數中心度(Betweenness?Centrality)則能夠衡量個體在網絡中所承擔的這種重要性，是網絡分析中一個極其關鍵的度量指標。對于該指標來說，傳統的全局度量方法會引入長路徑所帶來的干擾，且其計算所需的時間代價過高，這些都是限制網絡分析技術發展的重要瓶頸。因此，如何基于多重網絡關系設計高效的、實時的介數中心度計算方法，使得在社交網絡、傳感器網絡等不同網絡中能夠快速準確地找到起到關鍵作用的重要節點，是現今網絡分析領域中需要解決的關鍵技術問題。

因此，目前需要本領域技術人員迫切解決的一個技術問題就是：如何能夠創新地提出一種有效的網絡分析方法，以滿足實際應用中的更多需求。

發明內容

本發明所要解決的技術問題是提供一種多維網絡基于介數中心度進行網絡分析的方法，通過在網絡分析中快速準確地定位個體所處橋接位置的重要性，找到網絡中真正起到溝通連接作用的重要個體，以此分析并控制網絡中信息的傳播和個體間的交流情況。

為了解決上述技術問題，本發明實施例公開了一種多維網絡基于介數中心度進行網絡分析的方法，包括：

根據實際網絡關系生成多維網絡的函數；所述多維網絡的函數與實際網絡中的節點、維度邊和邊的維度相關；

將所述多維網絡中相鄰節點之間的維度邊通過映射函數映射到一維上，從而得到所述多維網絡對應的一維網絡；

計算網絡中所有個體的局部介數中心度；

按照所計算的局部介數中心度對網絡進行分析。

優選的，所述方法還包括：

當所述多維網絡結構發生動態變化時，更新局部介數中心度產生影響的點對依賴，以實現對網絡個體的局部介數中心度的更新。

優選的，所述多維網絡結構發生動態變化包括增加和/或刪除一條維度邊。

優選的，所述實際網絡為社交網絡、教育網絡、軍事網絡和/或游戲網絡。

優選的，當所述實際網絡為社交網絡中，維度集合包括親戚、同學、朋友、同事和/或鄰居不同維度上的關系

與現有技術相比，本發明具有以下優點：

本發明通過有效方法對多維網絡局部介數中心度進行計算，使得在網絡分析中能夠快速準確地定位個體所處橋接位置的重要性，找到網絡中真正起到溝通連接作用的重要個體，以此分析并控制網絡中信息的傳播和個體間的交流情況。

進一步地，本發明提出在動態網絡環境下局部介數中心度的更新方法，使得在網絡個體間關系發生改變的同時，個體所處溝通連接位置重要性能夠得到快速更新，從而實現對網絡特性、態勢的實時分析與監控。

附圖說明

圖1是本發明的一種多維網絡基于介數中心度進行網絡分析的方法實施例的流程示意圖。

具體實施方式

為使本發明的上述目的、特征和優點能夠更加明顯易懂，下面結合附圖和具體實施方式對本發明作進一步詳細的說明。

參見圖1，本方案所述的一種多維網絡基于介數中心度進行網絡分析的方法，具體包括：

步驟S101，根據實際網絡關系生成多維網絡的函數；所述多維網絡的函數與實際網絡中的節點、維度邊和邊的維度相關；

步驟S102，將所述多維網絡中相鄰節點之間的維度邊通過映射函數映射到一維上，從而得到所述多維網絡對應的一維網絡；

具體實踐中，根據實際網絡關系生成多維網絡G＝(V，E，L)。其中V表示網絡中的節點集合，E表示網絡中維度邊的集合，L表示網絡中所有維度集合。在實際應用中，實際網絡為社交網絡、教育網絡、軍事網絡和/或游戲網絡。例如在社交網絡中，維度集合可以包括親戚、同學、朋友、同事、鄰居等不同維度上的關系。

將網絡中相鄰節點之間的維度邊(v，w，d)通過映射函數ω映射到一維上。其中v，w∈V，d∈L。映射函數表示為：ω(v，w)＝|{(v，w，d)|(v，w，d)∈E}|，其中ω(v，w)∈[0，|L|]。