강제 방향 그래프 그리기

강제 지향 그래프 그리기^[1] 알고리즘을 사용한 소셜 네트워크 시각화

강제 지시 레이아웃을 사용하여 Wiki 페이지 간 링크 시각화

강제 지향 그래프 그리기 알고리즘은 미적으로 만족스러운 방법으로 그래프를 그리기 위한 알고리즘의 한 종류입니다.그 목적은 그래프의 노드를 2차원 또는 3차원 공간에 배치하여 모든 가장자리의 길이가 같거나 같으며 교차하는 가장자리가 최대한 적도록 하는 것이다. 상대적인 위치에 기초하여 가장자리 집합과 노드 집합 사이에 힘을 할당하고, 이러한 힘을 사용하여 시뮬레이션한다.e 가장자리 및 노드의 움직임 또는 에너지를 ^[2]최소화합니다.

그래프 드로잉은 어려운 문제가 될 수 있지만, 물리적인 시뮬레이션인 힘 지향 알고리즘은 보통 평면성과 같은 그래프 이론에 대한 특별한 지식이 필요하지 않습니다.

폭력

강제 지향 그래프 그리기 알고리즘은 그래프 도면의 에지 집합과 노드 집합 사이에 힘을 할당합니다.일반적으로 후크의 법칙에 기초한 스프링과 같은 흡인력은 그래프 가장자리의 끝점 쌍을 서로 끌어당기기 위해 사용되며, 쿨롱의 법칙에 기초한 전하를 띤 입자와 같은 반발력은 모든 노드 쌍을 분리하기 위해 사용된다.이 힘의 시스템의 평형 상태에서는 가장자리의 길이가 균일한 경향이 있으며(스프링 힘 때문에), 가장자리로 연결되지 않은 노드는(전기 반발 때문에) 더 멀리 끌어당기는 경향이 있다.가장자리 인력과 정점 반발력은 스프링과 입자의 물리적 거동에 기초하지 않는 함수를 사용하여 정의할 수 있다. 예를 들어, 일부 힘 지향 시스템은 끌어당기는 힘이 선형보다는 로그인 스프링을 사용한다.

대안 모델에서는 각 스프링의 이상적인 $\delta _{ij}$ θ i j \ $displaystyle \delta$ _ ${ij}$ 가 $(i,j)$ $\delta _{ij}$ 노드 i와 j 사이의 그래프 이론 거리에 비례하는 모든 $(i,j)$ 노드 쌍( $i$ $)$ 에 대해 스프링과 같은 힘을 고려한다(별도의 반발력을 사용하지 않음).유클리드 간 차이(일반적으로 제곱 차이)와 노드 간 이상적인 거리를 최소화하는 것은 메트릭 다차원 스케일링 문제와 동일합니다.

힘 지향 그래프는 기계적 스프링 및 전기적 반발 이외의 힘을 포함할 수 있다.중력과 유사한 힘은 그리기 공간의 고정점을 향해 정점을 당기기 위해 사용될 수 있다. 이것은 분리된 그래프의 서로 연결된 다른 구성 요소를 함께 당기기 위해 사용될 수 있다. 그렇지 않으면 반발력으로 인해 서로 떨어져 날아가는 경향이 있고 더 중심적인 위치를 가진 노드를 그리기 위해 사용될 수 있다.또한 ^[3]단일 구성요소 내의 정점 간격에도 영향을 줄 수 있습니다.자기장의 유추는 유도 그래프에 사용할 수 있다.반발력은 최종 도면에서 겹치거나 거의 겹치지 않도록 노드뿐만 아니라 가장자리에도 배치할 수 있다.원호 또는 스플라인 곡선 등의 곡선 모서리가 있는 도면에서는 예를 들어 각도 ^[4]분해능을 향상시키기 위해 이러한 곡선의 제어점에 힘을 배치할 수도 있습니다.

방법들

그래프의 노드와 모서리에 대한 힘이 정의되면 이러한 소스 아래에서 전체 그래프의 동작을 물리적 시스템처럼 시뮬레이션할 수 있습니다.이러한 시뮬레이션에서 힘은 노드에 작용하여 노드들을 더 가까이 당기거나 더 멀리 밀어냅니다.이것은 시스템이 기계적 평형 상태가 될 때까지 반복적으로 반복된다. 즉, 그들의 상대적 위치는 한 번의 반복에서 다음 반복으로 더 이상 변하지 않는다.이 평형에서 노드의 위치는 그래프의 도면을 생성하는 데 사용됩니다.

