SNS에서의 개선된 소셜 네트워크 분석 방법

손종수(Jong-Soo Sohn),조수환(Soo-Whan Cho),권경락(Kyung-Lag Kwon),정인정(In-Jeong Chung) 한국지능정보시스템학회 2012 지능정보연구 Vol.18 No.4

최근 온라인 소셜 네트워크 서비스(SNS)의 사용자가 크게 늘어나고 있으며 다양한 분야에서 SNS의 사용자 관계 구조 및 메시지를 분석하기 위한 연구를 진행하고 있다. 그러나 대부분의 소셜 네트워크 분석 방법들은 노드 사이의 최단거리를 기초로 하고 있으므로 계산 시간이 오래 걸린다. 이는 점차 대형화 되어가는 SNS의 데이터를 여러 분야에서 활용하는데 걸림돌이 되고 있다. 이에 따라 본 논문에서는 SNS의 사용자 그래프에서 사용자간 최단거리를 빠르게 찾기 위한 휴리스틱 기반의 최단 경로 탐색 방법을 제안한다. 제안하는 방법은 1) 트리로 표현된 소셜 네트워크에서 시작 노드와 목표 노드를 설정한다. 그리고 2) 만약 목표 노드가 경사 트리의 단말에 있다면 경사 트리가 시작하는 노드를 임시 골 노드로 설정한다. 마지막으로 3) 연결의 차수를 평가값으로 하는 휴리스틱 기반 최단거리 탐색을 수행한다. 이렇게 최단거리를 탐색한 후 매개 중심성 분석(Betweenness Centrality) 및 근접 중심성(Closeness Centrality)를 계산한다. 제안하는 방법을 사용하면 소셜 네트워크 분석에서 가장 많은 시간이 필요한 최단거리 탐색을 빠르게 수행할 수 있으므로 소셜 네트워크 분석의 효율성을 기대할 수 있다. 본 논문에서 제안하는 방법을 검증하기 위하여 약 16만 명으로 구성된 SNS에서의 실제 데이터를 이용하여 매개 중심성 분석과 근접 중심성 분석을 수행하였다. 실험 결과, 제안하는 방법은 전통적 방식에 비하여 매개 중심성, 근접 중심성의 계산 시간이 각각 6.8배, 1.8배 더 빠른 결과를 보였다. 본 논문에서 제안한 방법은 소셜 네트워크 분석의 시간을 향상시켜 여러 분야에서 사회 현상 및 동향을 분석하는데 유용하게 활용될 수 있다. 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 brea

데이터 웨어하우스에서 클러스터링 기법을 이용한 실체화 뷰 선택 알고리즘

양진혁,정인정,Yang, Jin-Hyuk,Chung, In-Jeong 한국정보처리학회 2000 정보처리논문지 Vol.7 No.8

In order to acquire the precise and fast response for an analytical query, proper selection of the views to materialize in data warehouse is very crucial. In traditional view selection algorithms, the whole relations are considered to be selected as materialized views. However, materializing the whole relations rather than a part of relations results in much worse performance in terms of time and space cost. Therefore, we present an improved algorithm for selection of views to materialize using clustering method to overcome the problem resulted from conventional view selection algorithms. In the presented algorithm, ASVMRT(Algorithm for Selection of Views to daterialize using Iteduced Table). we first generate reduced tables in clata warehouse using automatic clustering based on attrihute-values density, then we consider the combination of reduced tables as materialized views instead of the combination of the original hase relations. For the justification of the proposecl algorithm. we show the experimental results in which both time and space cost are approximately 1.8 times better than the conventional algorithms. 데이터 웨어하우스에서 실체화 할 뷰들을 알맞게 선택하는 것은 분석적인 질의에 대한 정확하고 신속한 응답을 얻기 위해서 대단히 중요한 문제이다. 기존의 뷰 선택 알고리즘들에서는 릴레이션 전체가 실체화 뷰들로서 고려되었다. 그러나, 릴레이션의 부분 대신 전체를 실체화한다는 것은 시간과 공간 비용측면에서 좋지 못한 성능을 초래한다. 따라서, 우리는 기존 뷰 선택 알고리즘들에서의 문제점을 극복하기 위해서 개선된 실체화 뷰 선택 알고리즘을 제안한다. 제안된 알고리즘 ASVMRT(Algorithm for Selection on Views to Materialize using Reduced Table)에서는 먼저 속성-값들의 농도에 기반을 둔 자동 클러스터링을 사용하여 축약 테이블들을 데이터 웨어하우스에서 생성한 다음, 원래의 베이스 릴레이션들의 조합 대신에 축약 테이블들의 조합을 실체화 뷰들로 고려한다. 제안한 알고리즘의 타당성 검증을 위하여 우리는 실험결과에서 시간 및 공간 모두에서 기존 알고리즘들보다 약 1.8배의 성능향상이 있음을 보인다.

