이번 세미나는 오늘날 구글을 있게 한 PageRank 알고리즘과 그 후속 연구인 Incremetal PageRank를 소개하였습니다. PageRank는 그래프 데이터에서 random walk를 활용하여 각 노드 간 영향도를 파악하기 위한 알고리즘입니다. 딥러닝의 발전 속도가 눈부시지만 딥러닝이 아닌 알고리즘도 여전히 중요하게 쓰이기 때문에 20년이 지난 지금도 관련 연구가 지속되고 있다는 것을 알 수 있었습니다. 특정 feature의 중요도나 상호 관계의 파악이 필요한 분들께 활용을 권해보고 싶습니다.

​

이번 세미나는 그 유명한 PageRank 알고리즘과 그 후속 연구인 Incremental PageRank를 강성현 연구원님이 소개해주었다. PageRank는 Web상의 수많은 페이지의 중요도를 측정하기 위해 쓰이는 알고리즘으로 여전히 구글 검색 엔진에 활용되고 있다고 한다. 우선 전통적인 PageRank를 계산하는 방법에 대해서 설명해 주었고 웹사이트를 Node, Hyperlink를 edge로 정의 했을 때 모든 Node로부터 도착 확률을 재귀적으로 계산하는 알고리즘이라고 한다. 간단한 예제를 통하여 PageRank에 대해서 직관적이고 쉽게 이해할 수 있었고 세미나에서 언급하였던 damping factor, dangling node를 다루는 방법도 흥미로웠다. 하지만 현재 웹사이트는 동적으로 변하고 있고 19억개가 넘는 사이트가 있으므로 전통적인 PageRank 알고리즘은 상당한 컴퓨팅 리소스와 시간을 필요로 하여 사용이 어렵다는 한계가 있다. 이러한 대규모의 네트워크 데이터를 다루기 위하여 Incremental PageRank를 소개해주었다. 이는 Monte Carlo 방법을 활용하여 충분한 수의 Random walk를 실행한 후 각 Node 별 방문 횟수로 PageRank 값을 구한다고 한다. 특히 기존 PageRank가 해당 Node에 '도착할 확률'을 계산하였다면 Incremental PageRank는 해당 Node를 '지나갈 확률'을 구한다는 것이 핵심이라고 한다. 해당 알고리즘 또한 쉽게 설명해주어 이해하는데 어려움 없었다. 수업으로 들었던 내용과 일부 관련 있는 내용이 있어 흥미롭게 들을 수 있었고 Network 데이터에서 중요도를 산출하는 것은 다양한 분야에 적용할 수 있으므로 추후 개인 연구에도 많은 도움이 될 것 같다는 생각이 들었다. 유익한 세미나를 준비해주신 강성현 연구원님께 감사드리며 이상으로 세미나 후기를 마친다.

이번 세미나에서는 PageRank에 대하여 강성현 연구원님이 설명을 해주었다.
그래프란 정점과 그 정점을 연결하는 간선을 하나로 모아놓은 자료 구조이다. 연결되어 있는 객체 간의 관계 표현이 필요한 다양한 도메인에서 활용되고 있다.
PageRank는 website 중요도를 연결 관계에 기반하여 측정한 지표를 말한다.
PageRank 계산 방법은 모든 정점으로부터 도착 확률을 재귀적으로 계산한다. 즉, 연결된 페이지 가지 수와, 연결된 페이지의 중요도가 클 수록 신뢰할 수 있는 페이지로 간주 한다.
또한 계산 방법에 대해서, 산업수학혁신센터의 예시로 쉽게 이해할 수 있도록 설명을 해주었다. 또한, 고립된 dangling node가 발생하는데, 이를 해결하는 방법에 대해서도 직관적으로 설명을 해주었다.
웹사이트는 끊임없이 변화를 하고 있고, 큰 규모로 인하여, PageRank score를 갱신하기 위해 처음부터 계산하는 것을 상당히 어렵고, 대응하기가 어렵다는 한계적 상황이 있다.
이에 대하여, Incremental PageRank 알고리즘을 소개해주었다.
Monte Carlo 방법을 활용하여 근사 PageRank를 구하는 방법이다. 이전 PageRank와의 차이점은 관점을 도착 확률에서 지나갈 확률로 전환을 하는 것이 주요 핵심 아이디어이다.
Incremental PageRank산출 방법에 대해서도 상세한 설명을 해주었다.
현재 듣고 있는 과목에서 Network간의 관계를 Graph Network로 나타내는 내용을 학습하고 있는데, 이와 관련 해서 유명한 알고리즘인 PageRank에 대해서 상세하게 들을 수 있어서 매우 유익하였다. Network 관계를 파악하는 방법은 여러 분야에서 적용을 하거나, 응용을 할 수 있을 것으로 생각된다. 접근하기 힘든 내용을 간략하고 깔끔하게 설명을 해주신 강성현 연구원님께 감사인사를 드립니다.

