페이지랭킹 by google 20042521 김진태 국민대학교.

Slides:



Advertisements
Similar presentations
글로벌 통상환경 변화와 한국의 통상협상방향 김학도 산업통상자원부 통상교섭실장 글로벌 통상환경 변화와 한국의 통상협상방향 (목) 통상교섭실장 김학도 제 128 회 세종로국정포럼.
Advertisements

1 산별노조 ! 갈까 말까 ? 2007 년 9 월 3 일 LG 화학노조 간부교육. 2 민주노조 건설 후 우리 삶의 변화  살 만 하십니까 ? 집도 있고, 아이들 공부도 시키고, 차도 중형급 이상 몰고 다니고 …. 회사도 잘 다니고 … 그런데도 어쩐지 … 좀.. 불안하시죠.
숭실대학교 캠퍼스 학과 중심 SNS. 소통을 위한 학과중심의 SNS 서비 스 Trend.
데이터마이닝 & 정보검색 연구실 신 현 일.  검색 시스템에 필요한 요소  인터넷 검색의 유형 / 태그란 ?  Blog 검색 시스템 설계  Target : Blog ? / 국내 Blog 사이트 분류  Collection : 어디서 무엇을 추출할 것인가 ? 
빅뱅이론과 발달사 박형민. 빅뱅이론의 발달  우주관  표준빅뱅이론  인플레이션 우주론  기타 우주론  맺음말.
1 Display Marketing BU 소개자료. 2 Display Marketing BU 소개
C 언어 컴퓨터학과 C 언어 ( STS ) (Chap5. Selection-Making Decisions ) C 언어.
소규모 합병 공고 주식회사 포스코는 주식회사 포스하이메탈과 2015년 12월23일 합병계약을
2. 세계 여러 지역의 자연과 문화 2) 육지가 넓고 인구가 많은 북반구.
연관규칙기법과 분류모형을 결합한 상품 추천 시스템:
전자상거래 원론: 제18장 전자상거래 수행전략 및 구현.
Predicting User Interests from Contextual Information
어서와 Java는 처음이지! 제3장선택과 반복.
중앙아시아와 아랍의 관문국가 터키 박솔지 이수지.
1. 각운동량 수지 방정식 2. 각운동량 수송 메카니즘 3. 각운동량과 제트 기류의 관계 이해
교육매체 컴퓨터 멀티미디어 인터넷활용교육 물리교육전공 홍승찬.
사회의학연구소 의사 타무라 아키히코(田村昭彦)
구매카드대출 인터넷매뉴얼 (판매기업용) 1.
소규모 합병 공고 주식회사 포스코는 포스코그린가스텍 주식회사와 2016년 2월26일 합병계약을
유비쿼터스 네트워크 연구실 (Ubiquitous Network Lab) Since 1994
제2절 법인세의 계산구조와 세무조정 1. 각 사업연도소득에 대한 법인세 계산구조 회계와 사회 결산서상 당기순이익
7장: 원격 통신 인터넷과 온라인 자원의 사용.
인터넷의 작동 원리 PARSONS/OJA 인터넷.
사업계획서.
포항공과대학교 COMPUTER VISION LAB. 석박통합과정 여동훈
특허 출원에 관하여 이지연.
독도 바로알기 2. 사료와 지도로 보는 독도.
PDA를 이용한 Remote Service Control
국제 경제 기구론 국제경제기구의 창설배경, 국제경제에서의 역할 및 한국과의 관계를 중심으로 알아본다.
1.민족의 발전과 민족 문화 창달(4)주체적 문화교류의 자세
학생 매뉴얼 5) 학생회원 매뉴얼 Communication with world wide web~ DAON 학생 로그인
제주닷컴 매뉴얼 (실시간 예약시스템) 2013년 10월.
사업 투자 설명회 AnyTime, AnyWhere 주식회사 비욘드네트웍스.
응급의학과 설명회 국내 응급의학의 역사, 현황 및 전망
2009, 46th KLA General Conference
전자세금계산서 이용 매뉴얼 1.
[INA240] Data Structures and Practice
Design Thinking 디자인씽킹은 불명확 한 문제를 조사하고 정보를 검색하고 지식 을 분석하고 설계 및 계획 분야에서 솔루션을 선정하는 방법 및 과정을 가리킨다.“
‘그린나래호텔’은 대한민국 공군에서 해운대 해수욕장변에 건축한 군의 복지향상을 위해 지은 군휴양소 건물입니다.
똑소리 나는 계약 담당자 되기.
기존 REC거래시스템 회원사의 신재생 통합포털 회원가입 설명서.
<정보 활용 능력> 담당 교수: 박용대
<정보 활용 능력> 담당 교수: 박용대
30605 김준표 게임의 구성요소.
Ⅳ. 컴퓨터와 생활.
CHAPTER 06 청소년의 행동문화 : 폭력(따돌림), 위험행동, 참여.
업체등록신청절차 목차 메인화면 메세지별 유형 2-1. 이미 가입된 공급업체
12장 하이퍼텍스트와 하이퍼미디어 12.1 간략한 역사 12.2 하이퍼텍스트의 특징 12.3 브라우징과 탐색
Smart Solution for a Green World 차세대 에너지, 신소재 분야를 선도하는 삼성SDI에서
팝업 차단된 여러 가지 화면 - (1) 1 구글(Google) 툴바가 설치된 상태
웹과 인터넷 활용 및 실습 (Web & Internet) 과목 개요 문양세 강원대학교 IT대학 컴퓨터과학전공.
예방접종등록시스템 전산교육 질병관리본부 질병예방센터 예방접종관리과.
광고센터 완전정복 매뉴얼 ( ).
Web & Internet [02] HTML5 기본구조와 작성법
비담 MOS 시뮬레이션 사용 절차 1 – 개별 사용 유형
05 ASP.NET 2.0 페이지 및 응용 프로그램 구조 웹 폼(Web Form) 웹 폼 이벤트
웹 검색의 구조.
수 업 계 획 1. 단원지도계획 2. 수업설계서 3. 학습지 4. 형성평가지 5. 참고자료 6. 참고사이트 7. 제작자
Module명 : 물품구매/공사구매/입찰
이런 직업도 있어요^^ 감성인식기술전문가 Q : 어떤 일을 하는 직업인가요?
World Class 300 이력관리시스템 사이트 사용자 매뉴얼 (선정기업) 한국산업기술진흥원.
학부모 매뉴얼 4) 학부모매뉴얼 Communication with world wide web~ DAON 학부모 로그인
매물장 로그인 직원을 미리 생성하시면 직원 ID로 로그인 가능.
8단계 3층을 완성한다 Case 1 Case 2 Case 3 Case 4
5. 환경 문제와 지속 가능한 환경 01.지구적 차원의 환경 문제 02.국경을 넘는 환경 문제 03. 일상생활과 환경 문제
일반대학원 사용자 매뉴얼(학생)
수강신청 설명서 1. 시스템 접속방법 학생포털시스템 Intro화면 학생수강신청 로그인 페이지
About Web 2.0.
우리의 일상이 된 사물인터넷 정보영재 학급 김서현, 이서연 지도 교사: 이유라 지도 교수: 김태영
관리자 페이지에서 관리자 승인 1. 정기권 신규고객 1. 로그인 화면 2. 차량등록여부 확인 3. 개인정보 활용 동의
Presentation transcript:

