국내 청소년 배드민턴 단식 개인 및 팀 랭킹 산출: PageRank 알고리즘 적용

나경민,이미숙,조은혜 한국체육대학교 체육과학연구소 2019 스포츠사이언스 Vol.37 No.1

The purpose of this study was to calculate the rankings of individuals and teams in domestic junior badminton singles by using PageRank algorithm and to examined its usefulness. For the purpose of the study, it collected the results of the male and female singles events of middle and high school in 2018 published on the homepage of Badminton Korea Association (2019). The collected data were ranked PageRank and Winning Percentage Ranking (WP_r), after that Kendall 's rank correlation analysis was performed to confirm the relationship between the two rankings. It used Ms-Excel, NetMiner 4.0 and IBM SPSS 21.0 program for data processing. The results of this study are as follows. First, as a result of calculating the badminton middle school single players ranking, high school single players ranking, the result of the top 15 results showed a difference between PageRank and Winning Percentage Ranking (WP_r), however the result of PageRank and Winning Percentage Ranking (WP_r) was significant. Second, as a result of calculating the badminton middle school single teams ranking, high school single teams ranking was significant. Third, since the relationship between PageRank and Winning Percentage Ranking (WP_r) confirmed to be significant, it is expected to provide objective basic data useful for selection of national youth players in Korea Badminton Association. 이 연구에서는 PageRank 알고리즘을 적용하여 국내 청소년 배드민턴 단식 개인 및 팀의 랭킹을 산출하고 그 유용성을 검토하는 데 목적이 있다. 주요 분석 대상 자료는 대한배드민턴협회(2019) 홈페이지에 공개된 자료로서 2018년도에 실시된 중등부와 고등부의 남ㆍ여 단식경기 결과이다. 수집된 자료는 PageRank 알고리즘을 적용한 랭킹과 승률에 기반한 랭킹(WP_r)을 산출하였으며, 두 랭킹 산출 방법 간의 관련도를 검토하기 위하여 Kendall의 순위상관분석을 적용하였다. 자료 분석을 위해서 MS-Excel, NetMiner 4.0과 IBM SPSS 21.0 프로그램을 사용하였다. 이 연구의 주요결과는 다음과 같다. 첫째, 배드민턴 중등부 남자단식 랭킹, 중등부 여자단식 랭킹, 고등부 남자단식 랭킹, 고등부여자단식 랭킹을 산출한 결과, 상위 15위 결과에서는 PageRank와 승률랭킹 간에는 차이가 있었지만, PageRank와 승률랭킹(WP_r)의 상관도를 검토 한 결과 통계적으로 유의한 것으로 나타났다. 둘째, 배드민턴 중등부 남자단식 팀 랭킹, 중등부 여자단식랭킹, 고등부 남자단식랭킹, 고등부 여자단식랭킹을 산출한 결과, 첫째 결과와 마찬가지로PageRank와 승률랭킹(WP_r)의 상관분석 결과 관계성이 유의하게 높은 것으로 나타났다. 셋째, PageRank와 승률랭킹(WP_r) 간의 결과에서 관계성이 유의한 것으로 확인됨으로써 대한배드민턴협회에서 실시하는 청소년대표 및 국가대표 후보군 선발 시 유용한 객관적인 기초자료 제공이 기대된다.

Ranking Quality Evaluation of PageRank Variations

팜민득(Pham Minh Duc),허준석(Jun-Seok Heo),이정훈(Jeong-Hoon Lee),황규영(Kyu-Young Whang) 大韓電子工學會 2009 電子工學會論文誌-CI (Computer and Information) Vol.46 No.5