인터넷 홈페이지 사이의 연결성을(관계) 고려한 홈페이지(데이터)의 중요성을 정량화하는 연구 분야에 대한 세미나였다. PageRank라는 핵심 아이디어 소개를 통해 본 연구 분야의 중요성과 개념을 잘 이해할 수 있었다. 나아가, 오늘날 같이 홈페이지 수가 어마어마한 인터넷 상에서는 기존 PageRank 알고리즘에 대한 연산량 버든이 심하게 다가오는데, 이러한 문제점들을 어떻게 보완할 수 있을까에 대한 내용을 세미나에서 청취할 수 있었다(대규모의 웹 규모 확장에 PageRank 연구 분야가 대응하기 시작).

이러한 연구 분야가 딥러닝, 머신러닝 기반의 그래프 네트워크 연구 분야에도 확장될 수 있으면 새로운 연구가 될 것 같다. 웹페이지 데이터 뿐만 아니라, 날이 갈수록 복잡하고 대규모의 연결 관계를 가진 데이터셋은 분명히 생겨날 것이고, 이와 관련된 연산량 처리를 딥러닝으로도 실시할 수 있어야 하기 때문이다. 본 연구 분야에서의 적용되었던 연산량 감소 아이디어들이, 딥러닝 기반 그래프 네트워크 데이터에도 누군가는 열심히 반영하고 있을 것만 같은 느낌이 들었다.

이번 세미나는 Incremental PageRank라는 주제로 진행되었다. PageRank는 Website 간의 중요도를 연결 관계에 기반하여 측정한 지표이다. 즉, Website의 연결관계처럼 그래프 형태의 데이터에서 중요 노드를 찾고자 하는 알고리즘이다. 이는 모든 정점으로부터 도착 확률을 재귀적으로 계산하며, 연결된 노드의 수와 연결된 노드의 중요도가 클수록 신뢰할 수 있는 노드로 판단한다.

하지만 이러한 PageRank는 최근 급증하는 웹사이트의 수에 따라 오리지날 PageRank을 사용할 경우 이를 모두 연산할 수 없다. 이를 극복하기 위해서 제안된 방법론이 바로 Incremental PageRank이다. 이는 Monte Carlo 방법을 활용하여 반복 무작위 추출을 수행함으로써 근사 PageRank를 도출하였다. 이때 도착확률이 아닌 지나갈 확률로 관점을 전환한 것이 핵심이며, 기록된 path를 재활용하여 PageRank Score를 갱신한 것이 포인트가 된다. 이를 통해 적은 Random Walk 시도에서도 준수한 성능을 기록하는 등 근사 PageRank임에도 준수한 결과를 얻을 수 있었다.

최근 Website의 수에 대한 증가추세는 더욱 가파르게 될 것이며, 이러한 PageRank의 효율성에 대한 연구는 더더욱 필요할 것이다. 사실 논문을 볼 때 효율성보다는 성능적인 측면에 늘 집중해서 봤었는데, 이번 세미나를 계기로 효율의 중요성에 대해서 다시 한 번 짚고 넘어가는 계기가 되었다. 유익한 세미나를 준비해주신 강성현 연구원님께 감사드리며 이상으로 세미나 후기를 마친다.