페이지랭킹 by google 20042521 김진태 국민대학교

PageRank gadget http://www.sitepagerank.net/

Motivation 웹 페이지의 상대적 중요성을 어떻게 추산할 것인가? World Wide Web Hypertext 기존 score알고리즘의 문제 임의의 조작 가능

Link Structure of the Web Forwardlink(out edges) 페이지를 다운받으면 포워드링크를 알 수 있음. Backlink(in edges) 특정 페이지의 모든 백링크를 찾는 것은 불가능 Many Backlinks -> more important Important page’s forwarlink -> more important 어떤 페이지가 높은 랭크의 백링크를 많이 가질수록 그 페이지의 랭크도 올라간다. 예를 들어 페이지랭크가 9인 네이버에서 링크한 페이지는 아까 테스트할때 보았던 저의 보잘것 없는 블로그에서 링크한 페이지보다 더 중요한 페이지라는 것을 의미합니다.

pagerank (단순화시킨 버전) u = 웹페이지 Fu = u페이지가 가리키는 페이지의 집합 Bu = u페이지를 가리키는 페이지의 집합 Nu = |Fu| ; Fu의 개수 c = 노말라이제이션에 사용되는 팩터 (c < 1; 댕글링 링크)

pagerank – rank sink 두 페이지가 서로 가리키고 있으며 다른 페이지로는 연결되어 있지 않은 경우 무한 루프에 빠져 랭크를 계속 계산하며 외부로 전혀 분산하지 못한다. rank sink로부터 초래되는 문제를 해결하기 위해 rank source를 도입 source와 sink (그래프 이론 용어) sink : 밖으로 나가는 링크가 없는 것 source : 안으로 들어오는 링크가 없고 밖으로 나가는 것만 잇는 것 '소스'(source)와 '싱크'(sink)는 그래프 이론에서 나온 용어로, 아웃엣지가 없는, 즉 밖으로 나가는 링크가 없는 것을 싱크라 하고 반대로 인엣지가 없는, 즉 안으로 들어 오는 링크는 없고 밖으로 나가는 것만 있는 것을 소스라 합니다.

