연금술사

요약

• Clique: "가능한 가장 많은 노드들이 fully connected(=complete graph)로 연결된 undirected network". 
• k-plex: clique의 n-1에 해당하는 엣지의수 n-k로 일반화하여 조금 완화한 개념
• k-core: 각각의 노드들이 적어도 k에 연결되어있어야 하는 서브그레프
• k-clique: k개의 노드로 구성되어있는 clique

특징

1. maximal의 의미는 다른 가능한 많은 노드들이 최대한 많이 연결된 상태를 의미한다. (=더 clique로 추가 될만한 노드가 없는 경우 = fully connected 로 연결할 수 있는 노드가 없는 경우)
2. Clique은 서로 겹칠 수 있으며, 이는 한 노드(vertice)가 다른 clique에 포함될 수 있음을 의미한다.
3. Sparse network(서로서로 잘 연결되어있지 않는 네트웍)에서의 Clique의 존재는 어떤 응집력이 매우 좋은 집단이 있음을 의미한다. 예를 들어, 소셜 네트워크의 경우도, 대부분이 fully connected로 잘 연결되어있지 않고, 어쩌다 연결되고, 일부 연결되어있는 사람들끼리서는 다 연결되어있는 친목그룹따위가 존재한다. 
4. Clique을 구성하는 노드가 N개인경우 N-1개의 edge가 존재한다.

설명 및 예시

1. Maximal: 아래와 같이 4개의 노드(vertices)가 fully connected로 되어있고 (서로 연결), 이 4개외에는 fully connected로 연결해볼만한 노드가 더이상 없다.

2. Clique내 노드끼리는 겹칠 수 있다. clique내의 서브그레프도 하나의 clique라는 것을 의미하지 않고, 여러 clique내에 노드가 겹칠 수 있음을 의미한다. 예를 들어, 아래를 보면 A-B를 기점으로 clique가 2개로 될 수 있다. 그리고, 노드A와 B는 서로 각각 clique에 해당한다.

k-plex: k-plex은 clique(competed graph)의 모두 연결되어있어야하는 조건을 완화한 개념이다. 위에서 clique은 모든 노드들이 연결되어있어야한다고 했고, 이 경우는 n-1개의 연결(엣지)가 존재한다고 했다. k-plex은 여기어 n-1의 엣지수를 n-k로 일반화하여 조금 완화한 개념이라고 보면 이해가 직관적이다. 보통 "k plex of size n"을 의미하는데, 네트워크 안에 있는 n개의 노드중 적어도 n-k가 fully connected 되어있음을 의미한다. 예) k=1일 경우, 일반적인 clique와 동일한 의미를 갖는다. k=2인 경우는 적어도 vertex들이 다 연결되어있거나, 모든 노드들이 하나에만 연결되어있어야함을 의미한다. 

아래의 예시는 1-plex을 의미한다. 우선 모든 V1,V2,V3,V4가 모두 각각에 연결되어 clique이다. 그리고, n-k(=|V|(vertex 수 -1)은 3이므로, 각각 모든 노드가 3개의 엣지를 가지면 되는지 확인하면된다. V1,V2,V3,V4가 각각 3개의 노드를 가지므로 1-plex도 된다. 따라서, 1-plex = clique이다. 

다음은 몇-plex일까? 답은 2-plex. 우선 fully connected가 아니기 때문에 clique은 아니다. 즉, 1-plex은 아니라는 것이다. 2-plex일까? |V|(=n)은 5이고 각V1 ,V2은 3개의 엣지를 갖는다. 2-plex가 되려면, 모든 노드들이 5-2개의 엣지를 가져야한다. 그러나 V3, V4, V5은 2개씩의 엣지를 갖는다. 즉 2-plex도 아니다. 그러나, 이 그레프는 각 노드들이 최소 2개의 엣지를 갖는다. 이를 표현하면 $\delta(G)=2$라고 보통 표기한다. 따라서, 2>=5-k라는 수식을 두면, 가능한 k는 3,4,5가된다.

k-core : k-plex와 유사한 컨셉은 k-core라는 것이 있다. k-core은 k-plex와 마찬가지로 "maximal subset of vertice"으로 각각의 노드들이 적어도 k에 연결되어있어야하는 것이다. 예를 들어, 5개의 노드로 구성된 2-core는 (5-2)-plex와 같다. k-core와 k-plex와의 차니는 k-cores은 겹치는 것이 없다. k-cores의 장점은 적어도 k의 연결이 있어야하기에, 반대로 k-1개 이하의 엣지를 가진 노드를을 찾아 없애면되니, 상대적으로 k의 수를 알기가 쉬워 실용적인 분석이 될 수 있다.

* 그리고 k-core은 원래 그레프 G의 서브그레프 중에 유일한 서브그레프가 된다.

k-clique : 유사한 명명으로 되는 그레프 중에, k-clique가 있으며, 이는 한 노드에서 다른 노드로 최대 k개 이상의의 거리가 없는 경우의 "maximal subset" 을 의미한다. 만일 k=1이라면, clqiue랑 동일하다. 즉 모든 노드가 1개 이하의 거리를 갖는다. 만일 k가 커지면, 점점 그레프가 커지는거고 그레프의 최대 거리가 커지는 것을 의미한다. 이 개념이 다른 설명서에는 clique with k vertices라고 소개가 되는 경우도 있는데, k=3이면 3개의 노드로 이루어진 clique가 된다.

아래를 참고하면 쉬운 영상이 있다.

https://www.youtube.com/watch?v=V2CgqTLWxvY