Detecting community structure in networks

Topics/Social Web 2012. 8. 26. 17:20 posted by Minery


M.E.J. Newman은 설명이 필요없을 정도로 복잡계 네트워크 분야에서 유명인이다. 다양한 알고리즘을 제시했고 이미 그의 알고리즘들은 여기저기서 쓰이고 있다. 오늘 올리는 발표자료는 누만의 커뮤니티 발견에 대한 관련 연구 소개 논문이다. 물론 당신께서 쓰셨으니 당연히 누만의 알고리즘에 대한 소개가 좀 더 상세히 되었있다. ㅎ

본 발표자료는 논문의 모든 내용을 요약한 것이 아니고 관심이 가는 것 위주로 정리한 것이다. 고로 논문의 보다 상세한 내용이 필요하신 분은 아래 링크를 따라가서 읽어보시기를 추천한다.

원문 링크: http://www.springerlink.com/content/5gtdacx17bqv6cdc/


시맨틱 웹 기술로 사용자들의 SNS 활동을 완벽하게 기술할 수 있게 된다면 어떻게 될까? 시맨틱 웹을 한번이라도 공부해본 사람이라면 한번쯤 이런 고민을 해봤으리라. 오늘 소개해드리는 논문의 저자들 역시 마찬가지 였던 것으로 생각된다. 이 논문의 저자들은 DERI 연구소에 소속된 사람들인데 DERI 연구소는 시맨틱 웹과 소셜 웹에 관련되서 재밋는 아이디어들을 곧잘 논문으로 써내곤 한다. 시간이 난다면 한번씩 홈페이지에 들려서 논문을 읽어보는 것도 제법 도움이 되며 물론 재미도 있다.

Knowledge Discovery in distributed Social Web sharing activities

이 논문 이전에도 시맨틱 웹 기술을 이용한 소셜 웹에 대한 연구는 다양하게 있어왔다. 가장 대표적으로는 SKOS나 SIOC 같은 것이 있다. SKOS, SIOC 역시 마찬가지로 사용자의 활동을 시맨틱 웹 기술을 이용하여 작성하는 온톨로지 기반 어휘들인데 이런 것들이 있는데도 불구하고 왜 굳이 소셜 웹의 활동을 시맨틱 웹으로 표현하는 연구를 또해야만 했을까? 나는 이 논문을 읽기전에 이렇게 생각했다.

이 논문의 저자들은 다음과 같이 논문의 동기를 밝히고 있다.

1) 새로 찾게된 사람이나 지식을 PIM(Personal Information Model)로 작성해야한다.
2) 여러 SNS 서비스들의 글(Post)들이 의미적으로 연결되어야한다.
3) 소셜 기반의 추천이 가능해야한다.

이 세 개의 동기(문제점)을 해결하기 위하여 저자들은 DLPO라는 새로운 온톨로지 어휘를 제안하였다. DLPO는 완전히 새로운 온톨로지 어휘가 아니라 기존의 SIOC같은 어휘를 최대한 활용하고 LOD의 다양한 어휘까지 모두 활용하면서 기존에 제공하지 못하고 있었던 어휘를 추가하는 형태이다.


위 그림에서 보듯 여러 어휘체계들이 있지만 온라인 포스트부터 시작해서 다른 부분까지 완벽하게 제공하는 것은 자신들 뿐이라고 주장하고 있다. (평가항목이 이 것이 전부는 아닐터이지만.. 논문이란 것이 자신의 시스템이 훌륭하다고 주장하는 것이 일반적임을 감안해야하긴 한다.) 뭐 어쨌든 기존 방법들에 비해 어휘체계가 더 풍부한건 맞는 것같다. 혹여나 싶어서 소셜 웹의 사용자 활동을 기술하기 위한 여러 시맨틱 웹 기술들에 관한 논문들을 본인이 직접 찾아봤는데 그래도 그 중에 이 논문에서 제안한 것 보다 훌륭한건 아직 없어보였다.

사실, 연구를 하다보면 어?? 저 논문.. 아이디어는 신선하지만 실제로 구현이 어렵진 않았을 것 같은데?! 하는 것들이 제법 많다. 그러나 그런걸 함부로 무시하면 안된다. 그런 생각을 했다는 것과 못했다는 것은 굉장히 큰 차이기 때문이다. 피타고라스의 정리에서 직각삼각형의 대각선 거리 재는 공식을 활용해서 다차원 공간의 벡터 노름 구하는 공식을 구한 사람 또한 위대한 수학자로 인정받고 있지 않는가?

이 논문 역시 마찬가지로 내가 평가할 땐 소셜 웹의 사용자 활동을 완벽하게 시맨틱 웹 기술로 표현하고 그걸 여러 소셜 네트워크 서비스의 데이터에 적용가능하게 하고 또한, 그걸로 소셜 추천이 가능하도록 한 아이디어 자체가 나이스포인트라고 본다. 아직까진 그런 시도를 한 사람이 없으니까. 오히려 왜 그런 시도가 여태 없었지? 하는 의문이 들 정도다.

나처럼 설렁설렁 공부하는 사람들은 아마 .. 나와 마찬가지로 SIOC로 다 되잖아? 라고 이미 생각한 후 넘겨버렸을지도 모른다.