pagerank (랭크 소스 도입) E(u) : 랭크의 소스에 해당하는 웹 페이지의 벡터 중 하나 Random Surfer Model ‘랜덤 서퍼’의 행동을 모델링한 것이 페이지랭크 실제 웹서퍼가 rank sink를 만나 루프 내를 맴돌 가능성 -> ZERO 실제 웹서퍼라면 다른 페이지로 점프할 것이다. -> 부가적인 팩터 E

Dangling links problem 외부로 나가는 링크가 없는 페이지를 가리키는 링크 Problem dangling link의 가중치가 어디로 분산되고 있는지가 불분명 danglink link가 너무 많다. 다운로드한 문서가 100인 경우 100개의 문서에서 가리키는 링크의 문서를 모두 다운받기 어렵다. Solution dangling link 제거 모든 페이지 랭크가 계산될 때까지 무시 다른 링크의 노멀라이제이션이 영향을 받을 수는 있지만 크게 변화하지는 않는다. 페이지 랭크의 계산이 끝난 후 dangling link 첨가

Implementation 가중치 수렴 부모ID를 이용해서 링크 구조를 정렬 댕글링 링크 제거 랭크값 초기화 몇 번의 반복 작업만으로도 대부분의 댕글링 링크 제거 가능 랭크값 초기화 초기화 값을 잘 설정하면 수렴과정의 속도를 높일 수 있다. 가중치 수렴 현재 진행 중인 단계의 가중치는 메모리에 저장되고 전단계의 가중치는 디스크를 통해 리니어하게 엑세스한다. 가중치 수렴 후, 댕글링 링크 추가 후 랭킹 재연산

Convergence Properties

페이지랭크 적용 결과 비교 조건 : 1600만 페이지를 수집하여 제목만을 사용하는 검색  우리는 페이지랭크를 활용한 두 가지 검색엔진을 임플리멘테이션했다. 하나는 단순한 타이틀 기반의 검색엔진이고 다른 하나는 풀 텍스트 검색엔진이다. 후자의 이름은 구글이다. 구글은 표준적인 IR 측정치, 근접성(proximity), 앵커 텍스트(웹 페이지를 가리키는 링크의 텍스트), 그리고 페이지랭크 등의 많은 요소를 바탕으로 검색 결과를 랭킹한다.

Common Case 페이지랭크를 이용한 검색은 커먼케이스를 잘 처리하게 된다. 꽃을 검색하였을 때 단순히 꽃의 정보가 담긴 사이트가 아닌 꽃 판매 사이트를 출력하는 경우

Personalized PageRank 랭크싱크처럼 아웃엣지가 없는 싸이클을 보충하기 위한 랭크 소스 웹페이지의 벡터

페이지랭크의 적용 웹 트래픽의 추산 백 링크 예측자로써의 페이지랭크 사용자 네비게이션:페이지랭크 프락시

결론 페이지랭크 ‘중요한’페이지로부터의 백링크는 평균적인 페이지들로부터의 백 링크보다 더 중요하다. 페이지의 컨텐트에 상관없이 오직 웹의 그래프 구조 상의 위치에만 의존하는 모든 웹 페이지의 글로벌 랭킹 ‘중요한’페이지로부터의 백링크는 평균적인 페이지들로부터의 백 링크보다 더 중요하다. 재귀적인 정의를 통해 확실히 구현되어 있다. 페이지랭크 실험을 통해 웹 그래프의 구조가 정보검색 작업에서 매우 유용하다는 것을 증명하였다.