DIGITAL LIBRARY ARCHIVE
HOME > DIGITAL LIBRARY ARCHIVE
< Previous   List   Next >  
Improved Social Network Analysis Method in SNS
Full-text Download
Jong-Soo Sohn (Department of Computer and Information Science, Korea University)
Soo-Whan Cho (Department of Computer and Information Science, Korea University)
Kyung-Lag Kwon (Department of Computer and Information Science, Korea University)
In-Jeong Chung (Department of Computer and Information Science, Korea University)
Vol. 18, No. 4, Page: 117 ~ 127
Keywords
SNS, SNA, Centrality, Closeness, Closeness
Abstract
Due to the recent expansion of the Web 2.0 -based services, along with the widespread of smartphones, online social network services are being popularized among users. Online social network services are the online community services which enable users to communicate each other, share information and expand human relationships. In the social network services, each relation between users is represented by a graph consisting of nodes and links. As the users of online social network services are increasing rapidly, the SNS are actively utilized in enterprise marketing, analysis of social phenomenon and so on. Social Network Analysis (SNA) is the systematic way to analyze social relationships among the members of the social network using the network theory. In general social network theory consists of nodes and arcs, and it is often depicted in a social network diagram. In a social network diagram, nodes represent individual actors within the network and arcs represent relationships between the nodes. With SNA, we can measure relationships among the people such as degree of intimacy, intensity of connection and classification of the groups. Ever since Social Networking Services (SNS) have drawn increasing attention from millions of users, numerous researches have made to analyze their user relationships and messages. There are typical representative SNA methods: degree centrality, betweenness centrality and closeness centrality. In the degree of centrality analysis, the shortest path between nodes is not considered. However, it is used as a crucial factor in betweenness centrality, closeness centrality and other SNA methods. In previous researches in SNA, the computation time was not too expensive since the size of social network was small. Unfortunately, most SNA methods require significant time to process relevant data, and it makes difficult to apply the ever increasing SNS data in social network studies. For instance, if the number of nodes in online social network is n, the maximum number of link in social network is n(n-1)/2. It means that it is too expensive to analyze the social network, for example, if the number of nodes is 10,000 the number of links is 49,995,000. Therefore, we propose a heuristic-based method for finding the shortest path among users in the SNS user graph. Through the shortest path finding method, we will show how efficient our proposed approach may be by conducting betweenness centrality analysis and closeness centrality analysis, both of which are widely used in social network studies. Moreover, we devised an enhanced method with addition of best-first-search method and preprocessing step for the reduction of computation time and rapid search of the shortest paths in a huge size of online social network. Best-first-search method finds the shortest path heuristically, which generalizes human experiences. As large number of links is shared by only a few nodes in online social networks, most nods have relatively few connections. As a result, a node with multiple connections functions as a hub node. When searching for a particular node, looking for users with numerous links instead of searching all users indiscriminately has a better chance of finding the desired node more quickly. In this paper, we employ the degree of user node vn as heuristic evaluation function in a graph G = (N, E), where N is a set of vertices, and E is a set of links between two different nodes. As the heuristic evaluation function is used, the worst case could happen when the target node is situated in the bottom of skewed tree. In order to remove such a target node, the preprocessing step is conducted. Next, we find the shortest path between two nodes in social network efficiently and then analyze the social network. For the verification of the proposed method, we crawled 160,000 people from online and then constructed social network. Then we compared with previous methods, which are best-first-search and breath-first-search, in time for searching and analyzing. The suggested method takes 240 seconds to search nodes where breath-first-search based method takes 1,781 seconds (7.4 times faster). Moreover, for social network analysis, the suggested method is 6.8 times and 1.8 times faster than betweenness centrality analysis and closeness centrality analysis, respectively. The proposed method in this paper shows the possibility to analyze a large size of social network with the better performance in time. As a result, our method would improve the efficiency of social network analysis, making it particularly useful in studying social trends or phenomena.
Show/Hide Detailed Information in Korean
SNS에서의 개선된 소셜 네트워크 분석 방법
손종수 (고려대학교 과학기술대학 컴퓨터정보학과)
조수환 (고려대학교 과학기술대학 컴퓨터정보학과)
권경락 (고려대학교 과학기술대학 컴퓨터정보학과)
정인정 (고려대학교 과학기술대학 컴퓨터정보학과)
Abstract
최근 온라인 소셜 네트워크 서비스(SNS)의 사용자가 크게 늘어나고 있으며 다양한 분야에서 SNS의 사용자 관계 구조 및 메시지를 분석하기 위한 연구를 진행하고 있다. 그러나 대부분의 소셜 네트워크 분석 방법들은 노드 사이의 최단 거리를 기초로 하고 있으므로 계산 시간이 오래 걸린다. 이는 점차 대형화 되어가는 SNS의 데이터를 여러 분야에서 활용하는데 걸림돌이 되고 있다. 이에 따라 본 논문에서는 SNS의 사용자 그래프에서 사용자간 최단거리를 빠르게 찾기 위한 휴리스틱 기반의 최단 경로 탐색 방법을 제안한다. 제안하는 방법은 1) 트리로 표현된 소셜 네트워크에서 시작 노드와 목표 노드를 설정한다. 그리고 2) 만약 목표 노드가 경사 트리의 단말에 있다면 경사 트리가 시작하는 노드를 임시 골 노드로 설정한다. 마지막으로 3) 연결의 차수를 평가값으로 하는 휴리스틱 기반 최단거리 탐색을 수행한다. 이렇게 최단거리를 탐색한 후 매개 중심성 분석(Betweenness Centrality) 및 근접 중심성(Closeness Centrality)를 계산한다. 제안하는 방법을 사용하면 소셜 네트워크 분석에서 가장 많은 시간이 필요한 최단거리 탐색을 빠르게 수행할 수 있으므로 소셜 네트워크 분석의 효율성을 기대할 수 있다. 본 논문에서 제안하는 방법을 검증하기 위하여 약 16만 명으로 구성된 SNS에서의 실제 데이터를 이용하여 매개 중심성 분석과 근접 중심성 분석을 수행하였다. 실험 결과, 제안하는 방법은 전통적 방식에 비하여 매개 중심성, 근접 중심성의 계산 시간이 각각 6.8배, 1.8배 더 빠른 결과를 보였다. 본 논문에서 제안한 방법은 소셜 네트워크 분석의 시간을 향상시켜 여러 분야에서 사회 현상 및 동향을 분석하는데 유용하게 활용될 수 있다.
Cite this article
JIIS Style
Sohn, J.-S., S.-W. . Cho, K.-L. Kwon, and I.-J. . Chung, "Improved Social Network Analysis Method in SNS", Journal of Intelligence and Information Systems, Vol. 18, No. 4 (2012), 117~127.

