[發明專利]一種基于三角檢測的圖高度節點檢測與分類方法

在審

• 申請號: 202011090374.9
• 申請日: 2020-10-13
• 公開（公告）號: CN112199563A
• 公開（公告）日: 2021-01-08
• 發明（設計）人: 趙穎;劉家瑋;王江奎;吉梓芃;李俊俏;蔣昊瑾;周芳芳
• 申請（專利權）人: 中南大學
• 主分類號: G06F16/906
• 分類號: G06F16/906;G06Q50/00
• 代理公司: 長沙新裕知識產權代理有限公司 43210
• 代理人: 劉加

本發明公開了一種基于三角檢測的圖高度節點檢測與分類方法，首先，構建節點與邊的原始圖G＝(V,E)，并根據原始圖的結構信息計算出所有節點的度和鄰居列表。然后從任意節點開始采用深度優先策略進行遍歷，對遍歷到的節點，檢查其與父節點及祖父節點是否存在三角關聯，如是則標記這三個節點。遍歷完成后，所有未標記的高度節點為Star節點，而所有標記的高度節點為Pivot節點。最后，對節點根據度大小排序，位于前5％的Pivot節點為匯聚結構；同時節點度大小高于平均度的Star節點為大型星型結構。本發明實現了將三角檢測應用于社交網絡和網絡脆弱性分析中，具有檢測速度快、準確性高的特點，適合推廣應用。

技術領域

本發明屬于數據結構和頻繁子圖挖掘技術領域，涉及一種基于三角檢測的圖高度(High Degree)節點檢測與分類方法。

背景技術

圖結構是一種常見的非線性結構，被用于描述各種復雜的數據對象，在自然科學、社會科學和人文科學等許多領域有著非常廣泛的應用。圖中通常包含豐富的信息，其中高度節點在很多應用場景中受到高度關注。而高度節點又可以根據是否存在相連的鄰居劃分為匯聚結構(Super Pivot)和大型星型結構(Huge Star)。例如，在社交網絡的分析中，人們對匯聚結構和大型星形結構十分感興趣。比如想快速傳播信息的人就對度數極高的節點比較感興趣，因為在社交網絡中度數極高的節點(匯聚結構和大型星形結構)很可能是社交達人，也可能是流量大咖，這些人能迅速地將信息傳播給更多的人。又例如，網絡脆弱性分析是網絡安全分析和風險評估的重要組成部分。網絡脆弱性分析是通過對網絡進行基于經驗的分析或基于模型的分析等有效手段得出網絡的脆弱性，然后評估網絡安全，幫助管理員及時了解網絡系統的安全狀況，及時發現并修補漏洞，避免網絡攻擊。在網絡脆弱性分析中，人們會對大型星形結構比較感興趣，因為這些結構很容易成為被攻擊的對象。

常見對匯聚結構和大型星形結構的分類方法是通過直接檢測是否有相連的鄰居來實現的。但是，直接檢測方法在面對社交網絡、計算機網絡等數據量大的應用場景時，存在耗時較大，并且有很多重復計算和不必要的步驟。

發明內容

本發明的目的在于提供一種基于三角檢測的圖高度節點檢測與分類方法。

其具體技術方案為：

一種基于三角檢測的圖高度節點檢測與分類方法，包括以下步驟：

步驟1、將社交網絡、計算機網絡等圖數據抽象為由節點與鄰邊構成的單一網絡圖G；

步驟2、構建并初始化三角形節點標記集合T；

步驟3、對步驟1中網絡圖G的節點進行遍歷操作，對當前遍歷的節點v_i，根據其與父節點v_f及祖父節點v_p三者在G中的連接關系，判斷三個節點是否構成三角形結構關聯，如是則將三個節點均加入到步驟2中的三角形節點標記集合T中；

步驟4、遍歷完成后，所有未標記的高度節點為Star節點，所有標記的高度節點為Pivot節點。

步驟5、對步驟4中所得到的兩類高度節點，根據節點度大小進行排序，位于全局度的前5％的Pivot節點為匯聚結構(Super Pivot)；節點度大小高于全局平均度的Star節點為大型星型結構(Huge Star)。

進一步地，所述步驟1中，單一網絡圖為無屬性且無方向的簡單圖，標記為G＝(V,E)，其中V＝{v₁,v₂,…,v_n}表示節點集合，E＝{e₁,e₂,…,e_m}表示邊集合，對于任意e＝(v_i,v_j)表示節點v_i與v_j之間存在關聯。