Community detection in graphs 결론 요약

Community detection in graphs

S Fortunato - Physics Reports, 2010 - Elsevier

(http://www.sciencedirect.com/science/article/pii/S0370157309002841)

먼저 논문의 굉장히 일부만을 보고 적은 글임을 밝힙니다.

1. INTRODUCTION
2. COMMUNITIES IN REAL-WORLD NETWORKS
3. ELEMENTS OF COMMUNITY 
   - edge 가 node 보다 많으면 데이터 클러스터링(hierarchical partitioning, spectral clustering) 문제에 더 가까움
4. TRADITIONAL METHODS
   A. Grpah partitioning
   B. Hierarchical clustering
   - 클러스터에 대한 사전 지식이 필요하지 않지만,
   - 정확하지 않고 scalable 하지 않다.
   C. Partitional clustering
   D. Spectral clustering
   - object 는 metric space 의 한 점 또는 graph 의 vertice 가 될 수 있음
5. DIVISIVE ALGORITHMS
6. MODULARITY-BASED METHODS
   - 정확도와 복잡도의 trade off
7. SPECTRAL ALGORITHMS
8. DYNAMIC ALGORITHMS
9. METHODS BASED ON STATISTICAL INFERENCE
10. ALTERNATIVE METHODS
11. MULTISOLUTION METHODS AND CLUSTER HIEARARCH
12. 12
13. 13
14. 14
15. 15
16. 16
17. 17
18. OUTLOOK
    - 현재 만족할만한 그래프 클러스터링 솔루션은 없음
    - 실재하는 그래프는 대부분 hierarchy 를 가짐
    - null model = random edge + 같은 degree sequence
    (여기서 null model 은 커뮤니티가 존재하지 않는 그래프의 모델을 말합니다.)
    - null model 의 정의가 정확하지 않고, 아직 모든 종류의 null model 이 밝혀지지 않음
    - Palla 의 The clique Percolation Method 는 취미가 비슷한 소수의 그룹이 아주 많이 존재하는 - 소셜 그래프 - 같은 그래프의 클러스터링에 적합
    - 대부분의 알고리즘이 edge 가 undirected 이고 unweighted 인 그래프만 다루고 있음