隨著電網數據網的規模越來越巨大,網絡環境越來越多樣化,對傳統的力導向布局技術的效率提出了新的挑戰。
傳統力導向算法通過對每個節點的計算,算出引力和排斥力的合力,再由此合力來移動節點的位置。執行一次後根據節點新位置算出新的能量值,如同力學概念,能量值越小,表示整個網絡越趨於穩定。
一般來說能量值越小,網絡圖的配置顯示就會越清晰,因此當能量值到達最小值的時候,網狀圖的配置狀態就是我們想要的結果。
這種方法的缺點是是網狀圖的節點數、連線數多時,計算所用的時間呈指數上漲,效率很低,用戶體驗較差。
現有少部分電力數據網網絡管理系統布局使用力導向布局算法,但均使用的是傳統力導向布局算法,力導向布局算法使各個網絡設備節點布局的位置不會重疊,各連線的長度幾乎相等,且儘可能不相交。
使用力導向布局方式可以讓拓圖有規則且清爽,但傳統力導向布局算法的計算時間隨著節點個數和連線數量呈指數增長。
在大規模複雜網絡中,這一問題更加明顯。
由此,在大型複雜網絡中,用戶可能難以短時間內獲取拓撲布局,目前的電力數據網網絡管理工具都不具備短時間快速拓撲布局的能力。
通過迭代仿真該物理系統,直到達到某種平衡(力平衡,或能量最小),從而形成一個較為合理的布局。該算法模型通用性很強,被廣泛地應用很多網絡可視化系統當中。
在粒子間斥力和引力的不斷作用下,粒子們從隨機無序的初態不斷發生位移,逐漸趨於平衡有序的終態。
同時整個物理系統的能量也在不斷消耗,經過數次迭代後,粒子之間幾乎不再發生相對位移,整個系統達到一種穩定平衡的狀態,即能量趨於零。
此刻,最終的這幅理想的拓撲結構圖也基本繪製完成。
在傳統力導向布局算法的力模型中,引力即為彈簧力,遵循胡克定律:
上式的參數解釋如下:
FElastic 是兩個相連的節點所受的彈簧力;
K 是彈簧力的彈力係數;
Lcurrent 是兩個節點當前的笛卡爾距離;
Lnature 是彈簧的自然長短,即彈簧不受彈簧方向外力時的長度。
在傳統力導向布局算法的力模型中,斥力即為節點間庫倫力,遵循庫倫定律:
上式的參數解釋如下:
FReplling 是兩個節點所受的斥力;
k 為庫倫常數,即靜電力常數,以此調整全局節點之間的斥力;在傳統力導向算法的力模型中,節點為同性帶電粒子,產生斥力,所以 k 取負數;
q1 和 q2 分別是兩個節點的電荷量;
R 是兩個節點當前的笛卡爾距離。
設力導向布局進行 k 次迭代計算,V 為節點集合,E 為節點之間的邊集合,傳統力導向布局算法的計算流程偽代碼如下:
Forn in V
Do//隨機設置節點的橫坐標(x)位置;u.x = Random_set_x()//隨機設置節點的縱坐標(y)位置;u.y = Random_set_y()
Done
Loop k//循環迭代 k 次
For u in VDo
For v in VDo
If u != v
Then
//計算 u 和 v 節點的庫倫斥力u.force-=Coulomb_repulsion(u,v)//計算 v 和 u 節點的庫倫斥力
v.force-= Coulomb_repulsion(v, u)
Fi
DoneDone
For e in E
Do
//計算 e 邊的胡克引力,u,v 為 e 的端點;e.u.force += Hooke_attraction(e)
e.v.force += Hooke_attraction(e)
Done
For u in V
Do//根據力更新每個節點的橫坐標(x)位置;u.x=Force_update_x(u.force)//根據力更新每個節點的縱坐標(y)位置;
u.y = Force_update_y(u.force)
Done
End Loop
即首先隨機分布所有節點的位置,然後循環計算 k 次每個節點受到的引力和斥力,通過受力情況更新每個節點的位置。
傳統的力導向布局算法的平均時間複雜度是由兩部分組成——每次迭代計算每兩點間的斥力變化0(n2)和每條邊給端點帶來的引力變化0(e),共進行k次迭代計算,即0(k*(n2+
e))。
其中 n 為節點個數,e 為邊數。可以分析出時間隨節點個數成指數增長,隨邊條數呈線性增長。
表 1 為傳統力導向布局在電力數據網大規模拓撲中所用時間的統計結果,每次都添加同樣數量節點與連線,k 值設定為 10。
由表 1 可以分析出傳統的力導向布局算法在大規模拓撲中時間隨節點個數、邊條數增長而增長,
布局時間表現不盡如人意,難以在電力數據網這樣的大規模拓撲中應用。
力導向布局結果連線的長度幾乎相等,且儘可能不相交,節點分布均勻,布局結果較為人性化。
傳統的力導向布局算法在大規模拓撲結構中的計算時間很不理想,因此難以適用於電力數據網這樣的大型拓撲。
可以通過將多層次技術與引力/斥力近似計算算法相結合,得以提高力導向布局算法的效率,是其適用於電力數據網這樣的大型拓撲結構。
就像在大多數傳統的力定向方法中一樣,用相互排斥的帶電粒子作為節點,用彈簧作為節點間的邊。設兩個電荷 u 和 v 之間的距離是 d,u 和 v 之間的斥力正比於 1／d 。
這裡對彈簧引力的選擇並不嚴格地與物理現實有關,使用進行邊 e 彈簧引力的計算,通過該方式計算的彈簧引力可以減少力導向布局算法的計算不相關引力的次數。
由於在經典的力導向算法中,需要多次迭代才能將一個大圖形的初始(隨機)繪圖轉換為最終繪圖,因此我們可以通過多層次策略來降低力導向算法的迭代次數常數因子k。
基本思想:給定 G=(V,E):G0,根據 G0 尺寸遞減創建一系列的圖形 G1,⋯,Gk。然後,用經典的力導向(單級)算法繪製 k 級的最小圖 Gk。
此圖用於獲得隨後繪製的下一個更大圖形 Gk-1 的初始布局。重複這個過程,直到繪製出原始圖形 G0。
多級劃分思想如下:首先,將 G 的節點集劃分為不相交的子集。感應連通子圖稱為太陽系。
太陽系由一個中央太陽節點組成。太陽節點的每個直連的節點叫做行星節點(p-node),在該太陽系中除太陽節點、行星外的其他節點稱為月亮節點(m-node),並且每個 m-node 需要用距離 2 相關 s-node。
每個 m-node 分配給其最近的鄰近 p-node。這個 p-node被重新標記為有月亮節點的行星節點(pm-node),表示它至少分配了一個 m-node。因此,由太陽系引起的 G 子圖的直徑不超過 4。
將一個圖 G 的進行太陽系劃分,分三個步驟工作:
(1)創建太陽節點。拷貝 V 作為太陽節點候選人 V',並從V'中隨機選擇一個節點 s1 作為第一個太陽節點。然後,在 V'中刪除s1以及與s1距離最多為2的節點。
通過同樣的方法迭代選擇下一個太陽節點,直到 V'為空,太陽節點=s1,⋯,s1 即為所有太陽節點的集合。
(2)對於每一個太陽節點,它的所有鄰居都被標記為行星節點。
(3)V 中可能有一些節點既不是行星節點,也不是太陽節點。這些節點是月亮節點,將每個月亮節點分配給 G 中離它最近的行星節點。
圖 1 為原始布局,圖 2 為經過層次劃分後的各個太陽系集合,太陽、行星和月亮節點分別由白色的大圓圈、灰色的中圓圈和黑色的小圓圈表示。
實邊表示太陽系內部的邊,而連接兩個不同太陽系的節點(太陽系間的邊)的邊是虛線邊。
連接m節點及其指定pm節點的邊被繪製為有向邊,表示m節點被分配給這個行星節點。
通過對拓撲圖進行層次劃分,然後對子圖進行力導向迭代計算,對力導向布局方法進行了優化,計算流程如下:
(1)通過多層次劃分方法將原始拓撲進行多層次劃分處理;
(2)多層次劃分處理後,得到一系列太陽系集合,根據太陽系集合將G劃分為G1,⋯,Gk,其中Gk-1完全包含G(k k≥1);
(3)使用傳統力導向布局算法對 Gk 進行布局,得到 G'k;
(4)G'k 的布局作為繪製的下一個更大圖形 Gk-1 的初始布局,通過力導向算法進行 Gk-1 的布局;
(5)重複步驟(3)和步驟(4),直至迭代繪製出圖形 G'o(6)最後使用G'o更新原始的圖結構Go的信息,即得到布局後的結果。
圖 3 為圖 1 對應拓撲的快速力導向布局迭代計算過程。
其中圖 3-a 是 G(k k=3,即 G3),圖 3-b 是 Gk(-1 k=3,即 G2),圖 3-c 是 Gk(-2 k=3,即 G1),圖 3-d 是 Gk(-3 k=3,即 G0)。
快速力導向布局算法的平均時間複雜度是由兩部分組成——每次迭代計算每兩點間的斥力變化 0(nlogn)和每條邊給端點帶來的引力變化 0(e),共進行 k 次迭代計算,即 0(k*(nlogn+e))。
其中 n 為節點個數,e 為邊數。可以分析出時間隨節點個數成對數增長,隨邊條數呈線性增長。
表 2 為快速力導向布局在電力數據網大規模拓撲中所用時間的統計結果,每次都添加同樣數量節點與連線,k 值根據算法劃分子圖自動獲得。
力導向算法是常用的布局算法,該算法在電力數據網網絡元素布局中有廣泛應用。
通過對傳統力導向布局算法的優化,得到一種快速力導向布局算法,該算法可以很好地適用於大型的網絡,相較於傳統力導向布局算法有很大的效率提升。
圖 4 為電力綜合數據網核心、匯聚層網絡元素的力導向布局結果,共有 171 個節點,用時 0.3 秒。
圖 5 為電力綜合數據網所有網絡元素的力導向布局結果,共有 493 個節點,用時 3.1 秒。
快速力導向布局算法能夠快速地對當前綜合數據網進行布局,根據 2.4 的測試數據分析,快速力導向布局算法能夠適用於當前電力所有數據網,該算法成果可以推廣到電力系統相關的所有數據網。
「瓦特和比特」致力於打造國內最專業有趣的能源電力&數據分析學習社區，集結能源行業優秀的業務專家和數據分析大咖，為數據分析從業者和能源從業者提供一種全新的能源電力&數據分析交流方式。
小瓦君提示：關注「瓦特和比特」，學習最新的電力數據技能，為你熱愛的工作打開新的視野～同時也歡迎從事不同崗位的電力人，公眾號留言，跟小瓦君一起分享你的「電力人生」😊