PageRank 알고리즘 공부

 

페이지 랭크(PR, PageRank) 알고리즘은 구글 검색엔진의 핵심이다.

 

요약하자면 하이퍼텍스트 정보를 이용하여 웹페이지 사이 연결정보로 검색 결과를 향상시키기 위한 알고리즘이다.

 

연결정보로부터 특정 페이지를 다른 페이지들이 얼마나 인용하는지 세는 방식이다.

 

예를 들어, A 페이지를 B, C 페이지에서 인용하고 있다고 가정하자.

 

이 때, B 페이지에서 전체 인용 링크 수 5개 중 1개가 A 페이지인 경우 PR(B) / L(B) = 1 / 5 가 된다.

 

PR(B)의 경우 초기값은 1이고, 재귀적으로 반복 계산되어 수렴되는 PR 을 사용한다.

 

N은 전체 문서 수, L은 인용 수, d는 Damping Factor 값(Random Surfer)이다.

 

여기서 Random Surfer는 사용자가 해당 페이지에 만족하지 못하고 다른 페이지로 이동하는 랜덤 확률을 나타낸다.

 

d 값은 일반적으로 (논문들에서) 0.85 값을 사용하며, 이는 85%는 만족하지 못하고 다른 페이지로 이동하며,

 

나머지 15%만이 해당 페이지를 유의깊게 읽어본다는 말이 된다.

 

위의 예를 1회 계산하면,

 

PR(A) = (1 - 0.85) / 3 + 0.85 * (1 / 5 + 1 / 1) = 1.07

 

여기서 C 는 전체 인용 링크 수 1개 중 1개가 A 페이지인 경우를 예로 들었다.

 

단순한 예에서는 PR 값이 순환되지 않아 PR(A), PR(B), PR(C) 값이 1회 계산으로 수렴되지만,

 

실제 서비스 환경에서는 계산을 반복할 수록 PR 값이 수렴하는 결과를 얻을 수 있다.

 

PageRank를 간단하게 Java 프로그램으로 테스트할 수 있다. (참고)

 

예를 들어 CSV 형태의 url, outLink1, outLink2, ... 데이터가 있다고 가정해보자.

 

먼저 다음과 같이 각 url 키를 담을 객체가 필요하다.

public class PageRankValue {
	private double pageRankScore;
	private double outLinkScore;
	private List<String> outLinks;
}

 

다음으로 매 url 마다 PageRankValue를 생성해야 한다.

private void addPageRankValue(String[] csv) {
	if (csv == null || csv.length == 0) throw new IllegalArgumentException();

	String key = csv[Configurations.IDX_KEY_LINK];
	if (!Validator.validateString(key)) throw new NullPointerException();

	PageRankValue prValue = null;
	if (mapPageRanks.containsKey(key)) prValue = mapPageRanks.get(key);
	else prValue = new PageRankValue();

	for (int i = (Configurations.IDX_KEY_LINK + 1); i < csv.length; i++) {
		prValue.addOutLink(csv[i]);
		if (!mapPageRanks.containsKey(csv[i])) mapPageRanks.put(csv[i], new PageRankValue());
	}
	mapPageRanks.put(key, prValue);
}

 

이제 미리 정해둔 iteration 횟수만큼 evaluation을 수행하면 된다.

@Override
public void evaluate() {
	// Set the outLinkScore for the entire links
	mapPageRanks.keySet().stream().forEach(k -> {
		PageRankValue prValue = mapPageRanks.get(k);
		Iterator<String> outLinks = prValue.getOutLinks();

		while (outLinks.hasNext()) {
			PageRankValue prOutLink = mapPageRanks.get(outLinks.next());

			if (prOutLink != null) {
				// Divides the source link's page rank score by the number of out links
				double score = prValue.getScore() / prValue.getOutLinkCount();
				prOutLink.addOutLinkScore(score);
			}
		}
	});

	// After setting outLinkScore, evaluate each page rank score using the number of entire links
	mapPageRanks.keySet().stream()
			.forEach(k -> mapPageRanks.get(k).evaluate(Configurations.DAMPING_FACTOR, mapPageRanks.size()));
}

 

이렇게 연습해본 PageRank 알고리즘에 실제 대용량의 데이터를 적용하려면, Hadoop, Spark 등과 같은 대용량 데이터 처리 프레임워크를 기반으로 처리해 볼 수 있다.