개요
- 그래프 데이터를 처리하는 알고리즘: PageRank, SimRank, 커뮤니티 탐지, 스팸 탐지
- Web as a directed graph
- Nodes = Webpages
- Edges = Hyperlinks
- 웹을 체계화(organize)하는 방법
- First try: 인간이 직접 분류하는 것(Human curated)
- Web directories: Yahoo, DMOZ, Looksmart
- Second try: 웹 검색 엔진(Web search)
- Information Retrieval investigates: 작고 신뢰있는 집합에서 관련 문헌을 어떻게 잘 찾아내는지 연구하는 학문
- Newspaper articles, Patents, etc.
- Information Retrieval investigates: 작고 신뢰있는 집합에서 관련 문헌을 어떻게 잘 찾아내는지 연구하는 학문
- 실제 웹은 너무 거대하며, 신뢰되지 않는 문서들이 매우 많다. 스팸도 그러하다.
- 검색 엔진의 2가지 난제
- 웹은 많은 정보를 포함한다. 신뢰(trust)에 대한 정보를 어떻게 알 수 있나?
- 신뢰있는 페이지들은 서로서로 참조할 것이다.
- (키워드)“newspaper”를 질의할 때 최고의 대답(검색결과)는 무엇인가?
- newspaper에 대해 실제로 아는 페이지들은 많은 newspaper들을 참조하고 있을 것이다.
- 그래프에서 노드(웹 페이지)를 등급 매기는 방법
- 모든 웹 페이지는 동등하게 중요하지 않다.
- 웹 그래프 노드 연결성에 대해 많은 다양성이 있다.
- 링크 구조에 따라 페이지들에 등급을 매길 수 있다.
- 링크 분석 알고리즘(Link Analysis Algorithms): 그래프에서 노드의 중요도(importances or score)를 계산하기 위한 접근법
-
Page-Rank
-
Topic-Specific (Personalized) Page-Rank
-
Web Spam Detection Algorithms
PageRank: The “Flow” Formulation
- 투표로 보는 링크(Links as Votes)
- 페이지는 많은 링크를 가질수록 중요해진다.
- In-coming links: 노드로 들어오는 링크
- Out-going links: 노드에서 나가는 링크
- in-links를 (다른 페이지로부터 받는) 투표로 보기
- 예를 들어, 스탠포드 대학 사이트는 23,400 의 in-links를 가진다.
- in-links가 많은 노드로부터 in-links를 받는 노드는 중요도가 더 높은 링크를 갖는다.
- 인기있는 웹페이지로부터 참조를 받으면 다른 링크보다 중요도가 더 높아진다.
- 재귀적으로 in-links의 근원지(source)를 찾아 링크마다 scoring
- 아래 노드들의 점수는 다른 노드에서 들어오는 score와 나가는 score가 동일할 때의 값이다. (a.k.a 동적 평형)
- 단순 재귀 공식화(Simple Recursive Formulation)
- 각 링크의 투표(vote)는 들어오는 페이지의 중요도에 비례한다. (중요도만큼 투표를 받은 것으로 간주)
- 중요도 rj를 가지는 페이지 j가 n개의 out-links를 가진다면, 각 out-links는 rj/n 만큼의 중요도를 다른 노드에게 준다.
- 페이지 j의 중요도는 모든 in-links의 값들의 합이다.
- 즉, 노드는 자신의 score에서 out-links의 개수만큼 나눈 값을 다른 노드로 전달한다.
노드 k에 out-links의 개수는 4이기 때문에, 노드 k의 각 out-links의 값은 노드 k의 중요도 / 4 이다.
노드 i에서 out-links의 개수는 3이기 때문에, 노드 i의 각 out-links의 값은 노드 i의 중요도 / 3 이다.
노드 j에서 in-links는 노드 i와 k에서 오는 것만 있으므로, 중요도는 (노드 k의 중요도 / 4) + (노드 i의 중요도 / 3)이 된다.
PageRank: The “Flow” Model
- 중요한 페이지에서 투표값(score or vote)은 더욱 가치가 있다. 한 페이지는 다른 중요한 페이지들로부터 참조되면 더욱 중요해진다.
- 페이지 j에 대한 rank rj 의 정의
- di 는 노드 i의 out-degree (나가는 링크의 개수)이다.
- 노드 i에서 노드 j로 나가는 링크가 존재한다고 가정
- Flow 수식 풀기
- 3개의 수식, 3개의 미지수, 상수는 없을 때, 유일해는 없다.
- 모든 해는 scale factor를 나머지 연산한 것과 동일하다.
- 추가적인 제약이 유일해를 이끌어낸다.
- 가우시안 소거법은 작은 예제에서는 잘 동작하지만, 매우 큰 웹 그래프에 대해서는 더 나은 방법이 필요하다.
PageRank: Matrix Formulation
- 확률론적 인접 행렬(Stochastic adjacency matrix)
- 페이지 i가 di 값의 out-links 를 가질 때, 페이지 i에서 j로 링크가 있다면 인접행렬 M의 원소 Mij=1/di가 되며, 링크가 없다면 해당 원소는 0이 된다.
- 행렬 M은 column stochastic matrix 로 열 벡터의 합은 1이다.
- Rank Vector r: 원소가 페이지당 rank 에 해당되는 벡터
- ri 는 페이지 i의 중요도 점수이다.
- 벡터의 원소의 합은 1이다.
- Flow 수식은 아래와 같다.
- 페이지 i의 score 를 페이지 i에서 j로 이동한 out-going link 의 개수로 나누면 노드 j의 score를 구할 수 있다.
- Eigenvector Formulation: rank vector r은 학률론적 웹 행렬(stochastic web matrix) M 의 eigenvector 이다.
- 행렬 M은 모두 양수인 원소를 갖는 column stochastic이기 때문에 가장 큰 eigenvalue는 1이다.
- 벡터 r의 길이는 1이며, 행렬 M의 각 컬럼의 합도 1이다. M*r <= 1
- 그러나 이 방법은 느리기 때문에 보다 효율적으로 벡터 r을 구해야 한다.
- 그 방법을 Power Iteration이라고 한다.
Power Iteration Method
- n개의 노드를 갖는 웹 그래프가 주어질 때, 노드들은 페이지를 의미하고 간선은 하이퍼링크를 의미한다.
- Power iteration: 단순 반복 계획(a simple iterative scheme)
-
N = 웹 페이지 개수
-
초기화 단계에서 N으로 나누는 것은 모든 페이지들이 평등하단 의미이다.
- 각 노드에 들어오는 score를 연립방정식으로 세우는 것이 중요하다.
- Power iteration은 가장 큰 eigenvalue에 대응하는 벡터인, dominant eigenvector를 찾는 방법
Thus 부분이 중요하다. 결국 M^k*r(0) 는 상수*(첫번째 eigenvalue의 k승 * 첫번째 eigenvector)에 가까워진다.
Random Walk Interpretation
- 랜덤 웹 서퍼(random web surfer)
- t 시점에, 어떤 페이지 i를 서핑한다.
- t+1 시점에, 서퍼는 랜덤으로 균일하게 페이지 i로부터 out-link를 따라간다.
- 페이지 i로부터 연결된 페이지 j에서 끝이 난다.
- 무한하게 위의 과정을 반복한다.
- p(t) = 서퍼가 t 시점에 페이지 i에 있음을 증명하는 i번째 좌표를 가진 벡터
- p(t)는 페이지에 대한 확률 분포이다.
- 고정 분포(The Stationary Distribution)
- t+1 시점에 서퍼가 어디 있는가?
- 랜덤으로 균일하게 link를 따른다.
- p(t+1) = M*p(t)
- p(t+1) = M*p(t) = p(t) 일 때, p(t)는 random walk의 고정 분포이다. 즉, 어떤 상태(state)에 도달한 것이다.
- 원래 rank vector r은 r=M*r을 만족한다. 따라서 r은 random walk에 대한 고정 분포이다.
- 존재와 유일함(Existence and Uniqueness)
- random walk 이론으로부터 주요 결과는 Markov processes로 알려졌는데, 어떤 조건을 만족시키는 그래프에 대해서 고정 분포는 유일하고 초기 확률 분포가 어떻든지 마침내 어떤 상태에 도달할 것이다.
- 즉, 무한 루프가 아니다.
PageRank: The Google Formulation
- 3가지 질문
-
언제 끝나는가? (Does this converge?)
-
우리가 원할 때 끝나는가? (Does it converge to what we want?)
-
결과는 합리적인가? (Are results reasonable?)
- 문제점
- Dead end: 어떤 페이지들은 out-links를 갖지 않아, random walk는 갈 곳이 없다.
- r 벡터는 모두 0이 되는 현상
- 이런 페이지들은 중요도를 누출시킨다. (leak out)
- Spider trap: random walk가 트랩에 빠지는 현상
- 모든 out-links가 그룹 내 에 있어서 외부 링크 벡터가 0이 되는 현상
- 결국 모든 중요도를 없애버린다.
노드 m에 도달하면 계속 m에 대한 링크만 타고 가게 된다. (trapped)
- 해결책: Teleports
- 구글은 spider trap에 대한 해결책을 제시했다. 각 시점의 스텝마다, 랜덤 서퍼는 2가지 옵션을 갖는 것이다.
- 𝜷 를 가지고 랜덤으로 링크를 따라간다.
- 1-𝜷 를 가지고 랜덤 페이지로 점프한다.
- 𝜷 에 대한 일반적인 값은 0.8 ~ 0.9이다.
- 서퍼는 몇몇 시점에 스텝 시 spider trap에 걸리면 텔레포트(teleport)할 것이다.
- dead-end에서 확률 1을 가지고 랜덤으로 링크를 teleport 한다.
- 이 때 노드의 개수만큼 확률을 나눠갖기 때문에 1이 분산된다.
m이 모두 0이어서 dead-end 상태였으나, random teleport 때문에 m에 ⅓ 씩 값을 갖게 된다.
- Teleport가 문제를 해결하는 이유
- Spider-traps 은 문제는 아니지만, 트랩이 있는 PageRank의 score는 원하던 것이 아니다. 유한한 숫자만큼 이동(steps)하면 spider trap 으로부터 teleport 할 수 있다.
- Dead-ends 는 문제가 맞다. 행렬은 column stochastic 이 아니어서, 초기 추측값이 다를 수 있다. 항상 갈 곳이 달리 없을 때 teleport해주어서 행렬의 column stochastic을 만들 수 있다.
- Random Teleport: 구글의 해결책
- 각 단계에서 랜덤 서퍼가 가지는 두 가지 옵션
- 𝜷 를 가지고 랜덤으로 링크를 따라간다.
- 1-𝜷 를 가지고 랜덤 페이지로 점프한다.
- Google Matrix
- NxN 행렬은 모든 원소가 1/N 이다.
- 재귀적인 문제: r = A*r
- Power method 가 여전히 잘 동작한다.
- 𝜷 에 대한 정의
- 실제로 0.8, 0.9 이다.
PageRank 계산하는 방법
- matrix-vector multiplication
- 충분한 메모리를 가진다면 쉬우나, 실제로 행렬 A와 벡터 r은 매우 크다.
- N = 1 billion pages
- 각 원소마다 4바이트가 필요하고, r 벡터가 2 billion 개의 원소를 가진다면 대략 벡터 r 이 2개이므로 8 GB 가 필요하다.
- 행렬 A 는 N*N 개의 원소를 갖게된다.
- Matrix Formulation: N개의 페이지들이 있을 때, out-links 를 di 개 가지고 있는 페이지 i가 있다면 다음과 같은 공식이 성립한다.
- random teleport
- 페이지 i에서 모든 다른 페이지까지 teleport link를 추가하고 이동 확률(transition probability)을 (1-𝜷)/N 으로 설정한다.
- 각 out-link 를 1/|di| 에서 𝜷/|di| 로 확률을 줄인다.
- 전체에서 𝜷를 곱한 게 전체가 되었으므로 그만큼 값이 분산된다.
- 각 페이지의 점수에 (1-𝜷) 를 곱하고 다시 분배한다.
- 모든 웹페이지의 Rank Score 에서 (1-𝜷) 만큼 받아서 전체로 다시 분배(동일하게 나눠줌)
- 결국 전체 score는 이전 score의 (1-𝜷) 가 된다.
여기서 행렬 M은 dead-ends가 없다고 가정한다. 벡터 r의 모든 원소의 합은 1이다.
- Sparse Matrix Formulation
- 행렬 M은 sparse matrix이지만 dead-ends가 없다.
- 각 노드에 10개의 link가 있으면 M의 원소의 개수는 10N 으로 근사한다.
- 매 반복마다 새로운 벡터 r을 계산해야 하고, 상수값을 새 벡터 r 에 더해주어야 한다.
- 이 방법으로 인해 계산이 빨라진다.
- Sparse Matrix Encoding: 0이 아닌 원소만 사용하는 것
- link의 개수가 대략 공간에 비례한다.
- 10N 개의 원소가 있으면 4*10*1 billion = 40 GB 를 차지
- 여전히 메모리에는 올리기 힘들며, 오히려 디스크에 맞출 수 있는 크기이다.
-
위의 행렬 구조를 사용하는 것이다. 첫번째 행은 0번 노드에서는 1번,5번,7번 노드로 가는 out-link만 가지고 있는 걸 의미한다.
- 큰 행렬을 이용하여 계산하는 방법 (Basic Algorithm: Update Step)
- 새로운 벡터 r을 메모리로 맞추기 위해 충분한 RAM이 있다고 가정하자.
- 오래된 벡터 r과 행렬 M은 디스크에 있다.
- 위의 중간 행렬이 M인데 여기서 계산이 되는 행과 오래된 벡터 r의 계산이 될 원소만 메모리로 가져와서 연산이 끝나면 다시 한 줄씩 가져오는 것이다. 행렬이 디스크 공간 상에 순차적으로 저장이 되었기 때문에 디스크 연산이 근처 영역만 읽기(linear scan) 때문에 입출력 시간이 비교적 적다. 메모리에는 새로운 벡터 r만 있는데 random access 가 가능하므로 입출력 시간이 비교적 적다.
- 새로운 벡터 r의 각 원소에는 행렬 M의 첫번째 행에 따라 오래된 벡터의 0번 원소의 score를 ⅓ 씩 나눠준 것이다.
- 비용이 디스크에 새로운 벡터 r과 오래된 벡터 r을 써야해서 2|r|이 되고 행렬 M은 모든 원소를 한번씩 읽어야 하므로 |M|이 된다.
- 여기서 비용은 디스크 입출력 연산만 포함한다.
- 만약 메모리에 올려야 하는 새로운 벡터 r이 너무 크다면, 위의 방법을 사용하기 어렵다.
- 블록 기반의 갱신 알고리즘 (Block-based Update Algorithm)
- 새로운 벡터 r을 블록 단위로 쪼개서 메모리에 올린다. 그리고 각 블록마다 한 번씩 M과 오래된 벡터 r을 스캔한다.
- 행렬 M과 오래된 벡터 r을 스캔하는 비용이 커진다. k는 스캔하는 횟수=블록 개수
- 블록 스트라이프 갱신 알고리즘(Block-Stripe Update Algorithm)
- 행렬 M을 stripe 단위로 나누어서 저장하는데, 연산 시, 필요한 원소만 읽고 쓸 수 있다.
- 엡실론은 매우 작은 숫자이다. 1+엡실론 < k 라고 가정한다.
- 벡터 r에 대해 (k+1)번 입출력 연산이 되는 이유는 마지막 1이 새로운 벡터 r을 저장하는데 드는 비용이기 때문이다.
PageRank 에 여전히 존재하는 문제점
- 페이지의 일반적인 인기도 측정
- 이전까지는 link의 개수에만 영향을 받았다.
- 그러나 페이지가 담고 있는 내용도 신경 쓸 필요가 있다.
- Topic-Specific PageRank
- 중요도의 단순한 척도를 사용
- 측정 항목을 늘릴 필요가 있다.
- Hubs-and-Authorities
- 링크 스팸(Link spam)을 허용
- 의도적으로 page rank 를 올리는 수단(linking 문제)을 방지해야 한다.
- TrustRank
매우 큰 그래프의 분석: TrustRank 와 WebSpam
Topic-Specific PageRank
- 범용적인 인기도 대신에, 주제와 관련된 인기 척도를 사용
- 웹 페이지들이 특정 주제(e.g. “sports” or “history”)와 얼마나 가까운지에 따라 인기도를 계산하는 법
- 검색 요청(search queries)에 대해 사용자의 흥미를 기반으로 응답해줄 필요가 있다.
-
“Trojan” 이라는 단어를 검색했을 때, 국가 이름인지 사람 이름인지 알 필요가 있다.
- 랜덤 워커(Random walker)는 어떤 단계에서는 teleport를 할 작을 확률을 가진다.
- Standard PageRank
- 어떤 페이지든지 동일한 확률을 가진다.
- dead-end와 spider-trap 문제를 피할 수 있다.
- Topic Specific PageRank
- 주제 구체적인, 관련 페이지들의 집합 = teleport set
- 기본 아이디어: random walk 마다 bias를 주기
- 워커가 텔레포트를 할 때, 집합 S로부터 페이지를 선택한다.
- 집합 S는 해당 주제와 관련된 페이지들만 포함한다.
- 집합 S로 매 텔레포트가 발생하면, 매 순간 다른 벡터 r을 얻는다.
- Matrix Formulation
-
잘 동작하게 하려면, PageRank 수식의 teleportation 부분을 갱신해줄 필요가 있다.
A is stochastic! —> 위의 조건은 도착지 노드가 s에 포함되는 경우
- teleport set S에 있는 모든 페이지에 동등하게 가중치를 매긴다.
- 페이지에 다른 가중치를 할당할 수도 있다.
- 표준 PageRank에 대해서 연산
- M으로 곱하고 벡터에 더한다.
- sparseness를 유지한다.
위에 1번 노드로 들어오는 링크의 값은 tax로, 항상 1로 teleport 하므로 추가되는 값이다.
- Topic Vector S
- 다른 주제에 대한 다른 PageRank를 생성
- 어떤 주제 랭킹을 사용할 것인가?
- Context: 사용자가 검색한 키워드의 목록 (history of queries)
- 키워드 중 중의적인 의미가 있으면 이전 쿼리를 조회해서 의도를 알아내는 것이 목적
- 사용자는 메뉴로부터 선택할 수 있다.
- 검색 요청을 주제로 분류한다.
- 검색 요청의 context를 사용할 수 있다.
- User Context → 사용자의 북마크 등
그래프에서 근사 측정(measuring proximity)을 응용하기
- 예시: Relevance, Closeness, Similarity
- 좋은 근사 측정 방법
- 최단 거리는 1개의 out-link만 있는 경우에는 그닥 좋지 않고, 네트워크 흐름도 긴 경로가 있는 경우 감점시키는 것이 없어서 그닥 좋지 않음
- 다수의 연결
- 연결의 품질
- Direct & Indirect connections
- Length, Degree, Weight, ...
- SimRank
- k-partite 그래프에서 고정된 노드로부터 random walks
- 설정 사항: k-partite 그래프는 노드의 종류가 k개이다.
- Authors, Conferences, Tags
- 노드 u로부터 Topic Specific PageRank → teleport set S = {u}
- 노드 u에서 유사도를 측정해서 score를 낸다.
- 문제점
- 각 노드 u에 대해 한 번씩 수행되어야 한다.
- 하위 웹 규모의 응용프로그램에 적당하다.
PageRank 요약
- “Normal” PageRank
- 균일하게 랜덤으로 어떤 노드에 텔레포트 한다.
- 모든 노드들은 자신에게 도착하는 서퍼의 확률을 동일하게 갖는다.
- S = [0.1, 0.1, 0.1, 0.1, 0.1, 0.1]
- Topic-Specific PageRank (a.k.a. Personalized PageRank)
- 주제 특화된 집합의 페이지에만 텔레포트 한다.
- 노드들은 자신에게 도착하는 서퍼의 확률을 달리 갖는다.
- S = [0.1, 0, 0, 0.2, 0, 0, 0.5, 0, 0, 0.2]
- Random Walk with Restarts
- 같은 노드로 항상 텔레포트하는 Topic-Specific PageRank
- 그러나, 항상 같은 노드에서 출발하면 비효율적이다.
- S = [0,0,0,0,1,0,0,0,0]
TrustRank: Web spam과의 싸움
- Spamming
- 검색 엔진 결과에서 페이지의 실제 값과는 어울리지 않게 웹의 페이지 위치를 상승시키기 위한 어떤 교묘한 동작(deliberate action)
- in-links 개수 < out-links 개수
- Spam: spamming의 결과가 되는 웹 페이지
- SEO = Search Engine Optimization
- 전체 웹 페이지의 대략 10-15% 는 스팸이다. 많을수록 웹 랭킹이 흐트러진다.
- Web Search
- 초기 검색 엔진은 웹을 크롤링해놓고 포함된 단어들에 따라 페이지를 인덱싱하였다. 따라서 검색 요청에 따라 해당 키워드를 포함하는 페이지들로 응답하였다.
- 초기 페이지 랭킹은 중요도에 따라 다른 페이지들이 검색 요청과 매칭되는지 확인하였다.
- 첫번째 검색 엔진은 (1) 요청 단어의 수 (2) 단어의 위치 e.g. titile, header 만으로 고려되어졌다.
- First Spammers
- 사람들이 웹에서 무언가를 찾기 위해 검색 엔진을 사용하면서, 상업적인 관심이 사람들을 자신의 사이트로 데려오기 위해 검색 엔진을 악용하는 것에 있었다.
- 특정 사이트의 랭킹을 올리려는 사람들에 의해
- 예제: 영화에 대한 것으로 구실을 삼으나, 셔츠 판매원인 경우
- 웹 페이지에 대한 관련성/중요도를 높게 이루는 기술이 필요
- 예제: 영화에 대해서 페이지가 어떻게 나타나는가? (스팸 만드는 과정)
- 페이지에 단어 “movie”를 1000번 추가한 후, 텍스트 색상을 배경색으로 맞추어서 검색 시 사이트가 보이게 하는 방법
- 대상 검색 엔진에 “move”라는 검색을 수행하면, 처음에 목록에 뜨는 페이지들 중 내용을 복사해서 자신의 페이지에 붙인 뒤 보이지 않는 옵션을 주는 방법
- 이와 유사한 방법을 term spam 이라고 한다.
- 예제: 영화에 대해서 페이지가 어떻게 나타나는가? (스팸 만드는 과정)
- term spam 에 대한 구글의 해결책
- 사이트 주인이 기재한 내용보다 외부로부터의 언급 내용을 참조
- 링크를 표현하는 밑줄 그은 텍스트(anchor text)에서의 단어를 사용한다. 또는 링크 주변의 텍스트를 이용한다.
- 웹 페이지의 중요도를 측정하기 위한 도구로서의 PageRank
- 중요도는 in-coming link만 고려한다.
- 해결책이 잘 동작하는 이유 → 예시: 가짜 셔츠 판매자
- 다른 것들이 영화에 대해 이야기하지 않기 때문에, 셔츠 판매자가 페이지에서 영화에 대해 이야기 하는 것이 도움이 되지 않는다.
- 셔츠 판매자의 페이지는 매우 중요하지 않아서, 셔츠나 영화에 대해 높게 등급이 매겨지지 않을 것이다.
- 셔츠 판매자는 1000개의 페이지를 만들고, 각 link는 auchor text에서 “movie” 단어를 가지고 페이지를 참조한다. 이러한 페이지들은 내부에 들어오는 link는 없어서 작은 PageRank를 얻는다. 따라서 셔츠 판매자는 정말로 중요한 영화 페이지 (IMDB같이)를 이길 수 없다.
- 해결책이 잘 동작하지 않는 이유 → Spam Farming
- 구글이 검색 엔진으로 승승장구하면서, spammer들은 구글을 속이는 방법을 연구하기 시작했다
- Spam farms: 특정 사이트의 PageRank를 올리는 툴
- Link spam: 링크를 올리는 스팸, 특정 페이지의 PageRank를 올리는 링크 구조를 만드는 방법
- spammer의 관점에서는 3가지의 웹 페이지가 존재한다.
- Inaccessible pages
- Owned pages → spammer에 의해 완전히 통제되는 자기 페이지
- Accessible pages → blog comments pages (기사글 댓글에 링크걸기)
- spammer의 목표: 대상 페이지 t의 PageRank를 최대화하는 것
- spammer가 사용한 기술
- 대상 페이지 t에 가능한 accessible pages로부터 많은 link를 얻는다.
- PageRank 상승 효과를 얻기 위해 link farm을 구성한다.
- 𝜷y/M 은 link farm의 빨간 점들에 t가 보낸 link score
- (1-𝜷)/N 은 random teleport 로 인한 (1-𝜷) 를 전체 페이지 개수인 N으로 나눈 값
-
획득한 PageRank에 대한 상승 효과(Multiplier effect) → M(=link farm의 페이지 개수)이 클수록, 대상 페이지 t의 Rank는 원하는 만큼 더 커질 수 있다.
TrustRank
- Combating term spam
- 통계적 방법을 이용한 텍스트 분석
- 이메일 스팸 필터링과 유사한 방법 사용
- 거의 똑같고, 중복되는 페이지들을 탐지하는데 유용한 방법 사용
- Combating link spam
- spam farm처럼 보이는 구조를 탐지해서 블랙 리스트에 담는 방법
- 또 다른 전쟁을 이끈다. → spam farm들과 숨바꼭질..
- TrustRank = 신뢰되는 페이지들의 teleport set을 가진 topic-specific PageRank
- .edu domains, similar domains for non-US schools
- 주 원리: Approximate isolation
- 나쁜 페이지를 참조하는 좋은 페이지가 없다는 가정
- 웹으로부터 seed pages의 집합을 샘플링
- seed set에서 좋은 페이지들과 스팸 페이지들을 식별하는 사람(oracle)이 있음
- 단, 비싼 업무라서 가능한 작은 seed set을 만들어야만 한다.
- Trust Propagation
- 식별되는 seed pages의 부분집합을 좋고 신뢰되는 페이지라고 부름
- teleport set = trusted pages 인 topic-sensitive PageRank를 수행
- 링크를 통해서 trust를 전파 → 신뢰되는 페이지들끼리 전파하는 것
- 각 페이지는 trust value과 0또는 1의 값을 갖는다. 여기서 0이면 스팸
- 해결책
- 임계값을 사용해서, 신뢰도 임계값 이하의 스팸이 되는 모든 페이지들을 표시
- 알고리즘
- 각각의 신뢰되는 페이지의 신뢰도를 1로 설정
- 페이지 p의 신뢰도를 t_p로 가정할 때, 페이지 p는 out-links의 집합 o_p를 가진다면, o_p에 속하는 각각의 q는 페이지 p의 out-links 중 하나이다.
- 페이지 p의 out link 로 나가는 신뢰도 =
- 페이지 p의 out link 로 나가는 신뢰도 =
- 신뢰도는 추가된다.
- 페이지 p의 신뢰도는 p로 들어오는 링크를 갖는 페이지들의 trust의 합이다.
- Topic-Specific PageRank 에서의 유사도
- scaling factor 안에, teleport set으로 신뢰되는 페이지들을 갖는 PageRank 는 TrustRank 이다.
- 장점
- 신뢰도 감쇠(Trust attenuation): 신뢰되는 페이지들에 의해 모여진 신뢰도는 그래프에서 거리를 감소시킨다.
- 신뢰도 분할(Trust splitting): 페이지의 out-links 수가 많을수록 페이지 작성자가 각 out-link 별로 정밀도를 떨어뜨린다. 즉, 신뢰도가 out-link를 통해 분할된다.
- Seed Set 선택
- 두 가지 고려 사항이 충돌한다.
- 사람이 각 seed page를 관찰해야 하므로, seed set은 가능한 작아야만 한다.
- 모든 good page는 적절한 trust rank를 얻도록 보장해야 하므로, 모든 good page가 seed set으로부터 최단 경로에 의해 도달해야 한다.
- 즉, 그래프 크기에 비해 seed set이 너무 작으면 trust를 많이 받지 못한다.
- 접근법
- PageRank: 상위 k개의 페이지를 선택해서, seed set에 넣는다. 이론적으로 bad page의 rank는 실제로 높은 값을 가질 수 없다.
- Use trusted domains: 신뢰되는 도메인들을 추려서 seed set에 추가하여 크기를 확장한다. 예를 들어, .edu, .mil, .gov 같은 도메인들을 통제할 수 있는 소속력(membership)을 갖는다.
- k 개의 페이지들의 seed set을 선택하는 방법
- Spam Mass
- TrustRank 모델에서, 좋은 페이지를 가지고 시작하고 신뢰도를 전파한다.
- 상호 보완적인 관점에서, 높은 PageRank를 갖는 사이트 중 스팸에서 얻은 스코어가 많은 사이트도 있다.
- 페이지의 PageRank는 얼마만큼 스팸 페이지로부터 받는가?
- 실제로, 스팸 페이지들을 알지 못하므로 측정할 필요가 있다.
- 측정방법
- 스팸 페이지에서 얻은 PageRank = 전체 PageRank - 신뢰되는 페이지에서 얻은 PageRank
- Spam mass = 스팸 페이지에서 얻은 PageRank / 전체 PageRank
HITS: Hubs and Authorities
- HITS (Hypertext-Induced Topic Selection)
- PageRank와 유사한 문서나 페이지의 중요도를 측정하기 위한 항목
- PageRank 와 동일한 시점에 제안되었다.
- 목표
- 좋은 newspapers를 찾는 것
- 단순히 찾기 보다는 전문가들을 먼저 찾는다.
- 여기서 전문가란 조정된 방법 내에서 좋은 newspapers로 링크를 하는 사람 또는 페이지를 의미한다.
- 기본적인 아이디어가 Links as votes 이다. 페이지는 더 많은 링크를 가질수록 중요하다.
- In-coming links
- Out-going links
- Hubs and Authorities: 각 페이지는 2가지 score를 가진다.
- Quality as an expert (hubs): authorities가 참조했던 link의 합
- Quality as a content (authority): expert로부터 받은 vote의 합
- 거듭된 개선의 원칙
- 아래 예시에서 파란 점은 hub이고 초록색은 authority이다.
- authority 값이 클수록 hub들이 좋은 것이며 역도 성립한다.
- 흥미로운 페이지들은 두 가지 클래스로 분류된다.
- Authorities: 유용한 정보를 포함하는 페이지들
- Newspaper home pages
- Course home pages
- Home pages of auto manufacturers
- Hubs: authorities에 링크를 하는 페이지들
- List of newspapers
- Course bulletin
- List of US auto manufacturers
- hub 점수가 높고 authority 점수가 낮으면 hub로 분류된다. 좋은 hub는 좋은 authority를 참조한다.
- 예제
- 위에서 작은 점들이 hub이고 큰 점들이 authority이다. 실제로는 다 페이지이지만 클래스를 나누기 위해 점의 크기를 달리 표현하였다.
- 각 페이지는 1점의 hub로 시작을 한다. authority는 링크하는 hub들의 점수를 모은 것이다.
-
Authority의 옆에 링크하는 hub(시작은 1점짜리)의 점수들을 합한 것을 볼 수 있다.
-
그리고 다시 hubs는 연결되는 authority 들의 점수들을 합해서 저장한다.
- authority는 갱신된 hubs의 점수들을 이용해서 자신의 점수를 갱신한다. (재귀 정의)
- 실제로 각 페이지는 hub/authority의 score를 모두 갖는다.
- 상호적, 재귀적 정의
- 좋은 hub는 많은 좋은 authorities를 링크한다.
- 좋은 authority는 많은 좋은 hubs로부터 링크된다.
- 각 노드마다 두 가지 score를 이용하는 모델
- Hub score, Authority score
- 벡터 h와 a로 나타낼 수 있다.
- 각 페이지 i는 두 가지 score를 가진다.
행렬 A는 노드 간 인접한지의 유무만 저장한다. 인접하면 1, 아니면 0
h=A*a, a=At*h
h와 a 의 마지막 값은 정규화를 거친 결과이다.
PageRank 와 HITS
- 두 방식은 같은 문제를 다른 방식으로 해결한다.
- 문제: 페이지 u에서 페이지 v로 가는 in-link의 값이 무엇인가?
- PageRank 모델에서는 link의 값이 u로 가는 link들에만 의존한다.
- HITS 모델에서는 u에서 나가는 link들의 값에 의존한다.
'Software Application > Graph Analysis' 카테고리의 다른 글
| 네트워크의 커뮤니티 구조 (Community Structure in Networks) (0) | 2019.12.22 |
|---|---|
| 웹 그래프 (Web Graph) (0) | 2019.12.22 |
