維基百科

力導向圖

力導向圖形繪製算法是以美觀的方式繪製圖形的一類算法。它們的目的是將一個圖的節點定位在二維或二維三維空間中，這樣所有的邊或多或少都是等長的，交叉的邊越少越好。方法是根據邊和節點的相對位置在邊和節點的集合中分配力，然後利用這些力模擬邊和節點的運動[2]。

使用力導向圖算法的社交網絡可視化[1]
使用力導向圖算法的維基網頁間連結的可視化

雖然圖形繪製可能是一個難題，但作為物理模擬的力導向算法通常不需要關於平面性等圖論的特殊知識。

力

力導向圖繪製算法把把力賦給圖形繪製的節點集合與邊的集合。通常，基於胡克定律的類似彈簧的吸引力用於相互吸引的圖形中邊的端點，同時使用基於庫侖定律的帶電粒子的排斥力來分隔所有節點對。在該力系統的平衡狀態下，邊的長度往往是一致的（因為彈簧引力），而沒有通過邊連接的節點往往會被拉開得更遠（因為電荷斥力）。可以使用不基於彈簧和粒子的物理行為的函數來定義邊引力和頂點斥力；例如，一些力導向系統使用吸引力是對數而不是線性的彈簧。

一個替代模型為每對節點考慮一個類似彈簧的力 ，其中每個彈簧的理想長度 與節點i和j之間的圖論距離成正比，無需使用單獨的排斥力。極小化節點之間的歐幾里德距離和理想距離之間的差異（通常是平方差）相當於一個度量多維標度問題。

力導向圖可以涉及機械彈簧和電荷斥力以外的力。可以使用類似於重力的力將頂點拉向繪圖空間的固定點；這可用於將斷開連接的圖的不同連通分量拉到一起，否則這些圖會由於斥力而彼此分開，並把具有更大連通分量的節點繪製到圖中更中心的位置[3]。它還可能影響單個組件內的頂點間距。類似的，磁場也可用於有向圖。排斥力可以放在邊緣和節點上，以避免在最終繪圖中重疊或近似於重疊。在諸如圓弧或樣條曲線之類的邊為曲線的圖形中，也可以在這些曲線的控制點上施加力，例如提高它們的角解像度。[4]

方法

一旦定義了圖的節點和邊上的力，就可以模擬在這些源下整個圖的行為，就好像它是一個物理系統一樣。在這樣的模擬中，力被施加到節點上，將它們拉得更近或推得更遠。如此反覆迭代，直到系統達到機械平衡狀態；即，從當前迭代到下一次迭代，它們的相對位置不再改變。該平衡中節點的位置用於生成圖形的繪製。

對於由理想長度與圖論距離成正比的彈簧定義的力，應力優化（英語：Stress majorization）提供了一種表現非常好的（即單調收斂）[5]和數學上優雅的方法來極小化這些差異，從而找到對於圖形來說一個好的佈局。

也可以採用更直接地搜索能量極小值的機制，而不是物理模擬或與物理模擬結合使用。這種機制是一般全局優化（英語：Global optimization）方法的例子，包括模擬退火和遺傳算法。

優點

以下是力導向算法最重要的優點：

高質量的結果
至少對於中等大小（最多 50-500 個頂點）的圖形，基於以下標準，獲得的結果通常具有非常好的結果：均勻的邊長、均勻的頂點分佈和顯示對稱性。最後一個標準是最重要的標準之一，任何其他類型的算法都很難實現。
靈活性
力導向算法可以很容易地進行調整和擴展，以滿足額外的審美標準。這使它們成為最通用的圖形繪製算法類。現有擴展的示例包括有向圖、3D圖繪製[6]、 集群圖繪製、約束圖繪製和動態圖繪製。
直覺的
由於它們基於常見物體（如彈簧）的物理類比，因此算法的行為相對容易預測和理解。其他類型的圖形繪製算法並非如此。
簡單
典型的力導向算法很簡單，只需幾行代碼即可實現。其他類別的圖形繪製算法，例如用於正交佈局的算法，通常涉及更多。
互動性
此類算法的另一個優點是交互性。通過繪製圖形的中間階段，用戶可以跟蹤圖形如何演變，看到它從混亂的混亂狀態展開，變成漂亮的配置。在一些交互式圖形繪製工具中，用戶可以將一個或多個節點從其平衡狀態中拉出並觀察它們遷移回原位。這使它們成為動態和在線圖形繪製系統的首選。
紮實的理論基礎
雖然簡單的專門的力導向算法經常出現在文獻和實踐中（因為它們相對容易理解），但更合理的方法開始受到關注。自1930年代以來，統計學家一直在解決多維標度(MDS) 中的類似問題，物理學家在處理相關n體問題方面也有着悠久的歷史——因此存在極其成熟的方法。例如，度量 MDS的應力優化（英語：stress majorization）方法可以應用於上述圖形繪製。這已被證明是單調收斂的。單調收斂是算法在每次迭代時減少佈局的壓力或成本的特性，它很重要，因為它保證佈局最終會達到局部最小值並停止。阻尼調度會導致算法停止，但不能保證達到真正的局部最小值。

