그래프 알고리즘 (1)

그래프란

• 그래프는 레온하르트 오일러가 ‘쾨니히스베르크의 일곱 개 다리’ 문제로부터 유래되었다. 그래프는 수학에서 유래되었고 데이터를 모델링하고 분석하는 실용적이고 충실한 방법이다.

• 그래프를 구성하는 객체를 노드 또는 정점이라고 하며 이들 사이의 링크를 관계, 링크, 또는 엣지라고 한다. 이 책에서는 노드와 관계라는 용어를 사용한다. 노드는 문장 내에서 명사로, 관계는 노드에 콘텍스트를 제공하는 동사로 생각할 수 있다.

• 그래프는 실제 세계에 쉽게 맵핑 되고, ‘화이트보드 친화적’이기 때문에, 매력적이기도 하다. 이는 데이터 모델링과 분석을 조정하는데 도움이 된다.

그래프 분석과 알고리즘은 무엇인가?

• 그래프 알고리즘은 그래프 분석 도구의 서브 집합이다. 그래프 분석은 사용자가 하는 일로, 그래프 기반의 연결 데이터를 분석한다.

• 사용자가 분석하려고 다양한 방법을 사용할 수 있다. 그래프 데이터를 질의하거나, 기본 통계를 사용하거나, 그래프를 시각적으로 탐색하거나, 그래프를 머신러닝 작업에 통합할 수 있다. 그래프 패턴 기반 질의는 종종 로컬 데이터 분석에 사용되는 반면에 그래프 계산 알고리즘은 일반적으로 더 글로벌하고 반복적인 분석을 참조한다.

• 네트워크 과학자들은 그래프 알고리즘을 사용해 숨겨진 정보를 발견하고, 가설을 테스트하고, 행동을 예측한다.

OLPT 와 OLAP

• OLTP은 일반적으로 티켓 예약, 계정 입금, 판매 예약과 같은 짧은 동작을 의미한다. OLPT는 방대한 저지연 질의 프로세싱과 높은 데이터 무결성을 가짐을 의미한다.

• OLTP는 트랜잭션당 적은 수의 레코드만 포함할 수 있지만 시스템은 많은 트랜잭션을 동시에 처리한다.

• 반면에 OLAP은 많은 레코드에 대해서 더 적지만 오래 동작하는 트랜잭션을 처리한다. OLAP은 OLTP에서 발견되는 트랜잭션 업데이트를 고려하지 않고, 더 빠른 읽기에 집중하며 배치 지향 작업을 일반적으로 처리한다.

• 그러나 최근에 OLAP과 OLTP 사이의 경계가 모호해지기 시작했고 최근 데이터 집약적 애플리케이션은 실시간 트랜잭션 작업과 분석을 결합한다. 이러한 애플리케이션의 병합은 확장 가능한 트랜잭션 관리 및 증분 스트림 인스턴스와 같은 소프트웨어의 여러 발견과 저렴한 대용량 하드웨어의 의해서 촉진됐다.

그래프 알고리즘에 관심을 가져야하는 이유

• 그래프 알고리즘은 연결 데이터의 이해를 돕는데 사용된다. 우리는 단백질 상호작용에서 소셜 네트워크까지, 통신 시스템에서 전력망에 이르기까지, 실세 시스템의 관계를 볼 수 있다. 네트워크와 네트워크 내부의 연결을 이용하면 여러 통찰력과 혁신을 위한 놀라운 잠재력을 얻을 수 있다.

• 데이터가 더 많이 연결되고, 데이터 관계와 상호 종속성의 이해가 점점 더 중요해지고 있다. 네트워크의 성장을 연구하는 과학자들은 시간이 지날 수록 연결성이 증가하지만 균일하지는 않다고 밝혀냈다.

• 많은 타입의 그래프와 많은 실제 네트워크가 집중되어 있다. 여행 및 소셜 네트워크와 같은 그래프와 마찬가지로 웹은 몇 개의 노드가 고도로 연결되고 대부분의 노드가 적당히 연결되는 멱법칙 분포를 가진다.

그래프 이론과 개념

• 레이블이 있는 그래프는 그래프 데이터를 모델링하는 가장 인기 있는 방법 중 하나다. ‘레이블’은 노드를 그룹의 일부로 표시한다. (분류를 위한 레이블을 가질 수 있다. 레이블은 본연의 인덱스를 사용한다.)

• 관계느 관계 타입에 따라서 분류한다. (타입과 방향으로 노드의 관련성을 나타낸다.)

