[Neo4j] Graph Data Science-그래프 알고리즘(Graph Algorithms)

이번에는 다양한 알고리즘 계층과 알고리즘의 다양한 실행 모드 및 GDS에서 알고리즘을 실행하는 데 필요한 메모리를 추정하는 방법에 대해서 공부해볼 것이다.

 

계층

GDS 알고리즘은 알파, 베타, 프로덕션 세 계층으로 분류된다.

계층	설명	접두사
알파	알고리즘이 실험적이며 언제든지 변경되거나 제거될 수 있음을 나타낸다	gds.alpha.<algorithm>
베타	알고리즘이 프로덕션 품질 계층의 후보임을 나타낸다	gds.beta.<algorithm>
프로덕션 품질	알고리즘이 안정성 및 확장성과 관련하여 테스트되었음을 ​​나타낸다	gds.<algorithm>

 

실행 모드

GDS 알고리즘에는 알고리즘 결과를 처리하는 방법을 결정하는 4가지 실행모드가 있다.

실행모드	설명
stream	알고리즘의 결과를 레코드 스트림으로 반환한다.
stats	요약 통계의 단일 레코드를 반환하지만 Neo4j 데이터베이스에 쓰거나 데이터를 수정하지 않는다.
mutate	알고리즘의 결과를 메모리 내 그래프 프로젝션에 쓰고 요약 통계의 단일 레코드를 반환한다.
write	알고리즘의 결과를 Neo4j 데이터베이스에 다시 쓰고 요약 통계의 단일 레코드를 반환한다.

 

메모리 추정

데이터 크기가 커질 수록 필요한 메모리의 양을 파악하는 것은 중요해진다. 이를 위해 GDS는 알고리즘을 실제로 실행하기 전에 데이터에 알고리즘을 사용하는데 필요한 메모리를 추정할 수 있는 방법을 제공한다.

- estimate: 알고리즘 및 실행모드에 대한 메모리 추정을 하기 위한 명령

 

전체 알고리즘 구문

CALL gds[.<계층>].<알고리즘>.<실행모드>[.<메모리추정>](
	graphName: STRING,
	configuration: MAP
)

전체 알고리즘 구문은 위와 같다.

 

중심성과 중요성(Centrality and importance)

중심성 알고리즘: 그래프에서 개별 노드의 중요성을 결정하는데 사용

 

중심성의 일반적인 사용 사례

1. 추천: 콘텐츠 또는 제품 제공 카탈로그에서 가장 영향력 있거나 인기 있는 항목을 식별하고 추천 2. 공급망 분석: 네트워크의 공급자, 제조 제품의 일부인 원자재 또는 경로의 항구 등 공급망에서 가장 중요한 노드를 찾음 3. 사기 및 이상행위 탐지: 공유 식별자가 많거나 많은 커뮤니티 간의 브리지 역할을 하는 사용자를 찾음

 

차수 중심성(Degree Centrality)-gds.dgree.stream

차수 중심성은 가장 보편적이고 단순한 중심성 알고리즘 중 하나이다. 노드가 가진 관계의 수를 계산하는 알고리즘이다. GDS 구현에서는 특히 노드에서 나가는 관계의 수인 외부 중심성을 계산한다. 즉, 각 노드의 관계 수에만 기반하는 알고리즘이다.

 

CALL gds.graph.project('proj', ['Actor','Movie'], 'ACTED_IN');

먼저 그래프를 만든다. proj 이름으로 Actor와 Movie 노드를 가져오고 ACTED_IN 관계도 가져와 연결시킨 그래프를 만든다.

 

CALL gds.degree.stream('proj')
YIELD nodeId, score
RETURN gds.util.asNode(nodeId).name AS actorName, score AS numberOfMoviesActedIn
ORDER BY numberOfMoviesActedIn DESCENDING, actorName LIMIT 5

그 다음 차수 중심성 스트리밍을 한다.

