Clique (파벌, 패거리)란? 5분 컷이해

Clique (파벌, 패거리)란? 5분 컷이해

요약: 그레프 이론에서의 Clique란 "가능한 가장 많은 노드들이 fully connected(=complete graph)로 연결된 undirected network". k-plex란 clique의 n-1에 해당하는 엣지의수 n-k로 일반화하여 조금 완화한 개념

"maximal subset of the vertices in an undirected network such that every member of

the set is connected by an edge to every other" - networks an introduction

특징

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

설명 및 예시

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

Clique: 4개의 노드들이 서로 연결되어있는 경우(=더이상 추가할 노드가 없는 경우). 예를 들어 5시 방향에 있는 노드는 3시방향 6시방향의 노드와 연결되어있지만, 12시, 9시 방향의 노드와는 연결되어있지 않다.

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이다.

Clique 이자 1-plex

다음은 몇-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-clique

k-core

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

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

반응형

from http://analytics4everything.tistory.com/182 by ccl(A) rewrite - 2021-10-11 23:27:05