Complexity Analysis for the Improved Parallel Logic Programming Systems

정인정(In-Jeong Chung),이홍규(Heung-Kyu Lee) 한국정보보호학회 1992 정보보호학회논문지 Vol.2 No.1

패트리네트 모형을 이용한 보호된 논리 프로그램의 형식적 표현

정인정(In Jeong Chung),이흥규(Heong Kyu Lee) 한국정보과학회 1993 한국정보과학회 학술발표논문집 Vol.20 No.2

이 논문은 보호된 논리 프로그램과 이것을 annotated Petri net로 표현한 것에 관한 것이다. 우리는 이 논문에서 보호된 논리 프로그램이 APN으로 변환되는 방법을 제시하고, APN 모형의 syntax및 semantics를 정의하였다. 보호된 논리프로그램의 본질적인 행동방식이 APN에서 어떻게 표시되는지를 설명하였다. 또한 가능한 병렬성에 대하여 연구하고, 이 병렬성이 APN에서 어떻게 나타나지고 개발, 이용될수 있는지를 규명하였다.

소셜네트워크 기반의 콘텐츠 추천 방법

손종수,정인정,Sohn, Jong-Soo,Chung, In-Jeong 한국정보처리학회 2011 정보처리학회논문지B Vol.18 No.5

최근 웹 및 웹 콘텐츠의 양이 폭발적으로 증가함에 따라서 콘텐츠 추천 시스템(CRS, Contents Recommendation System)은 최근 중요한 이슈로 대두되었다. 이에 따라, 콘텐츠 추천 시스템에 대한 콘텐츠 추천 방법(CRM, Contents Recommendation Method)이 꾸준히 연구 및 소개되어 왔다. 그러나 전통적인 CRM들은 콘텐츠 생성자의 위상이 중요하게 여겨지는 웹 2.0 환경에서 활용하는데 부족함이 있다. 본 논문에서는 연결 정도 중심성 분석(Degree of centrality) 및 TF-IDF를 활용하여 양질의 콘텐츠를 추천하는 방법을 제안한다. 이를 위하여 본 논문에서는 RSS와 FOAF를 수집하여 TF-IDF와 연결 정도 중심성을 각각 분석한다. 그리고 분석된 두 값을 이용하여 콘텐츠를 추천한다. 본 논문에서 제안한 방법을 검증하기 위하여 우리는 시스템을 구현하였으며 콘텐츠 추천 결과를 보인다. 본 논문에서 제안한 방법을 사용하면 입력된 질의어에 대해 사용자와 콘텐츠의 관계를 분석하고 이를 통해 적절한 콘텐츠를 추출할 수 있다. 그리고 본 논문에서 제안한 방법을 통해 구축한 시스템은 전통적인 콘텐츠 추천 시스템과 달리 소셜네트워크에서 콘텐츠 생산자에 대한 중요도가 반영됨으로 보다 신뢰성이 있는 결과를 얻을 수있다. As the volume of internet and web contents have shown an explosive growth in recent years, lately contents recommendation system (CRS) has emerged as an important issue. Consequently, researches on contents recommendation method (CRM) for CRS have been conducted consistently. However, traditional CRMs have the limitations in that they are incapable of utilizing in web 2.0 environments where positions of content creators are important. In this paper, we suggest a novel way to recommend web contents of high quality using both degree of centrality and TF-IDF. For this purpose, we analyze TF-IDF and degree of centrality after collecting RSS and FOAF. Then we recommend contents using these two analyzed values. For the verification of the suggested method, we have developed the CRS and showed the results of contents recommendation. With the suggested idea we can analyze relations between users and contents on the entered query, and can consequently provide the appropriate contents to the user. Moreover, the implemented system we suggested in this paper can provide more reliable contents than traditional CRS because the importance of the role of content creators is reflected in the new system.

