Rescale에서 R을 사용하여 PageRank 크기 조정

페이지 랭크 (PageRank)
지난 몇 년 동안 데이터 기반 애플리케이션이 확산되면서 많은 애플리케이션이 대규모 데이터 세트에 대한 고급 분석에 의존하게 되었습니다. MapReduce 기반 프레임워크는 다음과 같습니다. 하둡을 사용하면 알고리즘을 빅 데이터 세트로 더 쉽게 확장할 수 있지만 제한적인 프로그래밍 프레임워크로 인해 기존 계산을 MapReduce 모델에 맞추기가 어렵습니다.
다음과 같은 배열 기반 언어 R, 통계 분석을 작성할 수 있는 훨씬 더 자연스럽고 표현력이 풍부한 프레임워크를 제공합니다. R은 1996년에 소개된 이후 전 세계 통계학자와 데이터 과학자가 선택하는 언어 중 하나가 되었습니다. 패키지는 활발한 커뮤니티와 대화형 생태계를 자랑하지만 상당한 제한 사항도 있습니다. R은 단일 스레드이며 더 큰 데이터 세트에서는 잘 확장되지 않습니다. 이러한 단점으로 인해 통계학자가 작성한 효과적인 통계 패키지가 중요하지 않은 데이터 세트에 쓸모 없게 됩니다.
알고리즘이 데이터 집약적이라면 Hadoop이 더 나은 솔루션임이 입증되었습니다. 그러나 기존 R 코드를 영리하게 리팩토링하면 R에서 더 나은 성능을 끌어낼 수 있습니다. 그런 점에서 저는 R에 대한 MPI 랩어라운드를 테스트하기로 결정했습니다. Rmpi.

페이지 랭크 (PageRank)

페이지 랭크 (PageRank) Google의 강력한 엔진을 탄생시킨 인기 있는 링크 분석 알고리즘입니다. 링크 분석 알고리즘은 어떤 사람이 무작위로 인터넷을 서핑하여 특정 웹페이지에 도달할 가능성을 나타냅니다. PageRank 계산은 수렴되기 전에 여러 번의 패스가 필요합니다. 한 노드가 다른 노드에 연결되면 PageRank 점수의 일부가 해당 노드의 전체 PageRank 점수에 기여합니다. PageRank가 더 높은 노드가 두 번째 노드에 연결되면 두 번째 노드가 자동으로 더 높은 PageRank를 받습니다. 알고리즘의 업데이트 기능은 다음과 같습니다.

PR (A) = (1-d) + d (PR (T1) / C (T1) + ... + PR (Tn) / C

PR(A) – 노드 A의 PageRank

d - 감쇠 인자

PR(Tn)/C(Tn) – PR(A)에 기여한 Tn 점수의 일부입니다. 여기서 T1… Tn은 A에 연결되는 노드입니다.

PageRank의 가장 순진한 버전은 모든 노드가 처음에 동일한 순위를 가지며 각 노드가 수렴될 때까지 이웃에 동일한 점수를 배포한다고 가정합니다. 이 알고리즘은 PageRank 벡터에 대한 연속 업데이트 간의 차이가 매우 작은 값보다 작을 때 수렴됩니다.

병렬화 전략

이 계산에는 두 가지 주요 데이터 구조가 있습니다. 인접 행렬은 그래프를 나타내고 PageRank 벡터에는 모든 노드에 대한 점수가 포함됩니다. 각 스레드는 인접 행렬 행의 해당 부분에서만 작동하지만 전체 PageRank 벡터는 각 반복 후에 슬레이브 스레드에서 사용할 수 있어야 합니다. 이렇게 하면 업데이트된 PageRank가 다음 반복에 사용됩니다. MPI 연산을 사용했습니다 분산 인접 행렬을 슬레이브 스레드에 배포하고 작업 모두 모아 사용 각 반복 후에 부분 PageRank 벡터의 결과를 수집합니다.

에 대한 실험 Rescale 플랫폼

내가 사용 스탠포드 네트워크 분석 프로젝트 내 실험을 위한 데이터 세트, 특히 고에너지 물리학 인용 네트워크 데이터 세트. 그래프에는 34,546개의 노드와 421,578개의 간선이 포함되어 있습니다. 바닐라 순차 버전의 런타임은 653.89초였습니다.

런타임 그래프는 12(86.733초) 스레드와 16(68.38초) 스레드 사이에서 런타임 이득이 점점 줄어드는 지수적 감소 분포를 따릅니다.

매우 큰 데이터 세트로 확장하는 것은 여전히 ​​어려운 일이지만, Rescale 플랫폼에서 시연된 것처럼 Rmpi와 같은 프레임워크를 사용하여 R을 적당한 크기의 데이터 세트로 확장할 수 있습니다.
이 시뮬레이션을 Rescale 계정으로 가져올 수 있습니다 여기에서 지금 확인해 보세요.. 아직 Rescale 계정이 없다면 다음으로 이동하세요. www.rescale.com/signup 오늘 무료 계정에 가입하세요.
Rescale에 대해 자세히 알아보려면 다음 사이트를 방문하세요. www.rescale.com. 엔지니어링 및 과학 시뮬레이션에 Rescale을 사용하려면 다음으로 문의하십시오. info@rescale.com.

비슷한 게시물