Relation Discovery Mechanism in Heterogeneous Information Networks

Abstract

그래프 데이터 설계는 실생활에 많은 문제들을 모델링 하기 위해 널리 사용되고 있다. 우리가 일상생활에서 만드는 활동에 대한 데이터는 서로 연결되어 있고, 이러한 연결은 하나의 네트워크를 형성한다. 그러므로 네트워크 연구는 지난 20년동안 컴퓨터네트워크와 시스템 정보의 영역에서 매우 장려되어 왔다. 그래프 성향을 가진 어떤 문제던지 네트워크로 모델링을 할 수 있다. 이 네트워크는 꼭지점(vertices) 와 에지(edges)로 구성되어 있어, 꼭지점(vertices)은 일상 생활 객체를 물리적 혹은 메타-물리적 객체로 나타내는 노드이고 에지(edges)는 꼭지점(vertices) 들의 관계를 나타낸다. 이 관계는 수적이거나 서술적 일 수 있다. 지금까지 엄청난 양의 네트워크 어플리케이션이 세상에 나왔고, 따라서 그래프 마이닝은 또한 데이터 마이닝 연구 커뮤니티에서 많은 관심 얻었다. 일상적 데이터와의 구조적 차이로 인해서, 일상적인 데이터 마이닝 기술은 그래프 마이닝에 직접적으로 적용될 수 없었고, 그래프 데이터 셋을 마이닝 하기 위해 그래프 데이터의 속성들을 고려하여 특정한 기법을 개발할 필요가 생기게 되었다. 다른 데이터 조각들 사이의 관계를 찾는 것은 지금까지 데이터 마이닝 영역에서 흥미 있는 도전으로 남아있다. 다른 데이터 셋을 기반으로 연구원들은 항시 각각의 개체들 사이에서의 관계를 찾으려 시도하고 있다. 그러나 이 영역에서 지금까지 이뤄진 모든 노력 은 동질의 네트워크에서 이루어져왔다. 이는 동질의 네트워크를 다루는 것이 쉽기 때문인데, 그 데이터 셋이 인접 매트릭스를 쉽게 변환 될 수 있어서이다. 관찰 된 또 다른 한계점은 대부분의 관계성 발견기법들을 수적인 데이터 셋에 작용하고 있다는 것이다. 본 논문에서는 이러한 단점을 극복하기 위하여, 클러스터링 개념을 활용하여 이질적 네트워크에서 객체들 사이의 관계성을 발견하기 위한 메카니즘을 제시한다. ●이종정보 네트워크 에서 객체들의 클러스터링 ●클러스터 센터로이드를 고려하므로써 하나의 클러스터에 있을 객체들 사이의 관계성을 발견하기 ●다른 크러스터에 있는 개체들의 관계를 찾기 위해 확률론적 방법을 사용하기 크러스터 개체를 위하여 우리는 구조에만 기반하여 객체들 사이의 유사성을 찾을뿐 아니라 네트워크가 구성되는 노드들에 대한 에지(edge)와 값들에 나타나는 관계 및 데이터를 이용하는 하이브리드 테크놀로지를 소개한다. 이렇게 해서 우리는 먼저 구조에 기반으로하여 객체를 클러스터링하고, 두 번째 반복으로서 객체들을 다른 객체들과의 관계에 기반하여 클러스터링을 한다. 클러스터링을 수행한 후에 우리는 유사성 메트릭스를 이용하여 다른 클러스터들 사이의 숨겨진 관계를 정의하기 위해 확률에 기반한 관계 발견 메커니즘을 소개 하였다. 우리는 새로운 그래프를 만들었다. 이는 노드들로서의 크러스터들과, 다른 크러스터들 사이의 관계를 발견하기 위한 클러스터들 사이의 공통 관계들을 에지(edge)로 나타내는 그래프이다. 우리는 news-twitter에 우리의 기법을 적용하여 실험하였고, 그 결과로 클러스터링과 관계 발견을 위한 기법들이 기존의 k-mean과 k-medoids 메소드 보다 더 나은 성능을 보였다.

Graph data structure is being widely used for modeling various problems of the real life. As it is a fact that data of activities that people generate in our daily life is connected with each other and these connections form a network. Therefore study of network has been highly encouraged during last two decades particularly in the domain of computer networks and information systems. Any problem that has a graph orientation can be modeled as a network. These networks consist of vertices and edges, vertices are nodes that represent daily life objects either physical or metaphysical and edges represent the relationship among these vertices. This relationship can be numeric or descriptive. As huge amount of networked applications have been marketed to date therefore Graph Mining has also obtained large attention in the data mining research community. Because of its structural difference from conventional data, conventional data mining techniques cannot be applied for graph mining directly that leads towards the need for the development of specific techniques for mining graph datasets by taking into account the properties of graph data. Finding relationship among different pieces of data has been remained an interesting challenge in data mining domain to date. Based on different datasets researchers always keep trying to discover relationship among different objects. However all efforts that are made to date in this domain have been made on homogenous networks as it is easy to deal with the homogenous networks particularly those datasets that can easily be converted into adjacency matrices. Another limitation that has been observed is that the most of relationship discovery techniques work on the numeric datasets. In order to overcome these drawbacks, this thesis presents a mechanism for discovering relationship among the objects in a heterogeneous network by utilizing the clustering concept. The proposed method consists of three major steps ●Clustering objects present in a heterogeneous information network ● Discovering relationship between objects present in one cluster by taking cluster centroids into account ● Using probabilistic method to find relationship among objects in different clusters In order to cluster objects this thesis introduces a new hybrid technique that find the similarity between objects not based on structure only but also utilizes the data and relationships that are present on the edges and the values of the nodes of that a network is composed. In this way firstly objects based on structure are clustered to their respective clusters and then in the second iteration those cluster objects are clustered based on their relationships with the other objects. After performing the clustering this thesis has introduced a probability based relationship discovery mechanism to identify the hidden relationship among different clusters using the similarity matrix. For this the creation of new graph comprises of clusters as the nodes and common relationships among these clusters as the edges has been proposed in order to discover the relationship among different clusters. The proposed has been examined on news-twitter dataset and results shows the presented techniques for clustering and relation discovery perform better then present k-mean and k-medoids methods.