缺點

力導向算法的主要缺點包括：

高運行時間
典型的力導向算法通常被認為具有等效於O(n3)的運行時間，其中n是輸入圖的節點數。只是因為估計需要迭代O(n)，每次迭代需要計算每對節點間的斥力。這與物理學中的N體問題有關。然而，由於排斥力本質上是局部的，因此可以將圖劃分為僅考慮相鄰頂點。確定大圖佈局的常用技術包括高維嵌入算法、多層繪製和其他與N體模擬相關的方法。例如，基於Barnes–Hut模擬的FADE方法[7][8]可以將每次迭代的運行時間提高到n*log(n)。作為粗略的指導，使用標準的每次迭代n2技術在幾秒鐘內最多可以繪製1,000個節點，使用每次迭代n*log(n)技術在幾秒鐘內可繪製100,000個節點。力導向算法與多層次方法相結合時，可以繪製數百萬個節點的圖形。[8] Force-directed algorithms, when combined with a multilevel approach, can draw graphs of millions of nodes.[9]
局部極小值
很容易看出，力導向算法產生了一個能量極小的圖，特別是一個總能量僅為局部極小值的圖。在許多情況下，找到的局部極小值可能比全局最小值差很多，這會轉化為低質量的繪圖。對於許多算法，尤其是那些只允許頂點下坡移動的算法，最終結果會受到在大多數情況下是隨機生成的初始佈局的強烈影響。隨着圖的頂點數量的增加，局部最小值差的問題變得更加重要。不同算法的組合應用有助於解決這個問題。[10]例如，使用Kamada-Kawai算法[11]快速生成合理的初始佈局，然後使用 Fruchterman-Reingold算法[12]來改進相鄰節點的放置。另一種實現全局最小值的技術是使用多級方法。[13]

歷史

力導向方法繪製圖形可追溯到Tutte (1963)：多面體圖形可以在平面上繪製的所有面凸出通過固定的平面的外表面的嵌入圖表的入頂點凸位置，在每條邊上放置一個類似彈簧的吸引力，讓系統達到平衡。[14]由於在這種情況下力的簡單性質，系統不會陷入局部最小值，而是收斂到唯一的全局最優配置。由於這項工作，具有凸面的平面圖的嵌入有時稱為Tutte嵌入。

1984年Eades提出了邊表示引力，所有節點對之間為斥力的模型。[15]此外這方面的先鋒工作還有1991年Fruchterman Reingold。[12]

在頂點對之間只使用彈簧力，理想彈簧力等於頂點間的圖論距離的模型，是Kamada Kawai在1989年提出的。[11]

參見

  • Cytoscape（英語：Cytoscape），用於可視化生物網絡的軟件。 基礎包包括力導向佈局作為內置方法之一。
  • Gephi，一個針對各種網絡和複雜系統、動態和層次圖的交互式可視化和探索平台。
  • Graphviz，實現多級力導向佈局算法（以及許多其他算法）的軟件，能夠處理非常大的圖形。
  • Tulip（英語：Tulip (software)），實現大多數力導向佈局算法（GEM、LGL、GRIP、FM³）的軟件。
  • Prefuse（英語：Prefuse）

延伸閲讀

外部連結