PageRank 알고리즘은 구글(Google)등의 검색 엔진에서 웹 페이지의 순위(rank)를 정하는 중요한 요소이다. PageRank 알고리즘의 순위 품질(ranking quality)을 향상시키기 위해 많은 변형 알고리즘들이 제안되었지만 어떤 변형 알고리즘(혹은 변형 알고리즘들간의 조합)이 가장 좋은 순위 품질을 제공하는지가 명확하지 않다. 본 논문에서는 PageRank 알고리즘의 잘 알려진 변형 알고리즘들과 그들 간의 조합들에 대해 순위 품질을 평가한다. 이를 위해, 먼저 변형 알고리즘들을 웹의 링크(link) 구조를 이용하는 링크기반 방법(Link-based approaches)과 웹의 의미 정보를 이용하는 지식기반 방법(Knowledge-based approaches)으로 분류한다. 다음으로, 이 두 가지 방법에 속하는 알고리즘들을 조합한 알고리즘들을 제안하고, 변형 알고리즘들과 그들을 조합한 알고리즘들을 구현한다. 백만 개의 웹 페이지들로 구성된 실제 데이터에 대한 실험을 통해 PageRank의 변형 알고리즘들과 그들 간의 조합들로부터 가장 좋은 순위 품질을 제공하는 알고리즘을 찾는다. The PageRank algorithm is an important component for ranking Web pages in Google and other search engines. While many improvements for the original PageRank algorithm have been proposed, it is unclear which variations (and their combinations) provide the “best” ranked results. In this paper, we evaluate the ranking quality of the well-known variations of the original PageRank algorithm and their combinations. In order to do this, we first classify the variations into link-based approaches, which exploit the link structure of the Web, and knowledge-based approaches, which exploit the semantics of the Web. We then propose algorithms that combine the ranking algorithms in these two approaches and implement both the variations and their combinations. For our evaluation, we perform extensive experiments using a real data set of one million Web pages. Through the experiments, we find the algorithms that provide the best ranked results from either the variations or their combinations.

PageRank 알고리즘을 활용한 사이버표적 중요성 순위 선정 방안 연구

김국진 ( Kook-jin Kim ),오승환 ( Seung-hwan Oh ),이동환 ( Dong-hwan Lee ),오행록 ( Haeng-rok Oh ),이정식 ( Jung-sik Lee ),신동규 ( Dong-kyoo Shin ) 한국인터넷정보학회 2021 인터넷정보학회논문지 Vol.22 No.6

전 세계적으로 과학기술의 발달에 따라 육·해·공·우주에 이어 사이버공간이라는 영역 또한 전장 영역으로 인식되고 있다. 이에 따라 육·해·공·우주에서 이루어지는 물리적 작전뿐만 아니라 사이버공간에서 이루어지는 사이버 작전 수행을 위한 정의, 체계, 절차, 계획 등 다양한 요소를 설계·수립해야 한다. 본 연구에서는 사이버 작전의 표적처리(Targeting) 중 표적개발 및 우선순위 부여 단계에서 중간표적개발을 통해 선정한 사이버 표적 목록에 대한 우선순위를 부여할 때 고려할 수 사이버 표적의 중요성을 고려 요소로 선정하여 이에 대한 점수를 산출, 사이버 표적 우선순위 선정 점수의 일부로 활용하는 방안을 제시한다. 이에 따라, 사이버 표적 우선순위 부여 과정에서 사이버 표적 중요성 범주를 설정하고, 사이버 표적 중요성 개념 및 기준항목을 도출한다. 도출된 기준항목별 점수 산정 및 종합을 위해 PageRank 알고리즘을 기반으로 Event Prioritization Framework 등의 매개변수를 종합한 TIR(Target Importance Rank) 알고리즘을 제안한다. 그리고 스턱스넷 사례 기반 네트워크 토폴로지 및 시나리오 데이터를 구성하여 제안된 알고리즘으로 사이버 표적 중요성 점수를 도출하고 사이버 표적의 우선순위를 선정하여 제안된 알고리즘을 검증한다. With the development of science and technology around the world, the realm of cyberspace, following land, sea, air, and space, is also recognized as a battlefield area. Accordingly, it is necessary to design and establish various elements such as definitions, systems, procedures, and plans for not only physical operations in land, sea, air, and space but also cyber operations in cyberspace. In this research, the importance of cyber targets that can be considered when prioritizing the list of cyber targets selected through intermediate target development in the target development and prioritization stage of targeting processing of cyber operations was selected as a factor to be considered. We propose a method to calculate the score for the cyber target and use it as a part of the cyber target prioritization score. Accordingly, in the cyber target prioritization process, the cyber target importance category is set, and the cyber target importance concept and reference item are derived. We propose a TIR (Target Importance Rank) algorithm that synthesizes parameters such as Event Prioritization Framework based on PageRank algorithm for score calculation and synthesis for each derived standard item. And, by constructing the Stuxnet case-based network topology and scenario data, a cyber target importance score is derived with the proposed algorithm, and the cyber target is prioritized to verify the proposed algorithm.

