컴퓨터공학의 많은분야를 하나의 네트워크로표현 후 분석

개요 : 컴퓨터공학의 많은 분야중 일부를 뽑아 하나의 네트워크로 도식화한 후에 어떠한 특성이있는지 Social Network Analysis에 근거하여 분석.

* 그래프의 각 노드들이 연결맺는 데이터관계는 본인이 임의로 생성함.

1. 데이터를 불러와 무방향그래프로 그렸고, 각 핵심분야는 컬러를 입혔음.

2. maximal clique를 그려봤는데  VR과 AR이 아주 밀접하게 그래픽스와 선형대수를 기반으로하는 기술이라는것이 보여짐.

3. A라는 분야가 B라는 분야와 얼마나 밀접한지를 보여줌.

4.  각 분야가 얼마나많은 직접적인 edge를 갖는지를 보여준다. 그래픽스가  가장많고 그다음은 웹이다.

5. 이 네트워크에서 각분야들을 각각의 커뮤니티로 분류했다. (커뮤니티분류 알고리즘마다 클러스터링하는것에 차이가있다)

6. 링크기반의 커뮤니티분류알고리즘을 적용해봤다. 링크기반의 커뮤니티분류는 위의분류방법과는 달리, 한개의 노드가 다수의 커뮤니티에 소속될수있기에, 밑의 그래프에서는 그 비율을 보여준다.

7. 링크기반의 커뮤니티기법에 dendrogram을 보여주는데, modularity(Q)값이 가장높을떄를 기준으로해서 커뮤니티를 분류한걸 볼 수 있고, 거의 왠만한 커뮤니티분류알고리즘들은 루프를돌다가 modularity값이 가장높을때를 기준으로해서 커뮤니티를 분류한다.

8. 각 노드가 얼마만큼의 제약성을 갖는지보여주는데 수치가 낮을수록 제약성이 덜하다는뜻이다. 즉, 다른노드에의해 제약을 덜 받는다는것인데 가장 낮은수치는 'Web'이다. 소셜네트워크분석에서는 제약성이 낮은 구조적 공백의 이점을 가진 노드는 다른노드들에게 '중개자' 역할을 한다.

9. A->B, B->C 일때, A->C라는 수치를보여준다. BIGDATA, AR, VR이 추이관계성이 가장 높다.

10. 사이중심도를 보여주는데, 그래픽스(5번째)가 가장 높다. 그다음으로는 웹(8번째)이다 사이중심도는 어떤노드에서 어떤노드로갈떄 어떤노드를 얼마나많이지나가는지에 대한 지표이다. 즉, 이네트워크에서는 각노드간 접촉에있어서, 그래픽스를 거의 필수로 거쳐서 가야한다고 볼 수 있다.

11. 근접중심도를 보여주는데, AR(12번째)이 가장 높다. 근접중심도는 어떤노드에서 어떤노드로갈때 가장최단경로를 많이갖는 노드라고볼 수 있다. 즉, 평균적으로 어떤노드로갈떄의 거리가 가장짧다.

12. 아이겐벡터중심도는 그래픽스(5번째)가 가장높다(아이겐벡터중심도에 대한 설명은 PageRank 알고리즘글 참고)

이 내용에서 쓴 커뮤니티탐지알고리즘들은 그룹기반인데, 맴버기반의 커뮤니티탐지알고리즘은 비용은 더썌지만 조금더 정밀한 탐지가 가능하다는 장점이있고 그중, Node similarity기법은 DFS/BFS 기법을 이용하기때문에 비용을 조금 줄일수있다.

네트워크를 여러개의 커뮤니티로 분리했을 때 재대로 분리됬는지 검증하는 방법에는 ground truth방식과 ground truth를쓰지않는 방식이있다.
Ground truth의 방법3가지:

1. Precision and Recall, F-measure (Recall값이 Precision값보다 더 크면 detected된 커 뮤니티는 재대로 detection이 안됬다는 뜻)

2. Purity (계산은 간단하지만 F-measure보다 정확성이 떨어진다) 3. NMI (NMI값이 높으면 잘분리된거고 값이 낮으면 잘분리되지않음)

True positive: 비슷한 멤버들이 같은 커뮤니티에 할당됬을때 (정확한 결정) 

True negative: 다른 멤버들이 다른 커뮤니티에 할당됬을때 (정확한 결정) 

False positive: 비슷한 맴버들이 다른 커뮤니티에 할당됬을때 (부정확한 결정) 

False negative: 다른 맴버들이 같은 커뮤니티에 할당됬을때 (부정확한 결정)

F-measure은 Precision and Recall방식의 조화평균값이다 F-measure값이크면 커뮤니티가 잘못 detection됬다는 뜻 

clique에서는 k-plex라는것도있는데 clique자체가 아주서로밀집해있기때문에 이것을 따로 분류하는것도 의미있지만 최소 n-k개의 연결을갖는 부분그래프인 k-plex라는것도 의미가있다.

k-plex에서 k값이 높을수록 군집화의 의미가 떨어진다. 왜냐하면 작은덩어리들끼리 군집화가 되 는게 가장 이상적인데, 엄청나게 큰
덩어리가 군집화되면 그 덩어리 안에서는 특징을 추출하는게 의미가 없어진다.

 클릭완화방법(CPM) 단계

1. k개의 클릭들을 찾는다

2. 공통노드가 k-1개이상 존재하지않는 클릭은 연결에서 뺀다

3. 공통노드가 k-1개이상 존재하는 클릭들을 연결한다

 1~3과정을 거치면 자동으로 커뮤니티가 형성되있는걸 볼 수 있다. 

이외에 랜덤네트워크라던지 더 많은 내용이있지만 본 글의 주제와는 관련이없으므로 생략.