參考文獻

  1. ^ Grandjean, Martin, Introduction à la visualisation de données, l'analyse de réseau en histoire, Geschichte und Informatik 18/19 (PDF): 109–128, 2015 [2021-08-12], （原始內容 (PDF)存檔於2021-05-06） 
  2. ^ Chernobelskiy, R.; Cunningham, K.; Goodrich, M. T.; Kobourov, S. G.; Trott, L., Force-directed Lombardi-style graph drawing, Proc. 19th Symposium on Graph Drawing (PDF): 78–90, 2011 [2021-08-12], （原始內容 (PDF)存檔於2021-08-12） .
  3. ^ Bannister, M. J.; Eppstein, D.; Goodrich, M. T.; Trott, L., Force-directed graph drawing using social gravity and scaling, Proc. 20th Int. Symp. Graph Drawing, 2012, Bibcode:2012arXiv1209.0748B, arXiv:1209.0748   .
  4. ^ Chernobelskiy, R.; Cunningham, K.; Goodrich, M. T.; Kobourov, S. G.; Trott, L., Force-directed Lombardi-style graph drawing, Proc. 19th Symposium on Graph Drawing (PDF): 78–90, 2011 [2021-08-12], （原始內容 (PDF)存檔於2021-08-12） .
  5. ^ de Leeuw, Jan, Convergence of the majorization method for multidimensional scaling, Journal of Classification (Springer), 1988, 5 (2): 163–180, doi:10.1007/BF01897162 .
  6. ^ Vose, Aaron. 3D Phylogenetic Tree Viewer. [3 June 2012]. [失效連結]
  7. ^ Harel, David; Koren, Yehuda, Graph drawing by high-dimensional embedding, Proceedings of the 9th International Symposium on Graph Drawing: 207–219, 2002, CiteSeerX 10.1.1.20.5390  , ISBN 3-540-00158-1 
  8. ^ 8.0 8.1 Quigley, Aaron; Eades, Peter, FADE: Graph Drawing, Clustering, and Visual Abstraction, Proceedings of the 8th International Symposium on Graph Drawing (PDF): 197–210, 2001 [2021-08-12], ISBN 3-540-41554-8, （原始內容存檔 (PDF)於2021-08-12） .
  9. ^ A Gallery of Large Graphs. [22 Oct 2017]. （原始內容存檔於2021-05-25）. 
  10. ^ Collberg, Christian; Kobourov, Stephen; Nagra, Jasvir; Pitts, Jacob; Wampler, Kevin, A System for Graph-based Visualization of the Evolution of Software, Proceedings of the 2003 ACM Symposium on Software Visualization (SoftVis '03), New York, NY, USA: ACM: 77–86; figures on p. 212, 2003, ISBN 1-58113-642-0, doi:10.1145/774833.774844, To achieve an aesthetically pleasing layout of the graph it is also necessary to employ modified Fruchterman–Reingold forces, as the Kamada–Kawai method does not achieve satisfactory methods by itself but rather creates a good approximate layout so that the Fruchterman-Reingold calculations can quickly "tidy up" the layout. 
  11. ^ 11.0 11.1 Kamada, Tomihisa; Kawai, Satoru, An algorithm for drawing general undirected graphs, Information Processing Letters (Elsevier), 1989, 31 (1): 7–15, doi:10.1016/0020-0190(89)90102-6 .
  12. ^ 12.0 12.1 Fruchterman, Thomas M. J.; Reingold, Edward M., Graph Drawing by Force-Directed Placement, Software – Practice & Experience (Wiley), 1991, 21 (11): 1129–1164, doi:10.1002/spe.4380211102 .
  13. ^ http://jgaa.info/accepted/2003/Walshaw2003.7.3.pdf （頁面存檔備份，存於互聯網檔案館） A Multilevel Algorithm for Force-Directed Graph-Drawing
  14. ^ Tutte, W. T., How to draw a graph, Proceedings of the London Mathematical Society, 1963, 13 (52): 743–768, doi:10.1112/plms/s3-13.1.743 .
  15. ^ Eades, Peter, A Heuristic for Graph Drawing, Congressus Numerantium, 1984, 42 (11): 149–160 .
取自 "https://zh.wikipedia.org/w/index.php?title=力导向图&oldid=76188552"