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

在審

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

1.一種基于三角檢測的圖高度節(jié)點檢測與分類方法，其特征在于，包括以下步驟：

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

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

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

步驟4、遍歷完成后，所有未標記的高度節(jié)點為Star節(jié)點，所有標記的高度節(jié)點為Pivot節(jié)點；

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

2.根據權利要求1所述的基于三角檢測的圖高度節(jié)點檢測與分類方法，其特征在于，所述步驟1中，單一網絡圖為無屬性且無方向的簡單圖，標記為G＝(V,E)，其中V＝{v₁,v₂,…,v_n}表示節(jié)點集合，E＝{e₁,e₂,…,e_m}表示邊集合，對于任意e＝(v_i,v_j)表示節(jié)點v_i與v_j之間存在關聯。

3.根據權利要求1所述的基于三角檢測的圖高度節(jié)點檢測與分類方法，其特征在于，所述步驟3中，基于深度優(yōu)先策略對節(jié)點進行遍歷，并且在遍歷過程中同時記錄當前遍歷節(jié)點的父節(jié)點v_f和祖父節(jié)點v_p，從而根據網絡圖G中是否存在關于三者兩兩關聯的邊來判斷三個節(jié)點是否組成三角形結構，具體步驟為：

步驟3.1、初始化遍歷標記集SEEN；

步驟3.2、對網絡圖G中所有節(jié)點進行遍歷，對于每一次遍歷到的節(jié)點v_i，如果該節(jié)點不屬于步驟3.1的SEEN集合，則初始化當前節(jié)點的父節(jié)點v_f與祖父節(jié)點v_p為空并執(zhí)行步驟3.3，否則不進行操作；

步驟3.3、將當前遍歷節(jié)點v_i加入至SEEN集合中；

步驟3.4、對網絡圖G中v_i的所有鄰居節(jié)點進行遍歷，對每一個遍歷的鄰居節(jié)點c_j，有如下三種處理方式：

1)如果c_j＝v_p，或在G中滿足e＝(v_f,c_j)∈E，則表明G中存有如下連邊關系：

e＝(v_i,c_j)∈E

e＝(v_f,c_j)∈E

e＝(v_i,v_f)∈E

由此，v_i、v_f以及c_j三個節(jié)點構成三角形結構關系，將三者均加入至步驟2的三角形節(jié)點標記集合T中；

2)如果c_j＝v_f，或在G中則不做任何操作；

3)如不滿足以上兩種情況，令v_i＝c_j，v_f＝v_i，v_p＝v_f，回到步驟3.3迭代執(zhí)行。

4.根據權利要求1所述的基于三角檢測的圖高度節(jié)點檢測與分類方法，其特征在于，所述步驟5中，對于Super Pivot節(jié)點集P_c，度大小閾值為全局度的前5％，記該閾值對應的度大小為μ，則對于任意x屬于P_c，x的鄰居數大于等于μ，其中Γ(x)表示節(jié)點x在G中的一步鄰居節(jié)點集合，|Γ(x)|表示Γ(x)的規(guī)模大小；對于Huge Star節(jié)點集S_c，度大小閾值為G中所有節(jié)點的平均度，記該平均度大小為ε，則對于任意x屬于S_c，x的鄰居個數大于等于ε。