cs224w 수업을 듣고 정리한 내용입니다.
정확하지 않은 내용이 있으면 알려주시면 감사하겠습니다.
Subnetwork는 해당 네트워크의 특성과 차별성을 가지고 있다.
노드가 3개 인 subgraph( directed) 는 위와 같은 경우의 수를 가진다.
( 각 경우의 수중에 동일한 모양의 subgraph는 없다.)
각 네트워크에서 위의 subgraph들이 얼마나 있는지 확인할수 있다.
Network motifs는 아래와 같은 특성을 가지낟.
Pattern은 해당 subgraph가 유도되는지, Recurring은 몇번 , 빈도수가 얼마인지, Significant는 예상보다 얼마나 나타나는지
Significant에 대한 설명이 모호한데 각각 예시를 알아보겠습니다.
Induced subgraphs
왼쪽 위와 같은 subgraph를 오른쪽 네트워크에서 찾을수 있는지 알아보는것이다.
Recurrence
해당 Motif가 오른쪽 네트워크에서 4번 활용된것을 볼수가 있다.
(Overlapping 허용)
Significance
랜덤 네트워크보다 실제 네트워크에서 많다는 내용이다.
( 랜덤 네트워크에 대한 설명은 이전 강의 정리에 있다.
https://medium.com/@zxzxs9182/cs224w-2%EA%B0%95-%EC%A0%95%EB%A6%AC-698e90c77a7)
그러한 Significance를 정하기 위해서 위와 같은 식으로 정한다.
실제 네트워크에서 발생횟수에서 랜덤 네트워크에서 평균 발생 횟수를 뺀후
표준편차로 나눠준다.
이러한 값은 네트워크가 커질수록 더 커진다고 한다.
이부분은 이해가 확실치 않다..
대략적으로는 실제 네트워크와의 degree sequence는 동일한 랜덤 그래프를 만드는 방법을 서술한것 같다. 위 사진처럼 만든후 아래의 Switching을 하여서 다른 모양의 네트워크를 계속 해서 만든다.
중간에 질문이 들어온 내용으로는 model은 task에 영향을 받는다고 한다.
( task마다 model을 다르게 한다는 말인듯)
위에서 설명한 내용을 다시 recap으로 하였다.
강의 중간에 질문 들어온 내용중에서 몇개의 랜덤 네트워크로 하냐는 질문이 있었는데 대략 1~10만개 정도라고 한다.
Graphlets
노드의 개수에 따른 그래프들이다.
각 그래프에 내부에 적혀있는 숫자들은 내가 이해하기론 그래프 위상(?)종류이다.( 강의에선 touch(?) 라고 하였던것 같다.)
아래 예시를 보자
Graphlet Degree Vector는 해당 orbit이 네트워크의 빈도를 보여준다.
아래 예시 그림을 보는 것 처럼 a는 두번 b는 한번 c는 0번 (나머지 노드가 두개 연결되어있기 때문) d는 두번이다.
이때 c,d가 있는 subgraph를 보면 어떤 노드를 v에 대입하냐에 따라 그래프의 적용여부가 달라진다.( 위에서 말한 touch )
GDV의 또 다른 예시이다. 위에 사진으로 올라가 각 subgraph들을 확인해보면 이해에 도움이 갈것이다.
그렇다면 이러한 Motifs와 Graphlets을 어떻게 찾을까?
그냥 찾기에는 복잡도가 너무 높다.
3가지 방법이 있는데 여기서는 ESU algorithm에 대해서 설명을 한다.
Exact Subgraph Enumeration (ESU)
알고리즘에 대한 설명이다. 해석해보면 현재 node_id보다 높은 노드를 방문하고 이전에 포함되있는 노드는 다시 추가하지않는 재귀적인 알고리즘이다.
아래 수도코드를 확인해보자.
위의 설명한 것처럼 모든 노드에 대해서 반복하면서 EXTENDSUBGRAPH라는 함수를 재귀적으로 반복하고 있다. 이해가 바로 되지않으니 아래 예시를 확인하자.
1번 노드에서 연결되 있는 노드를 가지고 함수에 들어간다.(여기서는 3번 노드만)
그리고 3번 노드와 연결될수있는 노드를 V_extension으로 가지고 다시 들어간다. 이때 subgraph의 크기가 k가 되면 리턴되므로{1,2,3} , {1,3,4},{1,3,5}의 그래프가 나오게 되고 이러한 방법으로 모든 노드에 대해서 탐색한다.
그리고 각 subgraph의 개수를 세보면 위와 같이 알수가 있다.
두개의 그래프가 topologically equivalent한지를 묻는 내용이였는데 brute force와 backpropagation을 언급하면서 계산량이 많다고 하였다.
Structural Roles in Networks
네트워크에서 노드의 역할을 role이라고 한다.
role의 예시를 보여준다.
Role 과 Communities/Gropus 의 차이를 보여주고있다.
위의 u,v 노드 아래의 3,4노드는 structurally equivalent하다고 한다.
다른 노드에 대한 관계가 동일하다는 것인데 아래 처럼 Adjacency matrix를 확인하면 쉽게 알수가 있다.
Discovering Structural Roles in Networks
role이 왜 중요한지에 대한 설명을 하고 있다.
타겟이랑 거의 비슷한 행동을 한다고 함
RolX라는 방법을 쓰면 알수가 있는데 Unsupervise learning이며 이전의 지식이 요구되지 않다고 한다.
전체적인 방법을 보자면 Adjacency Matrix가 input으로 들어가면 Feature Extraction을 하여 Node x Feature인 Matrix가 나오게 된다.
이떄 Role Extraction을 하여 Node x Role Matrix , Role x Feature Matrix가 나오게 된다.
이러한 방식으로 결과가 나온다 ( 다음장에서 더 자세히 설명) Local, Egonet, Recursive 로 feature들이 나뉘어져 있다.
Egonet은 주변 노드에게 다 연결되어있는 노드라고 한다.
Local feature는 node degree에 관련된 위와 같은 특징들이고 Egonet과 관련된 feature들 또한 있다.
Recursive는 이전에 나온 feature를 가지고 새로운 feature를 만드는 것이다.
위에서는 이웃 노드들 간에 중간 값을 가지고 새로운 feature를 만들었다고 예시가 나와있다.
하지만 이렇게 하면 exponentially , 즉 매우 많은 feature가 나오게 되므로 pruning technique으로 제어한다.
위와 같이 구분을 할수가 있다.
끝~