FOAF와 SNA를 이용한 개선된 인터넷 자원 추천 방법

손종수,정인정,Sohn, Jong-Soo,Chung, In-Jeong 한국정보처리학회 2012 정보처리학회논문지B Vol.19 No.3

최근 사용자들이 생성한 콘텐츠들이 크게 늘어나고 커뮤니티 기반 웹 사이트가 발전함으로 인하여 사용자들에게 인터넷 자원을 추천하는 시스템이 큰 각광을 받고 있다. 그러나 대부분의 인터넷 자원 추천 시스템들은 사용자의 특징을 충분하게 반영하지 못하는 한계를 가지고 있다. 이에 따라 본 논문에서는 사용자의 특징이 충분히 반영되는 자원의 추천을 위하여 FOAF와 SNA를 사용한 추천 방법을 제안한다. 제안하는 방법은 1) FOAF를 통해 사용자의 특징 데이터와 태그 데이터를 취득한다. 2) 취득한 데이터를 세 종류의 행렬에 삽입하고 통합한 후 사용자, 사용자의 특징, 태그를 나타내는 그래프를 생성한다. 3) 소셜 네트워크 분석을 통해 추천 항목의 일반 특징과 핫태그(Hot tag)를 선정하여 인터넷 자원을 추천한다. 본 논문의 검증을 위하여 우리는 실험을 통해 본 논문에서 제안한 방법과 아이템 기반 추천 방법을 비교하였다. 이를 통해 보다 많은 사용자가 참여할수록 아이템 기반 추천 방법보다 본 논문에서 제안한 방법에 의한 추천 결과의 품질이 우수함을 확인하였다. 본 논문에서 제안하는 방법을 활용하면 사용자들에게 보다 적합한 자원을 추천하는 것이 가능하다. 그리고 제안하는 방법은 폭발적으로 늘어나는 인터넷 자원을 검색하는데 있어 효율적으로 활용될 수 있다. In recent years, due to rapidly increasing user-created internet contents coupled with the development of community-based websites, the internet resource recommendation systems are attracting attentions of the users. However, most of the systems have failed in properly reflecting users' characteristics and thus they have difficulty in recommending appropriate resources to users. In this paper, we propose an internet resource recommendation method using FOAF and SNA which fully reflects the characteristics of users. In our method, 1) we extract the data about user characteristics and tags using FOAF; 2) we generate graphs representing users, user characteristics and tags after inserting data into 3 matrixes and integrating them; 3) we recommend the appropriate internet resources after selecting common characteristics of the recommended items and Hot tags by analyzing social network. For verification of our proposed method, we implemented our method to establish and analyze an experimental social group. We verified through our experiments that the more users added in the social network, the higher quality of recommendation result we got than the item-based recommendation method. By using the suggested idea in this paper, we can make a more appropriate recommendation of resources to users while effectively retrieving explosively increasing internet resources.

개선된 패스트리를 이용한 지능형 생산관리 시스템

