[發明專利]一種基于力導引的異形區域拓撲布局算法

在審

• 申請號: 201810985452.8
• 申請日: 2018-08-28
• 公開（公告）號: CN109145462A
• 公開（公告）日: 2019-01-04
• 發明（設計）人: 姚興苗;焦海超;胡光岷
• 申請（專利權）人: 電子科技大學
• 主分類號: G06F17/50
• 分類號: G06F17/50
• 代理公司: 成都虹盛匯泉專利代理有限公司 51268
• 代理人: 王偉

本發明公開了一種基于力導引的異形區域拓撲布局算法，包括以下步驟：S1、基于標簽傳播的初始布局區域劃分；S2、在已確定的異形區域內進行節點的初始位置布局；S3、通過增加區域頂點對原始節點的吸引力從而將布局適應于異形區域的約束。本發明提供了一種基于力導引的異性區域拓撲布局算法，首先進行社團劃分以完成節點的初始位置布局，接著改進了FR算法模型中引力的計算方式，通過改變節點間的引力計算公式以及引入異性區域頂點的引力模型，使得拓撲布局算法可以達成各個節點在保持相對良好的美學要求下充分占據各異形區域空間的目標，消除了傳統FR算法所不能提供的區域約束的限制，取得了更好的布局效果。

技術領域

本發明涉及一種基于力導引的異形區域拓撲布局算法。

背景技術

真實世界的網絡大多是復雜網絡，其復雜性主要表現在結構復雜，無法用相對單一的拓撲結構進行表示，同時具有很強的聚集性，圍繞某些節點形成聚集度高的群體，再加上節點類型的復雜性，可以代表各種對象和他們的關系。大多數真實網絡的一個重要公共特性是聚集性，即網絡中若兩個節點都與另一個相同節點具有關系的話，這兩個節點彼此有較大概率也具有相互關系。相同網絡中由于節點聚集特性的不同，節點關系的緊密程度也相應不同，基于此可以將網絡分割成多個具有相同特征但規模較小的局部網絡，這就是所謂的社團。網絡的社團特征不僅對于網絡本身結構具有重要的研究意義，而在實際拓撲布局展示中也有正面作用，對于規模相對復雜的網絡，通過將其進行社團劃分，分治地進行拓撲布局，是目前對復雜拓撲進行可視化的一個重要手段。

可視化領域中，使用的比較廣泛的算法包括徑向布局算法等基于幾何形狀的拓撲布局算法以及力導引算法。力導引的基本模型包括彈簧模型、KK模型和FR模型，其中FR模型是實際使用中應用比較廣泛的一類模型。

FR模型中的節點具有兩種力，引力和斥力，其定義分別如公式(1-3)和公式(1-4)所示，公式中的d表示兩個節點的距離，k為常量，定義如公式(1-5)所示，其中C為常量，一般由實際實驗得到或者用戶自定義設置，area表示的是布局范圍的面積，式中分母則表示節點的總數，k的物理含義可以理解為當不考慮邊的影響時，所有節點均勻布局在空間中時每個節點周圍的空白區域的半徑。FR模型設定任意節點間都具有斥力，而引力僅存在于具有拓撲連接關系的節點之間，為了產生類似真實物理系統的平衡效果，使所有節點間的距離保持在最佳位置，模型中定義的引力隨著節點距離的增大而增大，定義的斥力則隨著節點距離的減小而增大，這樣既可以保證任意兩個節點在相距較近時能夠彼此反向移動，也能保證具有邊相連的節點不會被排斥過遠，最終在受力平衡時，布局達到最優效果。

f_a(d)＝d²/k (1-3)

f_r(d)＝-k²/d (1-4)

基于FR模型的力導引算法具體步驟為：

1、在待布局區域內部隨機初始化各節點的位置；

2、對每個節點，根據公式(1-4)計算其他節點對該節點的斥力；

3、對具有拓撲關系的節點，根據公式(1-3)計算彼此節點間的引力；

4、對每個節點，通過2、3步計算出其合力，并沿合力方向移動自定義距離S；

5、重復執行2-4步，并逐步減小S的值，直到設定的迭代次數終止。

FR模型中，通過步驟2和3的作用后，理想情況下引力和斥力會在某個位置使節點受力均衡，但實際應用中，由于節點移動布局是一個動態過程，所以應當將其理解為動態平衡。模型中對真實物理系統的重要修改之一在于步驟4的合力對節點影響的是速度的方向，而不是真實物理系統中力產生加速度的原理，避免了由于實時性而造成的實現難度問題。