[SOCIAL MEDIA MINING2] - types of graph

Null Graph and Empty Graph

G(V, E), V = C = 0

Null graph : node 가 없기에 dege 도 없음

Empty Graph : 노드만 있고 Edge가 없음

 

Simple Graphs and Multigraphs

단순 그래프(simple graph): 노드 쌍 간에는 단 하나의 에지만 존재 즉, 같은 두 노드 간에는 최대 한 개의 에지만 존재합니다.
멀티그래프(multigraph) : 두 노드 간에 여러 개의 에지 및 루프(loop)가 존재할 수 있는 그래프
즉, 같은 두 노드 간에 여러 개의 에지가 존재할 수 있고, 노드 자체에 루프가 존재할 수 있습니다.

 

Weighted Graph

가중치가 포현된 graph

 

Signed Graph

부호 그래프(signed graph)는 에지에 부호(positive, negative, 또는 zero)가 할당된 그래프

- 각 에지에 부호가 부여되어, 에지가 나타내는 관계의 성격을 나타낼 수 있습니다.
- 예를 들어, 소셜 네트워크에서 친구 관계를 나타내는 그래프에서 에지에 긍정적인 부호가 할당된 경우 두 노드 간의 친구 관계를 나타내고, 에지에 부정적인 부호가 할당된 경우 두 노드 간의 적대 관계를 나타낼 수 있습니다.
- 부호 그래프는 의사결정 분석, 사회 네트워크 분석, 감성 분석 등에서 활용될 수 있습니다.

 

Webgraph

• 웹 그래프(Webgraph)는 인터넷 사이트들이 웹상에서 연결되어 있는 방식을 나타내는 그래프
• 일반적으로 웹 그래프는 방향성이 있는 다중 그래프로 표현됩니다.
• 노드는 사이트를 나타내고, 에지는 사이트들 간의 링크를 나타냅니다.
• 두 개의 사이트는 서로를 가리키는 여러 개의 링크를 가질 수 있으며, 자기 자신을 가리키는 루프(링크가 자기 자신을 가리키는 경우)를 가질 수도 있습니다.
• 웹 그래프는 검색 엔진, 웹 크롤링, 웹 분석 등에서 사용될 수 있습니다.

 

Connectivity in Graphs

adjacent :  두 노드가 에지를 통해 연결되어 있음

incident : 두 개의 에지가 공통된 하나의 노드를 가지고 있다

그래프가 방향성을 가진 경우, 에지의 방향이 일치해야만 에지들이 일치하는 것으로 간주됩니다.

 

Walk, Path, Trail, Tour, and Cycle

Walk

A walk is a sequence of incident edges visited one after another

오픈 워크(Open Walk) : 워크가 시작한 곳에서 끝나지 않는 경우 (출발 !== 도착)
클로즈드 워크(Closed Walk) : 워크가 시작한 곳으로 돌아와 끝나는 경우 (출발 == 도착)

 

Trail

walk 의 한 종류, edge를 한 번씩만 방문하는 것

closed trail = tour = circuit(start == end)

 

path

walk 의 한 종류, node와 edge를 중복방문하지 않는 것

 

Random walk

에지의 가중치는 방문 확률을 정의하는 데 사용될 수 있습니다.

Connectivity

1. 노드 사이에 연결이 있는 경우

2. graph가 연결되어 있다는 것은 모든 노드 쌍 간에 경로가 있음

in directied graph,

- strongly connected : 모든 노드 쌍 간에 유향 경로가 존재하는 경우

- weakly connected : 에지 방향을 따르지 않고 모든 노드 쌍 간에 경로가 존재하는 경우

3. graph가 연결되어 있지 않다는 것은 그래프 내에서 경로가 존재하지 않음

(d)의 경우, V5 -> V2 path 없음

 

Component

in-directed에서는 각각이 subgraph

n-hop neighborhood

V5->V2 (2-hop neighborhood)

 

Diameter

그래프 내의 모든 노드 쌍 간의 가장 긴 최단 경로의 길이

web 클롤링 시 19개의 링크를 통해 크롤링하면 거의 모든 정보를 수집 가능

 

 

Adjacency Matrix and Connectivity

i, j 사이 공동 노드는 2개

 

Special Graph

무방향 그래프의 특별한 경우

- cycle 없음

- 어떤 두 노드 간 하나의 경로만 존재

- |V| = |E| + 1 성립(|V|: 노드의 수, |E|: 간선의 수)

- 연결되지 않은 트리들의 집합은 포레스트(Forest)라고 합니다.

 

Special Subgraphs

스패닝 트리(Spanning Tree)는 모든 노드를 포함하면서, 사이클이 없는 서브그래프
• 한 그래프에는 여러 개의 스패닝 트리가 존재할 수 있습니다.
• 가중 그래프에서, 스패닝 트리의 가중치는 트리에 포함된 간선들의 가중치의 합으로 정의됩니다.
• 가중 그래프에 대해 여러 개의 스패닝 트리가 존재할 경우, 그 중에서 가중치의 합이 최소인 트리를 최소 스패닝 트리(Minimum Spanning Tree, MST)라고 합니다.

 

Steiner Trees

가중 그래프 G(V, E, W)와 노드의 부분집합 (터미널 노드)이 주어졌을 때, Steiner Tree 문제는 이 트리가 노드의 부분집합을 포함하고 그 가중치가 최소화되는 트리를 찾는 문제

 

Complete Graphs

모든 node가 graph로 연결되어 있음(방항성 X), dense한 graph

 

Planar Graph

교차하는 그래프가 없음

Bipartite Graphs

VL간의 연결X, VR간의 연결X

 

Affiliation Networks

소속관계를 나타내는 graph로 멤버/단체를 나타낼 수 있음

행렬로도 나타낼 수 있음

행렬로 나타내는 내용 정리 필요

 

Regular Graphs

모든 노드가 동일한 degree를 가지는 그래프

 

Bridges (cut-edges)

해당 에지를 제거하면 연결된 컴포넌트의 개수가 증가하는 에지

굵은 선의 dege를 삭제하면 component가 늘어난다(graph 분화)