$\require{mediawiki-texvc}$

연합인증

연합인증 가입 기관의 연구자들은 소속기관의 인증정보(ID와 암호)를 이용해 다른 대학, 연구기관, 서비스 공급자의 다양한 온라인 자원과 연구 데이터를 이용할 수 있습니다.

이는 여행자가 자국에서 발행 받은 여권으로 세계 각국을 자유롭게 여행할 수 있는 것과 같습니다.

연합인증으로 이용이 가능한 서비스는 NTIS, DataON, Edison, Kafe, Webinar 등이 있습니다.

한번의 인증절차만으로 연합인증 가입 서비스에 추가 로그인 없이 이용이 가능합니다.

다만, 연합인증을 위해서는 최초 1회만 인증 절차가 필요합니다. (회원이 아닐 경우 회원 가입이 필요합니다.)

연합인증 절차는 다음과 같습니다.

최초이용시에는
ScienceON에 로그인 → 연합인증 서비스 접속 → 로그인 (본인 확인 또는 회원가입) → 서비스 이용

그 이후에는
ScienceON 로그인 → 연합인증 서비스 접속 → 서비스 이용

연합인증을 활용하시면 KISTI가 제공하는 다양한 서비스를 편리하게 이용하실 수 있습니다.

랜덤 워크를 활용한 그래프 랭킹 기반 추천 시스템 원문보기

정보과학회지 = Communications of the Korean Institute of Information Scientists and Engineers, v.34 no.6, 2016년, pp.30 - 35  

진우정 (서울대학교) ,  정진홍 (서울대학교) ,  강유 (서울대학교)

초록이 없습니다.

AI 본문요약
AI-Helper 아이콘 AI-Helper

* AI 자동 식별 결과로 적합하지 않은 문장이 있을 수 있으니, 이용에 유의하시기 바랍니다.

문제 정의

  • 그래프랭킹은 여러 방법에 의해서 구해질 수 있는데 본 논문에서는 랜덤 워크를 활용한 랭킹 기반 추천 시스템에 대하여 논하고자 한다.
  • 그러면 그래프 상에서 중요도를 계산하는데 랜덤 워크가 가진 장점은 무엇인지 피자 배달원 문제(Pizza delivery guy problem)를 통해 알아보자. 그림 2는 누가누구에게 전화를 걸었는지를 나타내는 콜 그래프이며, 이 그래프에서 노드 A로부터 상대적으로 중요한 노드를 찾고 싶다고 하자.
  • 결과를 정리하여 소개한다. 또한 랜덤 워크에서 아직 해결되지 않은 연구과제들을 제시하며 향후 랜덤워크를 활용한 그래프 랭킹 기반 추천 시스템의 연구방향에 대한 논의를 진행한다.
  • 본 논문에서는 그래프 랭킹 기반 추천을 가속화하기 위한 랜덤 워크 기법에 관련된 연구들을 정리, 안내하고, 국제적으로 진행된 최신 연구들의 연구방향과 결과를 정리하여 소개한다. 또한 랜덤 워크에서 아직 해결되지 않은 연구과제들을 제시하며 향후 랜덤워크를 활용한 그래프 랭킹 기반 추천 시스템의 연구방향에 대한 논의를 진행한다.
  • 추천 기법에 대한 관심이 커지고 있다. 본 논문에서는 랜덤 워크를 활용한 그래프 랭킹 기반 추천시스템에 대한 개략적인 안내와 더불어 RWR을 가속화하기 위한 알고리즘들을 안내하고 최근 5년간 주목받고 있는 두 개의 연구 흐름에 대해 안내를 하였다. 최근에는 RWR 계산의 가속화뿐만 아니라 간선에 부호가 있는 사인 그래프에서의 RWR 적용 연구와, 학습을 통한 효과적인 랭킹 기법을 통해 추천시스템의 정교화와 고도화를 위한 연구들이 진행되어 왔다.
  • 4장에서는 랜덤 워크를 활용하는 최근의 연구 동향을 소개하고 안내한다. 이를 통해 랜덤 워크를 활용한 그래프 랭킹 기반 추천 시스템의 발전 방향을 이해하고 추천 시스템에 대한 학문적 관심을 제고하고자 한다. 마지막으로 5장에서 결론을 맺는다.
  • 이와 같이 랜덤 워크를 활용한 그래프 랭킹 기법의 분류에 대해 알아보았다. PageRank는 그래프에서 글로벌 랭킹을 구하는 반면, RWRe 질의 노드에 개인화된 중요도를 계산하기 때문에 친구나 문서를 추천하는데 적합한 랭킹 기법이다.

