[發明專利]一種基于緊密度和結構洞的復雜網絡重要節點排序方法

在審

• 申請號: 201710481040.6
• 申請日: 2017-06-22
• 公開（公告）號: CN107317704A
• 公開（公告）日: 2017-11-03
• 發明（設計）人: 朱參世;汪筱陽;朱琳
• 申請（專利權）人: 西京學院
• 主分類號: H04L12/24
• 分類號: H04L12/24
• 代理公司: 西安西達專利代理有限責任公司61202
• 代理人: 高亦哲

技術領域

本發明屬于網絡評估方法技術領域，具體涉及一種基于緊密度和結構洞的復雜網絡重要節點排序方法。

背景技術

復雜網絡中節點重要性評估是網絡分析的一個基本問題，同時也越來越成為目前研究的熱點。在電力網絡、交通網絡和病毒與疾病免疫控制過程等不同網絡中如何確定關鍵節點都顯得非常重要。

然而，不同規模大小的網絡關鍵節點評估需要不同的方法。目前，基于網絡結構的節點重要性主要從網絡的局部屬性、全局屬性、網絡的位置和隨機游走四個方面進行評估。其中網絡的局部屬性主要考慮節點自身信息及其鄰居信息，由于計算簡單，時間復雜度低，一般可用于大型網絡。網絡的全局屬性主要考慮網絡的全局信息，但全局信息時間復雜度高，不適用于大型網絡。Kitsak等人于2010年首次提出了節點重要性依賴于其在整個網絡中的位置的思想，并且利用K-核分解獲得了節點重要性排序指標(k-shell)，該指標時間復雜度低，適用于大型網絡，而且比度、介數更能準確識別在疾病傳播中最有影響力的節點。隨機游走的節點重要性排序方法主要基于網頁之間的鏈接關系的網頁排序技術，由于網頁之間的鏈接關系可以解釋為網頁之間的相互關聯和相互支持，從而判斷出網頁的重要程度。

上述方法均只從某一方面評價節點重要性或對節點進行排序，實際上，網絡節點的重要性不僅和節點局部屬性有關，而且與其在網絡中所處位置以及節點之間的相互依賴程度密切相關。單一指標在不同的網絡拓撲結構上的計算具有很大的片面性，網絡中一個節點的重要性和網絡的整體結構相關，需要從不同的角度，利用節點的多個重要性指標來進行綜合評價。所以，評估節點重要性不僅要考慮節點自身屬性，同時要考慮節點的全局屬性。事實上，最具影響力節點在具有社團結構的網絡中應具有以下特征：社區中心和各社區中起到“橋接”作用的節點。因此，關鍵節點排序問題關注的焦點不能僅局限于網絡中的核心節點，也不可忽略處于結構洞位置的節點。節點緊密度能較好地反映該節點對其他節點的影響力，同時體現該節點在網絡拓撲位置的不同。綜上所述，基于緊密度和結構洞來評估復雜網絡的關鍵節點，綜合考慮了節點的局部信息(網絡約束系數)和全局信息(緊密度)，通過構建結構洞影響矩陣，能夠更加準確高效的評估網絡中的關鍵節點。

發明內容

本發明的目的在于克服現有技術的不足，提供一種基于緊密度和結構洞的復雜網絡重要節點排序方法，通過構建結構洞影響矩陣，使得評估結果對于大型真實復雜網絡能夠更加準確高效。

為實現上述發明目的，本發明所采用的技術方案是：一種基于緊密度和結構洞的復雜網絡重要節點排序方法，包括以下步驟：

Step1：根據節點連接情況建立復雜網絡鄰接矩陣A＝[a_ij]_n×n，其中，n為復雜網絡中的節點數量，當節點i和節點j有連接時，a_ij＝1；當節點i和節點j無連接時，a_ij＝0。

Step2：計算網絡中各節點的緊密度C_c和網絡約束系數C_i，計算公式為：

Step3：結合鄰接矩陣和緊密度，建立節點影響因子矩陣H_A；

Step4：結合節點影響因子矩陣和網絡約束系數，建立結構洞影響矩陣H_C；

Step5：計算各節點重要性M_i，計算公式為：

Step6：根據M_i得出的節點重要度按照從大到小的順序進行排序，排在前邊的節點即為相對重要的節點。

所述Step3中節點影響因子矩陣H_A的計算公式如式(Ⅳ)所示：

所述Step4中結構洞影響矩陣H_C的計算公式如式(Ⅴ)所示：

本發明的有益效果是：

相互連通節點之間的依賴關系最簡單最直接的形式是存在于鄰接節點之間。本發明綜合考慮了節點的緊密度(全局信息)和網絡約束系數(局部信息)，提出了基于緊密度和結構洞的復雜網絡重要節點排序方法，可以得到更為精確的評估結果。

附圖說明

圖1是本發明基于緊密度和結構洞的復雜網絡重要節點排序方法的流程圖；

圖2是ARPA網絡拓撲結構示意圖。

具體實施方式