- 1 - (3) 연결성 측도
(3-1) 회로계수(cyclomatic number) - 연결성 정도를 측정하는 절대 척도 - 제 1 Betti 수(first betti number)
- 회로(circuit)는 여러 연쇄선이 이어져 시작점과 마지막 결절점이 같을 때 나타나는 유한 의 폐쇄경로(closed path)를 말한다.
- 지점간의 연결 상태에 있어서 이러한 회로가 나타나는 것은 연쇄선수가 -1보다 같거나 클 때 즉, ≧-1일 때(단, ≧3) 이다. 즉 네트워크의 최소 구성(점 2, 선 1)의 점과 선의 관계로 나타난다.
- 이러한 회로 중, 3개의 점 이상을 한번씩 통과하는 경우를 기저회로(basic cycle, basic circuit, 독립적인 회로)라고 하며, 이 회로 안쪽에는 다른 회로가 존재 하지 않는다.
- 회로계수는 실제의 연쇄선수( )에서 최소연결상태(g=1, g는 성분)를 구성할 때 필요한 연 쇄선수(-1)를 뺀 값으로 계산된다. μ = -(-1) = - +1 이다. 단 최소연결상태 즉 성분(g)이 1일 때이다.
- 따라서 회로계수 μ = -(-g) = -+g 로 일반화 된다. 따라서 2개 이상의 성분으 로 구성된 그래프도 계산 할 수 있다.
- 즉 회로계수는 중복되지 않는 독립적인 기저회로의 수를 나타낸다.
- 이러한 회로계수는 네트워크상에서의 회로수의 정도를 나타내므로 이 수치가 크면 클수 록 연결성이 좋은 네트워크로 판단 할 수 있다.
- 다음 예제에서 각각의 회로계수를 계산 해보자
- (a) 의 성분수는 5이다.
- (a), (c)와 같은 분리형그래프(비연결성그래프)의 회로계수는 0 이다.
- (d) 와 같은 목형 그래프의 경우도 회로계수는 0이다.
- (b) 와 같은 분리형그래프라도 기저사이클이 존재하면 회로계수 값은 기저회로의 수이다.
- 따라서 분리형이나 목형그래프의 연결 정도를 비교하는 데는 부적절하다.
- 목형그래프는 항상 = -1 의 관계를 갖는다.
- 그래프 내에 기저사이클이 많으면 많을수록 회로계수의 값은 증가한다.
- 그 범위는 0~∞ 이다.
- 2 - (3-2) 알파지수(alpha index)
- 알파지수는 일종의 회로계수의 변형된 상태
- 알파지수란 네트워크상에서 존재 가능한 회로계수(완전연결을 가정한 회로계수)에 대한 실제 네트워크의 회로계수의 비율로 표현된다.
- 알파지수 α =
이다. 이때 는 그래프의 성분수, 비평면그래프의 공식
이다.
- 분자는 분석 대상 네트워크의 회로계수를 나타내며, 분모는 네트워크가 완전연결 상태일 때 가질 수 있는 최대의 회로계수를 의미한다. 따라서 알파지수는 회로계수의 또 다른 측 정 방법으로 비평면그래프의 완전연결상태를 기준(분모)으로한 대상 그래프의 연결상태를 상대적인 비례정도로 나타낸다고 할 수 있다.
- 완전 연결 상태의 점과 선의 관계?
점에 대한 조합관계 개이므로, 점에 대한 선의 관계 이다.
- 회로계수 -+g 의 에 위식을 대입하고, 완전연결상태에서 는 1이므로, = 이다.
따라서 분모는 완전영결 상태에서의 회로계수가 된다. 즉 그래프에 대한 이론적으로 가능 한 회로계수의 최대값이다.
- 만약 분석 대상 네트워크가 완전 연결 상태라면, 분모분자의 값은 같게되어 알파지수는 1 이 된다. 역으로 연결성이 가장 적고, 기저회로를 갖지 않는 목형 구조에서는 분자가 0이므 로 알파지수의 값은 0이 된다.
- 따라서 알파지수는 비율이므로 수치적 범위가 0~1 사이를 나타낸다.
- 범위가 있으므로 크기가 다른 그래프를 비교할 수 있다.
- 앞의 예제에 대한 알파지수를 계산해 보자????????????
- 다음 예제 (g), (h) (i), (j)의 알파지수는????????????
(그림)
- 3 -
- (h), (i), (j)는 비평면그래프의 완전연결 상태이므로 알파지수의 최대값 1이다.
- (a) ~ (d)와 같은 분리형그래프(비연결성그래프)나 목형그래프의 α지수는 0으로, (a)보다 (d)의 그래프가 더 강한 연결을 보임에도 불구하고 구별이 불가능하다는 단점이 있다.
- 앞의 직경, 분산은 그래프의 구성요소인 점과 선에 의한 규모나 흩어짐의 분석에 적당하 다면, 회로계수나 알파지수의 경우는 그래프의 점간의 연결 상태에서 이루어진 결합관계에 의한 연결정도를 파악함에 적당하다.
(3-3) 베타지수(beta index) - 점에 연결된 평균적 선의 수
- 베타지수는 네트워크의 전체 연결 상태에 대한 점에 대한 선의 관계성을 파악하는데 사 용된다.
- 베타지수 β =
- 네트워크 전체에 있어서 점에 대한 평균적 선의 수의 의미를 갖는다.
- 점의 수보다 선의 수가 많으면 많을수록 베타값은 커진다.
비평면그래프가 가질 수 있는 최대의 선의 수 /2의 관계가 성립한다.
이것을 공식의 분자에 대입하면, β =
=
이므로, 가 ∞ 이면,
β값도 ∞ 가 된다. 따라서 최대 값은 ∞이다.
- 점만 있고 선의 연결이 없는 그래프는 =0 이므로 β값도 0 이다. 따라서 β값의 최소값 은 0 이다. 따라서 β값의 범위는 0 ~ ∞ 이다.
- (a) ~ (j) 까지의 베타지수를 계산하여보자??????????????
- 분리그래프나 목형그래프(알파지수 α = 0)의 연결 강도를 구별 할 수 있다.
예를 들어 (c), (d)그래프의 값을 비교해보자?????????????
.
- 베타지수 값이 1인 경우 ; 1개의 성분으로 된 그래프에 있어서, 1개만의 기저 사이클을 갖는 경우이며, 점과 선의 수가 같을 때이다.
즉, μ = (단, μ =1, =1)
(그림) 베타지수가 1인 경우
- 완전 연결그래프의 베타값은 그래프의 점의 수가 많아질수록 커진다.
(i), (j), (h)의 β값은 각각 6/4, 10/5, 21/7 이다.
- 4 -
발달단계 α γ 유형
1 - 0≤ γ <1/3 미발달, 비연결
2 α =0 1/3≤ γ ≤1/2 spinal
3 0< α <1/2 1/2< γ <2/3 grid
4 1/2≤ α ≤1 2/3≤ γ ≤1 delta
표 1 네트워크의 발달단계와 지수의 범위 (3-4) 감마지수 (gamma index)
- 교통지리학자인 W.L., Garrison ＆ D.F., Marble (1961) 제창 - 감마지수는 γ =
- 분모는 n개의 점을 갖는 완전연결네트워크의 가능한 최대 선의 수이다.
- 따라서 감마지수는 네트워크의 완전연결 상태에서 가능한 최대 선의 수(이론상 가질 수 있는 선의 수)에 대한 실제 선수의 비율을 의미한다.
- 실제 선의수/ 완전연결상태의 선의수
- 앞 예제의 (a) ~ (j)의 감마지수를 계산해보자??????????????????????????
- 그래프가 완전연결이라면 γ = 1 즉, 최대값이다.
- 선이 하나도 연결되지 않은 그래프의 감마지수 γ = 0 즉 최소값 - 값의 범위도 0~1이다.
- 분리형그래프나 목형그래프의 연결강도를 구별 할 수 있다.
(4) 형상판별
- 일반적으로 교통망이나 네트워크는 시간이 경과하면서, 도로의 발달이나 선의 연결이 좋 아짐에 따라 선의 수가 늘어난다. 이러한 발달과정에 따라 네트워크가 연결상태를 미발달, 목형(tree, spinal 척골형), 격자형(greed), 델타(delta) 형태로 연결강도가 강해진다.
- 형상판별이란 현재의 네트워크상태가 발달과정상의 어디에 해당되는가를 판단하는 방법 이다.
- 이러한 형상 판별을 위해서는 알파지수와 감마지수가 사용되는데, 앞에서 설명한 비평면 상태의 네트워크가 아닌 평면상태(planar graph)에서 판단한다. 따라서
- 알파지수 α =
이며, 감마지수 γ =
를 사용한다.
- 알파지수의 분모는 평면그래프의 완전 연결상태의 회로계수를 나타낸다.
즉, 회로계수 -+g 에 평면그래프의 점과 선의 관계인 과 완전 연결그래 프이므로 를 대입하면, = 가 된다.
- 감마지수의 분모는 평면그래프의 완전연결상태에서 가질 수 있는 최대의 선의 수 - 두 지표는 분모가 모두 각각에 대한 완전 연결상태의 최대값으로 이루어져 있어서 비평 면그래프와 마찬가지로 0~1의 범위를 갖는다.
- 두지수의 각각의 값의 범위는 아래 표와 같다.
- 5 - (4-1) 형상판별에 사용하는 알파지수의 범위에 대한 고찰 (4-1-1) 목형(tree, spinal, 척추형)의 알파지수가 0이 되는 이유
- 목형이므로 점과 선의 관계는 이다.
α =
에서 이고, 위식을 대입하면, α =
= 0
- 따라서 목형일 때 알파지수는 모두 0이다.
(4-1-2) 격자형(grid)과 삼각형(delta, 델타)의 경계가 1/2이 되는 이유 - 1/2은 격자형의 가장 강한상태와 가장 약한 델타형 사이에 존재 - 델타형의 가장 약한 상태를 고찰하면 된다.
- 델타형의 가장 약한 상태란?
델타모양을 유지하면서 무한히 점을 증가시킨 상태(→∞),
즉 1점을 추가 할 때마다 2개의 선이 증가하면 최소한의 델타형이 유지되지만 이때 1점이 증가 할수록 기저 사이클의 감소가 하나씩(0, 1, 2, 3 ...) 늘어나게 되어 약한 델타 형태를 갖게 된다.
(그림) 교통지리학 220쪽 그림 1-14 참조
- 이때 점과 선의 관계는????? 이다.
- α =
에서 이고, 위식을 대입하면, α =
=
이다.
이식을 미분하면(→ ∞), 1/2이다.
- 6 - (4-2) 감마지수 범위에 대한 고찰
(4-2-1) 1/3의 의미 - 목형의 가장 약한 상태가 1/3 - 목형의 점과 선의 관계 - γ =
=
- 미분하면 1/3
(4-2-2) 1/2의 의미 - 목형의 가장 강한 상태가 1/2
- 목형에서 격자형으로 변화 되는 과정 중 가장 단순한 격자형의 형성되기 바로 직전단계 가 목형의 최대치 상태가 된다.
- 즉 4개의 점과 3개의 선으로 이루어진 목형그래프가 격자형의 직전 상태 - 목형의 점과 선의 관계
- γ =
=
에 를 대입하면, 3/6 =1/2
(4-2-3) 2/3의 의미 - 델타형의 가장 약한 상태가 2/3 - 델타형의 점과 선의 관계 - γ =
- 미분하면 2/3
예) 교통지리학 219쪽 그림 1-13
㉮ =13, =5 이다. α = ?, γ = ? 따라서 미발달형이다.
㉯ =13, =12 이다. α = ?, γ = ? 따라서 ( 형)이다
㉰ =13, =( ) 이다. α = ?, γ = ? 따라서 ( 형)이다.
㉱ =13, =26 이다. α = ?, γ = ? 따라서 ( 형)이다.
- 7 - (5) 중심화(centralization)
중심화란 전체연결망 형태가 어느 정도 중앙에 집중되어있는가를 측정하는 지표를 말한 다. 즉, 하나의 연결망이 얼마나 중앙 집중적 구조를 갖고 있는가?
(가) 중심화 =∑(Cdmax - CdPi)/(V2-3V+2)
여기서 Cd =차수(degree, 연결중앙성) Cdmax = 최대 차수, CdPi =다른 점들의 차수이다.
분모는 최대의 중심화를 이룬 상태(별형)의 값을 의미,
즉,
- 이때, 분모가 점과 선의 조합관계인 = 이 아니고, 인 것은 가장 차수가 높은 점을 빼고 나머지 점들에 대한 조합관계를 나타내기 때문이다.
- 이 그래프의 분자는 (6-6)x1 + (6-1)x 6 = 30 분모는 (7-1)(7-2) = 30 따라서 중심화는 1 또는 100%
- 앞의 그림(가)의 중심화를 계산 하면 ; 분자는 (5-5)x1 +(5-1)x10 +(5-3)x5 = 50 분모는 (16-1)(16-2) = 210
그러므로 50/210 = 0.238 or 23.8%
- 8 -
(6) 네트워크의 분리성의 지표 절단수(cohesion number)와 관절수(articulation number)
- 분리성; 분리되기 쉬운 정도, 연결의 약한 정도
- 지역 또는 국가의 경제력, 군사력을 가장 유효하게 마비시키는 방법의 탐색에 이용 - 지역 간의 연결선이나 지역자체를 파괴함으로서 연결의 유용성을 마비시키거나 시스템을 고립 또는 분리시킴
- 측정 방법은 최소한 몇 개의 선 또는 점을 파괴하면 그래프가 분리되는가? 의 문제 - 이때 점을 파괴하면 연결된 선도 자동으로 삭제됨
- 최소 파괴할 선의 수를 절단수(G), 최소 파괴할 점의 수를 관절수(K) 라고 한다.
(그림)
- 위 그림의 절단수와 관절수는 2 - 관절수가 2가되는 모든 경우의 수는? 6가지 - 그래프에 브리지가 존재하면 절단수는 1이다.
- 그래프 외각에 연결된 브리지 상의 점은 파괴하여도 그래프가 분리되지 않는다. 따라서 관절수의 경우는 점을 삭제한 후에 두개의 분리형 그래프가 형성될 때를 말한다.
- 절단수나 관절수가 작을수록 그래프의 분리성은 높고, 구조적으로 연결성이 약하다