구글 페이지랭크 알고리즘에 의한 체조경기 랭킹모형 제안: 2015년도 남녀 마루운동 종목 랭킹 산출

박재현 ( Jae-hyeon Park ),한충식 ( Chung-sik Han ),윤지운 ( Jiwun Yoon ),윤효준 ( Hyojun Yun ) 한국체육대학교 체육과학연구소 2018 스포츠사이언스 Vol.35 No.2

이 연구는 구글 페이지랭크 알고리즘을 활용하여 남녀 체조경기의 랭킹모형을 제안하고자 한다. 구글 페이지랭크는 네트워크 이론을 기반으로 하여 웹페이지 순위를 매기는 모형인데, 최근 스포츠 분야의 랭킹 산출에 적용하려는 시도가 적지 않다. 전통적으로 스포츠분야에서 소개되고 있는 랭킹 모형은 일대일 경쟁을 기반으로 하여 승, 패, 무승부의 값을 갖게 되기 때문에 체조와 같은 승패를 산출할 수 없는 종목에 적용하는데 한계가 있어 왔다. 이 연구는 체조와 같이 다중경쟁자가 출전하는 종목에서 활용할 수 있는 랭킹 모형으로서 페이지랭크를 제안하였다. 페이지랭크는 네트워크 이론에 기반을 두고 있기 때문에 많은 선수들이 출전하는 경쟁에서도 어렵지 않게 모든 선수를 대상으로 순위를 매길 수 있으며, 실시간으로 순위를 업데이트 할 수 있다는 장점을 가지고 있다. 이 연구에서는 2015년도 남녀 마루운동 종목의 랭킹 산출에 실제 적용하였으며, 다중경쟁자가 출전하는 체조종목에 페이지랭크 알고리즘으로 순위를 계산할 수 있다는 사실을 확인 할 수 있었다. This study proposed a ranking model of male and female gymnastics players using the Google PageRank algorithm. Google PageRank is a web page ranking system that is based on network theory. Recently, there have been an attempts to apply it to rankings calculation in sports field. Traditionally, the ranking models introduced in sports are based on one-on-one competition. There has been a limit to applying to gymnastics that can not produce a win or loss. This study proposed Google PageRank as a ranking model that can be used in the events of multi-contestant such as gymnastics. Because PageRank is based on network theory, it has the advantage of being able to rank all players in a competitive position and to update rankings in real time. This study was applied to the ranking calculation of 2015 male and female floor exercise of Gymnastic sports, and it was confirmed that ranking competition can be calculated by the PageRank algorithm on the gymnastics events with multi-contestant competition.

Ranking Quality Evaluation of PageRank Variations

팜민득,허준석,이정훈,황규영,Pham, Minh-Duc,Heo, Jun-Seok,Lee, Jeong-Hoon,Whang, Kyu-Young The Institute of Electronics and Information Engin 2009 電子工學會論文誌-CI (Computer and Information) Vol.38 No.10

