[neo4j] Minimum Spanning Tree 사용하기

 오늘은 MST(Minimum Spanning Tree) 알고리즘을 neo4j에서 사용하는 법에 대해서 써본다. 굳이 쓰는 이유는 neo4j라이브러리가 업데이트되면서 알고리즘을 쓰는 방법들이 조금씩 달라졌기 때문이다. 그럼 시작해본다.

 

MST?

A minimum spanning tree (MST) or minimum weight spanning tree is a subset of the edges of a connected, edge-weighted undirected graph that connects all the vertices together, without any cycles and with the minimum possible total edge weight.

 위키피디아엔 위와같이 정의되어 있다. 번역하자면 "내부 순환(cycle)이 없고, 가중치가 있는 양방향 연결(undirected) 이며, 엣지의 가중치가 가능한한 최소로 연결되도록한 것이 최소신장트리 이다." 정도로 볼 수 있겠다. 

 어기서 가중치가 가능한한 최소로 연결된다는 점에서 주목해봐야 한다. 즉, 전역 최적(global optima) 가 아닌 부분 최적(local optima)라는 뜻이다. 따라서 전역 최적값을 찾고자 한다면, 다른 방법을 사용해야 한다. 

대략적인 알고리즘 진행순서

 프로그램이 알아서 해주긴 하지만 그래도 어느정도는 알고 있어야 한다고 생각한다.

• 시작 노드를 설정한다
• 시작 노드의 엣지들을 탐색한다
• 이 중 가장 가중치가 적은 엣지를 선택한다
• 다음 노드로 이동한다.
• 다음 노드가 방문한 적이 없으면 위의 과정을 반복한다
• 만약 방문한 적이 있다면, 이전 노드로 돌아가 그 다음으로 가중치가 적은 노드를 선택한다
• 반복한다
• 모두다 방문하면 끝낸다

아마 이럴텐데, 중간에 논리 오류가 있을 것이다. 이렇게 짜여있기 때문에, 전역 최적값이 아닐 수 있다. 왜냐하면 전역 최적은 전체를 놓고 봤을때 가장 작은 값이지, 각 단계에서 가중치의 합이 작은 것은 아니기 때문이다. 전역최적은 그 travel sales man problem이라고 치면 설명은 잘 나온다. 구현은 다른 이야기지만.

데이터 준비 및 버전 확인

데이터 불러오기는 지난번에 한 데이터를 그대로 사용한다

2022.07.05 - [논문/GraphDB(neo4j)] - [Neo4j / 데이터 불러오기] web csv에서 데이터 불러오기

각 버전은 위와같다. 여기서 특히 Graph Data Science Library(GDS) 버전을 잘 맞춰야 한다. 이게 안맞아서 그걸 찾는데 시간이 좀 걸렸다.

시작하기 전 주의사항

  GDS를 사용하는데 여러가지 옵션이 있다. stream, write 등이 있는듯 한데 아직 정확히는 모르겠다. 이 둘만 놓고 얘기한다면 stream은 그냥 결과만 보여준다. 하지만 write는 써있듯이, 계산 결과를 db에 쓰게 된다. MST의 경우, 계산한 edge를 db에 쓴다. 본인의 db 관리 시나리오에 이게 치명적이라면 주의해서 써야할것으로 보인다. 물론 edge 지우기가 그리 어렵지는 않았던거로 기억하니 문제되지 않을지도.

Docs읽기

https://neo4j.com/docs/graph-data-science/current/alpha-algorithms/minimum-weight-spanning-tree/

위 사이트에 들어가면 docs가 있다. 현재 mst가 alpha 버전이라고 그런다. 그러니까 추후에 언제 어디로 이동해서 바뀔지 모르니, 때마다 맞게 대응하시길 바란다.

순서는 항상 graph 만들기 실행하기

 docs 몇개를 보니 gds를 사용하는 패턴은 graph를 만들고, 그 후에 실행하도록 되어있다. graph는 일종의 환경설정과 비슷하다고 보면 될 것 같다. 이 부분에 대해선 해보면서 알아봐야겠다.

CALL gds.graph.project(
  'yourGraphName',
  'Place',
  {
    LINK: {
      type: 'EROAD',
      properties: 'distance',
      orientation: 'UNDIRECTED'
    }
  }
)

현재 우리의 데이터 스키마를 먼저 설명해야 겠다.

 이 사진을 보면 node에는 place라벨, edge(relation)에는 eroad가 있는 것을 볼 수 있다. minst는 사실 결과값인데, 지우지 않아서 존재한다. 따라서 이들에 맞게 바꾼 값을 반영한게 위의 내용이다.즉. 'Place', type: 'EROAD', properties: 'distance' 이 세부분이 바꼈다. 본인의 스키마가 다르다면 이에 맞게 해주면 될 듯 싶다.

MST 실행하기

MATCH (n:Place {id: 'Amsterdam'})
CALL gds.alpha.spanningTree.minimum.write('yourGraphName', {
  startNodeId: id(n),
  relationshipWeightProperty: 'distance',
  writeProperty: 'MINST',
  weightWriteProperty: 'writeCost'
})
YIELD preProcessingMillis, computeMillis, writeMillis, effectiveNodeCount
RETURN preProcessingMillis, computeMillis, writeMillis, effectiveNodeCount;

 마찬가지로 우리 상황에 맞게 변경했다. 데이터에 'Amsterdam'이 있기에 변경했다. 'Amsterdam'에서 시작하는 MST를 만들게 된다. 위에서 언급했듯, edge를 생성하기 때문에 writeProperty 부분에 'MINST'를 볼 수 있다.

결과 보기

 우선 좌 하단에 설정을 눌러, Connect result nodes를 끄고 진행한다. 이유는 테이블로 보는게 아닌 graph로 볼건데, 이게 켜져 있으면 모든 edge가 다 나오기 때문이다. 쿼리를 위한 Cypher는 다음과 같다.

MATCH path=(:Place)-[:MINST]->(:Place)
RETURN path

 

테이블로 보고싶다면 아래와 같이 쓰면된다

MATCH path = (n:Place {id: 'Amsterdam'})-[:MINST*]-()
WITH relationships(path) AS rels
UNWIND rels AS rel
WITH DISTINCT rel AS rel
RETURN startNode(rel).id AS source, endNode(rel).id AS destination, rel.writeCost AS cost

 

테이블로 보는것은 아무래도 python등과 연결했을때 데이터 분석을 위해 필요할 것으로 보인다. 그 방법은 추후 해보면서 할일이 있다면 해보도록 하겠다.

 

끝.