• 프로퍼티는 속성과 같으며 숫자와 문자열에서 공간 및 시간 데이터에 이르기까지 다양한 데이터타입을 포함할 수 있다. (노드와 관계의 속성, 이름 - 값 쌍으로 저장, 보통의 인덱스와 복합 인덱스를 저장할 수 있다.)

• 서브 그래프는 큰 그래프 내의 그래프다. 서브 그래프는 집중 분석을 위해 특정 특성을 가진 서브 집합이 필요한 경우의 필터로 사용되기에 유용하다.

• 그래프는 타입, 모양, 크기, 분석에 사용할 수 있는 속성의 종류가 다르다. 다음으로 그래프 알고리즘에 가장 적합한 그래프 종류를 설명한다.

그래프 타입과 구조

• 고전적인 그래프 이론에서 그래프라는 용어는 노드 간에 하나의 관계만 있는 단순한 그래프와 동일하다. 그러나 대부분의 실제 그래프는 노드 사이에 많은 관계와 심지어 자체 참조 관계를 가진다.

• 그래프는 다양한 형태를 취한다. 아래에서 세가지 대표적인 네트워크 타입을 보여준다.

랜덤 네트워크

• 연결의 완전한 평균 분포에서 랜덤 네트워크는 계층 구조가 없다. 이러한 타입의 무형 그래프는 식별 가능한 패턴이 없는 ‘평평’ 한 모습을 가진다. 모든 노드는 다른 노드에 연결될 확률이 같다.

작은 세상 네트워크

• 작은 세상 네트워크는 소셜 네트워크에서 매우 일반적이다. 현지화된 연결과 일부 허브와 스포크 패턴을 보여준다. ‘케빈 베이컨의 여섯 다리’ 게임은 작은 세상의 효과에 잘 알려진 예일 수 있다. 소수의 친구와 어울려도 그 친구가 유명배우이거나 지구 반대편에 있더라도 먼 관계가 아니다.

척도 독립 네트워크

• 척도 독립 네트워크는 멱 법칙 분포가 있고 월드 와이드 웹과 같이 규모에 관계없이 허브와 스포크 아키텍처를 가질 때 만들 수 있다.

• 이러한 네트워크 타입은 고유한 구조, 분포, 동작을 갖는 그래프를 만든다. 그래프 알고리즘을 사용하면, 결과에서 유사한 패턴을 볼 수 있다.

그래프가 갖는 여러 특징

• 그래프 알고리즘을 최대한 활용하려면, 접하게 될 가장 특징적인 그래프에 익숙해지는 것이 중요하다.

연결과 비연결 그래프

• 모든 노드 사이에 경로가 있는 경우 그래프는 연결된다. 그래프에 섬이 있으면 비연결이다. 섬의 노드에 연결돼 있으면 컴포넌트 (또는 클러스터) 라고 한다.

비가중 그래프와 가중 그래프

• 비가중 그래프에는 노드나 관계에 가중치 값이 할당되지 않는다. 가중 그래프의 경우 이러한 값은 비용, 시간, 거리, 용량, 도메인 별 우선순위와 같은 다양한 측정 값을 나타낸다.

• 기본 그래프 알고리즘은 실행에 대한 가중치를 관계의 강도나 가치에 대한 표현으로 사용할 수 있다. 많은 알고리즘이 후속 작업을 위한 가중치로 사용할 수 있는 내림수를 계산한다.

• 일부 알고리즘은 누적 합계, 최저 값 또는 최적 값을 찾으려고 계속 가중치 값을 업데이트한다.

• 가중 그래프의 고전적인 사용은 경로 찾기 알고리즘에 있다. 이러한 알고리즘은 휴대폰의 맵핑 애플리케이션을 뒷받침하고 있고 위치 간 가장 짧고 / 가장 저렴한 / 가장 빠른 전송 경로를 계산한다.

• 가중치가 없는 경우에는 가장 짧은 경로는 관계수가 되겠지만, 가중치가 있는 경우에는 총 합이 적은 방향으로 이동하게 된다.

비방향성 그래프와 방향성 그래프

• 비방향성 그래프에서 관계는 양방향 (예, 우정)으로 간주된다. 방향성 그래프에서 관계는 특정한 방향을 가진다. 노드를 가리키는 관계는 인링크라고 하며, 당연히 아웃링크는 노드에서 시작된다.