The PageRank algorithm is an important component for ranking Web pages in Google and other search engines. While many improvements for the original PageRank algorithm have been proposed, it is unclear which variations (and their combinations) provide the "best" ranked results. In this paper, we evaluate the ranking quality of the well-known variations of the original PageRank algorithm and their combinations. In order to do this, we first classify the variations into link-based approaches, which exploit the link structure of the Web, and knowledge-based approaches, which exploit the semantics of the Web. We then propose algorithms that combine the ranking algorithms in these two approaches and implement both the variations and their combinations. For our evaluation, we perform extensive experiments using a real data set of one million Web pages. Through the experiments, we find the algorithms that provide the best ranked results from either the variations or their combinations. PageRank 알고리즘은 구글(Google)등의 검색 엔진에서 웹 페이지의 순위(rank)를 정하는 중요한 요소이다. PageRank 알고리즘의 순위 품질(ranking quality)을 향상시키기 위해 많은 변형 알고리즘들이 제안되었지만 어떤 변형 알고리즘(혹은 변형 알고리즘들간의 조합)이 가장 좋은 순위 품질을 제공하는지가 명확하지 않다. 본 논문에서는 PageRank 알고리즘의 잘 알려진 변형 알고리즘들과 그들 간의 조합들에 대해 순위 품질을 평가한다. 이를 위해, 먼저 변형 알고리즘들을 웹의 링크(link) 구조를 이용하는 링크기반 방법(Link-based approaches)과 웹의 의미 정보를 이용하는 지식기반 방법(Knowledge-based approaches)으로 분류한다. 다음으로, 이 두 가지 방법에 속하는 알고리즘들을 조합한 알고리즘들을 제안하고, 변형 알고리즘들과 그들을 조합한 알고리즘들을 구현한다. 백만 개의 웹 페이지들로 구성된 실제 데이터에 대한 실험을 통해 PageRank의 변형 알고리즘들과 그들 간의 조합들로부터 가장 좋은 순위 품질을 제공하는 알고리즘을 찾는다.