IEEE Style
Jong-Soo Sohn, Soo-Whan Cho, Kyung-Lag Kwon, and In-Jeong Chung, "Improved Social Network Analysis Method in SNS", Journal of Intelligence and Information Systems, vol. 18, no. 4, pp. 117~127, 2012.

ACM Style
Sohn, J.-S., Cho, S.-W. ., Kwon, K.-L., and Chung, I.-J. ., 2012. Improved Social Network Analysis Method in SNS. Journal of Intelligence and Information Systems. 18, 4, 117--127.
Export Formats : BiBTeX, EndNote

Warning: include(/home/hosting_users/ev_jiisonline/www/admin/archive/advancedSearch.php) [function.include]: failed to open stream: No such file or directory in /home/hosting_users/ev_jiisonline/www/archive/detail.php on line 429

Warning: include() [function.include]: Failed opening '/home/hosting_users/ev_jiisonline/www/admin/archive/advancedSearch.php' for inclusion (include_path='.:/usr/local/php/lib/php') in /home/hosting_users/ev_jiisonline/www/archive/detail.php on line 429
@article{Sohn:JIIS:2012:515,
author = {Sohn, Jong-Soo and Cho, Soo-Whan and Kwon, Kyung-Lag and Chung, In-Jeong },
title = {Improved Social Network Analysis Method in SNS},
journal = {Journal of Intelligence and Information Systems},
issue_date = {December 2012},
volume = {18},
number = {4},
month = Dec,
year = {2012},
issn = {2288-4866},
pages = {117--127},
url = {},
doi = {},
publisher = {Korea Intelligent Information System Society},
address = {Seoul, Republic of Korea},
keywords = { SNS, SNA, Centrality, Closeness and Closeness },
}
%0 Journal Article
%1 515
%A Jong-Soo Sohn
%A Soo-Whan Cho
%A Kyung-Lag Kwon
%A In-Jeong Chung
%T Improved Social Network Analysis Method in SNS
%J Journal of Intelligence and Information Systems
%@ 2288-4866
%V 18
%N 4
%P 117-127
%D 2012
%R
%I Korea Intelligent Information System Society