[go: up one dir, main page]

KR101922326B1 - 링크 예측 장치 및 방법 - Google Patents

링크 예측 장치 및 방법 Download PDF

Info

Publication number
KR101922326B1
KR101922326B1 KR1020170015924A KR20170015924A KR101922326B1 KR 101922326 B1 KR101922326 B1 KR 101922326B1 KR 1020170015924 A KR1020170015924 A KR 1020170015924A KR 20170015924 A KR20170015924 A KR 20170015924A KR 101922326 B1 KR101922326 B1 KR 101922326B1
Authority
KR
South Korea
Prior art keywords
node
link
nodes
type
path
Prior art date
Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
Expired - Fee Related
Application number
KR1020170015924A
Other languages
English (en)
Other versions
KR20180091139A (ko
Inventor
김명호
정현지
김미진
김태연
Original Assignee
한국과학기술원
Priority date (The priority date is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the date listed.)
Filing date
Publication date
Application filed by 한국과학기술원 filed Critical 한국과학기술원
Priority to KR1020170015924A priority Critical patent/KR101922326B1/ko
Publication of KR20180091139A publication Critical patent/KR20180091139A/ko
Application granted granted Critical
Publication of KR101922326B1 publication Critical patent/KR101922326B1/ko
Expired - Fee Related legal-status Critical Current
Anticipated expiration legal-status Critical

Links

Images

Classifications

    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
    • H04L41/00—Arrangements for maintenance, administration or management of data switching networks, e.g. of packet switching networks
    • H04L41/14—Network analysis or design
    • H04L41/147—Network analysis or design for predicting network behaviour
    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06N—COMPUTING ARRANGEMENTS BASED ON SPECIFIC COMPUTATIONAL MODELS
    • G06N20/00—Machine learning
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
    • H04L41/00—Arrangements for maintenance, administration or management of data switching networks, e.g. of packet switching networks
    • H04L41/12—Discovery or management of network topologies
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
    • H04L41/00—Arrangements for maintenance, administration or management of data switching networks, e.g. of packet switching networks
    • H04L41/16—Arrangements for maintenance, administration or management of data switching networks, e.g. of packet switching networks using machine learning or artificial intelligence
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
    • H04L45/00—Routing or path finding of packets in data switching networks
    • H04L45/02—Topology update or discovery
    • H04L45/08—Learning-based routing, e.g. using neural networks or artificial intelligence
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
    • H04L45/00—Routing or path finding of packets in data switching networks
    • H04L45/24—Multipath
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
    • H04L43/00—Arrangements for monitoring or testing data switching networks
    • H04L43/08—Monitoring or testing based on specific metrics, e.g. QoS, energy consumption or environmental parameters
    • H04L43/0805—Monitoring or testing based on specific metrics, e.g. QoS, energy consumption or environmental parameters by checking availability
    • H04L43/0811—Monitoring or testing based on specific metrics, e.g. QoS, energy consumption or environmental parameters by checking availability by checking connectivity

Landscapes

  • Engineering & Computer Science (AREA)
  • Computer Networks & Wireless Communication (AREA)
  • Signal Processing (AREA)
  • Software Systems (AREA)
  • Medical Informatics (AREA)
  • Evolutionary Computation (AREA)
  • Artificial Intelligence (AREA)
  • Computer Vision & Pattern Recognition (AREA)
  • Theoretical Computer Science (AREA)
  • Physics & Mathematics (AREA)
  • Data Mining & Analysis (AREA)
  • Computing Systems (AREA)
  • General Engineering & Computer Science (AREA)
  • General Physics & Mathematics (AREA)
  • Mathematical Physics (AREA)
  • Databases & Information Systems (AREA)
  • Information Retrieval, Db Structures And Fs Structures Therefor (AREA)

Abstract

소스 노드와 타겟 노드 사이에 존재하는 경로 타입 및 상기 경로 타입에 별 경로 개수에 따라 학습된 가중치를 적용하여 링크 존재 가능성을 예측하는 링크 예측 장치가 제공된다. 상기 링크 예측 장치는 프로세서로 구현되고, 입력 그래프의 데이터를 이용하여 소스 노드 및 타겟 노드 사이에 존재하는 적어도 하나의 경로 타입을 특징 벡터로 생성하는 생성부 및 상기 특징 벡터에 학습된 결과 데이터인 가중치를 적용하여 상기 소스 노드 및 상기 타겟 노드 사이의 링크(link)의 존재를 예측하는 예측부를 포함할 수 있다. 상기 가중치는 상기 입력 그래프가 포함되는 네트워크 내에서 각각의 경로 타입에 대응하는 링크 존재 가능성을 나타낼 수 있다.

Description

링크 예측 장치 및 방법{APPARATUS AND METHOD OF LINK PREDICTION}
링크 예측 장치 및 방법에 연관되며, 보다 구체적으로는 복수의 노드 타입 및 링크 타입을 포함하는 이질형 정보 네트워크(heterogeneous information network)에 대한 링크 예측 장치 및 방법에 연관된다.
링크 예측이란 입력되는 그래프에 기초하여 현재 발견되지 않은 링크의 존재를 예측하는 기법을 나타낸다. 오늘날 소셜 네트워크 시스템 내에서의 추천 시스템이나 신약 개발을 위한 바이오 네트워크 분석 등 다양한 분야에서 링크 예측이 이용되고 있다. 최근에는 하나의 타입의 객체와 상기 객체들의 링크로 정의되는 동종형 그래프 데이터뿐만 아니고, 복수의 타입의 노드 및 링크를 포함하는 이질형 그래프 데이터에 대한 링크 예측 기술에 관하여 관심이 증가하고 있다.
종래 기술들은 이질형 그래프 데이터에서 링크 타입이 갖는 의미를 고려하지 않고 오로지 그래프의 구조적 특징에 기초하여 링크 예측을 수행하고 있다. 보다 구체적으로, 종래 기술들은 노드들 사이의 경로 개수, 두 노드가 가지는 공통 이웃의 개수, 페이지 랭크(pang rank)와 같은 구조적 특징에 기반하여 기계 학습을 수행하고 링크를 예측하는 방법을 사용하고 있다.
일측에 따르면, 소스 노드와 타겟 노드 사이에 존재하는 경로 타입 및 상기 경로 타입 별 경로 개수에 따라 학습된 링크 예측 모델을 적용하여 링크 존재 가능성을 예측하는 링크 예측 장치가 제공된다. 상기 링크 예측 장치는 프로세서로 구현되고, 입력 그래프의 데이터를 이용하여 소스 노드 및 타겟 노드 사이에 존재하는 적어도 하나의 경로 타입을 특징 벡터로 생성하는 생성부 및 상기 특징 벡터에 학습된 결과인 링크 예측 모델을 적용하여 상기 소스 노드 및 상기 타겟 노드 사이의 링크(link)의 존재를 예측하는 예측부를 포함할 수 있다.일실시예에 따르면, 상기 생성부는 상기 입력 그래프의 스키마 데이터를 이용하여 상기 소스 노드 및 상기 타겟 노드를 연결하는 노드 및 링크의 시퀀스를 추출하고, 상기 추출된 시퀀스를 상기 특징 벡터로서 생성할 수 있다.
다른 일실시예에 따르면, 상기 생성부는 복수의 노드 타입과 상기 노드 타입의 쌍에 따라 결정되는 복수의 경로 타입을 포함하는 이질형 정보 그래프(heterogeneous information graph)를 상기 입력 데이터로서 전달 받을 수 있다.
또 다른 일실시예에 따르면, 상기 예측부는 상기 입력 그래프가 포함되는 네트워크의 로우 데이터를 이용하여 기계 학습된 링크 예측 모델을 생성할 수 있다. 보다 구체적으로, 상기 예측부는 상기 네트워크 내의 임의의 노드 쌍을 연결하는 경로 타입 및 상기 경로 타입에 대응하는 링크 타입의 존재 여부 및 존재 개수에 따라 계산된 상관도를 상기 가중치로서 적용한 링크 예측 모델을 이용할 수 있다.
또 다른 일실시예에 따르면, 상기 예측부는 상기 기계 학습이 진행되는 경우에 상기 가중치로서, 제1 노드 및 제2 노드를 연결하는 제1 경로 타입의 제1 경로가 존재하는 경우에 각각의 링크 타입의 링크가 존재할 상관도를 적용할 수 있다.
또 다른 일실시예에 따르면, 상기 예측부는 상기 입력 그래프의 타입에 따라 미리 저장된 기계 학습의 결과 데이터 중 제1 링크 예측 모델을 선택하여 상기 링크의 존재를 예측할 수 있다.
다른 일측에 따르면, 소스 노드 및 타겟 노드 각각에 관한 이웃 노드 및 동료 노드를 이용하여 링크 예측 모델을 학습하고, 학습된 링크 예측 모델을 적용하여 링크 존재 가능성을 예측하는 경로 예측 장치가 제공된다. 상기 경로 예측 장치는 프로세서로 구현되고, 입력 그래프의 데이터를 이용하여 소스 노드 및 타겟 노드 사이에 존재하는 적어도 하나의 경로 타입을 특징 벡터로 생성하는 생성부 및 상기 특징 벡터에 학습된 결과인 링크 예측 모델을 적용하여 상기 소스 노드 및 상기 타겟 노드 사이의 링크(link)의 존재를 예측하는 예측부를 포함할 수 있다. 상기 링크 예측 모델은 상기 소스 노드 및 상기 타겟 노드 각각의 이웃 노드 및 동료 노드를 이용하여 기계 학습될 수 있다.
일실시예에 따르면, 상기 동료 노드는 두 개의 노드가 동일한 타입을 나타내고, 적어도 하나의 이웃 노드를 서로 공유 하는 경우를 나타낼 수 있다.
다른 일실시예에 따르면, 상기 생성부는 복수의 노드 타입과 상기 노드 타입의 쌍에 따라 결정되는 복수의 경로 타입을 포함하는 이질형 정보 그래프를 상기 입력 데이터로서 전달 받을 수 있다.
또 다른 일실시예에 따르면, 상기 예측부는 상기 타겟 노드의 이웃 노드이고, 상기 소스 노드의 동료 노드인 노드의 개수에 대응하는 링크 노드의 존재 가능성을 기계 학습을 위한 특징으로서 적용할 수 있다. 보다 구체적으로, 상기 예측부는 상기 타겟 노드의 이웃 노드이고, 설정 개수 이상의 공통 이웃 노드를 공유하는 동료 노드인 노드의 개수에 대응하는 링크 노드의 존재 가능성을 기계 학습을 위한 특징으로서 적용할 수 있다.
또 다른 일실시예에 따르면, 상기 예측부는 상기 소스 노드의 이웃 노드이고, 상기 타겟 노드의 동료 노드인 노드의 개수에 대응하는 링크 노드의 존재 가능성을 기계 학습을 위한 특징으로서 적용할 수 있다.
도 1은 일실시예에 따른 이질형 정보 그래프를 도시하는 예시도이다.
도 2a는 경로 타입과 링크 타입의 상관도를 계산하는 과정을 도시하는 흐름도이다.
도 2b 내지 도 2c는 임의의 노드 쌍으로 정의되는 링크 및 경로의 구조를 도시하는 예시도이다.
도 3은 기계 학습을 이용하여 링크 예측 모델을 학습하는 과정을 도시하는 흐름도이다.
도 4a는 일실시예에 따른 링크 예측 장치를 도시하는 블록도이다.
도 4b는 다른 일실시예에 따른 이질형 정보 그래프를 도시하는 예시도이다.
도 5는 일실시예에 따른 동료 노드를 나타내는 예시도이다.
도 6은 동료 노드의 개수를 이용하여 링크 예측 모델을 기계 학습하는 과정을 도시하는 흐름도이다.
도 7은 다른 일실시예에 따른 링크 예측 장치를 도시하는 블록도이다.
실시예들에 대한 특정한 구조적 또는 기능적 설명들은 단지 예시를 위한 목적으로 개시된 것으로서, 다양한 형태로 변경되어 실시될 수 있다. 따라서, 실시예들은 특정한 개시형태로 한정되는 것이 아니며, 본 명세서의 범위는 기술적 사상에 포함되는 변경, 균등물, 또는 대체물을 포함한다.
제1 또는 제2 등의 용어를 다양한 구성요소들을 설명하는데 사용될 수 있지만, 이런 용어들은 하나의 구성요소를 다른 구성요소로부터 구별하는 목적으로만 해석되어야 한다. 예를 들어, 제1 구성요소는 제2 구성요소로 명명될 수 있고, 유사하게 제2 구성요소는 제1 구성요소로도 명명될 수 있다.
어떤 구성요소가 다른 구성요소에 "연결되어" 있다고 언급된 때에는, 그 다른 구성요소에 직접적으로 연결되어 있거나 또는 접속되어 있을 수도 있지만, 중간에 다른 구성요소가 존재할 수도 있다고 이해되어야 할 것이다.
단수의 표현은 문맥상 명백하게 다르게 뜻하지 않는 한, 복수의 표현을 포함한다. 본 명세서에서, "포함하다" 또는 "가지다" 등의 용어는 설시된 특징, 숫자, 단계, 동작, 구성요소, 부분품 또는 이들을 조합한 것이 존재함으로 지정하려는 것이지, 하나 또는 그 이상의 다른 특징들이나 숫자, 단계, 동작, 구성요소, 부분품 또는 이들을 조합한 것들의 존재 또는 부가 가능성을 미리 배제하지 않는 것으로 이해되어야 한다.
다르게 정의되지 않는 한, 기술적이거나 과학적인 용어를 포함해서 여기서 사용되는 모든 용어들은 해당 기술 분야에서 통상의 지식을 가진 자에 의해 일반적으로 이해되는 것과 동일한 의미를 가진다. 일반적으로 사용되는 사전에 정의되어 있는 것과 같은 용어들은 관련 기술의 문맥상 가지는 의미와 일치하는 의미를 갖는 것으로 해석되어야 하며, 본 명세서에서 명백하게 정의하지 않는 한, 이상적이거나 과도하게 형식적인 의미로 해석되지 않는다.
이하, 실시예들을 첨부된 도면들을 참조하여 상세하게 설명한다. 첨부 도면을 참조하여 설명함에 있어, 도면 부호에 관계없이 동일한 구성 요소는 동일한 참조 부호를 부여하고, 이에 대한 중복되는 설명은 생략하기로 한다.
도 1은 일실시예에 따른 이질형 정보 그래프를 도시하는 예시도이다. 도 1은 참조하면, 복수의 노드 타입을 포함하는 이질형 정보 그래프가 도시된다. 이하의 설명에서 이질형 정보 그래프는 이질형 네트워크에 포함되는 복수의 노드 사이의 연결 관계를 도식화하는 그래프를 나타낼 수 있다. 예시적으로, 이질형 정보 그래프는 무방향(undirected) 이질형 정보 그래프일 수 있다.
또한, 이질형 네트워크는 서로 다른 타입(type)의 복수의 노드를 포함하고, 상기 노드의 쌍으로 정의되는 복수의 링크를 포함하는 네트워크를 나타낼 수 있다. 이질형 네트워크 내에서 서로 다른 타입의 노드 및 링크 각각은 서로 다른 시멘틱(semantic) 정보를 나타낼 수 있다. 일실시예로서, 이질형 네트워크가 소셜 네트워크인 경우에 각각의 노드는 사용자에 대응하는 성별 및 나이를 나타내는 개인 정보일 수 있고, 각각의 링크는 연인, 친구 등의 사용자의 관계를 나타내는 정보일 수 있다. 다른 일실시예로서, 이질형 네트워크가 생물학적 네트워크인 경우 각각의 노드는 단백질 구조, 약품 구조, 병원균 구조에 관한 정보일 수 있고, 각각의 링크는 상기 노드들 사이의 결합(binding), 치료(treat), 질병 원인(cause) 등에 관한 관계를 나타내는 정보일 수 있다. 위에서 기재한 이질형 네트워크에 관한 설명은 이해를 돕기 위한 예시적 기재일 뿐 다른 실시예의 범위를 제한하거나 한정하는 것으로 해석되어서는 안될 것이다.
도 1을 참조하면, 이질형 정보 그래프는 세 개의 노드 타입을 포함할 수 있다. 노드 타입이란 분류될 수 있는 각각의 노드가 가지는 타입을 나타낼 수 있다. 예시적으로, 이질형 정보 그래프는 제1 노드 타입 N1에 관한 제1 노드 n1(111) 및 제2 노드 n2(112)를 포함할 수 있다. 또한, 이질형 정보 그래프는 제2 노드 타입 N2에 관한 제3 노드 n3(121) 및 제4 노드 n4(122)를 포함할 수 있다. 또한, 이질형 정보 그래프는 제3 노드 타입 N3에 관한 제5 노드 n5(131) 및 제6 노드 n6(132)를 포함할 수 있다.
링크 타입은 노드 타입 쌍 (N1,N2)으로 정의되고 상기 노드 타입 사이의 관계를 나타낼 수 있다. 또한, 링크 타입 각각의 인스턴스(instance)를 링크로 정의할 수 있다. 도 1의 실시예에서는 노드 타입 쌍 (N1,N2)로 정의되는 제1 링크 타입 L1(141), 노드 타입 쌍 (N1,N3)으로 정의되는 제2 링크 타입 L2(142) 및 노드 타입 쌍 (N2,N3)으로 정의되는 제3 링크 타입 L3(143)이 도시된다.
경로 타입(P(N1,N2))은 두 노드 타입 사이의 시퀀스(sequence)를 나타낼 수 있고, 노드 타입과 링크 타입으로 이뤄질 수 있다. 보다 구체적으로, P(N1,N2)는 (N1,L1,…,Ln-1,N2)로 정의될 수 있다. 경로 타입 내에서 N1,…,Nn은 상기 경로 타입에 포함되는 노드 타입을 나타내고, L1,…,Ln -1은 상기 경로 타입에 포함되는 경로 타입을 나타낼 수 있다. 본 실시예 상에서 제1 노드(111) 및 제3 노드(121) 사이에는 제1 경로 타입 P1(111,121)이 존재할 수 있다. 보다 구체적으로, 제1 경로 타입 P1(111,121)은 제1 노드 타입 N1, 제1 링크 타입 L1(141), 제3 노드 타입 N3, 제2 링크 타입 L2(142), 제2 노드 타입 N2를 포함할 수 있다. 이하의 설명에서, 경로 예측 장치는 제1 노드(110) 및 제3 노드(121) 사이에 존재하는 제1 경로 타입 P1(111,121)에 기초하여 숨겨진 링크(160)의 존재 여부를 예측할 수 있다. 경로 타입 및 링크 타입 사이의 상관도에 기초하여 숨겨진 링크(160)를 예측하는 과정에 관한 보다 구체적인 설명은 이하에서 추가되는 도면과 함께 보다 자세하게 기재될 것이다.
도 2a는 경로 타입과 링크 타입의 상관도를 계산하는 과정을 도시하는 흐름도이다. 도 2a를 참조하면, 경로 타입과 링크 타입의 상관도를 계산하는 방법은 입력 그래프를 이용하여 네트워크 내의 소스 노드 및 타겟 노드 사이의 존재 가능한 경로 타입을 추출하는 단계(210) 및 상기 소스 노드 및 상기 타겟 노드의 조합에 따른 경로 타입과 링크 타입의 상관도를 계산하는 단계(220)를 포함할 수 있다.
단계(210)에서 경로 예측 장치는 경로 예측의 대상이 되는 입력 그래프를 전달 받을 수 있다. 일실시예로서, 상기 입력 그래프는 복수의 노드 타입 및 상기 노드 타입의 쌍으로 각각 정의되는 복수의 링크 타입을 포함하는 무방향 이질형 그래프를 나타낼 수 있다. 또한 상기 입력 그래프는 복수의 노드를 정의하는 제1 데이터 필드, 상기 복수의 노드들의 연결 관계를 정의하는 제2 데이터 필드, 복수의 노드 타입 각각을 정의하는 제3 데이터 필드 및 복수의 링크 타입 각각을 정의하는 제4 데이터 필드를 포함하는 스키마 데이터(schema data)를 포함할 수 있다. 경로 예측 장치는 전달된 스키마 데이터에 기초하여 소스 노드와 타겟 노드 사이에 존재 가능한 경로 타입을 추출할 수 있다. 보다 구체적으로, 경로 예측 장치는 스키마 그래프를 생성하고, 너비 우선 탐색을 수행하여 각각의 노드 타입 쌍으로 정의되는 존재 가능한 경로 타입을 추출할 수 있다.
단계(220)에서 경로 예측 장치는 경로 타입과 링크 타입의 상관도를 계산할 수 있다. 경로 예측 장치는 입력 그래프가 포함되는 네트워크의 전체 그래프를 이용하여 상기 상관도를 계산할 수 있다. 보다 구체적으로, 경로 예측 장치는 입력 그래프가 포함되는 전체 네트워크 내에서 특정 경로 타입과 특정 링크 타입이 동시에 존재하는 구조체의 비율을 이용하여 경로 타입과 링크 타입 사이의 상관도를 계산할 수 있다.
보다 구체적으로, 경로 예측 장치는 상관도 Corrpl을 링크 타입과 경로 타입의 쌍 (Li, Pi)(i는 1 이상 임의의 정수 n 이하의 정수)에 따라 정의할 수 있다. 하나의 노드 타입 쌍 (N1,N2)은 하나의 링크 타입 L=(N1,N2)과 적어도 하나의 경로 타입 P1,P2, … ,Pn을 결정할 수 있다.
예시적으로, 입력 그래프 G(V,E)에 존재하는 제1 경로 P1이 제1 경로 타입(N1,N2)에 포함되고, 제1 링크 L1이 제1 링크 타입(N1,N2)에 포함된 경우가 존재할 수 있다. 입력 그래프 G(V,E)에서 V는 입력 그래프 G에 포함되는 노드의 전체 집합을 나타낼 수 있다. 또한 입력 그래프 G(V,E)에서 E는 노드의 전체 집합 및 상기 노드의 전체 집합에 대한 카테시안 곱(Cartesian product) V
Figure 112017011906795-pat00001
V의 부분 집합으로서, 노드 타입의 쌍으로 정의되는 링크의 전체 집합을 나타낼 수 있다. 이하의 설명에서, 링크 예측은 현재 네트워크에서 발견되지 않은 링크인 I∈V
Figure 112017011906795-pat00002
V??E의 잠재적인 존재 여부를 예측하는 과정을 나타낼 수 있다. 또한, 입력 그래프 G(V,E)에는 제1 노드 타입 N1에 포함되는 소스 노드 s 및 제2 노드 타입 N2에 포함되는 타겟 노드 t가 포함될 수 있다.
링크 예측 장치는 제1 링크 타입(N1,N2)에 대응하는 제1 링크 L1(s,t)와 제1 경로 타입 P1(N1,N2)에 대응하는 경로의 존재 여부를 이용하여 경로 타입과 링크 타입의 상관도를 계산할 수 있다. 링크 예측 장치가 상관도를 계산하는 과정에 관한 구체적인 설명은 이하에서 추가되는 도면과 함께 보다 상세히 설명될 수 있다.
도 2b 내지 도 2c는 임의의 노드 쌍으로 정의되는 링크 및 경로의 구조를 도시하는 예시도이다. 임의의 노드 쌍인 소스 노드 s 및 타겟 노드 t 사이에 존재 가능한 구조체의 경우의 수는 아래의 표 1과 같이 표시될 수 있다.
경로 타입 P 링크 타입 L 구조 이름
1 1 Cycle
0 1 LinkOnly
1 0 PathOnly
상기 표 1의 첫 번째 열은 소스 노드 s 및 타겟 노드 t 사이에 경로 타입이 P인 경로의 존재 유무를 나타내는 제1 대표값을 의미할 수 있다. 상기 제1 대표값이 1인 경우에는 경로가 존재하는 경우를 나타내고, 상기 제1 대표값이 0인 경우에는 경로가 존재하지 않는 경우를 나타낼 수 있다. 상기 표 2의 두 번째 열은 소스 노드 s 및 타겟 노드 t 사이에 링크 타입이 L인 링크의 존재 유무를 나타내는 제2 대표값을 의미할 수 있다. 상기 제2 대표값이 1인 경우에는 링크가 존재하는 경우를 나타내고, 상기 제2 대표값이 0인 경우에는 링크가 존재하지 않는 경우를 나타낼 수 있다.
도 2b는 상기 표 1에서 도시된 Cycle 구조를 나타낼 수 있다. 경로 타입 P 및 링크 타입 L 각각에 관한 제1 대표값 및 제2 대표값 모두가 1인 경우로서, 소스 노드 s 및 타겟 노드 t 사이에 상응하는 타입의 경로 및 링크 모두가 존재하는 경우를 실선으로 도시할 수 있다.
도 2c는 상기 표 1에서 도시된 LinkOnly 구조를 나타낼 수 있다. 경로 타입 P에 관한 제1 대표값은 0이고, 링크 타입 L에 관한 제2 대표값은 1인 경우로서, 소스 노드 s 및 타겟 노드 t 사이에 상응하는 타입의 링크만이 존재하는 경우를 도시할 수 있다. 존재하지 않는 경로는 점선으로 도시된다.
도 2d는 상기 표 1에서 도시된 PathOnly 구조를 나타낼 수 있다. 경로 타입 P에 관한 제1 대표값은 1이고, 링크 타입 L에 관한 제2 대표값은 0인 경우로서, 소스 노드 s 및 타겟 노드 t 사이에 상응하는 타입의 경로만이 존재하는 경우를 도시할 수 있다. 마찬가지로, 존재하지 않는 링크는 점선으로 도시된다.
본 실시예에 따른 경로 예측 장치는 아래의 수학식 1에 따라 경로 타입 P 및 링크 타입 L 사이의 상관도를 계산해낼 수 있다.
Figure 112017011906795-pat00003
경로 예측 장치는 전체 네트워크 내에서 소스 노드 s 및 타겟 노드 t 사이에 존재하는 구조체의 경우의 수로부터 경로 타입 P 및 링크 타입 L에 상응하는 각각의 경로 및 링크가 동시에 존재하는 Cycle의 구조체의 비율을 계산할 수 있다. 또한, 경로 예측 장치는 계산된 구조체의 비율을 이용하여 상관도 Corrpl(경로 타입 P, 링크 타입 L)을 계산해낼 수 있다. 본 실시예에 따른 경로 예측 장치는 상기 수학식 1에 따라 계산된 상관도 Corrpl(경로 타입 P, 링크 타입 L)를 특징값으로 하여 숨겨진 경로를 예측하기 위한 가중치를 기계 학습할 수 있다. 그에 따라, 상기 경로 예측 장치는 임의의 두 노드 사이에 의미상 관계 있는 경로 타입이 존재하는 경우에 특정 링크가 존재할 확률이 높아지는 현실 세계의 시멘틱을 반영할 수 있어 링크 예측의 정확도가 높아지는 효과를 기대할 수 있다.
도 3은 기계 학습을 이용하여 링크 예측 모델을 학습하는 과정을 도시하는 흐름도이다. 도 3을 참조하면, 기계 학습을 이용하여 경로 타입 별 가중치를 학습하는 방법은 샘플링된 로우 데이터를 이용하여 기계 학습을 수행하기 위한 특징 벡터 및 상기 특징 벡터에 대응하는 라벨을 추출하는 단계(310) 및 상기 특징 벡터 및 상기 라벨을 이용하여 상관도를 적용한 링크 예측 모델을 학습하는 단계(320)를 포함할 수 있다.
단계(310)에서 경로 예측 장치는 기계 학습을 수행하기 위한 특징 벡터를 생성할 수 있다. 일실시예로서, 특징 벡터는 전체 네트워크 내에 존재 가능한 각각의 링크 타입 별로 생성될 수 있다. 보다 구체적으로, 특징 벡터의 행은 예측 하고자 하는 링크의 소스 노드 타입에 대응하는 노드 집합과 타겟 노드 타입에 대응하는 노드 집합의 카테시안 곱 집합을 나타낼 수 있다. 또한, 특징 벡터의 열은 소스 노드 타입과 타겟 노드 타입 사이에 존재 가능한 경로 타입을 나타낼 수 있다. 예시적으로, 특징으로는 소스 노드와 타겟 노드 사이에 존재하는 경로의 개수가 이용될 수 있다.
또한, 경로 예측 장치는 생성된 특징 벡터에 대응하는 라벨(label) 값을 추출할 수 있다. 경로 예측 장치는 전체 네트워크에 대응하는 스키마 데이터를 이용하여 특정 경로 타입을 갖는 두 노드 사이에 링크가 존재하는 경우에 상기 라벨을 1로 설정하고, 링크가 존재하지 않는 경우에 상기 라벨을 -1로 설정할 수 있다. 위의 라벨 값 설정에 관한 내용은 이해를 돕기 위한 예시적 기재일 뿐, 다른 실시예의 범위를 제한하거나 한정하는 것으로 해석되어서는 안될 것이다.
단계(320)에서 경로 예측 장치는 생성된 특징 벡터들 중에서 임의적으로 샘플링된 특징 벡터를 추출할 수 있다. 또한, 경로 예측 장치는 샘플링된 특징 벡터와 미리 추출된 라벨 값을 이용하여 경로 타입 및 링크 타입 사이의 상관 정도 Corrpl를 적용한 기계 학습을 수행할 수 있다.
일실시예로서, 경로 예측 장치는 랜덤 포레스트 방법을 이용하여 기계 학습을 수행할 수 있다. 보다 구체적으로, 경로 예측 장치는 특징과 라벨을 포함하는 훈련 데이터를 정확하게 분류하기 위한 다수의 결정 트리를 생성할 수 있다. 결정 트리는 데이터의 라벨을 판단하기 위해 이용되고, 데이터의 분류 조건을 트리 형태로 표현한 그래프를 나타낼 수 있다. 기계 학습 방법 중 랜덤 포레스트는 이해를 돕기 위한 예시적 기재일 뿐, 다른 기계 학습의 실시예가 본 사상에 적용되는 것을 제한하거나 한정하는 것으로 해석되어서는 안될 것이다.
도 4a는 일실시예에 따른 링크 예측 장치를 도시하는 블록도이다. 도 4a를 참조하면, 링크 예측 장치(400)는 생성부(410) 및 예측부(420)를 포함할 수 있다. 생성부(410) 및 예측부(420) 각각은 프로세서로 구현되고, 적어도 일시적으로 구현될 수 있다. 생성부(410)는 입력 그래프의 데이터를 이용하여 소스 노드 및 타겟 노드 사이에 존재하는 적어도 하나의 경로 타입을 특징 벡터로 생성할 수 있다. 보다 구체적으로, 생성부(410)는 상기 입력 그래프의 스키마 데이터를 이용하여 상기 소스 노드 및 상기 타겟 노드를 연결하는 노드 및 링크의 시퀀스를 추출하고, 상기 추출된 시퀀스를 상기 특징 벡터로서 생성할 수 있다.
또한, 생성부(410)는 복수의 노드 타입과 상기 노드 타입의 쌍에 따라 결정되는 복수의 경로 타입을 포함하는 이질형 정보 그래프를 상기 입력 데이터로서 전달받을 수 있다.
예측부(420)는 상기 특징 벡터에 학습된 결과인 링크 예측 모델을 적용하여 상기 소스 노드 및 상기 타겟 노드 사이의 링크(link)의 존재를 예측할 수 있다. 예측부(420)는 상기 입력 그래프가 포함되는 네트워크의 로우 데이터와 상관도를 이용하여 기계 학습된 상기 링크 예측 모델을 기반으로 링크 예측을 수행할 수 있다. 상관도를 계산하고, 상기 상관도에 따른 링크 예측 모델을 학습하는 과정에 관한 자세한 설명은 앞서 도 3에서 설명된 내용이 그대로 적용될 수 있기 때문에 중복되는 설명은 생략하기로 한다.
일실시예로서, 상기 가중치는 기계 학습의 결과 데이터로서 미리 정의한 에러 함수를 최소화하기 위한 복수의 결정 트리의 분기값을 나타낼 수 있다. 예측부(420)는 생성된 특징 벡터에 미리 학습된 복수의 결정 트리를 적용하여 예측된 라벨 값을 생성할 수 있다. 또한, 예측부(420)는 예측된 라벨 중 가장 많은 수의 라벨을 해당 특징 벡터의 최종 라벨로 선정하고, 데이터의 분류를 수행할 수 있다.
도 4b는 다른 일실시예에 따른 이질형 정보 그래프를 도시하는 예시도이다. 도 4b를 참조하면, 경로 예측 장치에 의해 경로 예측이 수행되는 이질형 정보 네트워크의 예시도가 도시된다. 이질형 정보 네트워크는 약품에 대응하는 Drug 노드(431, 451), 질병에 대응하는 Disease 노드(433, 453), 타겟 단백질 구조에 대응하는 Target 노드(435, 455)를 포함할 수 있다. 또한, 이질형 정보 네트워크는 Drug 노드(451)와 Disease 노드(453)를 연결하는 treat 링크(452) 및 Disease 노드(453)와 Target 노드(455)를 연결하는 cause 링크(454)를 포함할 수 있다.
본 실시예의 링크 예측 장치는 제1 Drug 노드(451) 및 제1 Target 노드(455) 사이에 bind(결합) 링크(460)가 존재하는지 여부를 예측할 수 있다. 링크 예측 장치는 제1 Drug 노드(451) 및 제1 Target 노드(455) 사이에 존재 가능한 경로 타입의 경우의 수를 계산할 수 있다. 본 실시예에 도시된 것과 같이, Drug 노드(451, 431) 및 Target 노드(435, 455) 사이에는 Drug 노드, treat 링크, Disease 노드, cause 링크, Target 노드를 연결하는 제1 경로 타입과 belong to 링크와 react 링크를 포함하는 제2 경로 타입이 존재할 수 있다.
링크 예측 장치는 각각의 경로 타입에 따라 경로와 링크가 동시에 존재하는 구조체의 비율을 상관도로서 계산할 수 있다. 앞서 기재한 바와 같이, 상관도 계산에 있어서 제2 Drug 노드(431) 및 제2 Target 노드(435) 사이에 존재하는 bind 링크(440)가 기계 학습의 훈련 데이터로서 미리 이용될 수 있다. 본 실시예에 따른 링크 예측 장치는 전체 네트워크 내에 존재하는 링크 타입 및 경로 타입 사이의 상관도에 따른 링크 예측 모델을 미리 기계 학습할 수 있다. 구체적으로, 링크 예측 장치는 bind 링크(440)의 존재를 이용하여 상관도를 고려한 링크 예측 모델을 미리 기계 학습하고, bind 링크(460)의 존재 여부를 예측하는데 상기 링크 예측 모델을 이용하여 링크 예측의 정확도를 높이는 효과를 제공할 수 있다.
도 5는 일실시예에 따른 동료 노드를 나타내는 예시도이다. 도 5를 참조하면, 링크 예측 장치에 의해 링크 예측이 수행되는 이질형 정보 네트워크의 예시도가 도시된다. 링크 예측 장치는 입력 그래프를 이용하여 소스 노드(510) 및 타겟 노드(520) 사이의 숨겨진 링크(540)의 존재 여부를 예측할 수 있다.
링크 예측 장치는 입력 그래프로부터 동료 노드(colleague node)를 정의할 수 있다. 보다 구체적으로, 링크 예측 장치는 두 노드가 서로 동일한 타입이고, 적어도 하나의 공통 이웃 노드를 공유하고 잇는 경우에, 상기 두 노드를 서로의 동료 노드로서 정의할 수 있다. 예시적으로, 소스 노드 s의 동료 노드의 집합은 Colleagues(s)로 나타낼 수 있다. 도 5의 실시예에서, 노드를 나타내는 형태가 동일한 경우에 서로 동일한 노드 타입을 나타낸다고 하면, 링크 예측 장치는 소스 노드 s(510)에 관한 동료 노드 집합 Colleagues(s)을 {n1(531),n2(532),n3(533)}와 같이 계산해낼 수 있다.
Colleagues(s)는 n개의 부분적으로 겹치는(overlapping) 부분집합 Colleagues1(s), Colleagues2(s),…, Colleaguesn(s)으로 각각 분리될 수 있다. 이 경우에 Colleaguesi(s)는 s와 i개 또는 그 이상의 공통 이웃 노드를 공유하는 동료 집합을 나타내고, i는 1 이상 n 이하의 임의의 정수를 나타낼 수 있다.
도 5에서 설명되는 실시예에서는 Colleagues1(s)은 {n1(531),n2(532),n3(533)}이고, Colleagues2(s)는 {n3(533)}을 나타낼 수 있다. 보다 구체적으로, Colleagues1(s)의 원소들은 소스 노드 s(510)와 1개 또는 그 이상의 공통 이웃 노드를 공유하는 노드를 나타낼 수 있다. 또한, Colleagues2(s)의 원소들은 소스 노드 s(510)와 2개 또는 그 이상의 공통 이웃 노드를 공유하는 노드를 나타낼 수 있다. Colleagues2(s)는 Colleagues1(s)와 대비하여 소스 노드 s와 동일하거나 더욱 유사한 특징을 나타내는 경향이 존재한다.
도 6은 동료 노드의 개수를 이용하여 링크 예측을 위한 가중치를 기계 학습하는 과정을 도시하는 흐름도이다. 도 6을 참조하면, 동료 노드의 개수를 이용하여 링크 예측을 위한 모델을 기계 학습하는 방법은 입력 그래프를 이용하여 네트워크 내의 소스 노드 및 타겟 노드의 조합에 따른 라벨을 추출하는 단계(610) 및 상기 소스 노드 및 상기 타겟 노드의 조합에 따른 동료 노드의 개수를 이용하여 링크 예측모델을 학습하는 단계(620)를 포함할 수 있다.
단계(610)에서 경로 예측 장치는 기계 학습을 수행하기 위한 특징 벡터를 생성할 수 있다. 일실시예로서, 경로 예측 장치는 상기 특징 벡터의 행을 예측 하고자 하는 링크의 소스 노드 타입에 대응하는 노드 집합 및 상기 링크의 타겟 노드 타입에 대응하는 노드 집합의 카테시안 곱 집합으로 정의할 수 있다. 또한, 경로 예측 장치는 각각의 특징을 상기 특징 벡터의 열로서 정의할 수 있다. 경로 예측 장치는 기계 학습을 수행하기 위한 특징으로는 동료 노드 집합을 이용할 수 있다.
예시적으로, 경로 예측 장치가 소스 노드 s와 타겟 노드 t 사이의 링크를 예측하는 경우가 존재할 수 있다. 이 경우에, Colleagues(s) 중 임계 개수 이상의 원소가 타겟 노드 t와 직접적으로 연결을 갖는 이웃 노드라면 소스 노드 s와 타겟 노드 t 사이에 숨겨진 링크가 존재할 가능성은 증가할 것이다. 마찬가지로, Colleagues(t) 중 임계 개수 이상의 원소가 소스 노드 s와 직접적으로 연결을 갖는 이웃 노드라면 마찬가지로 소스 노드 s와 타겟 노드 t 사이에 숨겨진 링크가 존재할 가능성은 증가할 것이다.
본 실시예의 링크 예측 장치는 타겟 노드 t의 이웃 노드이고, Colleagues(s)의 원소인 노드 집합(Neighbors(t)∩Colleaguesi(s))을 소스 노드 s의 인접 동료 집합으로 정의할 수 있다. 링크 예측 장치는 이 집합의 원소의 개수 |Neighbors(t)∩Colleaguesi(s)|를 링크 예측을 위한 특징으로 이용할 수 있다.
다른 일실시예로서, 링크 예측 장치는 소스 노드 s의 이웃 노드이고, Colleagues(t)의 원소인 노드 집합(Neighbors(s)∩Colleaguesi(t))를 타겟 노드 t의 인접 동료 집합으로 정의할 수 있다. 링크 예측 장치는 이 집합의 원소의 개수 |Neighbors(s)∩Colleaguesi(t)|를 링크 예측을 위한 특징으로 이용할 수 있다.
단계(620)에서 링크 예측 장치는 상기 소스 노드 및 상기 타겟 노드의 조합에 따른 동료 노드의 개수를 이용하여 링크 예측 모델을 학습할 수 있다. 보다 구체적으로, 링크 예측 장치는 앞서 기재한 설명과 같이 타겟 노드의 인접 동료 집합의 개수 및 소스 노드의 인접 동료 집합의 개수 중 적어도 어느 하나를 특징으로 이용하여 기계 학습을 수행할 수 있다. 기계 학습 과정에 관한 자세한 설명은 앞서 도 3에 관한 설명이 그대로 적용될 수 있기 때문에 중복되는 설명은 생략하기로 한다.
도 7은 다른 일실시예에 따른 링크 예측 장치를 도시하는 블록도이다. 링크 예측 장치(700)는 생성부(710) 및 예측부(720)를 포함할 수 있다. 생성부(710)는 입력 그래프의 데이터를 이용하여 소스 노드 및 타겟 노드의 조합에 따른 동료 노드의 개수를 특징 벡터로 생성할 수 있다. 생성부(710)는 복수의 노드 타입과 상기 노드 타입의 쌍에 따라 결정되는 복수의 경로 타입을 포함하는 이질형 정보 그래프를 상기 입력 데이터로서 전달 받을 수 있다. 또한, 생성부(710)는 상기 특징 벡터를 이용하여 링크 예측 모델을 학습할 수 있다.
예측부(720)는 상기 특징 벡터에 학습된 결과 데이터인 링크 예측 모델을 이용하여 상기 소스 노드 및 상기 타겟 노드 사이의 링크(link)의 존재를 예측할 수 있다. 예측부(720)는 링크의 존재 유무에 따라 제1 결과값 및 제2 결과값 중 어느 하나를 출력할 수 있다. 예시적으로, 예측부(720)는 링크가 존재하는 제1 결과값으로서 1을 출력하고, 링크가 존재하지 않는 경우에 제2 결과값으로서 0을 출력할 수 있다. 상기 링크 예측 모델은 상기 소스 노드 및 상기 타겟 노드 각각의 이웃 노드 및 동료 노드를 이용하여 기계 학습된 결과일 수 있다. 상기 동료 노드는 두 개의 노드가 동일한 타입을 나타내고, 적어도 하나의 이웃 노드를 서로 공유 하는 경우를 나타낼 수 있다.
예측부(720)는 상기 타겟 노드의 이웃 노드이고, 설정 개수 이상의 공통 이웃 노드를 공유하는 동료 노드인 집합의 원소의 개수를 특징으로서 기계 학습된 링크 예측 모델을 적용하여 링크 노드의 존재 가능성을 예측할 수 있다.
또한, 예측부(720)는 상기 소스 노드의 이웃 노드이고, 상기 타겟 노드의 동료 노드인 집합의 원소 개수에 대응하는 링크 노드의 존재 가능성을 예측할 수 있다.
이상에서 설명된 실시예들은 하드웨어 구성요소, 소프트웨어 구성요소, 및/또는 하드웨어 구성요소 및 소프트웨어 구성요소의 조합으로 구현될 수 있다. 예를 들어, 실시예들에서 설명된 장치, 방법 및 구성요소는, 예를 들어, 프로세서, 콘트롤러, ALU(arithmetic logic unit), 디지털 신호 프로세서(digital signal processor), 마이크로컴퓨터, FPGA(field programmable gate array), PLU(programmable logic unit), 마이크로프로세서, 또는 명령(instruction)을 실행하고 응답할 수 있는 다른 어떠한 장치와 같이, 하나 이상의 범용 컴퓨터 또는 특수 목적 컴퓨터를 이용하여 구현될 수 있다. 처리 장치는 운영 체제(OS) 및 상기 운영 체제 상에서 수행되는 하나 이상의 소프트웨어 애플리케이션을 수행할 수 있다. 또한, 처리 장치는 소프트웨어의 실행에 응답하여, 데이터를 접근, 저장, 조작, 처리 및 생성할 수도 있다. 이해의 편의를 위하여, 처리 장치는 하나가 사용되는 것으로 설명된 경우도 있지만, 해당 기술분야에서 통상의 지식을 가진 자는, 처리 장치가 복수 개의 처리 요소(processing element) 및/또는 복수 유형의 처리 요소를 포함할 수 있음을 알 수 있다. 예를 들어, 처리 장치는 복수 개의 프로세서 또는 하나의 프로세서 및 하나의 콘트롤러를 포함할 수 있다. 또한, 병렬 프로세서(parallel processor)와 같은, 다른 처리 구성(processing configuration)도 가능하다.
소프트웨어는 컴퓨터 프로그램(computer program), 코드(code), 명령(instruction), 또는 이들 중 하나 이상의 조합을 포함할 수 있으며, 원하는 대로 동작하도록 처리 장치를 구성하거나 독립적으로 또는 결합적으로(collectively) 처리 장치를 명령할 수 있다. 소프트웨어 및/또는 데이터는, 처리 장치에 의하여 해석되거나 처리 장치에 명령 또는 데이터를 제공하기 위하여, 어떤 유형의 기계, 구성요소(component), 물리적 장치, 가상 장치(virtual equipment), 컴퓨터 저장 매체 또는 장치, 또는 전송되는 신호 파(signal wave)에 영구적으로, 또는 일시적으로 구체화(embody)될 수 있다. 소프트웨어는 네트워크로 연결된 컴퓨터 시스템 상에 분산되어서, 분산된 방법으로 저장되거나 실행될 수도 있다. 소프트웨어 및 데이터는 하나 이상의 컴퓨터 판독 가능 기록 매체에 저장될 수 있다.
실시예에 따른 방법은 다양한 컴퓨터 수단을 통하여 수행될 수 있는 프로그램 명령 형태로 구현되어 컴퓨터 판독 가능 매체에 기록될 수 있다. 컴퓨터 판독 가능 매체는 프로그램 명령, 데이터 파일, 데이터 구조 등을 단독으로 또는 조합하여 포함할 수 있다. 컴퓨터 판독 가능 매체에 기록되는 프로그램 명령은 실시예를 위하여 특별히 설계되고 구성된 것들이거나 컴퓨터 소프트웨어 당업자에게 공지되어 사용 가능한 것일 수도 있다. 컴퓨터 판독 가능 기록 매체의 예에는 하드 디스크, 플로피 디스크 및 자기 테이프와 같은 자기 매체(magnetic media), CD-ROM, DVD와 같은 광기록 매체(optical media), 플롭티컬 디스크(floptical disk)와 같은 자기-광 매체(magneto-optical media), 및 롬(ROM), 램(RAM), 플래시 메모리 등과 같은 프로그램 명령을 저장하고 수행하도록 특별히 구성된 하드웨어 장치가 포함된다. 프로그램 명령의 예에는 컴파일러에 의해 만들어지는 것과 같은 기계어 코드뿐만 아니라 인터프리터 등을 사용해서 컴퓨터에 의해서 실행될 수 있는 고급 언어 코드를 포함한다. 상기된 하드웨어 장치는 실시예의 동작을 수행하기 위해 하나 이상의 소프트웨어 모듈로서 작동하도록 구성될 수 있으며, 그 역도 마찬가지이다.
이상과 같이 실시예들이 비록 한정된 도면에 의해 설명되었으나, 해당 기술분야에서 통상의 지식을 가진 자라면 상기를 기초로 다양한 기술적 수정 및 변형을 적용할 수 있다. 예를 들어, 설명된 기술들이 설명된 방법과 다른 순서로 수행되거나, 및/또는 설명된 시스템, 구조, 장치, 회로 등의 구성요소들이 설명된 방법과 다른 형태로 결합 또는 조합되거나, 다른 구성요소 또는 균등물에 의하여 대치되거나 치환되더라도 적절한 결과가 달성될 수 있다.

Claims (13)

  1. 프로세서로 구현되는:
    입력 그래프의 데이터를 이용하여 소스 노드 및 타겟 노드 사이에 존재하는 적어도 하나의 경로 타입을 특징 벡터로 생성하는 생성부; 및
    상기 특징 벡터에 학습된 결과인 링크 예측 모델을 적용하여 상기 소스 노드 및 상기 타겟 노드 사이의 링크(link)의 존재를 예측하는 예측부
    를 포함하고,
    상기 생성부는 복수의 노드를 정의하는 제1 데이터 필드, 상기 복수의 노드들의 연결 관계를 정의하는 제2 데이터 필드, 복수의 노드 타입 각각을 정의하는 제3 데이터 필드 및 복수의 링크 타입 각각을 정의하는 제4 데이터 필드를 포함하는 스키마 데이터를 이용하여 상기 소스 노드 및 상기 타겟 노드를 연결하는 노드 및 링크의 시퀀스를 추출하고, 상기 추출된 시퀀스를 상기 특징 벡터로서 생성하고,
    상기 예측부는, 상기 입력 그래프가 포함되는 네트워크 내에서 특정 경로 타입과 특정 링크 타입이 동시에 존재하는 구조체의 비율을 이용하여 계산된 상관도를 가중치로서 적용하고, 기계 학습된 링크 예측 모델을 이용하여 링크의 존재를 예측하는 경로 예측 장치.
  2. 삭제
  3. 제1항에 있어서,
    상기 생성부는 복수의 노드 타입과 상기 노드 타입의 쌍에 따라 결정되는 복수의 경로 타입을 포함하는 이질형 정보 그래프(heterogeneous information graph)를 상기 입력 그래프의 데이터로서 전달 받는 경로 예측 장치.
  4. 제1항에 있어서,
    상기 예측부는,
    상기 입력 그래프가 포함되는 네트워크의 로우 데이터를 이용하여 기계 학습된 링크 예측 모델을 생성하는 경로 예측 장치.
  5. 삭제
  6. 제1항에 있어서,
    상기 예측부는,
    상기 기계 학습이 진행되는 경우에 상기 가중치로서, 제1 노드 및 제2 노드를 연결하는 제1 경로 타입의 제1 경로가 존재하는 경우에 각각의 링크 타입의 링크가 존재할 상관도를 적용하는 경로 예측 장치.
  7. 제1항에 있어서,
    상기 예측부는 상기 입력 그래프의 타입에 따라 미리 저장된 기계 학습의 결과 데이터 중 제1 링크 예측 모델을 선택하여 상기 링크의 존재를 예측하는 경로 예측 장치.
  8. 프로세서로 구현되는:
    입력 그래프의 데이터를 이용하여 소스 노드 및 타겟 노드 사이에 존재하는 적어도 하나의 경로 타입을 특징 벡터로 생성하는 생성부; 및
    상기 특징 벡터에 학습된 결과인 링크 예측 모델을 적용하여 상기 소스 노드 및 상기 타겟 노드 사이의 링크(link)의 존재를 예측하는 예측부
    를 포함하고,
    상기 링크 예측 모델은 상기 소스 노드 및 상기 타겟 노드 각각의 이웃 노드 및 동료 노드를 이용하여 기계 학습되고,
    상기 생성부는 복수의 노드를 정의하는 제1 데이터 필드, 상기 복수의 노드들의 연결 관계를 정의하는 제2 데이터 필드, 복수의 노드 타입 각각을 정의하는 제3 데이터 필드 및 복수의 링크 타입 각각을 정의하는 제4 데이터 필드를 포함하는 스키마 데이터를 이용하여 상기 소스 노드 및 상기 타겟 노드를 연결하는 노드 및 링크의 시퀀스를 추출하고, 상기 추출된 시퀀스를 상기 특징 벡터로서 생성하고,
    상기 예측부는, 상기 입력 그래프가 포함되는 네트워크 내에서 특정 경로 타입과 특정 링크 타입이 동시에 존재하는 구조체의 비율을 이용하여 계산된 상관도를 가중치로서 적용하고, 기계 학습된 링크 예측 모델을 이용하여 링크의 존재를 예측하는 경로 예측 장치.
  9. 제8항에 있어서,
    상기 동료 노드는 두 개의 노드가 동일한 타입을 나타내고, 적어도 하나의 이웃 노드를 서로 공유 하는 경우를 나타내는 경로 예측 장치.
  10. 제8항에 있어서,
    상기 생성부는 복수의 노드 타입과 상기 노드 타입의 쌍에 따라 결정되는 복수의 경로 타입을 포함하는 이질형 정보 그래프를 상기 입력 그래프의 데이터로서 전달 받는 경로 예측 장치.
  11. 제9항에 있어서,
    상기 예측부는,
    상기 타겟 노드의 이웃 노드이고, 상기 소스 노드의 동료 노드인 노드의 개수에 대응하는 링크 노드의 존재 가능성을 기계 학습을 위한 특징으로서 적용하는 경로 예측 장치.
  12. 제11항에 있어서,
    상기 예측부는,
    상기 타겟 노드의 이웃 노드이고, 설정 개수 이상의 공통 이웃 노드를 공유하는 동료 노드인 노드의 개수에 대응하는 링크 노드의 존재 가능성을 기계 학습을 위한 특징으로서 적용하는 경로 예측 장치.
  13. 제9항에 있어서,
    상기 예측부는,
    상기 소스 노드의 이웃 노드이고, 상기 타겟 노드의 동료 노드인 노드의 개수에 대응하는 링크 노드의 존재 가능성을 기계 학습을 위한 특징으로서 적용하는 경로 예측 장치.
KR1020170015924A 2017-02-06 2017-02-06 링크 예측 장치 및 방법 Expired - Fee Related KR101922326B1 (ko)

Priority Applications (1)

Application Number Priority Date Filing Date Title
KR1020170015924A KR101922326B1 (ko) 2017-02-06 2017-02-06 링크 예측 장치 및 방법

Applications Claiming Priority (1)

Application Number Priority Date Filing Date Title
KR1020170015924A KR101922326B1 (ko) 2017-02-06 2017-02-06 링크 예측 장치 및 방법

Publications (2)

Publication Number Publication Date
KR20180091139A KR20180091139A (ko) 2018-08-16
KR101922326B1 true KR101922326B1 (ko) 2018-11-26

Family

ID=63443633

Family Applications (1)

Application Number Title Priority Date Filing Date
KR1020170015924A Expired - Fee Related KR101922326B1 (ko) 2017-02-06 2017-02-06 링크 예측 장치 및 방법

Country Status (1)

Country Link
KR (1) KR101922326B1 (ko)

Families Citing this family (7)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
CN109245952A (zh) * 2018-11-16 2019-01-18 大连理工大学 一种基于mpa模型的消失链路预测方法
KR102076763B1 (ko) 2018-12-10 2020-02-12 단국대학교 산학협력단 기댓값 최대화 기반 네트워크 임베딩을 활용한 링크 예측 장치 및 방법
CN114662786B (zh) * 2022-04-18 2025-09-16 兰州大学 一种基于层次化链接模式的多尺度链接预测方法和系统
CN115408584A (zh) * 2022-08-08 2022-11-29 浙江中烟工业有限责任公司 基于图结构的数据血缘链路节点相关性展示方法
CN116151461A (zh) * 2023-02-27 2023-05-23 中银金融科技有限公司 一种航空网络链路预测实现方法及相关设备
CN117151279A (zh) * 2023-08-15 2023-12-01 哈尔滨工业大学 一种基于线图神经网络的同构网络链路预测方法及系统
KR102784508B1 (ko) * 2024-01-23 2025-03-19 서울대학교산학협력단 포지티브-언라벨 데이터 학습 기반의 정확한 간선 예측 모델을 이용한 간선 예측 방법 및 장치

Also Published As

Publication number Publication date
KR20180091139A (ko) 2018-08-16

Similar Documents

Publication Publication Date Title
KR101922326B1 (ko) 링크 예측 장치 및 방법
US20230134742A1 (en) Deep neural network system for similarity-based graph representations
Zitnik et al. Predicting multicellular function through multi-layer tissue networks
Wistuba et al. Two-stage transfer surrogate model for automatic hyperparameter optimization
Rere et al. Metaheuristic algorithms for convolution neural network
CN116261731A (zh) 基于多跳注意力图神经网络的关系学习方法与系统
CN112396106B (zh) 内容识别方法、内容识别模型训练方法及存储介质
Mendonça et al. Approximating network centrality measures using node embedding and machine learning
Seijo-Pardo et al. Using data complexity measures for thresholding in feature selection rankers
Zhou et al. Make a long image short: Adaptive token length for vision transformers
Manoochehri et al. Graph convolutional networks for predicting drug-protein interactions
Claypo et al. Opinion mining for Thai restaurant reviews using neural networks and mRMR feature selection
CN113821676A (zh) 视频检索方法、装置、设备及存储介质
US11087060B1 (en) System, method, and computer program product for the integration of machine learning predictors in an automatic placement associated with an electronic design
Alsaeedi et al. A proactive grey wolf optimization for improving bioinformatic systems with high dimensional data
WO2024187142A2 (en) Data representation with cross-modality knowledge sharing
US11048852B1 (en) System, method and computer program product for automatic generation of sizing constraints by reusing existing electronic designs
Aleskerov et al. Stability and similarity in networks based on topology and nodes importance
Javaheripi et al. Swann: Small-world architecture for fast convergence of neural networks
US11669727B2 (en) Information processing device, neural network design method, and recording medium
Hsu et al. Class structure visualization with semi-supervised growing self-organizing maps
CN111459990B (zh) 对象处理方法、系统及计算机可读存储介质和计算机设备
US11275882B1 (en) System, method, and computer program product for group and isolation prediction using machine learning and applications in analog placement and sizing
JP2024509966A (ja) マルチメディアリソースの推薦方法、装置、機器、及びコンピュータプログラム
Allaparthi et al. An investigational study on implementing integrated frameworks of machine learning and evolutionary algorithms for solving real-world applications

Legal Events

Date Code Title Description
A201 Request for examination
PA0109 Patent application

St.27 status event code: A-0-1-A10-A12-nap-PA0109

PA0201 Request for examination

St.27 status event code: A-1-2-D10-D11-exm-PA0201

E902 Notification of reason for refusal
PE0902 Notice of grounds for rejection

St.27 status event code: A-1-2-D10-D21-exm-PE0902

E13-X000 Pre-grant limitation requested

St.27 status event code: A-2-3-E10-E13-lim-X000

P11-X000 Amendment of application requested

St.27 status event code: A-2-2-P10-P11-nap-X000

P13-X000 Application amended

St.27 status event code: A-2-2-P10-P13-nap-X000

PG1501 Laying open of application

St.27 status event code: A-1-1-Q10-Q12-nap-PG1501

E701 Decision to grant or registration of patent right
PE0701 Decision of registration

St.27 status event code: A-1-2-D10-D22-exm-PE0701

GRNT Written decision to grant
PR0701 Registration of establishment

St.27 status event code: A-2-4-F10-F11-exm-PR0701

PR1002 Payment of registration fee

St.27 status event code: A-2-2-U10-U11-oth-PR1002

Fee payment year number: 1

PG1601 Publication of registration

St.27 status event code: A-4-4-Q10-Q13-nap-PG1601

R18-X000 Changes to party contact information recorded

St.27 status event code: A-5-5-R10-R18-oth-X000

PN2301 Change of applicant

St.27 status event code: A-5-5-R10-R13-asn-PN2301

St.27 status event code: A-5-5-R10-R11-asn-PN2301

R18-X000 Changes to party contact information recorded

St.27 status event code: A-5-5-R10-R18-oth-X000

PR1001 Payment of annual fee

St.27 status event code: A-4-4-U10-U11-oth-PR1001

Fee payment year number: 4

P22-X000 Classification modified

St.27 status event code: A-4-4-P10-P22-nap-X000

PC1903 Unpaid annual fee

St.27 status event code: A-4-4-U10-U13-oth-PC1903

Not in force date: 20221121

Payment event data comment text: Termination Category : DEFAULT_OF_REGISTRATION_FEE

R18-X000 Changes to party contact information recorded

St.27 status event code: A-5-5-R10-R18-oth-X000

R18-X000 Changes to party contact information recorded

St.27 status event code: A-5-5-R10-R18-oth-X000

P22-X000 Classification modified

St.27 status event code: A-4-4-P10-P22-nap-X000

PC1903 Unpaid annual fee

St.27 status event code: N-4-6-H10-H13-oth-PC1903

Ip right cessation event data comment text: Termination Category : DEFAULT_OF_REGISTRATION_FEE

Not in force date: 20221121