gds.degree.stream 형식으로 사용해, proj의 관계인 ACTED_IN의 차수를 계산한다. 

위 쿼리의 경우, 가장 많은 영화에 출연한 탑 5 배우를 가져오는 쿼리이다. 즉, Acotr에서 나가는 관계인 ACTED_IN 관계의 개수를 셈으로써 차수 중심성을 사용한다.

 

페이지 랭크 알고리즘(Page Rank)

차수 중심성 알고리즘 외 또다른 일반적인 중심성 알고리즘은 바로 Page Rank 알고리즘이다. PageRank는 지불 네트워크, 공급망 및 물류, 통신, 라우팅, 웹 사이트 및 링크의 그래프와 같이 관계가 특정 형태의 이동 흐름 을 의미하는 유향 그래프에서 노드의 영향을 측정하기 위한 좋은 알고리즘이다. 

 

PageRank는 원래 Google의 Larray Page 와 Sergey Brin이 새로운 종류의 검색 엔진에 대한 연구 프로젝트의 일환으로 개발한 알고리즘이다. 이는 Google 검색에서 검색 엔진 결과에서 웹 페이지의 페이지 순위를 매기는 데 사용되었다.

 

PageRank는 이웃 노드의 중요성 및 외도 중심성으로 가중된 이웃 노드에서 들어오는 관계 수를 계산하여 노드의 중요도를 측정한다. 더 중요한 노드가 다른 중요한 노드에서 비례적으로 더 많은 사용자 유입을 가진다는 가정에서 나온 아이디어이다. 

 

그 예시로 1990년 이후에 출시된 영화 중 수익이 최소 1000만 달러 이상인 영화에서, 감독->배우 네트워크에서 가장 영향력있는 인물을 찾기 위해 PageRank를 사용한 것을 테스트 해보도록 하자!

 

//drop last graph projection
CALL gds.graph.drop('proj', false);

//create Cypher projection for network of people directing actors
//filter to recent high grossing movies
CALL gds.graph.project.cypher(
  'proj',
  'MATCH (a:Person) RETURN id(a) AS id, labels(a) AS labels',
  'MATCH (a1:Person)-[:DIRECTED]->(m:Movie)<-[:ACTED_IN]-(a2)
   WHERE m.year >= 1990 AND m.revenue >= 10000000
   RETURN id(a1) AS source , id(a2) AS target, count(*) AS actedWithCount,
    "DIRECTED_ACTOR" AS type'
);

먼저 그래프를 만들기 위해 기존에 있던 proj를 gds.graph.drop 명령을 사용해 지워준다.

그 다음 사이퍼 프로젝션을 만들어 준다.

1. proj이라는 이름의 프로젝션을 만드는데

2. 모든 Person 노드를 가져와 id(a)와 labels(a)를 반환한 값을 그래프의 노드로 사용한다. (아이디와 레이블)

3. WHERE 절에서 1990년 이후에 출시되고 10000000달러 이상의 수익을 낸 조건으로 (a1:Person), DIRECTED 관계, Movie 노드, ACTED_IN 관계, (a2:Person) 노드를 검색한다.

4. a1의 id, a2의 id를 가져오고 이 두 개의 합산한 값을 count 함수를 사용해 가져온다. 그리고 DIRECTED_ACTOR라는 관계로 연결지어 준다.

 

CALL gds.pageRank.stream('proj')
YIELD nodeId, score
RETURN gds.util.asNode(nodeId).name AS personName, score AS influence
ORDER BY influence DESCENDING, personName LIMIT 5

그 다음 PageRank 알고리즘을 사용해 DIRECTED_ACTOR 네트워크에서 가장 영향력 있는 상위 5명의 인물을 찾는다. gds.pageRank.stream 함수를 사용해  proj 프로젝션에 PageRank 알고리즘을 사용할 것을 명시한다.

 

기타 중심성 알고리즘