• 방향은 정보의 또 다른 차원을 추가한다. 동일한 타입이지만 반대 방향의 관계는 서로 다른 의미론적 의미를 전달하고 종속성을 표현하거나 흐름을 나타내며 신뢰성이나 그룹 강도의 지표로 사용될 수 있다.

• 도로망은 두 가지 타입의 그래프를 모두 사용하려는 이유를 보여준다. 예를 들어서 도시간 고속도로는 종종 양방향으로 이동한다. 그러나 도시 내 일부 도로는 일방통행 도로 형태를 가진다. (일부 정보 흐름도 마찬가지다).

• 방향성과 비교해 비빙향성 방식으로 알고리즘을 실행하면 다른 결과를 얻는다. 예를 들어 고속도로나 우정의 경우 비방향성 그래프에서 모든 관계는 항상 양방향으로 진행된다고 가정한다.

비순환 그래프와 순환 그래프

• 그래프 이론에서 순환은 동일한 노드에서 시작하고 끝나는 관계와 노드를 가진 경로다. 비순환 그래프에서는 그러한 순환이 없다.

• 방향성 비순환 그래프는 정의에 따라서 항상 막다른 끝 (리프 노드)을 가진다.

• 사이클의 사용은 일반적이며, 때때로 순환 그래프를 비순환 그래프로 변환해야 한다 (관계를 절단). 방향성 비순환 그래프는 일정, 계보, 버전 기록에서 자연스럽게 얻을 수 있다.

트리

• 고전적인 그래프 이론에서 방향성이 없는 비순환 그래프를 ‘트리’라고 한다. 컴퓨터 과학에서 트리는 방향성을 가질 수 있다. 트리의 더 포괄적인 정의는 두 노드가 하나의 경로로만 연결되는 그래프다.

• 트리는 그래프 구조와 많은 알고리즘을 이해하는 데 중요하다. 네트워크, 데이터 구조와 검색 최적화를 설계해 분류 또는 조직 계층을 개선하는데 핵심적인 역할을 한다.

• 트리에는 많은 변형이 있는데 특히 신장 트리가 이 책과 가장 관련이 높으며, 신장 트리는 더 큰 비순환 그래프의 모든 노드를 포함하지만, 관계는 포함하지 않는 비순환 서브 그래프이다. 최소 신장 트리는 그래프의 모든 노드를 최소 홉 수나 최소 가중치 경로로 연결한다.

희소 그래프와 밀집 그래프

• 그래프의 희소성은 모든 노드 쌍 사이에 관계가 있을 경우 발생할 수 있는 최대 가능한 관계 수와 비교한 관계수를 기반으로 한다. 모든 노드가 다른 모든 노드와 관계가 있는 그래프를 완전 그래프 또는 구성 요소의 클릭이라고 한다.

• 예를 들면 모든 친구가 서로를 안다면, 그것은 클릭이 된다. 그래프의 최대 밀도는 완전 그래프에서 가능한 관계의 수 다.

• 엄격한 구분선은 없지만 실제 밀도가 최대 밀도에 가까워지는 그래프는 밀도가 높은 것으로 간주한다. 실제 네트워크를 기반으로 한 대부분의 그래프는 전체 노드와 전체 관계의 희소한 선형 상관 관계를 가진다.

• 많은 와이어, 파이프, 도로 또는 우정이 한 지점으로 몰릴 때 실질적인 제한과 같은 물리적 요소가 사용되는 경우가 해당한다.

• 일부 알고리즘은 극도로 희소하거나 밀집 그래프에서 실행될 때 의미 없는 결과를 반환한다. 그래프가 너무 희소하면 알고리즘이 유용한 결과를 계산하기에 충분한 관계가 없을 수 있다. 또한 매우 밀집된 연결 노드는 연결성이 높기 때문에 추가 정보를 많이 가지지 않고 있고 고밀도는 일부 결과를 왜곡하거나 계산 복잡성을 추가할 수 있다.

• 이러한 상황에서 서브 그래프를 필터링 하는 것이 실용적인 방법이다.

일분, 이분, K분 그래프

• 대부분의 네트워크는 여러 노드와 관계형 데이터를 포함한다. 그러나 그래프 알고리즘은 하나의 노드 유형과 하나의 관계 유형만을 고려하는 경우가 많다. 하나의 노드 타입과 관계 타입이 있는 그래프를 일분이라고도 한다.

• 이분 그래프는 노드를 두 세트로 나눌 수 있는 그래프로 관계는 한 세트의 노드와 다른 세트의 노드만 연결한다. (여기서 멈춤…)

참고 문헌

• 그래프 알고리즘