이상적인 길이가 그래프 이론적 거리에 비례하는 스프링에서 정의되는 힘의 경우 응력 대화는 이러한 차이를 최소화할 수 있는 매우 양호한 동작(즉, 단조롭게 수렴됨)^[5]과 수학적으로 우아한 방법을 제공하므로 그래프에 대한 좋은 레이아웃을 찾을 수 있다.

물리적 시뮬레이션 대신 또는 물리적 시뮬레이션과 연계하여 에너지 최소값을 더 직접적으로 검색하는 메커니즘을 사용할 수도 있다.이러한 메커니즘은 일반적인 글로벌 최적화 방법의 예로서 시뮬레이션 어닐링과 유전자 알고리즘을 포함한다.

이점

다음은 힘 지향 알고리즘의 가장 중요한 장점 중 하나입니다.

좋은 결과: 적어도 중간 크기의 그래프(최대 50~500개의 정점)의 경우, 얻은 결과는 대개 균일한 가장자리 길이, 균일한 정점 분포 및 대칭성을 나타내는 기준에 따라 매우 좋은 결과를 얻었다.이 마지막 기준은 가장 중요한 기준 중 하나이며 다른 유형의 알고리즘으로는 달성하기 어렵습니다.
유연성: 힘 지향 알고리즘은 추가 미적 기준을 충족하도록 쉽게 적응하고 확장할 수 있다.따라서 그래프 그리기 알고리즘의 가장 다용도 클래스가 됩니다.기존 확장의 예로는 방향 그래프, 3D 그래프 그리기,^[6] 클러스터 그래프 그리기, 제약된 그래프 그리기, 동적 그래프 그리기 등이 있습니다.
직감적: 이러한 알고리즘은 스프링과 같은 일반적인 물체의 물리적 유추에 기초하기 때문에 알고리즘의 동작을 예측하고 이해하기 쉽습니다.이것은 다른 유형의 그래프 그리기 알고리즘에서는 해당되지 않습니다.
심플함: 일반적인 힘 지향 알고리즘은 단순하며 몇 줄의 코드로 구현할 수 있습니다.직교 레이아웃과 같은 그래프 그리기 알고리즘의 다른 클래스는 일반적으로 훨씬 더 많이 관여합니다.
인터랙티브: 이 알고리즘 클래스의 또 다른 장점은 대화형 측면입니다.그래프의 중간 단계를 그리면, 사용자는 그래프가 뒤엉킨 뒤죽박죽에서 아름다운 구성으로 전개되는 과정을 따라갈 수 있다.일부 인터랙티브 그래프 그리기 도구에서는 사용자가 평형 상태에서 하나 이상의 노드를 꺼내 다시 제자리로 이동하는 것을 볼 수 있습니다.따라서 동적 및 온라인 그래프 그리기 시스템에서 선호되는 선택지가 됩니다.
강력한 이론적 기반: 단순한 임시 힘 지향 알고리즘이 문헌과 실제로 자주 나타나지만(상대적으로 이해하기 쉽기 때문에), 보다 합리적인 접근법이 설득력을 얻기 시작하고 있다.통계학자들은 1930년대부터 다차원 스케일링(MDS)에서 유사한 문제를 해결하고 있으며, 물리학자들도 관련 n-body 문제를 오랫동안 연구해 왔기 때문에 매우 성숙한 접근방식이 존재한다.예를 들어, 위에서 설명한 그래프 그리기에는 메트릭 MDS에 대한 응력 큰화 접근법을 적용할 수 있다.이것은 단조롭게 ^[5]수렴한다는 것이 증명되었다.각 반복에서 알고리즘이 레이아웃의 스트레스 또는 비용을 감소시키는 속성인 모노톤 수렴은 레이아웃이 최종적으로 로컬 최소값에 도달하여 정지하는 것을 보증하기 때문에 중요합니다.댐핑 스케줄에 의해 알고리즘이 정지되지만 진정한 로컬 최소값에 도달하는 것은 보증할 수 없습니다.

단점들

force-directed 알고리즘의 주요 단점은 다음과 같습니다.