World Ranking of Men`s Singles Badminton Players using PageRank Algorithm

( Hyo Jun Yun ),( Jae Hyeon Park ),( Sung Ho Park ),( Chang Hwan Choi ) 한국체육학회 2015 국제스포츠과학 학술대회 Vol.2015 No.1

Purpose: The purpose of this study is to introduce the basic concepts of PR(PageRank) algorithm and to calculate the World Ranking of men`s singles badminton players using PR algorithm as an application case of sports field. After that, this study will compare the PR method and BR(World Ranking published by Badminton World Federation) method. Method: To calculate the world ranking of men`s singles of badminton players, match data of 98 players who participated in the 16 tournaments from June 2014 Japan Open to Jun 2015 Indonesia Open were collected. Above all match data were collected from the web site of the Badminton World Federation and were organized using Excel 2013. PR algorithm was applied using Matlab 7.0, Damping Factor was set at 0.15 for the ranking calculation. Result: As a result of comparison the PR method and BR method, there were the differences in two respects. The first is the difference of ranking calculation method by the number of winning matches. Compare to the BR method, the PR method was showed that the quality was more important than quantity in terms of winning matches. The second is the difference of ranking calculation method by the number of participated tournament. The PR method is considered more important the final result of tournament than the number of participated tournament. Conclusion: Ranking calculation using PR algorithm is shown that the quality of wining matches is more important. There is no meaningful to which method is more appropriate. Introducing the concepts and characteristics of PR algorithm in itself is worthy enough. We expect that this study can be a good staring for researching the ranking calculation further in the sports field.

Improved Subgraph Estimation PageRank Algorithm for Web Page Rank

Lanying Li,Qiuli Zhou,Yin Kong,Yiming Dong 보안공학연구지원센터 2015 International Journal of Security and Its Applicat Vol.9 No.11

The traditional PageRank algorithm can’t efficiently dispose large data Webpage scheduling problem. This paper proposes an accelerated algorithm named topK-Rank .It is based on PageRank on the MapReduce platform. Owing to this algorithm ,Top k nodes can be found efficiently for a given graph without sacrificing accuracy. It can iteratively estimate lower/upper bounds of PageRank scores, and construct subgraphs in each iteration by pruning unnecessary nodes and edges. Theoretical analysis shows that this method guarantees result exactness. Experiments show that it can find top k nodes much faster than the existing approaches.

A New Multi-View and Controllable Community-Uncovering Algorithm

Zhang Xin,Wang Xiaolong,Liu Bingquan 보안공학연구지원센터 2015 International Journal of Hybrid Information Techno Vol.8 No.7

This paper introduces a new multi-view and controllable community-uncovering algorithm, an achievement of improving PageRank algorithm and Spin-glass model, which can avoid the overlapping community structure in the process of detecting communities by means of other algorithms and also helps to improve the usual community-expansion model.The process of uncovering communities by the introduced algorithms can be divided into three steps: first, identifying the nuclear one among nodes ranked by the advanced PageRank algorithms; Second, through using multi-view recognition modularity provided by Potts spin-glass model, optimizing the expansion model of local community that is found by applying the improved Iterative Greedy algorithm to eliminate the traditional modularity’s limits in the resolution limit and the following negative effects. Finally, grasping the overlapping structure and notes carefully. By analyzing and comparing the two results of respectively using PRSGMFCA and traditional technical schemes in both computer simulation network and the real network, it proves that the former enjoys stronger stability and higher accuracy than the latter, and its computation complexity is also acceptable.

큰 그래프 상에서의 개인화된 페이지 랭크에 대한 빠른 계산 기법

박성찬,김연아,이상구 한국정보과학회 2022 정보과학회논문지 Vol.49 No.10

Computation of Personalized PageRank (PPR) in graphs is an important function that is widely utilized in myriad application domains such as search, recommendation, and knowledge discovery. As the computation of PPR is an expensive process, a good number of innovative and efficient algorithms for computing PPR have been developed. However, efficient computation of PPR within very large graphs with over millions of nodes is still an open problem. Moreover, previously proposed algorithms cannot handle updates efficiently, thereby severely limiting their capability of handling dynamic graphs. In this paper, we present a fast converging algorithm that guarantees high and controlled precision. We attempted to improve the convergence rate of the traditional Power Iteration approximation methods and fully exact methods. The results revealed that the proposed algorithm is at least 20 times faster than the Power Iteration and outperforms other state-of-the-art algorithms in terms of computation time. 그래프 내에서 개인화된 페이지랭크(Personalized PageRank, PPR)를 계산하는 것은 검색, 추천, 지식발견 등 여러 분야에서 광범위하게 활용되는 중요한 작업이다. 개인화된 페이지랭크를 계산하는 것은 고비용의 과정이 필요하므로, 개인화된 페이지랭크를 계산하는 효율적이고 혁신적인 방법들이 다수 개발되어왔다. 그러나 수백만 이상의 노드를 가진 대용량 그래프에 대한 PPR 계산은 여전히 시간이 크게 소요되는 작업이다. 그에 더하여, 기존에 제시된 알고리즘들은 그래프 갱신을 효율적으로 처리하지 못하여, 동적으로 변화하는 그래프 처리에 한계가 있다. 이에 대응하여, 본 연구에서는 높은 정밀도를 보장하면서도 빠르게 수렴하는 PPR 계산 알고리즘을 제시한다. 전통적인 거듭제곱법(Power Iteration)에, 축차가속 완화법(Successive Over Relaxation)과 초기 추측값 보정법(Initial Guess Revision)을 활용한 벡터 재사용 전략을 적용하여 수렴 속도를 개선하였다. 제시된 방법은 기존 거듭제곱법의 장점인 단순성과 엄밀성을 유지하면서도 수렴율과 계산속도를 크게 개선한다. 또한 개인화된 페이지랭크 벡터의 갱신을 위하여 이전에 계산되어 저장된 벡터를 재사용하여, 갱신에 드는 시간이 크게 단축된다. 본 방법은 주어진 오차 한계에 도달하는 즉시 결과값을 산출하므로 정확도와 계산시간을 유연하게 조절할 수 있으며, 이는 표본 기반 추정방법이나 역행렬 기반 방법이 가지지 못한 특성이다. 실험 결과, 본 방법은 거듭제곱법에 비하여 20배 이상 빠르게 수렴한다는 것이 확인되었으며, 기 제시된 최속 알고리즘과 비교하여도 결과 품질을 일정 수준 이상으로 유지하면서도 수행시간 면에서 우수한 성능을 보이는 것 또한 확인되었다.

Representative Information Retrieval Algorithm Based on PageRank Algorithm and MapReduce Model

Ling Wei,Yang Li,Yongjiang Wei 보안공학연구지원센터 2016 International Journal of Database Theory and Appli Vol.9 No.3