1. 네트워크 분석 개요
네트워크(network)란 도로나 수계와 같은 선들의 집합을 의미한다. 거의 대부분의 것이 운송할 화물(goods)이 될 수 있다. 도로망의 경우 사람, 차 등이 될 수도 있고, 물류 네트워크의 경우 화물, 통신망의 경우에는 전화선, 수계의 경우 오염물질 등이 '화물'이 될 수 있다.
네트워크 분석은 래스터 데이터를 사용할수도 있고, 벡터 데이터를 사용할 수도 있다. 그러나 선 객체가 네트워크를 자연스럽게 표현할 수 있고 선 객체에 용량(capacity)이나 단위비용(cost per unit)과 같은 교통 특성을 쉽게 지정할 수 있으므로 벡터 데이터를 많이 사용한다. 네트워크에서 하나의 중요한 구분요소 중의 하나는 네트워크를 구성하는 선들이 방향성을 갖고 있느냐이다. 방향성 네트워크(directed network)는 각 선에 방향이 지정되어 있는 네트워크이고, 비방향성 네트워크(undirected network)는 방향이 지정되어있지 않는 네트워크이다. 후자의 경우 화물은 양 방향을로 운송 가능하다. 네트워크는 노드(node:끝점)에서만 연결되고 중간점(vertex)에서는 연결되지 않는 선들의 집합이라고 가정한다.
네트워크 분석의 경우 대부분 평면 네트워크(planar network) 즉 2차원 평면으로 작성된 네트워크를 이용한다. 실제로 자연에서 존재하는 수계와 같은 네트워크는 평면 네트워크이다. 대축척 도로망의 경우 도로에 다단계의 고가 및 지하 교차로가 존재하기 때문에 평면 네트워크가 될 수 없다. 평면 네트워크는 위상법칙이 간단하기 때문에 계산에 사용하기 쉽다. 모든 지리정보시스템이 평면이 아닌 네트워크를 지원하는 것은 아니지만 이러한 지리정보시스템에서도 약간의 기법을 사용하여 평면이 아닌 네트워크를 처리할 수 있다. 예를 들면 다음과 같은 방법이 있다. 고가 또는 지하 교차로를 교차점에서 분할함으로서 2개의 선을 4개로 만든다. 이러한 상태로 두면 실제로 회전이 불가능한 방향으로도 회전이 가능할 것이다. 일부 지리정보시스템에서는 노드 속성으로서 비용을 추가할 수 있는데 이 비용을 무한대로 함으로써 고가차도나 지하차도인 것처럼 만들 수 있다.
여기까지는 교차로의 기하학적인 형태만을 예를 들어 설명하였을 뿐 네트워크의 상황을 완전히 기술한 것은 아니다. 네트워크에서 어떠한 것이 가능하고 어떠한 것이 불가능한지를 정의하려면 응용에 따라 특수한 별도의 법칙을 필요로 한다. 대부분의 지리정보시스템은 이와 같이 별도의 법칙을 정의할 수 있는 도구를 제공한다. 지리정보시스템은 여러 네트워크 공간분석을 지원하고 있는데 그중에 중요한 것은 최적경로탐색과 네트워크분할이다. 최적경로탐색(optimal path finding)은 네트워크의 도형 및 속성자료를 이용하여 미리 지정한 지점간의 최소비용경로를 산출하는 방법이다. 네트워크 분할(network partitioning)은 미리 정의한 기준에 따라 네트워크요소(노드 및 선분)를 다른 기준위치에 배정하는 방법이다.
2. 최적경로탐색
최적경로 탐색 기법은 네트워크에 존재하는 두 지점간의 최소비용경로를 찾고자 할때 사용한다. 이때 두 지점은 각각 시점(origin)과 종점(destination)이라고 한다. 최적경로 탐색의 목적은 시점에서 종점으로 찾아갈 때 최소의 비용으로 연결되는 선들의 순서를 찾고자 하는 것이다.
비용함수는 예를 들어 경로상의 선의 길이를 비용으로 삼을수 있을 정도로 간단할 수 있다. 그러나 선의 용량이나 최대 전달 속도 등 여행시간을 근사시킬 수 있는 여러 특성을 사용 가능하다. 선에 관련된 비용 외에도 노드를 방문할 때마다 비용을 부과하는 경우도 있다. 이러한 노드 방문 비용을 회전 비용(turning cost)이라고 하며 각각의 노드별로 한 선으로 들어와서 다른 선으로 나갈 때의 비용을 의미하는 별도의 회전 비용 테이블로 정의한다.
최적경로 탐색과 관련하여 순서부여(ordered) 최적경로탐색과 무순서(unordered) 최적경로탐색이 존재한다. 두 가지 경우는 시점과 종점 외에도 중간에 다른 점을 방문하는 경우이다. 순서부여 최적경로탐색에서는 중간점을 방문하는 순서가 정해져 있으며 무순서 최적경로탐색에서는 순서가 존재하지 않는다.
3. 네트워크 분할
네트워크 분할의 목적은 네트워크에 속하는 노드나 선을 여러 개의 목표점에 지정하는 것에 있다. 목표점은 네트워크의 서비스 센터 역할을 담당한다. 서비스는 의료서비스, 교육, 물 공급과 같이 여러 종류가 될 수 있다. 이러한 형태의 네트워크 분할을 네트워크 할당(network allocation)이라고 한다. 또다른 네트워크 분석으로 추적 분석(trace analysis)이 있다. 이것은 주어진 목표점으로부터 상류(또는 하류)에 속하는 부분을 결정하는 것이다. 수계에서 공해물질을 추적하거나 에너지 분배망에서 고장난 곳을 검색하는데 사용한다.
네트워크 할당은 서비스센터의 역할을 하는 여러 목표점에 대하여 네트워크에 속한 노드나 선을 배타적으로 할당하는 문제이다. 문제를 복잡하게 만드는 요소로는 하나의 센터가 수용할 수 있는 자원의 용량, 각 선과 노드의 자원소모량 등이 있다. 자원소모량은 예를 들면 어떤 도로에서 사고가 많이 발생하고 어느 지역에 학생이 더 많이 살며 지역별로 전기소모량이 어디가 더 많은가 등이다.
추적 분석은 네트워크 중에서 선택된 노드에 조건적으로 연결된(conditionally connected)부분을 찾아내는 기법이다. 어떠한 노드나 선이 조건적으로 연결되었다고 하는 것은 노드나 선으로부터 추적원점에 도달하는 경로가 존재하며 연결된 경로가 조건을 만족하는 것을 의미한다.