그래프의 연결 요소(connected component)

1. connected component connected component란 다음 두 조건을 모두 만족하는 node의 집합 1) 모든 node가 path로 연결이 가능하다 2) 하나의 node를 추가 했을 때 위 조건을 만족해서는 안된다. 쉽게 생각해서 서로 연결되어 모여있는 집합들이 연결요소다. {9} 하나의 경우도 위 network에서 하나의 연결요소다. 두번째 조건이 무슨 말인지 이해하기 어려운데 {1,2,3,4}의 경우 node 5를 추가하면 {1,2,3,4,5}는 첫번째 조건을 만족하므로 {1,2,3,4}는 연결요소가 아니라는 뜻이다. 2. giant connected component In many networks as the network grows the components get gra..

• format_list_bulleted Graph
• · 2023. 7. 23.
• textsms

그래프의 연결성(degree)에 대한 고찰

1. degree 어떤 node V의 degree란 V에 연결된 link의 수 혹은 V의 neighbor의 수와 같다. 그래서 V의 degree를 $d(V)=\left | N(V) \right |$로 표기 1은 2,5와 연결되어 있어서 1의 연결성은 2이다. 2. direction graph 방향성이 있는 그래프의 경우 나가는 연결성(out degree)와 들어오는 연결성(in degree)을 구분한다. 당연하겠지만 나가는 연결성(out degree)는 특정 node V에서 나가는 방향과 연결된 node의 수이고 $d_{out}(V)=\left | N_{out}(V) \right |$으로 표기 들어오는 연결성(in degree)는 특정 노드 V에 들어오는 방향으로 연결된 node의 수이고 $d_{in..

• format_list_bulleted Graph
• · 2022. 2. 16.
• textsms

그래프의 path, distance, diameter 그리고 작은 세상 효과(small world effect) 이해하기

1. path 두 node u와 v사이 path란 다음 두 조건을 모두 만족하는 순열이다. u에서 시작해서 v로 끝난다. 부분순열에서 연속된 두 node는 link되어 있다. 왕복하는 1,4,3,4,6,8도 1에서 8까지 path인데 1에서 시작해서 8로 끝나고 어느 두 연속된 node도 link되어 있어서 그렇다. 5에서 6은 끊어져있으니 1,3,4,5,6,8은 path가 아니다. 2. the length of path 해당 path에 존재하는 모든 link의 길이를 말한다. 1,4,6,8에는 3개의 link가 존재하므로 길이는 3 물론 link 1개의 길이가 1일때 그렇다 3. distance 두 node u와 v사이 distance는 모든 path중 최단경로의 길이 u와 v사이 모든 path를 구해..

• format_list_bulleted Graph
• · 2022. 2. 13.
• textsms

실제 그래프(real graph)와 랜덤 그래프(random graph)

1. 실제 그래프(real graph) 실제 그래프(real graph)는 실제 존재하는 complex system으로부터 데이터를 얻어 표현한 그래프 MSN은 옛날에 microsoft에서 서비스하던건데 지금은 안한다고 한다 실제 그래프는 어떻게 이해해야할까? 잘 이해하기위한 비교대상이 필요하다. 그것이 바로 random graph 2. 랜덤 그래프(random graph) In mathematics, random graph is the general term to refer to probability distributions over graphs. Random graphs may be described simply by a probability distribution, or by a random pro..

• format_list_bulleted Graph
• · 2022. 2. 3.
• textsms