높은 실행 시간: 일반적인 힘 지향 알고리즘은 일반적으로 입방 시간( $O(n^{3})$ $O(n^{3})$ 3) $O(n^{3})$ { $displaystyle$ O $(n^{3})})$ 에 실행되는 것으로 간주됩니다. $n$ 서 n ${displaystyle$ n $}$ 은 $n$ 입력 그래프의 노드 수입니다.이는 반복 횟수가 선형( $O(n)$ ( $O(n)$ ) \ $displaystyle$ O ( $n$ ) $O(n)$ ), ), this ), this this this this this this this this this this this this this this this this this this this this this this this this this this this this this this this this this this this this이것은 물리학의 N-body 문제와 관련이 있다.그러나 반발력은 본질적으로 국소적이기 때문에 그래프는 인접한 정점만 고려되도록 분할할 수 있다.큰 그래프의 레이아웃을 결정하기 위해 알고리즘에 의해 사용되는 일반적인 기술은 고차원 매립,^[7] 다층 도면 및 N체 시뮬레이션과 관련된 다른 방법을 포함한다.예를 들어, 반즈 가족...Hut 시뮬레이션 기반의 메서드^[8] FADE를 사용하면 실행 시간을 선형적으로 $n\log(n)$ 하거나 반복마다 $n\log(n)$ 의 로그 $n\log(n)$ µ ( $n\log(n)$ ) \ $display style$ n \ $log$ ( $n$ )로 $n\log(n)$ 개선할 수 있습니다.대략적인 가이드로 몇 초 안에 반복 $n^{2}$ $n^{2}$ n2 $({$ $displaystyle$ n $^{$ $2})$ 를 $n^{2}$ 사용하여 최대 1,000개의 노드를 그릴 수 있으며 반복 ^[8]기술당 n $n\log(n)$ µ( $n)$ 를 $n\log(n)$ $n\log(n)$ 하여 100,000개의 노드를 그릴 수 있습니다.강제 지향^{[clarification needed]} 알고리즘은 다단계 접근법과 결합하면 수백만 ^[9]개의 노드를 그래프로 그릴 수 있다.

열악한 로컬 최소값: 힘 지향 알고리즘이 최소 에너지, 특히 총 에너지가 국소 최소에 불과한 그래프를 생성하는 것을 쉽게 볼 수 있다.발견된 로컬 최소값은 대부분의 경우 글로벌 최소값보다 상당히 나빠질 수 있으며, 이는 저품질 도면으로 변환됩니다.많은 알고리즘, 특히 정점의 하향 이동만 허용하는 알고리즘의 경우, 최종 결과는 대부분의 경우 랜덤으로 생성되는 초기 레이아웃에 의해 강하게 영향을 받을 수 있습니다.그래프의 꼭지점 수가 증가할수록 낮은 국소 최소값의 문제가 더욱 중요해집니다.이 ^[10]문제를 해결하려면 서로 다른 알고리즘을 조합하여 적용하면 도움이 됩니다.예를 들어 Kamada-Kawai 알고리즘을^[11] 사용하여 적절한 초기 레이아웃을 신속하게 생성하고 다음으로 Fruchterman-Reingold 알고리즘을^[12] 사용하여 인접 노드의 배치를 개선합니다.글로벌 최소값을 달성하기 위한 또 다른 기술은 다단계 ^[13]접근법을 사용하는 것입니다.

역사

그래프 그리기에서의 힘 방향 방법은 투테(1963)의 작업으로 거슬러 올라간다. 투테는 그래프의 평면 매립의 외부 면의 정점을 볼록한 위치에 고정하고, 스프링과 같은 유인력을 각 모서리에 배치하고, 시스템이 볼록한 평면에 정착하도록 함으로써 다면체 그래프를 그릴 수 있음을 보여주었다.평형^[14]이 경우 힘이 단순하기 때문에 시스템은 로컬 최소값에 머무르지 않고 고유한 글로벌 최적 구성으로 수렴됩니다.이 작업 때문에 볼록면이 있는 평면 그래프의 임베딩을 Tutte 임베딩이라고 부르기도 한다.

인접한 정점에 대한 흡인력과 모든 정점에 대한 반발력의 조합은 Eades(1984)[15]에 의해 처음 사용되었으며, 이러한 유형의 힘 지향 배치에 대한 추가 선구적 연구는 Fruchterman & Reingold(1991)[12]에 의해 수행되었다.이상적인 스프링 길이가 정점의 그래프 이론적 거리와 동일한 모든 정점 쌍 사이에 스프링 힘만을 사용한다는 아이디어는 카마다 & 카와이(1989)[11]에서 나왔다.

「」를 참조해 주세요.

생체 네트워크를 시각화하는 소프트웨어인 Cytoscape.기본 패키지에는 기본 제공 방법 중 하나로 강제 지시 레이아웃이 포함되어 있습니다.
Gephi는 모든 종류의 네트워크와 복잡한 시스템, 동적 및 계층형 그래프에 대한 대화형 시각화 및 탐색 플랫폼입니다.
Graphviz는 매우 큰 그래프를 처리할 수 있는 다단계 힘 지향 레이아웃 알고리즘을 구현하는 소프트웨어입니다.
Tulip, 대부분의 강제 방향 레이아웃 알고리즘(GEM, LGL, GRIP, FM)을 구현하는 소프트웨어입니다.
프리퓨즈

레퍼런스

^ Grandjean, Martin (2015), "Introduction à la visualisation de données, l'analyse de réseau en histoire", Geschichte und Informatik 18/19 (PDF), pp. 109–128
^ 를 클릭합니다Kobourov, Stephen G. (2012), Spring Embedders and Force-Directed Graph Drawing Algorithms, arXiv:1201.3011, Bibcode:2012arXiv1201.3011K.
^ 를 클릭합니다Bannister, M. J.; Eppstein, D.; Goodrich, M. T.; Trott, L. (2012), "Force-directed graph drawing using social gravity and scaling", Proc. 20th Int. Symp. Graph Drawing, arXiv:1209.0748, Bibcode:2012arXiv1209.0748B.
^ 를 클릭합니다Chernobelskiy, R.; Cunningham, K.; Goodrich, M. T.; Kobourov, S. G.; Trott, L. (2011), "Force-directed Lombardi-style graph drawing", Proc. 19th Symposium on Graph Drawing (PDF), pp. 78–90.
^ ^a ^b 를 클릭합니다de Leeuw, Jan (1988), "Convergence of the majorization method for multidimensional scaling", Journal of Classification, Springer, 5 (2): 163–180, doi:10.1007/BF01897162, S2CID 122413124.
^ Vose, Aaron. "3D Phylogenetic Tree Viewer". Retrieved 3 June 2012.
^ Harel, David; Koren, Yehuda (2002), "Graph drawing by high-dimensional embedding", Proceedings of the 9th International Symposium on Graph Drawing, pp. 207–219, CiteSeerX 10.1.1.20.5390, ISBN 3-540-00158-1
^ ^a ^b 를 클릭합니다Quigley, Aaron; Eades, Peter (2001), "FADE: Graph Drawing, Clustering, and Visual Abstraction", Proceedings of the 8th International Symposium on Graph Drawing (PDF), pp. 197–210, ISBN 3-540-41554-8.
^ "A Gallery of Large Graphs". Retrieved 22 Oct 2017.
^ Collberg, Christian; Kobourov, Stephen; Nagra, Jasvir; Pitts, Jacob; Wampler, Kevin (2003), "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, pp. 77–86, figures on p. 212, doi:10.1145/774833.774844, ISBN 1-58113-642-0, S2CID 824991, 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.
^ ^a ^b 를 클릭합니다Kamada, Tomihisa; Kawai, Satoru (1989), "An algorithm for drawing general undirected graphs", Information Processing Letters, Elsevier, 31 (1): 7–15, doi:10.1016/0020-0190(89)90102-6.
^ ^a ^b 를 클릭합니다Fruchterman, Thomas M. J.; Reingold, Edward M. (1991), "Graph Drawing by Force-Directed Placement", Software: Practice and Experience, Wiley, 21 (11): 1129–1164, doi:10.1002/spe.4380211102, S2CID 31468174.
^ http://jgaa.info/accepted/2003/Walshaw2003.7.3.pdf Force-Directed Graph-Drawing을 위한 멀티레벨 알고리즘
^ 를 클릭합니다Tutte, W. T. (1963), "How to draw a graph", Proceedings of the London Mathematical Society, 13 (52): 743–768, doi:10.1112/plms/s3-13.1.743.
^ 를 클릭합니다Eades, Peter (1984), "A Heuristic for Graph Drawing", Congressus Numerantium, 42 (11): 149–160.

추가 정보

di Battista, Giuseppe; Peter Eades; Roberto Tamassia; Ioannis G. Tollis (1999), Graph Drawing: Algorithms for the Visualization of Graphs, Prentice Hall, ISBN 978-0-13-301615-4
Kaufmann, Michael; Wagner, Dorothea, eds. (2001), Drawing graphs: methods and models, Lecture Notes in Computer Science 2025, vol. 2025, Springer, doi:10.1007/3-540-44969-8, ISBN 978-3-540-42062-0, S2CID 1808286

외부 링크

Stephen G. Kobourov의 힘 지향 드로잉 알고리즘에 대한 책
Daniel Tunkelang의 힘 지향 그래프 레이아웃에 관한 논문

[1] Grandjean, Martin (2015), "Introduction à la visualisation de données, l'analyse de réseau en histoire", Geschichte und Informatik 18/19 (PDF), pp. 109–128

[2] 를 클릭합니다Kobourov, Stephen G. (2012), Spring Embedders and Force-Directed Graph Drawing Algorithms, arXiv:1201.3011, Bibcode:2012arXiv1201.3011K.

[3] 를 클릭합니다Bannister, M. J.; Eppstein, D.; Goodrich, M. T.; Trott, L. (2012), "Force-directed graph drawing using social gravity and scaling", Proc. 20th Int. Symp. Graph Drawing, arXiv:1209.0748, Bibcode:2012arXiv1209.0748B.

[4] 를 클릭합니다Chernobelskiy, R.; Cunningham, K.; Goodrich, M. T.; Kobourov, S. G.; Trott, L. (2011), "Force-directed Lombardi-style graph drawing", Proc. 19th Symposium on Graph Drawing (PDF), pp. 78–90.

[dl88-5] 를 클릭합니다de Leeuw, Jan (1988), "Convergence of the majorization method for multidimensional scaling", Journal of Classification, Springer, 5 (2): 163–180, doi:10.1007/BF01897162, S2CID 122413124.

[6] Vose, Aaron. "3D Phylogenetic Tree Viewer". Retrieved 3 June 2012.

[7] Harel, David; Koren, Yehuda (2002), "Graph drawing by high-dimensional embedding", Proceedings of the 9th International Symposium on Graph Drawing, pp. 207–219, CiteSeerX 10.1.1.20.5390, ISBN 3-540-00158-1

[quigley+eades-8] 를 클릭합니다Quigley, Aaron; Eades, Peter (2001), "FADE: Graph Drawing, Clustering, and Visual Abstraction", Proceedings of the 8th International Symposium on Graph Drawing (PDF), pp. 197–210, ISBN 3-540-41554-8.

[9] "A Gallery of Large Graphs". Retrieved 22 Oct 2017.

[10] Collberg, Christian; Kobourov, Stephen; Nagra, Jasvir; Pitts, Jacob; Wampler, Kevin (2003), "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, pp. 77–86, figures on p. 212, doi:10.1145/774833.774844, ISBN 1-58113-642-0, S2CID 824991, 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.

[kk89-11] 를 클릭합니다Kamada, Tomihisa; Kawai, Satoru (1989), "An algorithm for drawing general undirected graphs", Information Processing Letters, Elsevier, 31 (1): 7–15, doi:10.1016/0020-0190(89)90102-6.

[fr91-12] 를 클릭합니다Fruchterman, Thomas M. J.; Reingold, Edward M. (1991), "Graph Drawing by Force-Directed Placement", Software: Practice and Experience, Wiley, 21 (11): 1129–1164, doi:10.1002/spe.4380211102, S2CID 31468174.

[13] ttp://jgaa.info/accepted/2003/Walshaw2003.7.3.pdf Force-Directed Graph-Drawing을 위한 멀티레벨 알고리즘

[14] 를 클릭합니다Tutte, W. T. (1963), "How to draw a graph", Proceedings of the London Mathematical Society, 13 (52): 743–768, doi:10.1112/plms/s3-13.1.743.

[15] 를 클릭합니다Eades, Peter (1984), "A Heuristic for Graph Drawing", Congressus Numerantium, 42 (11): 149–160.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

Search

강제 방향 그래프 그리기

네임스페이스

더

목차

폭력

방법들

이점

단점들

역사

「」를 참조해 주세요.

레퍼런스

추가 정보

외부 링크

Search

강제 방향 그래프 그리기

폭력

방법들

이점

단점들

역사

「 」를 참조해 주세요.

레퍼런스

추가 정보

외부 링크

「」를 참조해 주세요.