[Graph Theory]Graph Density & Sparsity

Dense Graph vs Sparse Graph

밀집 그래프(Dense Graph)란 간선(edge)의 수가 최대 간선수에 가까운 그래프이다. 즉 정점(vertex, node)들 간의 연결 쌍이 매우 많음을 의미한다. 만약, 모든 노드들이 서로 연결된 형태일 때 이를 완전 그래프(Complete Graph)라고 한다. 반대로, 간선이 거의 없는 그래프를 희소 그래프(Sparse Graph)라고 한다. 희소 그래프의 대표적인 예시는 트리(tree)이다.

위의 그림은 밀집 그래프인 완전 그래프와 희소 그래프인 트리이다. 5개의 정점이 서로 연결된 것을 확인할 수 있다. 이 때 총 간선의 수는 10개이다. 완전 그래프에서 간선의 수는 서로 다른 \(n\)개의 정점 중 순서에 상관없이 2개의 점점을 선택하는 경우의 수이며 수식은 다음과 같다. 이를 수식으로 표현하면 \(_nC_2 = \frac{n(n-1)}{2}\)이다. 트리는 정점이 \(n\)개일 때, \(n-1\)개의 간선을 가진다.

그래프의 밀집도(density)는 이와 같이 정점의 수(\(\vert V \vert\))와 간선의 수(\(\vert E \vert\))에 영향을 많이 받는다. 가장 간단한 형태의 무방향 그래프(Undirected Graph)에서 그래프의 밀도는 다음과 같다.

방향 그래프(Directed Graph)의 밀집도는 다음과 같으며, 무방향 그래프의 밀집도에서 2로 나눠준 것과 같다. (양방향이 아닌 한방향만을 고려하기 때문에 2로 나눠준 것)

이 때, 정점의 개수가 \(\vert V \vert\)일 때 무방향 그래프에서 최대 간선 수는 \(\begin{pmatrix} \vert V \vert \\ 2 \end{pmatrix} = \frac{\vert V \vert (\vert V \vert - 1)}{2}\) 이므로, Density의 최대값은 1이다. Sparsity는 \(1 - Density\)이다.

• Density: \(\frac{2\vert E \vert}{\vert V \vert (\vert V \vert - 1)}\)
• Sparsity: 1 - Density

하지만, 위의 개념만으로는 그래프의 특징을 설명하기는 부족하며, 평균 degree가 몇인지, degree의 분포가 어떻게 되는지 등등도 같이 설명하는 것이 좋다.

Codes

• Using networkx library

## Constructing Graph Function
def nxGraph(url):
    response = requests.get(url)
    data = response.json()
    Undirected_Graph = nx.Graph()
    for ex in data:
        h, r, t = ex['head_id'], ex['relation'], ex['tail_id']
        Undirected_Graph.add_node(h)
        Undirected_Graph.add_node(t)
        Undirected_Graph.add_edge(h, t, relation = r)
    return Undirected_Graph

## UMLS
path = 'https://raw.githubusercontent.com/meaningful96/Blogging/main/Graph/Dataset/UMLS/train.txt.json'

G_umls = nxGraph(path)


# 그래프 density 계산
density = nx.density(G_umls)

# 그래프 sparsity 계산
sparsity = 1 - density

# 결과 출력
print(f"Graph density: {density}")
print(f"Graph sparsity: {sparsity}")

############## Output ##############
# Graph density: 0.34328358208955223
# Graph sparsity: 0.6567164179104478
####################################

Reference

Dense Graph

Graph 카테고리 내 다른 글 보러가기