사회관계망에서 매개 중심도 추정을 위한 효율적인 알고리즘
An Efficient Algorithm for Betweenness Centrality Estimation in Social Networks
0
조회
0
다운로드
1
인용
0
참고문헌
키워드
초록
사회관계망 분석에 있어서 매개 중심도(Betweenness Centrality)는 네트워크를 구성하는 노드들의 상대적인 중요도를 파악하기 위한 척도로서 주로 사용되어 왔다. 그러나 매개 중심도를 측정하기 위한 시간 복잡도가 높기 때문에 대규모의 온라인 사회관계망 서비스에서 각노드의 매개 중심도를 산출하는 것은 쉽지 않은 문제이다. 그래서 본 연구팀에서는 과거에 네트워크를 구성하는 각각의 노드들마다 자신의지역 정보를 활용하여 확장 자아 네트워크(Expanded Ego Network)를 정의하고 그 네트워크에서 확장 자아 매개 중심도(Expanded Ego Betweenness)를 산출하여 기존의 매개 중심도를 대체하려는 시도를 하였다. 본 논문에서는 지역정보 기반의 확장 자아 네트워크의 특징을분석하여 확장 자아 매개 중심도를 빠르게 산출할 수 있는 알고리즘을 제안한다. 그리고 일반적인 사회관계망의 특성을 대표하는Barabási-Albert 네트워크 모델을 사용한 가상 네트워크와 실제 사회관계망을 대표하는 페이스북 친구 관계 네트워크에서의 실험을 통하여확장 자아 매개 중심도의 중요도 순위가 기존 매개 중심도의 중요도 순위와 거의 일치함을 보인다. 또한 제안하는 알고리즘이 기존 알고리즘에 비해 확장 자아 네트워크에서의 확장 자아 매개 중심도를 더 빠르게 산출함을 보인다.
Abstract
In traditional social network analysis, the betweenness centrality measure has been heavily used to identify the relative importance of nodes. Since the time complexity to calculate the betweenness centrality is very high, however, it is difficult to get it of each node in large-scale social network where there are so many nodes and edges. In our past study, we defined a new type of network, called the expanded ego network, which is built only with each node’s local information, i.e., neighbor information of the node’s neighbor nodes, and also defined a new measure, called the expanded ego betweenness centrality. In this paper, We propose algorithm that quickly computes expanded ego betweenness centrality by exploiting structural properties of expanded ego network. Through the experiment with virtual network used Barabási-Albert network model to represent the generic social network and facebook network to represent actual social network, We show that the node’s importance rank based on the expanded ego betweenness centrality has high similarity with that the node’s importance rank based on the existing betweenness centrality. We also show that the proposed algorithm computes the expanded ego betweenness centrality quickly than existing algorithm.
참고문헌 (15)
- H. Kwak, "What is Twitter, a social network or a new media?", Proceedings of the 19th International World Wide Web (WWW) Conference, pp.591~600 (2010)
- Linkbar and Forensik: Two Systems for Interactive Visualization of Online Social Networks, "R. Pittinger", University of Applied Sciences Augsburg, ~ (2007)
- 손종수, "SNS에서의 개선된 소셜 네트워크 분석 방법", 지능정보연구, 18(4), pp.117~127 (2012), 한국지능정보시스템학회
- Lei Tang, "Community Detection and Mining in Social Media", Synthesis Lectures on Data Mining and Knowledge Discovery, 2(1) (2010)
- M. Everett, "Ego Network Betweenness", Social Networks, 27(1), pp.31~38 (2005)
- 손진곤, "사회관계망에서 중요 노드 식별을 위한 지역정보 기반 매개 중심도", 정보처리학회논문지. 컴퓨터 및 통신시스템, 2(5), pp.209~216 (2013), 한국정보처리학회[DOI]
- U. Brandes, "A Faster Algorithm for Betweenness Centrality", Journal of Mathematical Sociology, 25(2), pp.163~177 (2001)
- M. Baglioni, "Fast Exact Computation of Betweenness Centrality in Social Networks", Proceedings of IEEE, 2012, 450~456
- A. L. Barabási, "Emergence of scaling in random networks", Science, 286, pp.509~512 (1999)
- P. Holme, "Growing scale-free networks with tunable clustering", Physics Review. E, 65, pp.026107~ (2002)
- "SNAP Stanford"[URL]
- Y.-h. Kim, "Betweenness of Expanded Ego Networks in Sociality-Aware Delay Tolerant Networks", Ubiquitous Information Technologies and Applications (LNEE, Proc. of CUTE 2012), pp.499~505 (2012), Springer
- B. A. Huberman, "Social networks that matter: Twitter under the microscope", First Monday, 14(1) (2009)
- S. Wasserman, "Social Network Analysis:Methods and Applications" (1994), Cambridge University Press
- F. Odella, "Using Ego-networks in Surveys: Methodological and Research Issues", Proceedings of International Conference on Network Science (2006)