한 엣지(edge)에 여러 노드(node)가 동시에 연결된 네트워크가 있습니다. 개개인을 한 노드로 하는 거대한 사회 연결망(social network)을 구축했을 때 여러 가족을 표현할 때를 예로 들 수 있습니다. 가족에는 2명 이상의 개개인이 속하게 되는데, 이 때 가족이라는 한 엣지로 2개 이상의 노드가 연결되는 것입니다.

HNexample이런 네트워크를 하이퍼그래프라고 하고, 하이퍼그래프 안에서 2개 이상의 노드를 연결해주는 엣지를 하이퍼엣지(hyperedge)라고 합니다. 위 그림은 사람을 노드로 갖는 하이퍼그래프를 나타내고 있습니다. 하이퍼엣지1은 6개의 노드를 연결하고 있고, 하이퍼엣지2, 3은 각각 6개, 4개의 노드를 연결해주고 있습니다. 여기서 하이퍼엣지는 가족, 함께 수강하는 과목, 취미 등 노드들이 가진 공통점이면 무엇이든 될 수 있습니다.

하이퍼그래프에서 특히 모든 하이퍼엣지에 속한 노드의 수(cardinality)가 k개로 같은 경우를 k-균일 하이퍼그래프(k-uniform hypergraph)라고 합니다. 즉, 3-균일 하이퍼그래프는 모든 하이퍼엣지에 노드가 3개인 경우를 의미하는 것입니다.

uniformHN

3-uniform hypernetwork

 

 

하이퍼그래프는 실생활에서 생각보다 여러가지를 나타낼 수 있습니다.application

위의 표와 같이 거의 모든 네트워크가 하이퍼그래프로 표현될 수 있는데, 특히 연결된 노드끼리 공통점이 있을 때 하이퍼그래프를 주로 씁니다. 사회학에서는 이런 네트워크를 협력 네트워크(affiliation network)라고 합니다.

하지만 하이퍼그래프는 비중있게 다뤄지지 않는데, 이분 그래프(bipartite graph)를 사용하면 같은 정보를 전달하면서 좀 더 편리하게 다룰 수 있기 때문입니다. ==★

sig

광고