네트워크는 공학이나 자연과학은 물론이고 사회과학의 여러 분야를 연구하는데 중요하게 사용되는 모델이다. 이런 네트워크를 좀 더 쉽게 분석하기 위해서는 시각적으로 네트워크의 특징을 잘 나타내는 것이 필요하다. 이러한 그래프 레이아웃 연구는 컴퓨터 기술이 발달함에 따라 많이 연구되고 있다. 그 중에서 요즘 새롭게 부각되고 있는 척도 없는(Scale-free) 네트워크는 다양한 분야에서 복잡한 현상들을 분석하고 이해하는데 유용하게 쓰이고 있다. 이 네트워크의 특징은 링크의 수(Degree)가 멱함수(power law) 분포를 보이고, 다수의 링크를 가지는 허브가 존재함이 알려졌다. 따라서 척도 없는 네트워크에서는 허브를 시각적으로 잘 표현하는 것이 중요하지만 기존의 그래프 레이아웃 알고리즘은 클러스터를 잘 표현하는 정도이다. 그래서 본 논문에서는 척도 없는 네트워크를 잘 표현하는 그래프 레이아웃 알고리즘을 제안한다. 본 논문에서 제안한 알고리즘에서 허브들 간에 작용하는 허브성 척력이 거리에 반비례하고, 허브들의 degree가 a배 증가하면, 허브사이에 작용하는 척력의 크기는 ${\alpha}^{\gamma}({\gamma}$는 연결선 지수)배가 된다. 또한, 전체 노드수와 전체 링크수에 따라 적용되는 힘의 크기를 조정하는 계수를 두어서 네트워크의 규모에 관계없이 허브성 척력이 적용되는 특성이 있다. 제안한 알고리즘이 허브를 잘 표현하는 그래프 레이아웃 알고리즘인지를 기존의 방식과 실험을 통해서 비교하였다. 실험의 절차는 먼저 네트워크에 허브가 존재하는지를 식별한다. 허브의 존재를 식별하기 위한 방법은 연결선 지수를 확인하고, 연결선 지수의 값이 2와 3사이에 있으면 허브가 존재하는 척도 없는 네트워크로 판단한다. 다음은 이 네트워크의 레이아웃 작성에 제안한 알고리즘을 사용한다. 그 결과, 제안한 그래프 레이아웃 알고리즘이 기존의 Noack등의 클러스터중심의 알고리즘에 비해서 척도 없는 네트워크의 허브를 확실히 잘 보여주고 있음을 확인할 수 있었다.
네트워크는 공학이나 자연과학은 물론이고 사회과학의 여러 분야를 연구하는데 중요하게 사용되는 모델이다. 이런 네트워크를 좀 더 쉽게 분석하기 위해서는 시각적으로 네트워크의 특징을 잘 나타내는 것이 필요하다. 이러한 그래프 레이아웃 연구는 컴퓨터 기술이 발달함에 따라 많이 연구되고 있다. 그 중에서 요즘 새롭게 부각되고 있는 척도 없는(Scale-free) 네트워크는 다양한 분야에서 복잡한 현상들을 분석하고 이해하는데 유용하게 쓰이고 있다. 이 네트워크의 특징은 링크의 수(Degree)가 멱함수(power law) 분포를 보이고, 다수의 링크를 가지는 허브가 존재함이 알려졌다. 따라서 척도 없는 네트워크에서는 허브를 시각적으로 잘 표현하는 것이 중요하지만 기존의 그래프 레이아웃 알고리즘은 클러스터를 잘 표현하는 정도이다. 그래서 본 논문에서는 척도 없는 네트워크를 잘 표현하는 그래프 레이아웃 알고리즘을 제안한다. 본 논문에서 제안한 알고리즘에서 허브들 간에 작용하는 허브성 척력이 거리에 반비례하고, 허브들의 degree가 a배 증가하면, 허브사이에 작용하는 척력의 크기는 ${\alpha}^{\gamma}({\gamma}$는 연결선 지수)배가 된다. 또한, 전체 노드수와 전체 링크수에 따라 적용되는 힘의 크기를 조정하는 계수를 두어서 네트워크의 규모에 관계없이 허브성 척력이 적용되는 특성이 있다. 제안한 알고리즘이 허브를 잘 표현하는 그래프 레이아웃 알고리즘인지를 기존의 방식과 실험을 통해서 비교하였다. 실험의 절차는 먼저 네트워크에 허브가 존재하는지를 식별한다. 허브의 존재를 식별하기 위한 방법은 연결선 지수를 확인하고, 연결선 지수의 값이 2와 3사이에 있으면 허브가 존재하는 척도 없는 네트워크로 판단한다. 다음은 이 네트워크의 레이아웃 작성에 제안한 알고리즘을 사용한다. 그 결과, 제안한 그래프 레이아웃 알고리즘이 기존의 Noack등의 클러스터중심의 알고리즘에 비해서 척도 없는 네트워크의 허브를 확실히 잘 보여주고 있음을 확인할 수 있었다.
A network is an important model widely used in natural and social science as well as engineering. To analyze these networks easily it is necessary that we should layout the features of networks visually. These Graph-Layout researches have been performed recently according to the development of the c...
A network is an important model widely used in natural and social science as well as engineering. To analyze these networks easily it is necessary that we should layout the features of networks visually. These Graph-Layout researches have been performed recently according to the development of the computer technology. Among them, the Scale-free Network that stands out in these days is widely used in analyzing and understanding the complicated situations in various fields. The Scale-free Network is featured in two points. The first, the number of link(Degree) shows the Power-function distribution. The second, the network has the hub that has multiple links. Consequently, it is important for us to represent the hub visually in Scale-free Network but the existing Graph-layout algorithms only represent clusters for the present. Therefor in this thesis we suggest Graph-layout algorithm that effectively presents the Scale-free network. The Hubity(hub+ity) repulsive force between hubs in suggested algorithm in this thesis is in inverse proportion to the distance, and if the degree of hubs increases in a times the Hubity repulsive force between hubs is ${\alpha}^{\gamma}$ times (${\gamma}$??is a connection line index). Also, if the algorithm has the counter that controls the force in proportion to the total node number and the total link number, The Hubity repulsive force is independent of the scale of a network. The proposed algorithm is compared with Graph-layout algorithm through an experiment. The experimental process is as follows: First of all, make out the hub that exists in the network or not. Check out the connection line index to recognize the existence of hub, and then if the value of connection line index is between 2 and 3, then conclude the Scale-free network that has a hub. And then use the suggested algorithm. In result, We validated that the proposed Graph-layout algorithm showed the Scale-free network more effectively than the existing cluster-centered algorithms[Noack, etc.].
A network is an important model widely used in natural and social science as well as engineering. To analyze these networks easily it is necessary that we should layout the features of networks visually. These Graph-Layout researches have been performed recently according to the development of the computer technology. Among them, the Scale-free Network that stands out in these days is widely used in analyzing and understanding the complicated situations in various fields. The Scale-free Network is featured in two points. The first, the number of link(Degree) shows the Power-function distribution. The second, the network has the hub that has multiple links. Consequently, it is important for us to represent the hub visually in Scale-free Network but the existing Graph-layout algorithms only represent clusters for the present. Therefor in this thesis we suggest Graph-layout algorithm that effectively presents the Scale-free network. The Hubity(hub+ity) repulsive force between hubs in suggested algorithm in this thesis is in inverse proportion to the distance, and if the degree of hubs increases in a times the Hubity repulsive force between hubs is ${\alpha}^{\gamma}$ times (${\gamma}$??is a connection line index). Also, if the algorithm has the counter that controls the force in proportion to the total node number and the total link number, The Hubity repulsive force is independent of the scale of a network. The proposed algorithm is compared with Graph-layout algorithm through an experiment. The experimental process is as follows: First of all, make out the hub that exists in the network or not. Check out the connection line index to recognize the existence of hub, and then if the value of connection line index is between 2 and 3, then conclude the Scale-free network that has a hub. And then use the suggested algorithm. In result, We validated that the proposed Graph-layout algorithm showed the Scale-free network more effectively than the existing cluster-centered algorithms[Noack, etc.].
* AI 자동 식별 결과로 적합하지 않은 문장이 있을 수 있으니, 이용에 유의하시기 바랍니다.
문제 정의
따라서 결집계수(Clustering coefficient)[3]가 높은 좁은 세상 네트워크와 허브가 존재하는 척도 없는 네트워크에 대해서 각 네트워크의 특징들을 살펴보고, 네트워크를 시각화 하는 기존의 그래프 레이아웃 알고리즘들에 대해서도 알아본다.
일반적으로 연결선 지수 了의 값이 2~3사이의 값을 가지는 네트워크를 척도 없는 네트워크라 한다[28丄 앞에서 말했듯이 이런 네트워크를 분석하기위해서 레이아웃 알고리즘을 적용해서 시각적으로 나타내는데, 시각적으로 나타낼 때 척도 없는 네트워크에서 가장 중요한 구성요소인 허브를 잘 표현할 필요가 있다. 따라서 본 논문에서는 다음에 설명하는 기존의 여러 레이아웃과 다르게 허브를 잘 표현하는 그래프 레이아웃을 제안한다.
Noack의 에너지 모델(Z添-log) 은 클러스터를 잘 표현하기는 하지만, 모든 네트워크의 특성을 잘 나타내는 것은 아니다 특히 척도 없는 네트워크의 허브를 표현하는 데는 적합하지 않다. 따라서 본 논문에서는 척도 없는 네트워크를 위한 그래프 레이아웃 알고리즘을 제안한다.
왜냐하면 척도 없는 네트워크에는 클러스터가 중요한 구성요소가 아니라 허브가 중요한 구성요소이기 때문이다. 따라서 본 논문에서는 일반적인 에너지모델에서 척력을 나타내는 수식부분을 허브의 특성을 반영하도록 고치는 것이다. 표 2에서는 제안한 그래프 레이아웃의 전체 프로그램 수행 순서의 의사코드를 나타낸다.
그런데 자연에는 척도 없는 네트워크가 아주 많다[26L 이런 척도 없는 네트워크에는 허브가 존재하는데 기존의 알고리즘은 클러스터를 잘 표현하는 정도이지 허브의 표현은 매우 어렵다. 그래서 본 논문에서는 척도 없는 네트워크를 잘 표현하는 그래프 레이아웃 알고리즘을 제안했다. 본 논문에서 제안한 알고리즘에서 허브들 간에 작용하는 허브성 척력이 거리에 반비례하고, 허브들의 degree가 a 배 증가하면, 허브사이에 작용하는 척력의 크기는 a7(7 는 연결선 지수)배가 된다.
가설 설정
각각에 대해서 알아보면, 우선 Spring embedded방법은 노드와 노드 사이에 링크가 있으면, 이것을 스프링으로 가정한다. 스프링은 노드들이 서로 너무 멀리 떨어지거나 너무 가까이 접근하지 않도록 적당한 길이와 강도를 갖도록 설정한다[7L 에너지 기반의 방법들은 일반적으로 두 부분으로 나뉜다.
제안 방법
기존의 레이아웃 방법들이 좁은 세상 네트워크의 중요한 특징인 클러스터를 잘 표현하는 알고리즘 중심으로 연구[21, 22]되었다면, 본 논문에서는 척도 없는 네트워크에서 중요한 구성요소로 다루는 허브를 잘 표현하는 그래프 레이아웃 알고리즘에 대한 연구를 하였다. 본 논문에서 제안한 알고리즘의 특성은허브성 척력이 거리에 반비례하고, 각 노드의 degree가 각각 a배 중가하면 허브사이에 작용하는 척력의 크기는 "(7는 연결선 지수)배가 된다. 또한, 전체 노드 수와 전체 링크 수에 따라 적용되는 힘의 크기를 조정하는 계수를 두어서 네트워크의 규모에 관계없이 적용되는 특성이 있다.
이 논문에서는 좁은 세상 네트워크와 척도 없는 네트워크의 시각화를 네트워크의 구성요소, 즉 허브의 존재유무에 따라 다른 그래프 레이아웃 알고리즘을 적용한다. 따라서 결집계수(Clustering coefficient)[3]가 높은 좁은 세상 네트워크와 허브가 존재하는 척도 없는 네트워크에 대해서 각 네트워크의 특징들을 살펴보고, 네트워크를 시각화 하는 기존의 그래프 레이아웃 알고리즘들에 대해서도 알아본다.
Eades이후 1991년 Fruchterman 과 Reingold 는 레이아웃의 계산에 있어서, 여러 면에서 속도향상을 보이도록 Spring embedded 방법을 개선했다. 우선 힘 (force)을 좀 더 빠르게 평가하도록 하고, 척력은 모든 노드들의 쌍(pair) 사이에 적용시키고, 스프링 대신 인력(引力)을 추가하였다. 인력은 인접한 노드들 사이에 적용되며 인접한 노드에서는 인력과 척력의 조합이 스프링과 같은 힘으로 산출된다.
따라서 허브가 이 클러스터 안쪽에 뭉쳐지기 때문에 허브들을 잘 구별하기가 어렵다. 제안한 Hub_Layoute 일반적인 에너지모델에서 척력을 나타내는 수식부분을 허브의 특성을 반영하도록 고치는 것이다. 다음은 제안하는 에너지 모델의 수식이다.
앞의 수식에서 와。노드 사이에는 적용되는 두 가지 힘, 즉 인력과 척력(허브성 척력)이 존재하는데, 허브들끼리는 서로 밀치고 그러지 않은(degree가 낮은) 노드들은 가깝게 그려지도록 4四항을 도입해서 허브를 잘 표현하는 알고리즘으로 수정하였다. 아래 그림 3에서처럼 거리가 다른 두 노드이지만, 각각의 de음ree는 같다.
본 논문에서 제안한 알고리즘은 네트워크의 규모에 관계없이 허브성 척력이 적용되도록 네트워크의 규모(전체 노드수와 링크수에 따른 이상적인 거리를 계산한다. 이에 관한 내용은 논문[31]을 참조하여 구현하였다.
이와 같이 노드가 degree와 rank 두 경우 모두에서 멱함수 법칙을 따르는 척도 없는 네트워크 특성을 보였다. 하지만 본 연구에서 제안한 알고리즘에서는 링크 수(Degree)를 주로 사용한다.
또한, 전체 노드수와 전체 링크 수에 따라 적용되는 힘의 크기를 조정하는 계수를 두어서 네트워크의 규모에 관계없이 허브성 척력이 적용되는 특성이 있다. 제안한 알고리즘은 먼저 허브의 존재를 식별한 후 그 정보를 토대로 허브끼리 밀도록 하는 것을 원리로 한다. 허브의 존재는 네트워크가 척도 없는 네트워크인지를 구분하는 것과 같다.
여기서 k는 노드의 링크 수이고, 1은 연결선 지수이다. 제안한 알고리즘이 기존의 클러스터링 중심의 레이아웃 알고리즘(Noack의 Z沅-Zog)에 비해서 허브를 잘 표현하는지에 대한 실험을 해보았다. 실험에 사용한 네트워크가 연결선 지수 7= 2.
대상 데이터
작성되었다. 본 논문의 실험에서 사용한 네트워크는 Barabash 모델을 이용해서 만든 가상의 네트워크이다.
이론/모형
멱함수의 계산 결과 연결선 지수의 값이 2미만이면, Cluster. Layout을 수행하는데, Cluster_Layouter Noack의 식에서 차수 (r) 의 값을 1 로 하는 Lin — Log (Clustering Energy Model)알고리즘을 그대로 이용해서 그래프 레이아웃을 그린다. 다음은 Log알고리즘 식이다.
실험에 사용된 네트워크는 척도 없는 네트워크로서 Barabasi의 모델을 이용해서 만들어 졌다. Random Network는 실험에 사용된 네트워크와 같은 수의 노드와 링크를 갖는 완전한 무작위 네트워크이다.
성능/효과
부분이다. 다음은 제안한 식이 노드들 간의 거리에 반비례해서 척력이 적용되며, 거리가 일정 비율로 증가할 때 척력의 크기도 일정한 비율로 감소함을 증명하고, 네트워크의 규모에 관계없이 허브성에 비례해서 노드들간에 척력이 작용함을 증명한다.
이에 관한 내용은 논문[31]을 참조하여 구현하였다. 이상과 같이 정리 1, 2에 의하여 제안한 알고리즘은 허브성 척력이 거리에 반비례하고, 각각의 degree가 증가함에 따라서 일정한 크기로 증가하며, 네트워크의 규모에 관계없이 적용되는 것이 특징이다.
이레이아웃에서 허브들이 외곽으로 적절히 분산되어 그려지고 있다. 따라서 허브들의 정보를 파악하는데 제안한 알고리즘이 매우 유용하다. 만약 이 그래프의 레이아웃을 그리는데, 기존의 클러스터 중심으로 표현하는 레이아웃 알고리즘을 적용해 본다면, 그림 10에서 보여주는 것처럼 중심에 노드들이 뭉쳐져 척도 없는 그래프에서 알고자 하는 허브들을 분석하기가 매우 힘들다.
그래서 본 논문에서는 척도 없는 네트워크를 잘 표현하는 그래프 레이아웃 알고리즘을 제안했다. 본 논문에서 제안한 알고리즘에서 허브들 간에 작용하는 허브성 척력이 거리에 반비례하고, 허브들의 degree가 a 배 증가하면, 허브사이에 작용하는 척력의 크기는 a7(7 는 연결선 지수)배가 된다. 또한, 전체 노드수와 전체 링크 수에 따라 적용되는 힘의 크기를 조정하는 계수를 두어서 네트워크의 규모에 관계없이 허브성 척력이 적용되는 특성이 있다.
76을 나타내므로 허브를 가지고 있는 척도 없는 네트워크로 볼 수 있다. 따라서 이 네트워크에 제안한 그래프 레이아웃을 적용했을 때, 그림 9와 그림 12에서 보이는 바와 같이, 그림 10, 11, 13과 비교해서 허브를 매우 쉽게 구별하고, 네트워크 분석에 도움이 됨을 알 수 있다. 그리고 향후 연구방향은 좀 더 네트워크의 분류를 세분화해서, 각각의 네트워크에 적합한 그래프 레이아웃을 자동적으로 적용시키는 방법에 대해서 연구한다.
후속연구
에너지 모델의 목적은 인간의 시각으로, 그려진 그래프의 속성을 추론하도록 만드는 것이다. 추론하기에 좀 더 효과적이고 유용한 결과를 만들기 위해서 작고 일정한 에지(edges)의 길이, 잘 분산된 노드들, 잘 분리된 클러스터와 같은 분명한 특성을 레이아웃에서 요구한다. 본 연구에서는 레이아웃알고리즘에 요구하는 분명한 특성은 허브이다 다음은 일반적인 에너지 모델의 수식이다.
따라서 이 네트워크에 제안한 그래프 레이아웃을 적용했을 때, 그림 9와 그림 12에서 보이는 바와 같이, 그림 10, 11, 13과 비교해서 허브를 매우 쉽게 구별하고, 네트워크 분석에 도움이 됨을 알 수 있다. 그리고 향후 연구방향은 좀 더 네트워크의 분류를 세분화해서, 각각의 네트워크에 적합한 그래프 레이아웃을 자동적으로 적용시키는 방법에 대해서 연구한다.
참고문헌 (32)
Gray William Flake, The Computational Beauty of Nature, A Bradford Book, the MIT Press, 1998
S. Wasserman and K. Faust, Social networks analysis, Cambridge University Press, Cambridge (1994)
D. Watts and S. H. Strogatz, 'Collective dynamics of small world networks,' Nature(London) 393, 440, 1998
R. Albert, H. Jeong, and A.-L. Barabasi, 'Diameter of the world-wide web,' Nature 401, 130-131, 1999
Charles J. Alpert and Andrew B. Kahng, 'Recent directions in netlist partitioning: A survey,' Technical report, Computer Science Department, University of California at Los Angeles, 1995
M. Kaufmann, D. Wagner (Eds.), Drawing Graphs: Methods and Models, Lecture Notes in Computer Science. Springer Berlin / Heidelberg. Volume 2025, 2001
Ivan Herman, Guy Melanc¸on, and M. Scott Marshall, Graph visualization and navigation in information visualization. volume 6(1), pages 24？43, 2000
I. Herman, G. Melancon, MS Marshall. 'Graph Visualization and Navigation in Information Visualization : a Survey,' In: IEEE Transactions on Visualization and Computer Graphics, 6(1), pp. 24-43, 2000
I. F. Cruz and J. P. Twarog, '3D Graph Drawing with Simulated Annealing', Proceedings of the Symposium on Graph Drawing GD '95, Springer-Verlag, pp.162-165, 1995
R. Davidson and D. Harel, 'Drawing Graphs Nicely Using Simulated Annealing,' ACM Transaction on Graphics, Vol.15, No.4, pp.301-331, 1996
P. Eades, 'A Heuristic for Graph Drawing,' Congressus Numerantium, Vol.42, pp.149-160, 1984
C.-S Jeong and A. Pang, 'Reconfigurable Disc Trees for Visualizing Large Hierarchical Information Space,' Proceedings of the IEEE Symposium on Information Visualization (InfoViz'98), IEEE CS Press, 1998
G. di Battista, P. Eades, R. Tamassia, and I.G. Tollis, 'Algorithms for drawing graphs: an annotated bibliography,' Computational Geometry: Theory and Applications, Vol.4, No.5, pp.235-282, 1994
Andre M.S. Barreto, Helio J.C. Barbosa, 'Graph Layout Using a Genetic Algorithm,' sbrn, p. 179, VI Brazilian Symposium on Neural Networks (SBRN'00), 2000
J. Kleinberg, 'The small-world phenomenon: An algorithmic perspective,' In Proc. 32nd ACM Symposium on Theory of Computing, 2000
R. Albert and A.-L. Barabasi, 'Statistical mechanics of complex networks,' Rev. Mod. Phys. 74, 4797, 2002
P. Eades and Q.-W. Feng, 'Multilevel Visualization of Clustered Graphs,' Proceedings of the Symposium on Graph Drawing GD '96, Springer-Verlag, pp.101-112, 1997
A. Noack. 'An energy model for visual graph clustering,' In Proc. 11th Int. Symp. on Graph Drawing, pages 425？436. Springer-Verlag, 2003
M. Faloutsos, P. Faloutsos, and C. Faloutsos, On power-law relationships of the internet topology, Computer Communications Review 29, 251 (1999)
Mark E. J. Newman, Stevens H. Strogatz, and Duncan J. Watts. 'Random graphs with arbitrary degree distributions and their applications,' Physics Reviews E, 64, 2001
Bollobas B, Riordan O, Spencer J, Tusnady G, 'The Degree Sequence of a Scale-Free Random Graph Process,' Random Structures and Algori thms 18, 279-290, May 2001
A. Noack. 'Energy models for drawing clustered small-world graphs,' Technical Report 07/03, Institute of Computer Science, Brandenburg University of Technology at Cottbus, 2003
Ulrik Brandes. Drawing on physical analogies. In M. Kaufmann and D. Wagner, editors, Drawing Graphs, LNCS 2025, pages 71-86. Springer-Verlag, Berlin, 2001
Thomas M. J. Fruchterman, Edward M. Reingold, 'Graph Drawing by Force-directed Placement,' Software-Practice and Experience archive Volume 21(11), November 1991
Bing Wang, Zhongzhi Zhang, Huanwen Tang, Zhilong Xiu. 'Evolving Scale-Free Network Model with Tunable Clustering,' International Journal of Modern Physics B November 16, 2005
※ AI-Helper는 부적절한 답변을 할 수 있습니다.