권경락,류재환,손종수,정인정,Kwon, Kyung-Lag,Ryu, Jae-Hwan,Sohn, Jong-Soo,Chung, In-Jeong 한국정보처리학회 2009 정보처리학회논문지D Vol.16 No.4

최근 RFID 기술과 기업정보시스템을 연계하여 사용하려는 많은 시도가 진행되어 왔다. 하지만, 대부분의 경우 동시에 많은 양의 인식할 수 있는 RFID의 기본적인 특징에만 충실했을 뿐, 리더로부터 생성되는 많은 양의 데이터에 대한 관리적인 측면을 고려하지 못하고 있다. 그 결과, 이러한 시스템을 통해 시간이나 흐름과 관련된 연속적이고 동적인 정보를 얻기가 어렵다. 본 논문에서는 대량의 RFID 데이터를 효율적으로 관리하기 위해 RFID 데이터 마이닝 기법의 하나인 경로 트리(PathTree)를 보완한 공정트리(Procedure Tree)라는 새로운 방법을 제안한다. 제안한 방법을 실제 기업 정보 시스템과 연계하여 실시간 공정 관리 시스템에 적용한 후 제안한 시스템의 효율성을 평가한다. 제안한 방법을 통해 기존 RFID 기반 생산관리 시스템이 하기 어려운 실시간 공정 관리를 위한 공정 흐름의 예측이나 추적과 같은 업무를 효과적으로 수행할 수 있었다. In recent years, there have been many attempts to connect the latest RFID (Radio Frequency Identification) technology with EIS (Enterprise Information System) and utilize them. However, in most cases the focus is only on the simultaneous multiple reading capability of the RFID technology neglecting the management of massive data created from the reader. As a result, it is difficult to obtain time-related information such as flow prediction and analysis in process control. In this paper, we suggest a new method called 'procedure tree', an enhanced and complementary version of PathTree which is one of RFID data mining techniques, to manage massive RFID data sets effectively and to perform a real-time process control efficiently. We will evaluate efficiency of the proposed system after applying real-time process management system connected with the RFID-based EIS. Through the suggested method, we are able to perform such tasks as prediction or tracking of process flow for real-time process control and inventory management efficiently which the existing RFID-based production system could not have done.

Fuzzy OWL을 이용한 사용자 Context의 표현 및 추론

손종수(Jong-Soo Sohn),정인정(In-Jeong Chung) 한국지능정보시스템학회 2008 지능정보연구 Vol.14 No.1

본 논문에서는 유비쿼터스 환경에서 사용자 Context를 표현하는 과제를 해결하기 위하여 시맨틱 웹 기술 및 퍼지개념을이용하여 사용자 Context를 언어와 기종에 독립적이면서 사람이 생각하는 것과 최대한 유사한 형태로 기술하는 것을 제안한다. 재래의 방법으로 사용되어온 일반 집합으로 Context를 표현하는 방법은 실세계의 환경을 표현하는데 한계가 있기 때문에 본 논문에서는 퍼지 개념과 표준 웹 온톨로지 언어 OWL이 융합된 Fuzzy OWL 언어를 사용하였다. 본 논문에서 제안하는 방법은 사용자가 접한 환경정보들을 수치로 표현하며 이를 OWL로 기술한다. 그리고 OWL로 변환된 Context를 Fuzzy OWL로 변환한다. 마지막으로 자동적인 상황인지가 가능한지 여부를 퍼지 추론 엔진인 FiRE를 사용하여 검증한다. 본 논문에서 제시하는 방법을 사용하면 유비쿼터스 컴퓨팅 환경에서도 사용할 수 있는 형태로 Context를 기술할 수 있으며 퍼지의 개념을 사용하여 Context를 표현하기 때문에 상태나 정도를 표현함에 있어 좀 더 효과적이다. 뿐만 아니라, 기술된 Context를 기반으로 현재 사용자가 접한 환경의 상태를 추론할 수 있으며 추론된 상태에 따라 시스템이 자동적으로 작동하게 하는 것이 가능하다. In order to constructan ubiquitous computing environment, it is necessary to develop a technology that can recognize users and circumstances. In this regard, the question of recognizing and expressing user Context regardless of computer and language types has emerged as an important task under the heterogeneous distributed processing system. As a means to solve this task of representing user Context in the ubiquitous environment, this paper proposes to describe user Context as the most similar form of human thinking by using semantic web and fuzzy concept independentof language and computer types. Because the conventional method of representing Context using an usual collection has some limitations in expressing the environment of the real world, this paper has chosen to use Fuzzy OWL language, a fusion of fuzzy concept and standard web ontology language OWL. Accordingly, this paper suggests the following method. First we represent user contacted environmental information with a numerical value and states, and describe it with OWL. After that we transform the converted OWL Context into Fuzzy OWL. As a last step, we prove whether the automatic circumstances are possible in this procedure when we use fuzzy inference engine FiRE. With use the suggested method in this paper, we can describe Context which can be used in the ubiquitous computing environment. This method is more effective in expressing degree and status of the Context due to using fuzzy concept. Moreover, on the basis of the stated Context we can also infer the user contacted status of the environment. It is also possible to enable this system to function automatically in compliance with the inferred state.