가설 설정

  • SRW는 기계 학습 기법인 로지스틱 회귀와 RWR을 결합한 방법이다. 먼저 몇 개의 질의 노드에 관해 친구가 될 노드와 그렇지 않은 노드들이 주어져 있고 그래프의 각 연결마다 특징(feature)이 주어져 있다고 가정하자. 특징은 각 노드들의 연결이 얼마나 오래되었는지 또는 각 노드의 차수 등이 될 수 있다.
  • ). 먼저 최단 거리로 중요도를 매긴다고 가정해보자. 그러 면 노드 B와 C는 A로부터 같은 거리에 있으므로 중요도가 같다.
본문요약 정보가 도움이 되었나요?

참고문헌 (16)

  1. L. Backstrom and J. Leskovec, "Supervised random walks: predicting and recommending links in social networks", In Proceedings of the fourth ACM international conference on Web search and data mining, pp. 635-644, 2011. 

  2. D. Liben-Nowell and J. Kleinberg, "The link prediction problem for social networks", Journal of the American society for information science and technology, Vol. 58, No. 7, pp. 1019-1031 , 2007. 

    상세보기 crossref

  3. L. Page and et al., "The PageRank citation ranking: bringing order to the web", 1999. 

  4. S. Brin and L. Page, "Reprint of: The anatomy of a large-scale hypertextual web search engine", Computer networks, Vol. 56, No. 18, pp. 3825-3833, 2012. 

    상세보기 crossref

  5. T. Haveliwala H, "Topic-sensitive pagerank", In Proceedings of the 11th international conference on World Wide Web, pp. 517-526, 2002. 

  6. J. Sun and et al., "Neighborhood formation and anomaly detection in bipartite graphs", In Data Mining, Fifth IEEE International Conference on, p. 8, 2005. 

  7. D. Gleich and M. Polito, "Approximating personalized pagerank with minimal use of web graph data", Internet Mathematics, Vol. 3, No. 3, pp. 257-294, 2006. 

    상세보기 crossref

  8. H. Tong, C. Faloutsos and J. Pan, "Fast random walk with restart and its applications", 2006. 

  9. Y. Fujiwara and et al., "Efficient personalized pagerank with accuracy assurance", In Proceedings of the 18th ACM SIGKDD international conference on Knowledge discovely and data mining, pp. 15-23, 2012. 

  10. Y. Fujiwara and et al., "Fast and exact top-k search for random walk with restart", Proceedings of the VLDB Endowment, Vol. 5, No. 5, pp. 442-453, 2012. 

    상세보기 crossref

  11. K. Shin and et al., "BEAR: Block Elimination Approach for Random Walk with Restart on Large Graphs", In Proceedings of the 20 15 ACM SIGMOD International Conference on Management of Data, pp. 1571-1585, 2015. 

  12. J. Jung and et al., "Random Wa1k with Restart on Large Graphs Using Block Elimination", ACM Transactions on Database Systems (TODS), Vol. 41 , No. 2, p. 12, 2016. 

  13. U. Kang and C. Faloutsos, "Beyond 'caveman communities' : Hubs and spokes for graph compression and mining" In Data Mining (ICDM), IEEE 11th International Conference on. IEEE, pp. 300-309, 2011. 

  14. Y. Lim, U. Kang and C. Faloutsos, "Slashburn: Graph compression and mining beyond caveman communities", Knowledge and Data Engineering, IEEE Transactions, Vol. 26, No. 12, pp. 3077-3089, 2014. 

    상세보기 crossref

  15. M. Shahriari and M. Jalili, "Ranking nodes in signed social networks", Social Network Analysis and Mining, Vol. 4, No. 1, pp. 1-12, 2014 

  16. Z. Wu, C. Aggarwal and J. Sun, "The Troll-Trust Model for Ranking in Signed Networks", In Proceedings of the Ninth ACM International Conference on Web Search and Data Mining, pp. 447-456, 2016. 

저자의 다른 논문 :

관련 콘텐츠

이 논문과 함께 이용한 콘텐츠

저작권 관리 안내
섹션별 컨텐츠 바로가기

AI-Helper ※ AI-Helper는 오픈소스 모델을 사용합니다.

AI-Helper 아이콘
AI-Helper
안녕하세요, AI-Helper입니다. 좌측 "선택된 텍스트"에서 텍스트를 선택하여 요약, 번역, 용어설명을 실행하세요.
※ AI-Helper는 부적절한 답변을 할 수 있습니다.

선택된 텍스트

맨위로