사회관계망에서 중요 노드 식별을 위한 지역정보 기반 매개 중심도
Local Information-based Betweenness Centrality to Identify Important Nodes in Social Networks
0
조회
0
다운로드
4
인용
0
참고문헌
키워드
초록
전통적인 사회관계망 분석에 있어서 각 노드의 매개 중심도는 메시지 전달 측면에서의 각 노드들의 상대적인 중요도를 파악하는 척도로 오랫동안 사용되어 왔다. 하지만, 매개 중심도를 산출하기 위한 계산 복잡도가 높기 때문에 노드의 수와 간선의 수가 매우 많은 대규모 사회관계망에서는 각 노드의 매개 중심도를 산출하기가 어렵다. 본 논문에서는 각 노드들마다 자신의 지역정보, 즉 이웃노드들이 지닌 각각의 이웃노드 정보를 활용하여 구성가능한 확장 자아 네트워크(Expanded Ego Network)를 새롭게 정의하고 이러한 네트워크를 기반으로 확장 자아 매개 중심도(Expanded Ego Betweenness Centrality)를 정의한다. 일반적인 사회관계망의 특성인 척도 없는 네트워크(Scale-free Network)를 생성할 수 있는 Barabási-Albert 네트워크 모델을 사용한 실험을 통하여 제안한 확장 자아 매개 중심도의 각 노드별 순위는 기존의 전통적인 방식으로 산출한 매개 중심도의 각 노드별 순위와 거의 일치함을 보인다.
Abstract
In traditional social network analysis, the betweenness centrality measure has been heavily used to identify the relative importance of nodes in terms of message delivery. 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 this paper, we define 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 define a new measure, called the expended ego betweenness centrality. Through the intensive experiment with Barabási-Albert network model to generate the scale-free networks which most social networks have as their embedded feature, we also show that the nodes’ importance rank based on the expanded ego betweenness centrality has high similarity with that based on the traditional betweenness centrality.
참고문헌 (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)
- R. Pittinger, "Linkbar and Forensik: Two Systems for Interactive Visualization of Online Social Networks" (2007), University of Applied Sciences Augsburg
- Lei Tang, "Community Detection and Mining in Social Media", Synthesis Lectures on Data Mining and Knowledge Discovery, 2(1) (2010)
- S. Wasserman, "Social Network Analysis: Methods and Applications" (1994), Cambridge University Press
- 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
- M. Everett, "Ego Network Betweenness", Social Networks, 27(1), pp.31~38 (2005)
- F. Odella, "Using Ego-networks in Surveys: Methodological and Research Issues", Proceedings of International Conference on Network Science (2006)
- E. Daly, "Social Network Analysis for Information Flow in Disconnected Delay-Tolerant MANETs", IEEE Trans. on Mobile Computing, 8(5), pp.606~621 (2009)
- 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
- A. Mtibaa, "PeopleRank: combining social and contact information for opportunistic forwarding" (2010), Proceedings of INFOCOM
- F. Fabbri, "A sociability-based routing scheme for delay-tolerant networks", EURASIP Journal on Wireless Communications and Networking (2011)
- A. L. Barabái, "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 (2002)
- B. A. Huberman, D. M. Romero, and F. Wu, "Social networks that matter : Twitter under the microscope", First Monday, 14(1) (2009)