법령 정보검색 시스템 구현에 관한 연구

민재홍(Jae Hong Min),조평동(Pyung Dong Cho),양진혁(Jin Hyuk Yang),박평구(Pyung Koo Park),정인정(In Jeong Chung) 한국정보처리학회 2000 정보처리학회논문지 Vol.7 No.11

Telecommunications standards have two different types of regulations one is a law, enacted by government which all telecommunications related industries must observe. The other is a recommendatory standards, formulated by either government agency or some standardization organizations. Observation of these standards is not obligatory. However, technical standards are strict laws and ordinances based on common judgement and various conditions for evaluation of levels and limits. This paper deals with enhancing productivity of enactment and revision of technical standards. Through database of above related information we secure information continuity and public property of cyber space for the public. In this paper, we also classify recent data within the website in and out of the country offering four different methods of information retrieval and management system. The four retrieval methods suggested in this paper are itemized keyword retrieval, hierarchical retrieval, regulatory keyword retrieval and chronological keyword retrieval. These various retrieval methods provide the public with information of enactment and amendment of laws and regulations in the cyber space, thereby guarantees the sharing of information. Finally the important feature of the information retrieval system implemented in this paper is the online updating capability of law and regulations through the internet.

지능형 e-비즈니스를 위한 플랫폼에 관한 연구: OWL-S의 CLP로의 확장 및 통합방안

양진혁 ( Jin-hyuk Yang ),정인정 ( In-jeong Chung ) 한국정보처리학회 2004 한국정보처리학회 학술대회논문집 Vol.11 No.1

본 논문에서 우리는 지능형 e-비즈니스를 효과적으로 수행하기 위한 시맨틱 웹 서비스 아키텍처의 구성요소인 마크업인 OWL-S를 CLP(Constraint Logic Program) RuleML로의 확장 및 통합방안에 관한 연구결과를 제시한다. 우리의 주 공헌은 OLP(Ordinary Logic Program), SCLP(Situated Courteous Logic Program) 및 CLP(Constraint Logic Program) 사이의 표현력과 계산력을 비교 및 분석한 근거를 바탕으로 하여 시맨틱 웹, 웹 서비스 그리고 규칙표현 모두가 함께 사용될 수 있는 근거를 제공하였다는 것이다. 본 논문에서 제안된 접근법은 온톨로지를 마크업하기 위한 노력과 규칙을 표현하기 위한 노력이 자연스러운 방법으로 통합될 수 있는 근간을 마련할 뿐만 아니라 규칙들을 이용하여 온톨로지들을 보완하고, 규칙들에서 사용되는 용어들을 온톨로지들에서 정의된 용어들 및 속성들로 표현할 수 있다는 장점을 가진다.