graph

그래프

그래프(graph)는 다음 그림처럼 노드(node 혹은 vertex)와 노드들을 잇는 간선(edge)으로 이루어진 구조를 말한다.

수학적으로 그래프 $G$ 는 노드집합 $V$ 와 간선집합 $E$ 로 구성된다.

$$G = (V, E)$$

간선은 두 개의 노드로 이루어진, 순서가 있는 쌍(ordered pair)이다.

$$E \subseteq V \times V$$

위에서 그린 그래프는 4개의 노드 집합과 6개의 간선 집합을 갖는다.

$$V = \{0, 1, 2, 3\}\\ E = \{(0,1), (0,2), (0,3), (1,2), (1,3), (2,3)\}$$

방향성 그래프와 비방향성 그래프

만약 간선 $(a, b)$와 $(b, a)$가 있을 때, 이 두 간선을 다른 것으로 본다면 방향이 있는 방향성 그래프(directed graph), 같은 것으로 본다면 방향이 없는 비방향성 그래프(undirected graph)이다. 그래프를 시각화할 때 방향성은 화살표로 표시한다.

NetworkX 패키지

NetworkX는 그래프를 다루기 위한 파이썬 패키지이다. 비방향성 그래프를 만드는 클래스 Graph 와, 방향성 그래프를 만드는 클래스DiGraph 를 제공한다.

# !pip3 install networkx
import networkx as nx
g1 = nx.DiGraph()

위에서 g1이라는 방향성 그래프를 생성하였다. 노드를 추가하려면 add_node 메서드를 사용한다. 노드에는 숫자나 문자열을 사용할 수 있으며, nodes 메서드로 추가된 노드들을 확인할 수 있다.

g1.add_node("a")
g1.add_node(1)
g1.add_node(2)
g1.nodes()

간선을 추가할 때는add_edge 메서드를 사용한다. 간선을 이을 두 노드를 인수로 사용한다. 그래프에 포함된 간선은 edges 메서드로 확인할 수 있다.

g1.add_edge(1, 'a')
g1.add_edge(1, 2)
g1.edges()

Graphviz 프로그램과 pydot 패키지를 설치하면 이를 시각화할 수 있다.

from IPython.core.display import Image
from networkx.drawing.nx_pydot import to_pydot

d1 = to_pydot(g1)
d1.set_dpi(300)
d1.set_rankdir("LR")
d1.set_margin(1)
Image(d1.create_png(), width=300)

노드 집합 $V$ 와 간선 집합 $E$ 를 갖는 그래프 $G$ 에 포함된 노드의 개수를 그래프의 크기(cardinality)라고 한다. $|G|$ 또는 $|V|$ 로 나타내며, 간선의 개수는 $|E|$ 로 나타낸다.

NetworkX 패키지에서는 각각 len , number_of_nodes, number_of_edges 메서드로 계산할 수 있다.

len(g1), g1.number_of_nodes(), g1.number_of_edges()

만약 두 노드 $a, b$ 를 포함하는 간선 $(a,b)$ 가 $E$ 안에 존재하면 두 노드는 인접(adjacent)하다고 하며, 인접한 두 노드를 서로 이웃(neighbor)이라고 한다.

$$(a, b) \in E$$

NetworkX 패키지 Graph 클래스의 neighbors 메서드는 인수로 받은 노드에 인접한 노드를 생성하므로 인접성을 확인하는 데 사용할 수 있다.

for n in g1.neighbors(1):
	print(n)

2 in g1.neighbors(1), 1 in g1.neighbors(2), 'a' in g1.neighbors(2), 'a' in g1.neighbors(1)

만약 어떤 노드에서 출발해 자기 자신으로 바로 돌아오는 간선이 있다면 셀프 루프(self loop)라고 한다. 다음 그래프에서는 노드2에 셀프루프가 있는 것이다.

g2 = nx.Graph()
g2.add_node(1)
g2.add_node(2)
g2.add_node(3)
g2.add_edge(1, 2)
g2.add_edge(2, 2)
g2.add_edge(2, 3)
np.random.seed(0)

d2 = to_pydot(g2)
d2.set_dpi(600)
d2.set_rankdir("LR")
Image(d2.create_png(), width=600)

워크, 트레일, 패스

어떤 노드를 출발해서 다른 노드로 도달하기 위한 인접한 노드의 순서열을 워크(walk)라고 하고, 워크 중에서 동일한 노드를 두 번 이상 지나지 않는 워크를 트레일(trail), 시작과 끝 노드를 제외하고 동일한 노드를 두 번 이상 지나지 않는 워크를 패스(path)라고 한다.

패스 중에서 시작점과 끝점이 동일한 패스를 사이클(cycle)이라고 하며, 사이클이 하나도 없는 그래프를 어사이클릭 그래프(acyclic graph)라고 한다.

g3 = nx.DiGraph()
g3.add_node("a")
g3.add_node("b")
g3.add_node("c")
g3.add_node("d")
g3.add_node("e")
g3.add_node("f")
g3.add_edge("a", "b")
g3.add_edge("c", "a")
g3.add_edge("b", "c")
g3.add_edge("c", "d")
g3.add_edge("d", "e")
g3.add_edge("e", "c")

d3 = to_pydot(g3)
d3.set_dpi(600)
d3.set_rankdir("LR")
d3.set_margin(0.5)
Image(d3.create_png(), width=800)

위 그래프 $g3$에서 워크, 트레일, 패스, 사이클을 찾아보자.

• $a- b-c-a-b-c-d-e-c$ 는 $a$ 에서 $c$ 로 가는 워크이다. 하지만 트레일이나 패스는 아니다.
• $a-b-c-d-e$ 는 트레일이다.
• $a-b-c-d-e-c$ 는 패스지만 트레일은 아니다.
• $a-b-c-a$ 는 사이클이다.

has_path 명령으로 두 노드간에 패스가 존재하는지 알 수 있다. 패스가 존재하면 shortest_path 명령으로 가장 짧은 패스를 구할 수 있다.

nx.has_path(g3, 'a', 'b'), nx.has_path(g3, 'a', 'e'), nx.has_path(g3, 'a', 'f')

nx.shortest_path(g3, 'a', 'e')

클리크

• 클리크(clique) : 모든 노드끼리 간선이 존재하는 무방향성 그래프의 노드 집합
• 최대 클리크(maximal clique) : 클리크에 포함된 노드에 인접한 다른 노드를 추가하면 클리크가 아니게 되는 것

g4 = nx.Graph()
g4.add_node("a")
g4.add_node("b")
g4.add_node("c")
g4.add_node("d")
g4.add_node("e")
g4.add_node("f")
g4.add_edge("a", "b")
g4.add_edge("a", "c")
g4.add_edge("b", "c")
g4.add_edge("b", "d")
g4.add_edge("c", "d")
g4.add_edge("d", "e")
g4.add_edge("d", "f")
g4.add_edge("e", "f")

d4 = to_pydot(g4)
d4.set_dpi(600)
d4.set_rankdir("LR")
Image(d4.create_png(), width=800)

위 그래프에서 클리크를 찾아보려면 enumerate_all_cliques, 최대 클리크를 찾아보려면 find_cliques 명령을 사용하면 된다.

[c for c in nx.enumerate_all_cliques(g4)]

[c for c in nx.find_cliques(g4)]

특정 노드가 포함된 클리크를 찾아보려면 해당 노드를 인수로 설정하여 cliques_containing_node 명령을 사용하면 된다.

nx.cliques_containing_node(g4, ['a'])

nx.cliques_containing_node(g4, ['a','b'])