[Graph] Multiple Source BFS Search

Matrix Multiplication 을 통한 Multi Source BFS Search

• Directed Graph 는, 특정 노드와 인접한 노드를 Matrix Multiplcation 을 통해 찾을 수 있습니다.

전체 흐름

세부 설명

• 예를 들어, 아래와 같은 Directed Graph 가 주어졌을 때

  

• 해당 Directed Graph 는 아래와 같은 Matrix 로 표현할 수 있습니다.

  

  • col : 시작 노드
  • row : 도착 노드

• 이때, 해당 Directed Graph 에서 3번 노드, 5번 노드와 인접한 노드를 찾고자 한다면

• Directed Graph Matrix 에 아래와 같은 Matrix 를 곱해주면 됩니다.

  

  • col : 시작 노드로 지정할 노드의 개수
  • row : 시작 노드의 번호

• 따라서, 아래와 같은 Matrix Multiplication 결과를 확인할 수 있으며,

  

• 결과 Matrix 를 통해 "3번 노드와 인접한 노드는 1번 노드와 5번 노드", "5번 노드와 인접한 노드는 6번 노드" 라는 결과를 확인할 수 있습니다.

• 또한, 해당 결과 Matrix 를 다시 우측 Matrix 로 사용해 Matrix Multiplication 을 진행한다면,

• "1번 노드, 5번 노드와 인접한 노드는 2번 노드, 6번 노드", "6번 노드와 인접한 노드는 2번 노드" 와 같은 결과를 확인할 수 있습니다.

• 따라서, 이처럼 결과 Matrix 를 우측 Matrix 로 반복해서 사용하며 Matrix Multiplication 을 진행한다면

• Matrix Multiplication 결과는 Density 가 높아지며,

• 시작 노드로부터의 BFS 탐색 결과와 동일해지게 됩니다.

참고

• https://slidetodoc.com/tools-and-primitives-for-high-performance-graph-computation/
  • 10p 부터