그래프(graph)와 관련된 인공지능 문제

1. node classification

 

node가 여러가지 유형을 가질 때 각 node의 유형을 추측하는 문제

 

아래 그림은 사용자 계정 간 리트윗 정보를 그래프로 표현하여 각 리트윗이 나타내는 정치적 성향을 분석하여 크게 2가지 색깔로 나타냄

 

같은 정치적 성향을 가지는 사람끼리는 서로 트윗 공유를 할 가능성이 높을 것이다.

 

 

같은 색을 가지는 node들이 서로 모여있다는 것을 알 수 있다.

 

위와 같은 분석결과에 정치적 성향을 모르는 새로운 node가 추가되었다면 공유관계를 분석하여 새롭게 분류할 수 있을 것

 

 

단백질의 상호작용을 분석하여 단백질의 유형을 나누는 문제

 

 

2. link prediction

 

주어진 그래프가 어떤 식으로 연결되면서 성장할지 거시적으로 link를 예측하는 문제

 

페이스북의 진화

 

 

페이스북 그래프가 점점 커질지? 작아질지?

 

각 node의 link는 점점 많아질지? 줄어들지? 예측하는 것이다.

 

 

3. recommendation

 

각 node가 앞으로 어떤 node와 연결될지 미시적인 관점에서 link를 예측하는 문제

 

쇼핑몰에서 구매 상품을 추천하는 문제

 

많은 추천시스템은 각 구매자가 어떠한 물건을 구매할지 예측하여 추천하며

 

어떤 물건을 구매해야 만족도가 높을지 고려한다.

 

 

4. community detection

 

서로 밀접하게 연결된 node의 집합인 군집(cluster)을 찾는 문제

 

많은 경우 군집은 특별한 의미를 가지는 경우가 많다.

 

SNS그래프에서 의미있는 사회적 무리를 찾아내는 문제

 

 

SNS를 나타낸 그래프로부터 대학교 친구나 같은 상사를 가지는 친구나 고등학교 친구나 가족을 나타내는 Social circle를 찾아내는 것이 community detection

 

 

5. ranking & information retrieval

 

전세계 인구수보다 많다고 알려진 세상의 웹페이지의 집합으로부터 자기가 원하는 정보를 가지는 중요한 웹페이지를 찾아내는 문제

 

다양한 웹페이지를 하나의 그래프로 나타내고 연결관계를 분석하여 의미있는 정보를 가진 검색 keyword와 관련된 웹페이지를 찾는다.

 

 

 

6. information cascading & viral marketing

 

정보를 어떻게하면 네트워크를 통해 잘 전달할 수 있을지 방법을 찾는 문제

 

어떻게 SNS로 상품을 광고해야 많은 사람들에게 광고 정보가 퍼질 수 있을지 고민하는 문제

 

 

강남스타일MV는 SNS를 통해 전 세계적으로 전달되었다