트리(tree) 네트워크는 닫힌 루프가 하나도 없으면서 임의의 한 노드(node)에서 다른 모든 노드(node)를 연결하는 경로(path)가 있는 네트워크를 말합니다. 상류에서부터 흘러내리는 강이 자연에서 볼 수 있는 트리 구조 네트워크라고 할 수 있습니다.

treeNetwork

트리 네트워크의 성질은

  • 모든 노드가 연결되어있고(connected), 루프(loop)가 없다.
  • n-1개의 엣지가 있다.
  • 어떤 한 엣지를 제거하면 끊긴(disconnected) 네트워크가 된다.
  • 임의의 두 노드 사이에 오직 하나의 경로(path)만이 존재한다.
  • 한 엣지를 추가하면 루프가 생긴다.

등으로 요약할 수 있습니다.

loess Plateau

황토고원(loess plateau)에서 볼 수 있는 자연에서 생성된 트리 네트워크

Natural Tree

황토고원의 트리 네트워크를 간단히 그린 것

 

 

 

 

 

 

 

 

모든 트리 네트워크는 뿌리내린 형식(rooted manner)으로 그릴 수 있습니다. 위 그림을 보면 가장 위에 있는 뿌리 노드(root node; 검정색)에서 아래쪽으로 가지를 뻗어나가는 것을 볼 수 있습니다. 각각의 가지에서 가장 아래에 위치해서 다른 한 노드와만 연결되어있는 노드를 잎사귀 노드(leaf node)라고 합니다. 위상수학적으로, 트리는 어느 특정한 뿌리 노드를 가지고 있지 않습니다. 네트워크의 어떤 노드라도 뿌리 노드가 되도록 그릴 수 있다는 것입니다.

Tree1

A). 트리 네트워크,   B). ‘A’네트워크를 뿌리내린 형식으로 그린 네트워크

트리 네트워크의 가장 중요한 특징으로 임의의 두 노드를 연결하는 경로가 오직 하나만 존재한다는 것을 들 수 있습니다. 트리 네트워크에 닫힌 루프가 없기 때문에 생기는, 어찌보면 명백한 특징이라고 할 수 있습니다. 이런 특징 덕분에 다른 네트워크를 쓸 때보다 여러가지 계산이 단순해집니다. 예를들어 네트워크의 지름(diameter)이나 매개 중심성(betweenness centrality)같이 최단 경로를 이용하는 특성을 계산할 때 트리 구조에서 매우 쉽게 계산할 수 있습니다. 이런 이유로 트리 네트워크는 네트워크의 기초 모형으로 사용됩니다.

트리 네트워크의 또 다른 유용한 성질로는 n개의 노드의 트리 네트워크는 항상 n-1개의 엣지(edge)를 가진다는 것이 있습니다. 이 역도 성립해서, n개의 노드와 n-1개의 엣지를 가진 네트워크는 전부 트리 네트워크라고 할 수 있습니다.

위의 성질들로 인해 트리 네트워크는 네트워크에 관한 연구에서 중요한 위치에 있습니다. 예를 들면, 네트워크의 계층적 분해(hierarchical decomposition)를 나타낼 때 유용하게 쓰이는 계통수(dendrogram)에 트리 네트워크가 쓰이고, AVL 트리같은 데이터 구조의 구성 요소로 트리 네트워크가 쓰이기도 합니다. 또, 케일리 트리(Cayley tree)나 베테 격자(Bethe lattice)같은 이론적인 맥락에서 활용되기도 합니다. ==★

Cayley Tree

케일리 트리(Cayley tree)

sig

 

광고