Graph - MST(Minimum Spanning Tree)

MST(Minimum Spanning Tree)

• 정의
  MST는 순환을 생성하지 않는 동시에, 가능한 최소의 edge weight 합으로 모든 노드를 연결하는 graph의 subgraph다.
  쉽게 말해 edge의 총 가중치를 최대한 줄이는 방식으로 생성되는 그래프로 가장 중요한 관계만 강조한다.가중치가 있는 무방향 그래프의 경우, MST는 가능한 가장 비용 효율적인 방식으로 모든 노드에서 다른 노드로 이동할 수 있도록 보장한다
  
  
• 계산 방법
  codependence matrix -> distance matrix ->  Kruskal 알고리즘
  데이터에 따라 적절한 codependence matrix 계산 방법론을 선택해야 한다. 
  distance matrix를 통해 만들어진 complete graph 로 부터 시작한다
  가장 많이 사용되는 Kruskal 알고리즘은 complete graph의 각 weight(거리)를 오름차순으로 정렬하고 MST에 채택할 가장 작은 간선부터 시작하여 cycle을 만들지 않으며 차례차례 추가한다.
  
  
• 장점
  • MST는 명확하고 단순한 구조를 제공하므로 시장에서 허브 역할을 하는 주요 주식을 더 쉽게 식별할 수 있다.
  • 가장 강한 상관관계(또는 가장 작은 거리를 기반으로 한 관계)만 포함함으로써 MST는 가장 중요한 연결을 강조한다
  • MST는 계산효율적이므로 금융 시장에서 일반적으로 사용되는 대규모 데이터 세트에 유용하다
• 단점
  • 순환 없이 트리 구조만 형성하기 때문에 많은 연결을 삭제하며 잠재적으로 주식 간의 중요한 2차 관계를 간과한다.
    각 주식에 대한 가장 강력한 연관성만 보여주기 때문에 전체 시장 구조, 특히 긴밀하게 상호 연결된 부문에서 전체 시장 구조를 잘못 나타낼 수 있다.

코스피 상위 종목들을 활용한 MST그래프