링크 예측

네트워크 이론에서, 링크 예측은 네트워크에서 두 실체 사이의 링크의 존재를 예측하는 문제다.링크 예측의 예로는 소셜 네트워크에서 사용자들 간의 우정 관계 예측, 인용 네트워크에서의 공동 저술 링크 예측, 생물 네트워크에서의 유전자와 단백질 간의 상호 작용 예측 등이 있다.링크 예측은 시간적 측면도 가질 수 있는데, 여기서 시간 $[\displaystyle t}$에서 링크 집합의 스냅샷을 제공하면$$$t{\displaystyle }$+ $[\displaystyle t+1} 시간$에 링크를 예측하는 것이 목표다$.$ 링크 예측은 광범위하게 적용된다.전자상거래에서 링크 예측은 종종 사용자에게 항목을 추천하는 하위 작업이다.인용 데이터베이스 큐레이션에서는 기록 중복 제거에 사용할 수 있다.생물정보학에서는 단백질-단백질 상호작용(PPI)을 예측하는 데 사용되어 왔다.또한 보안 관련 애플리케이션에서 테러리스트와 범죄자의 숨겨진 집단을 식별하는 데도 사용된다.^[1]

문제 정의

네트워크 $G{\displaystyle }$=${\displaystyle }$( ${\displaystyle V}$, E${\displaystyle }$) ${\displaystyle G=(V,E)}$을(를) 고려하십시오$.$ $여기$서 V ${\displaystyle V}$은(는) 네트워크의 엔티티 노드를 나타내고$$ $E{\displaystyle }$ ${\displaystyle \subseteq }$ ${\displaystyle V}$ $displaystyle E\subseteq$V$}$ x ${\displaystyle V}$ $displaystytype V}$은 네트워크 내의 엔티티 간에 "true" 링크 집합을 나타낸다$$.관찰된 링크라고 하는 실제 $링크$의 일부와$$ V ${\displaystyle V}$ 엔티티 집합이 제공된다.링크 예측의 목표는 관찰되지 않은 실제 링크를 식별하는 것이다.링크 예측의 시간적 공식화에서 관찰된 링크는 한 번에 $t{\displaystyle }$ ${\displaystyle t$의 참 링크에${\displaystyle \mathrm{해당}}$하며$,$ 목표는 t + 1 {\displaystyle $t+1}$ 시간에 참 링크 집합을 추론하는 것이다. 보통$$, 우리는 또한 잠재적 $링크{\displaystyle {}^{}}$ E${\displaystyle {}^{}}$′ ${\$라고 불리는 관찰되지 않은 링크의 하위 집합도 제공받으며, 우리는 ID가 필요하다.이들 잠재적 연결고리 사이에 진정한 연계를 꾀하다.

링크 예측 과제의 이항 분류 공식에서 잠재적 링크는 참 링크 또는 거짓 링크로 분류된다.이 설정에 대한 링크 예측 접근방식은 $E{\displaystyle {}^{}}$ ${\displaystyle {\prime }^{}}$ ${\$의 링크를 양 및 음의 레이블에$$ 매핑하는$$ 분류자 $M{\displaystyle {}_{}}$ ${\displaystyle b_{}}$ ${\$을(를) 학습한다.${\displaystyle M_{b:$$E'\to \{0,1$ 확률 추정 공식에서 잠재적 연결은 존재 확률과 연관된다.이 설정에 대한 링크 예측 접근방식은 $E{\displaystyle {}^{}}$ ${\displaystyle {\prime }^{}}$ ${\$ E$'}$의 링크를 확률에$$ 매핑하는$$ 모델 $M{\displaystyle {}_{}}$ ${\displaystyle p_{}}$ ${\$ $M_$${p}$을 학습한다.${\displaystyle M_{p}:$$E'\$to [$0,1$

단일 링크 접근법은 각 링크를 독립적으로 분류하는 모델을 학습한다.구조화된 예측 접근방식은 작업을 집합적인 링크 예측 작업으로 구성함으로써 잠재적 링크 간의 상관관계를 포착한다.집합적 링크 예측 접근방식은 잠재적 링크 집합 사이의 모든 실제 링크를 공동으로 식별하는 모델을 학습한다.

링크 예측 태스크는 결측값 추정 태스크의 인스턴스로도 공식화될 수 있다.여기서 그래프는 결측값이 있는 인접 행렬로 표현된다.결측값을 식별하여 행렬을 완성하는 것이 과제다.행렬 인자화 기반 방법은 일반적으로 이 제형을 사용한다.

역사

연계 예측이라는 과제는 통계와 네트워크 과학에서부터 머신러닝, 데이터 마이닝에 이르기까지 여러 연구 커뮤니티로부터 주목을 받았다.통계에서 확률 블록 모델과 같은 생성 무작위 그래프 모델은 무작위 그래프에서 노드 사이의 링크를 생성하는 접근방식을 제안한다.소셜네트워크에 대해서는 리벤-노웰과 클라인버그가 서로 다른 그래프 근접도 측정에 기초한 링크 예측 모델을 제안했다.^[2]머신러닝과 데이터 마이닝 커뮤니티에 의한 링크 예측을 위해 몇 가지 통계 모델이 제안되었다.예를 들어, Popescul 등에서는 관계형 특성을 사용할 수 있는 구조화된 로지스틱 회귀 모형을 제안했다.^[3]속성 및 구조적 특징에 기반한 국소 조건부 확률 모델은 O'Madadhain et al Getuor에 의해 제안되었다 집합적 링크 예측을 위한 지시된 그래픽 모델에 기반한 여러 모델이 제안되었다.^[5]랜덤워크에 기반한 다른 접근법 및 매트릭스 인자화 또한 제안되었다. ^[6]딥러닝의 등장으로 링크 예측에 기반한 접근법을 포함한 여러 그래프도 제안되었다.^[8]링크 예측에 대한 자세한 내용은 Getuor 등 및 Yu 등 조사 자료를 참조하십시오.^[9][10]

접근법 및 방법

기업 속성에 대해 계산된 유사성 측정, 무작위 보행 및 매트릭스 인자화 접근법, 그래픽 모델과 심층 학습에 기초한 감독 접근법 등과 같은 감독되지 않은 접근법을 포함하여 여러 링크 약탈 접근법이 제안되었다.링크 예측 접근방식은 기반 네트워크의 유형에 따라 두 가지 광범위한 범주로 나눌 수 있다. (1) 동종 네트워크에 대한 링크 예측 접근법 (2) 이종 네트워크에 대한 링크 예측 접근법.링크 예측에 사용되는 정보의 유형에 기초하여 접근방식은 토폴로지 기반 접근방식, 콘텐츠 기반 접근방식, 혼합된 방법으로 분류할 수 있다.^[11]

위상 기반 방법

토폴로지 기반 방법은 대체로 유사한 네트워크 구조를 가진 노드가 링크를 형성할 가능성이 더 높다는 가정을 한다.

공동 이웃

이것은 공통된 이웃의 수를 계산하는 예측을 연결하기 위한 일반적인 접근법이다.공통적으로 이웃이 더 많은 기업은 연결고리를 가질 가능성이 더 높다.다음과 같이 계산한다.

${\displaystyle CN(A,B)={A\cap B}}}$

이 접근법의 약점은 공통 이웃의 상대적인 수를 고려하지 않는다는 것이다.

자카드 치수

Jaccard Measure는 공통의 상대적인 이웃 수를 계산하여 Common Neighbors의 문제를 해결한다.

${\displaystyle J(A,B)={{A\cap B}\over {A\cup B}}}}}$

아다미크-아다르 측도

Adamic-Adar 측정은^[12] 두 개의 노드 이웃의 교차점 로그의 합이다.이것은 단순한 원홉 방식보다 더 좋은 결과를 낼 수 있는 투홉 유사성을 포착한다.다음과 같이 계산한다.

${\displaystyle A(x,y)=\sum _{u\in N(x)\cap N(y)}{\frac {1}{\log N(u)}},}$

여기서 $N{\displaystyle (u}$) ${\displaystyle N(u)}$은(는) $u{\displaystyle }$ ${\displaystyle u}$에 인접한 노드 집합입니다$.$

캣츠 치수

이웃 기반 방법은 이웃 수가 많을 때 효과적일 수 있지만 희소 그래프에서는 그렇지 않다.이러한 상황에서는 더 긴 보행을 설명하는 방법을 사용하는 것이 적절하다.Katz Measure는^[13] 이것을 포착하는 하나의 지표다.그래프에서$$ 길이 $t{\displaystyle }$ ${\displaystyle t}$의 경로를 검색하고 사용자 지정 가중치에 의해 가중된 각 경로 길이의 카운트를 추가하여 계산한다.

A를 네트워크의 인접 행렬로 간주한다.A의 요소$({\displaystyle i_{}}$ ${\displaystyle j_{}}$) ${\displaystyle(a_{ij}})$는 노드 i가 노드 j에 연결되어 있으면 값 1을, 그렇지 않으면 0을 취하는 변수다.A의 힘은 중개자를 통한 두 노드 사이의 연결의 존재(또는 부재)를 나타낸다.예를 들어, 행렬 ${\displaystyle {A\mathrm{}}^{}}$ 3 ${\$ A$^{3}$에서$$${\displaystyle \mathrm{요소}}({\displaystyle {2\mathrm{}}_{}}$, ${\displaystyle {12}_{}}$)${\displaystyle }$= 1 ${\displaystyle(a_{2,12})=1$}인 경우 노드 2와 노드 12가 길이 3의 일부 보행을 통해 연결되었음을 나타낸다$.$$C{\displaystyle {}_{}}$ ${\displaystyle {K\mathrm{}}_{}}$ ${\displaystyle {\mathrm{a}}_{}}$ t ${\displaystyle {\mathrm{z}}_{}}$( ${\displaystyle i}$) ${\displaystyle C_{\mathrm {Katz} }(i)}$이(가) Katz의 노드 i의 중심성을 나타내는$$ 경우 수학적으로 다음을 수행하십시오.

${\displaystyle C_{\mathrm {Katz}}}}(i)=\sum _{k=1}^{n}}\sum _{j=1}^{n}\알파 ^{k}(A^{k})_{ji}}}$

위의 정의는 A ${\displaystyle k^{}}$ ${\$의 위치$({\displaystyle i}$, j${\displaystyle }$) ${\displaystyle(i,j)}$에 있는 요소가 $노드{\displaystyle }$ i ${\displaystyle i}$과 $j{\displaystyle }$ ${\displaystyle j}$ 사이의 총 $k{\displaystyle }$ ${\displaystyle k}$도 연결 수를 반영한다는$$ 사실을 사용한다는 점에 유의하십시오$.$

노드 속성 기반 메서드

노드 유사성 방법은 노드 속성의 유사성에 기초하여 링크의 존재를 예측한다.

유클리드 거리

속성 값은 정규화된 벡터와 유사성 측정에 사용되는 벡터 사이의 거리로 표현된다.거리가 작을수록 유사성이 높아진다.

코사인 유사성

속성 값을 정규화한 후 두 벡터 사이의 코사인 계산은 유사성을 측정하는 좋은 척도가 되며, 값이 높을수록 유사성이 높아진다.

혼합 방법

혼합 방법은 속성과 위상 기반 방법을 결합한다.

그래프 임베딩

또한 그래프 임베딩은 링크를 예측하는 편리한 방법을 제공한다.^[8]Node2vc와 같은 그래프 내장 알고리즘은 인접 노드가 벡터로 표현되는 내장 공간을 학습하여 도트 제품 유사성 또는 유클리드 거리와 같은 벡터 유사성 측도가 내장 공간에 고정되도록 한다.이러한 유사성은 위상학적 특성과 속성 기반 유사성의 함수다.그런 다음 벡터 유사성에 기초하여 가장자리를 예측하기 위해 다른 기계 학습 기법을 사용할 수 있다.

확률적 관계 모형

확률론적 관계 모델(PRM)은 데이터베이스를 통한 확률 분포를 위한 템플릿을 지정한다.템플릿은 도메인의 관계 스키마 및 도메인 내 속성 간의 확률적 종속성을 설명한다.PRM은 특정 엔티티 및 관찰되지 않은 링크의 데이터베이스와 함께, 관찰되지 않은 링크에 대한 확률 분포를 정의한다.^[5]

확률론적 소프트 논리(PSL)

확률론적 소프트 논리(PSL)는 힌지 손실 마르코프 무작위 필드(HL-MRF)에 대한 확률론적 그래픽 모델이다.HL-MRF는 일련의 템플화된 1차 로직 유사 규칙에 의해 생성되며, 이 규칙들은 데이터 위에 기초한다.PSL은 속성 또는 로컬 정보를 위상학적 또는 관계적 정보와 결합할 수 있다.PSL은 코사인 유사성과 같은 로컬 예측 변수를 통합할 수 있지만, 네트워크의 삼각형 완료와 같은 관계 규칙도 지원한다.^[14]

MLN(Markov Logic Network)

MLN(Markov logic networks)은 Markov 네트워크를 통해 정의된 확률론적 그래픽 모델이다.이러한 네트워크는 1차 로직과 같은 템플리트로 정의되며, 이는 교육 데이터에 기초한다.MLN은 링크 예측을 목적으로 로컬 규칙과 관계 규칙을 모두 통합할 수 있다.^[15]

R-모델(RML)

R-Models(RMLs)는 링크 중량 예측 문제에 대한 딥러닝 접근법을 제공하기 위해 만들어진 신경망 모델이다.이 모델은 알려진 링크의 가중치(노드 간 관계)에서 노드 임베딩(노드에 대한 지식)을 추출하는 노드 임베딩 기법을 사용하며, 이 지식을 사용하여 알려지지 않은 링크의 가중치를 예측한다.^[16]

적용들

링크 예측은 다양한 용도를 발견했지만, 실체가 구조적인 방식으로 상호작용하는 모든 영역은 링크 예측의 효익을 얻을 수 있다.^[17]링크 예측의 일반적인 적용은 권고사항에 대한 협업 필터링 접근방식의 유사성 측정 개선이다.링크 예측은 소셜 네트워크에서도 이용자에게 친구를 제안하기 위해 자주 사용된다.범죄 연관성을 예측하는 데도 쓰였다.

생물학에서 연결 예측은 단백질-단백질 상호작용 네트워크에서 단백질 간의 상호작용을 예측하는 데 사용되어 왔다.^[18]링크 예측은 링크 예측을 이용하여 약물과 대상 간의 상호작용을 유추하는 데도 이용되어 왔다. 과학 공동저작망에서 협업 예측에서 또 다른 응용이 발견된다.

중복제거라고도 하는 엔티티 결의안은 일반적으로 링크 예측을 사용하여 네트워크의 두 엔티티가 동일한 물리적 엔티티에 대한 참조인지 여부를 예측한다.일부 저자는 네트워크 구조화된 도메인에서 컨텍스트 정보를 사용하여 엔티티 해결을 개선했다.^[20]

네트워크 효과의 맥락에서의 링크 예측은 네트워크 전체에 퍼지는 경향을 분석하는 데 사용되었고, 특히 바이럴 마케팅의 마케팅 전략 개선에 사용될 수 있다.^{[citation needed]}

소프트웨어 패키지

무료 오픈 소스 소프트웨어

무료 및 오픈 소스 버전이 포함된 독점 소프트웨어

독점 소프트웨어

참고 항목

참조