위 그림은 논문에서 제안한 DLPO의 구성도이다. 제안한 온톨로지는 크게 네 개의 부분으로 구성되어있는데 각각 Multimedia, presence, message, web document이다. 그리고 이 네개의 부분들은 SIOC, RDF 등 다른 어휘와 연결되어 구성된다.

구현과 결론 부에서는 아직 완성된 시스템을 보여주고 있지는 않은데 나는 한가지 의심이 드는 것이 과연 다양한 SNS의 데이터들을 시맨틱 웹으로 연결시켰을 때 어떤 시너지 효과가 있을 것인가 하는 것이다.

나는 소셜 네트워크 서비스의 구조에 대해 가지고 있는 아이디어가 하나 있는데 그 아이디어를 논문으로 쓸 때 DLPO를 가져다 쓸 수 있을지 그 때가서 생각해보려고 한다.

원문 링크: http://ceur-ws.org/Vol-838/paper_17.pdf

우리는 종종 어떤 물건을 사거나 질문을 할 때 주변 사람들에게 묻곤한다. 평소 친분이 깊은 사람에게 물어봤다면 별로 안 친한 사람에게 물어보는 것보다 마음속으로 더 깊은 신뢰감을 얻는 게 너무나 당연한 일이다. 사람과 사람들이 서로 대화하고 의견을 주고 받는다는 측면에서 소셜 네트워크는 우리의 실생활과 닮은 점이 많은 편이다. 그래서 온라인 소셜 네트워크에서 역시 실생활처럼 믿을 만한 사람을 찾는 일은 얼마나 신뢰있는 인터넷 생활을 하느냐로 직결된다고 볼 수 있다. 오늘 소개해드리는 논문은 소셜 네트워크에서 신뢰(Trust) 혹은 불신뢰(Distrust)를 측정(예측)하기 위한 논문이다.

트러스트란 '어느 사용자가 얼마나 다른 사용자에게 신뢰받고 있는가'를 측정하는 지표로 사용된다. (Manuela et al., 2012) 그리고 다른 정의에서는 '에이전트가 다른 에이전트에게 적당한 방식으로 행동하기 위한 신뢰의 정량화'라고 한다. (Zheng, 2011) 다시 말해 월드와이드웹에서의 트러스트는 사람이나 콘텐츠가 얼마나 신뢰받을만한지를 보이는 지표라고 할 수 있다.

소개해드리는 논문에서는 트러스트를 다음과 같이 설명하고 있다.

Trust information can help a user make decisions, sort and filter information, receive recommendations, and develop a context within a community with respect to whom to trust and why.

트러스트 정보는 커뮤니티에서 누가 왜 신뢰받고 있는지를 통해 사용자의 결정을 도울 수 있고 정보를 필터, 정렬할 수 있고 추천을 받을 수 있고 콘텍스트를 개발할 수 있다.

소개해드리는 논문은 소셜 네트워크에서 신뢰와 불신뢰를 측정하기 위한 알고리즘을 제안한다. 위에서 봤던 것과 같이 신뢰는 깔끔하게 정의되는데 불신뢰는 또 무엇인가? 하는 생각이 들 것이다. 필자 역시 마찬가지 였는데 이 논문에서 불신뢰를 하는 이유는 다음 그림으로 설명된다.

위 그림에서 보면 노드 A, B, C, D가 있는데 각 연결 선마다 있는 >.9 와 같은 표시는 신뢰(Trust)를 나타낸다. A는 B와 B를 상당히 높은 수준에서 신뢰하는 것을 볼 수 있는데 B와 C의 경우 D를 각각 0.9, 0.1만큼 신뢰한다. 이 때 A는 D를 얼마나 신뢰한다고 판단할 수 있을까? 측정값을 신뢰 하나만 사용하는 경우 위 그림과 같이 A와 D사이의 애매한 면이 드러나게된다.

위와 같은 문제를 해결 하기 위하여 논문에서는 신뢰를 측정하기 위하여 경로 확률(Path probability)를, 비신뢰를 측정하기 위하여 Spring-embedding 알고리즘을 사용한다. 그리고 이 두 계산 결과를 합하여 상대를 얼마나 신뢰할 수 있는지 판단한다.

이 논문에서 제안한 방법의 실험은 스탠포드 대학교의 Large dataset collection에서 세 개를 골라서 실험대상으로 삼아 실험을 하였다. 여기서 재밋는 것은 스탠포드 대학교의 데이터셑이다. 주소는 http://snap.stanford.edu/data 이다. 이 사이트에 들어가면 여러가지 형태의 네트워크 실험용 데이터를 얻을 수 있으며 다른 논문들에서도 이 데이터를 사용하여 여러가지 실험을 하고 있으므로 만약 여러분들이 그래프/네트워크 관련 연구를 하고 계시다면 증명용으로 상당히 쓸만하게 사용하실 수 있을 것이다.

마지막으로 참고삼아 말씀드리면 본 논문의 공저자 중에 한명인 Jennifer Golbeck은 Trust에 관한 다양한 연구를 하고 있고 많은 논문을 출판한 사람이므로 그녀의 이름으로 검색해서 논문을 찾아 읽으면 Trust에 관한 다양한 지식을 쌓을 수 있을 것이다.


원문 링크: http://www.cs.umd.edu/~golbeck/papers/sign.pdf