[소프트웨어 응용] 네트워크 구조

Network Structure

네트워크의 구성요소

네트워크; 구성요소들과 그들의 상호작용 → 이 전체 구조

Objects : nodes, vertices

Interactions : linkes, edges

System : network, graph

Network or Graph

→ 실제 시스템과 수학적인 표현

Network: 실제 시스템. 일반적인 용어

영화배우, 단백질 구조, Web, 소셜 네트워크, 도로 시스템, 인간관계 등

professional network, sexual networks, citation network

Network, Node, Link

Graph: 네트워크의 수학적인 표현.

웹 그래프. 소셜 그래프.

Graph, vertex, edge

Undirected vs. Directed Network

엣지에 방향성 존재 여부에 따라

Undirected

directed

Connectivity of Undirected Graphs

그래프의 연결성에 따라 connected / disconnected

Connected graph: 그래프 상의 모든 임의의 두 노드 사이에 길이 존재하면

Disconnected graph: 두 개 이상의 연결된 컴포넌트들로 이루어짐

컴포넌트 : 연결된 노드들. isolated node도 컴포넌트다.

Giant Component : 가장 큰 컴포넌트

연결 그래프에서 지우면 연결이 끊어지는 애들

Bridge edge: 만약 지우면, 그래프는 disconnected가 됨 (엣지)

Articulation point: 만약 지우면, 그래프는 disconnected가 됨 (노드)

Connectivity of Directed Graph

방향성이 있는 그래프에서 연결성이 존재하면 두 가지로 나뉜다.

Strongly connected directed graph: 그래프 상의 모든 각 노드들은 다른 모든 노드로 가는 길이 존재한다. (A→B, B→A 다 존재한다)

Weakly connected directed garph: 만약 무방향 그래프라고 치면, 연결 그래프 일 경우