[Social Network] Social Network Mining (Link Mining)

Social Network Mining

= Link Mining

 

Linked Network

Link는 데이터 사이의 relationship을 의미한다.

 

Object와 link의 종류에 따라 linked network는 크게 두 종류로 나눌 수 있다.

• Homogeneous network
  • = single model social networks
  • object의 종류가 하나이고 link의 종류가 하나이다.
  • 예시 : WWW(world wide web)
• Heterogeneous network 
  • object의 종류가 여러개이고 link의 종류가 여러개이다.
  • 예시
    • medical network : {patient, doctor, disease}, {contact, treatment}
    • bibilographic network : {publications, authors, venues}

 

다양한 Link Mining Tasks

• object-related task
  • link-based object ranking (LBR)
    • 타겟 : Object = 1종류, link = 1종류
    • 그래프의 link 구조를 분석해서 중요도를 기준으로 object를 순서화한다.
    • Community의 link를 분석하는 것에 초점이 맞춰져 있다.
    • 방법
      •  HITS
      • PageRank
  • link-based object classification (LBC)
    • attributes, link, linked object의 attribute을 이용하여 object의 카테고리를 예측한다.
    • 응용
      • 페이지 내의 단어 수 , 페이지 간 링크 등을 이용하여 웹 페이지의 카테고리를 예측한다.
      • 등장한 단어, 인용, 저자 등을 통해 논문의 토픽을 예측한다.
  • group detection (object clustering)
    • social network에 있는 노드들을 clustering한다.
    • Community 파악 : 같은 그룹 내에는 edge가 많이 존재하고 다른 그룹 간에는 edge가 적어진다.
    • 어려움 : 실세계에서의 커뮤니티 내에는 edge가 적고 다른 커뮤니티 간에는 noise edge가 존재한다.
    • 방법
      • Hiearchical clustering
      • Blockmodeling of SNA
      • Spectral graph partitioning
  • link cardinality estimation
    • cardinality ≒ degree 
    • object를 가리키는 link의 수를 예측한다.
      • 응용
        • in-link의 수를 토대로 중요한 페이지를 예측하거나 out-link의 수를 토대로 hub를 파악할 수 있다.
        • citation 수를 통해 페이지의 영향을 예측할 수 있다.
    • 특정 object로부터 도달 가능한 object의 수를 예측한다.
      • 응용
        • 크롤링을 통해 페이지의 수를 예측할 수 있다.
        • 특정 저널에 대한 author의 citation을 예측할 수 있다.
• link-related task
  
  • link prediction
    • 두 object 사이의 attribute를 기반으로 두 object 사이에 link가 존재할 것인지 예측한다.
    • 응용
      • 두 웹 페이지 사이에 link가 존재할 것인지 예측
      • 한 논문이 다른 논문을 인용할 것인지 예측
    • 방법
      • binary classification으로 변환해서 파악할 수 있다. 
      • 구조나 attribute feature에 기반한 local conditional probability model
• graph-related task
  • subgraph discovery
    • graph-based data mining
    • 전체 그래프에서 중요한 subgraph를 찾는 task
    • 전체 그래프 중 자주 나타나는 subgraph를 중요하다고 생각할 수 있다.
    • 응용 : 생물학에서의 유전자 구조, 화학에서의 분자구조 등
    • 방법 : subgraph pattern mining
  • graph classification
    • subgraph pattern analysis를 통해 그래프를 분류하는 task
  • generative model for graph