- 매개 중심성: 노드가 그래프에서 다른 노드 사이에 서 있는 정도를 측정한다. 그래프의 한 부분에서 다른 부분으로 다리 역할을 하는 노드를 찾는 데 자주 사용된다.

 

https://neo4j.com/docs/graph-data-science/current/algorithms/centrality/

Centrality - Neo4j Graph Data Science

더 많은 중심성 알고리즘은 위 페이지에서 확인 가능하다.

 

경로 찾기 알고리즘(Path Finding)

경로 찾기 알고리즘은 둘 이상의 노드 사이에서 최단 경로를 찾거나 경로의 가용성 및 품질을 평가하는데 사용된다

경로찾기 알고리즘의 일반적인 사용사례

1. 공급망 분석: 출발지와 도착지 또는 원자재와 완제품 사이의 가장 빠른 경로 식별 2. Customer Journey: 고객의 경험을 구성하는 이벤트를 분석 ex) 의료 분야에서는 입원에서 퇴원까지 입원 환자의 경험

 

Dijkstra 소스 - 타겟 최단 경로

 

일반적인 산업에서의 표준 경로 찾기 알고리즘은 Dijkstra이다. 이는 소스 노드와 대상 노드 사이의 최단 경로를 계산하는 알고리즘이다.

 

예제를 봐보자! 

CALL gds.graph.project('proj',
    ['Person','Movie'],
    {
        ACTED_IN:{orientation:'UNDIRECTED'},
        DIRECTED:{orientation:'UNDIRECTED'}
    }
);

먼저 그래프를 만들어줘야 한다. proj 이름으로 Person 노드와 Movie 노드를 가져오고, 관계에서 ACTED_IN이 없으면 UNDIRECTED, DIRECTED가 없으면 UNDIRECTED 관계로 연결지어주는 조건을 넣어서 관계를 만들어준다.

 

MATCH (a:Actor)
WHERE a.name IN ['Kevin Bacon', 'Denzel Washington']
WITH collect(id(a)) AS nodeIds
CALL gds.shortestPath.dijkstra.stream('proj', {sourceNode:nodeIds[0], TargetNode:nodeIds[1]})
YIELD sourceNode, targetNode, path
RETURN gds.util.asNode(sourceNode).name AS sourceNodeName,
    gds.util.asNode(targetNode).name AS targetNodeName,
    nodes(path) as path;

그러면 Dijkstra를 사용해 최단 경로를 확인할 수 있다.

- gds.shortestPath.dijkstra.stream(): dijkstra를 사용해 최단 경로를 찾는 알고리즘 메서드

 

위 쿼리의 경우 Kevin Bacon과 Denzel Washington 사이의 최단경로를 찾을 수 있고, 결과는 4개의 홉 경로가 나온다.

 

기타 경로 찾기 알고리즘

- 두 노드 사이의 최단 경로 탐색

A* Shortest Path	휴리스틱 함수를 사용하여 계산 속도를 높이는 Dijkstra의 확장
Yen's Algorithm Shortest Path	Dijkstra의 확장으로 여러 상위 k 최단 경로 를 찾을 수 있음

- 소스 노드와 다른 여러 대상 노드 간의 최단 경로 탐색

Dijkstra 단일 소스 최단 경로 (Dijkstra Single-Source Shortest Path)	하나의 소스와 여러 대상 간의 최단 경로를 위한 Dijkstra 구현
델타 스테핑 단일 소스 최단 경로 (Delta-Stepping Single-Source Shortest Path)	병렬화된 최단 경로 계산. Dijkstra 단일 소스 최단 경로보다 빠르게 계산하지만 더 많은 메모리를 사용

- 소스 노드와 다른 여러 대상 노드 간의 일반 경로 탐색

너비 우선 검색 (Breadth First Search)	각 반복에서 소스 노드로부터 거리가 증가하는 순서로 경로를 검색
깊이 우선 검색 (Depth First Search)	각 반복에서 단일 다중 홉 경로를 따라 가능한 한 멀리 검색