[發明專利]一種電力光纖網社團劃分方法

有效

• 申請號: 202110677581.2
• 申請日: 2021-06-18
• 公開（公告）號: CN113411691B
• 公開（公告）日: 2022-03-11
• 發明（設計）人: 姜萬昌;萬超逸;陳鵬飛;霍聰;王圣達;劉丹妮;郭健
• 申請（專利權）人: 東北電力大學
• 主分類號: H04Q11/00
• 分類號: H04Q11/00;G06F30/18;G06Q10/04;G06Q50/00;G06Q50/06
• 代理公司: 北京中理通專利代理事務所(普通合伙) 11633
• 代理人: 劉慧宇

1.一種電力光纖網社團劃分方法，其特征是：該方法由以下步驟實現：

步驟一、根據電力光纖網絡拓撲結構，構建電力光纖網絡模型G(V，E，W，B)；

節點集V＝{V_i|i＝1，2......，N}，N為節點的數量；邊集E{e_ij|i＝1，......，N，j＝1，......，N，i≠j}，e_ij＝(v_i，v_j)為從節點v_i到節點v_j的邊，其中e_ij＝e_ji，節點權值集其中為節點v_i的權重；B＝{0，1}，用于表示該節點是否為一二級骨干網絡上的節點；若是，則取值為1，否則取值為0；

步驟二、從步驟一構建的電力光纖網絡模型G(V，E，W，B)中抽取出一二級骨干網絡，并將所述一二級骨干網中省級下屬各個地級市行政區內部的站點和鏈路保留，形成初始社團，即獲得骨干網絡G₀(V⁽⁰⁾，E⁽⁰⁾，W)，節點集V⁽⁰⁾∈V，邊集E⁽⁰⁾∈E，確定社團集合為C⁽⁰⁾；

步驟三：定義G中邊e_ij的局部邊介數LEB_ij；

設定為G中經過邊e_ij的兩跳最短路徑的數目與所有兩跳路徑總數之比，為G中經過邊e_ij的三跳最短路徑的數目與所有三跳路徑總數之比，并綜合作為衡量每條邊e_ij的局部連通程度，分別用下式表示為：

式中，σ_st(2)為G中所有兩跳最短路徑的數目，σ_st(2)(e_ij)表示以節點v_s為起點，以節點v_t為終點的兩跳最短路徑中經過邊e_ij的數目；

式中，σ_st(3)為G中所有三跳最短路徑的數目，σ_st(3)(e_ij)表示以節點v_s為起點，以節點v_t為終點的三跳最短路徑中經過邊e_ij的數目；

根據和的公式，獲得局部邊介數LEB_ij為：

式中，1/2和1/3分別為和的權重系數；

步驟四：定義G中邊e_ij的全局鄰介數影響力度量

首先，定義鄰居節點的邊影響力度量用下式表示為：

式中，A_ik、A_jl分別為G的相鄰矩陣A中的(i，k)元和(j，l)元，A＝(A_ij)_N*N；如果存在連接節點v_i、v_k的邊，則A_ik＝1，否則A_ik＝0；如果存在連接節點v_j、v_l的邊，則A_jl＝1，否則A_jl＝0；

N[j]為包括節點v_j的所有鄰居節點，N[i]為包括節點v_i的所有鄰居節點；N(j)為不包括節點v_j的所有鄰居節點，N(i)為不包括節點v_i的所有鄰居節點；

V\N[j]為去除N[j]占節點集V的其它節點集；V\N[i]為去除N[i]占節集V的其它節點集；

分別采用A_ik*B′(k)和A_jl*B′(l)替換A_ik和A_jl，邊e_ij的全局鄰介數影響力度量用下式表示為：

式中，和為節點v_k、v_l的歸一化介數中心性，B(k)和B(l)為節點v_k、v_l的全局介數，并且

式中，σ_st為節點v_s、v_t之間的最短路徑數，σ_st(k)為通過節點v_k的節點v_s、v_t之間的最短路徑數；

步驟五、除了G₀中所保留的邊，將G中剩余的邊按照邊緣中心性LEC_ij去邊，找到模塊度最大時的社團劃分，定義為G₁；具體為：

步驟五一、根據步驟三獲得的局部邊介數LEB_ij和步驟四獲得的全局鄰介數的邊影響力度量獲得每條邊的邊緣中心性LEC_ij，用下式表示為：

步驟五二、根據模塊度的定義：

式中，m為整個網絡邊數，A_ij為連接節點v_i、v_j的邊，P_ij為空模型中節點v_i、v_j之間有邊相連的概率：

式中，d_i、d_j分別為G中節點v_i、v_j的度；

式中，c_i、c_j分別為節點v_i、v_j所屬的社團，當節點v_i、v_j屬于同一個社團時，δ(c_i，c_j)取值為1，否則取值為0；

步驟五三、設置不同的閾值θ用于劃分G，對于G中大于閾值θ的邊，則去掉該邊，計算每個閾值θ對應的模塊度Q，并選擇具有最大模塊度的網絡對應的θ作為G的閾值；

對于G中的每條邊的LEC_ij，按照降序排列，將邊集E⁽⁰⁾中的邊始終保留，當其余邊集E/E⁽⁰⁾中邊的LEC_ij大于閾值θ時，則去掉該邊，找到模塊度最大時劃分的社團G₁(V⁽¹⁾，E⁽¹⁾，W)；

步驟六：合并G₁中的孤立節點及剩余社團到G₀上，獲得最終社團劃分結果；具體過程為：

步驟六一、對于G₁中的孤立節點，當該孤立節點在G中的鄰居節點也都是孤立節點時，稱為雙孤立節點；找到所述鄰居節點中度最大的節點，將度最大的節點與雙孤立節點相連，形成零散社團；

當該孤立節點在G中存在鄰居節點且該鄰居節點位于某個社團時，稱為單孤立節點；將所述單孤立節點在G中度為1的節點與G中原有相連節點連接；在G中度不為1的節點與其鄰居節點中度最大的節點連接；

步驟六二、獲得帶有G₀的點和邊的p個社團與其余q個社團，此時網絡圖表示為G₂，G₂中的社團集合為C⁽²⁾＝{c₁，...，c_p，c_p+1，...，c_p+q}，其中前p個社團是帶有G₀中的節點和邊的社團，C⁽⁰⁾∈{c₁，...，c_p}；

根據連邊密度，將C⁽²⁾中社團{c_p+1，...，c_p+q}與社團{c₁，...，c_p}合并，并且前p個社團間不能互相合并，直到G₂中所有節點都連接在G₀上；具體為：

首先，建立一個q行p列的矩陣R＝(R_ab)_q*p；

式中，稱為連邊密度；|c_a|為該社團內部邊數，E(c_a，c_b)為社團c_a和社團c_b在G中社團間的連接邊數；

然后，找到矩陣R中最大的R_ab，合并社團c_a和社團c_b，更新矩陣，直到矩陣變成一個q行p列的零矩陣，獲得社團集合C⁽³⁾＝{c₁，...，c_p}，C⁽⁰⁾∈C⁽³⁾；

保持此時社團集合C⁽³⁾內的節點不變，將各個社團內部在G中原有的邊連接上，獲得最終劃分的社團集合C⁽⁴⁾＝{c₁，...，c_p}，C⁽³⁾∈C⁽⁴⁾。

2.根據權利要求1所述的一種電力光纖網社團劃分方法，其特征在于：步驟一中，將220kV以上的站點設定為權重為1的節點，其余站點設定為權重為0.5的節點；每條連接邊e_ij的權重為節點v_i、v_j的均值，即為：

式中，為節點v_j的權重。