📈 그래프 이론
그래프(Graph)
그래프 이론에서의 그래프는 점과 그 점을 연결하는 곡선의 집합을 뜻한다.
일반적으로 많이 알고 있는 y=x², y=x³+1 등의 그래프와는 다른 개념이다.
그래프 이론에서 말하는 그래프는 곡선의 모양, 길이, 점의 위치에는 의미가 없다.
오직 두 점 사이의 직접적 연결 여부에만 관심을 가진다고 할 수 있다.
꼭짓점(Vertex)과 변(Edge)
그래프 이론에서 점은 꼭짓점(Vertex), 곡선은 변(Edge) 이라 부른다.
따라서, 그래프는 꼭짓점 {A1, A2, ...}의 집합 V와 이들 점 사이를 연결하는 변의 집합 E로 정의할 수 있다.
집합 E는 서로 다른 점의 쌍 AiAj들을 순서에 상관 없이 나타낼 수 있다.
순서와 관련이 없기 때문에 AiAj와 AjAi는 같다.
행렬표현 (인접행렬)
그래프는 행렬로도 표현이 가능하다.
Ai와 Aj가 하나의 선에 의해 연결되면 aij = 1, 연결되지 않는다면 aij = 0으로 둘 수 있다.
방향이 없는 그래프는 자연스럽게 대칭 행렬이 된다.
차수(Degree)
점 Ai의 차수는 Ai를 끝점으로 가지는 변의 개수로 계산할 수 있다.
유향그래프
만약 변이 방향을 가지고 있다면?
새로운 그래프, 유향그래프를 정의해 볼 수 있게 된다.
유향그래프에는 시작점과 끝점이 존재한다.
AiAj에서는 시작점이 Ai, 끝점이 Aj가 되는 것이다.
반대로 AjAi는 시작점과 끝점이 각각 Aj, Ai가 된다.
우리는 이같은 변들을 유향변(directed line)이라 부른다.
일반적으로 그래프 이론은 여러 사회적 구조를 분석하고 연구하는 데에 잘 쓰인다.
인적 네트워크를 분석할 때 사람을 점으로,
그들 사이의 관계를 변으로 나타낸다고 생각해 보자.
🧍♂️ ------------- 🧍♀️
무향 그래프에서는 방향이 없으므로 서로 동시에 아는 사이만 나타낼 수 있다.
🧍♂️ ------------➤ 🧍♀️ ------------➤ 🧍♂️
그러나 유향 그래프에서는 A는 B를 아는데, B는 A를 모르는 관계 또한 나타낼 수 있다.
'좋아한다', '신뢰한다'를 분석할 때는 유향 그래프의 장점이 더욱 도드라질 수도 있다.
따라서, 유향그래프는 상황에 따라 매우 흥미롭고 유용한 도구가 된다.
내차수(indegree)와 외차수(outdegree)
점으로부터 시작하는 변의 수를 내차수(indegree)라 한다.
반대로 점에서 끝나는 변의 수를 외차수(outdegree)라고 한다.
그래프에서의 거리
그래프에서 거리는 출발점에서 도착점까지의 지난 점의 개수를 통해 알아볼 수 있다.
변이 반복되지 않으면 두 점 사이를 연결하는 경로가 형성되므로, 거리도 알아볼 수 있다.
추가로 유향 그래프에서 경로의 시작점과 끝점이 동일하다면,
그 경로를 닫힌 경로라고 부른다.
시작점과 끝점이 다를 때는 열린 경로라고 부른다.
🌎 네트워크 분석
네트워크
네트워크란 사람, 조직, 사물 등을 연결시키는 관계, 즉 연결망을 뜻한다.
네트워크 이론은 그래프 이론의 그래프를 현실 시스템에서 나타난 것이라고 해석할 수 있다.
네트워크는 그래프 이론과 마찬가지로
변수(Node) 와 그들의 관계(Link, or Edge) 를 통해 정의할 수 있다.
그래프와 네트워크, Node는 Vertex와, Edge는 Link와 자주 혼용되어 쓰이므로 알아두는 것이 좋다.
아무튼 우리는 네트워크 분석을 통해 시스템 속 복잡한 관계 패턴을 추정할 수 있으며,
구조를 파악함으로써 네트워크의 핵심 특징을 알아낼 수도 있다.
가중 네트워크
가중 네트워크는 Edge에 가중치가 주어진 네트워크를 뜻한다.
인적 네트워크를 다시 한 번 떠올려 보자.
🧍♂️A ------------- 🧍♀️B ------------- 🧍♀️C
A와 B는 서로 아는 사이고, B와 C도 서로 아는 사이다.
하지만 A와 B는 거의 매일 만날 정도로 친하고, B와 C는 얼굴만 아는 사이다.
단순히 '안다', '모른다'의 개념이 아닌,
'얼마나 친한가?'를 연구하는 네트워크를 위해서는 가중치(Weight) 를 사용할 수 있다.
🧍♂️A ---15--- 🧍♀️B -------2------ 🧍♀️C
Node 간의 거리는 가중치의 역수로 구할 수 있다.
즉, 가중치가 클 수록 거리가 가깝다.
중심성 (Centrality)
중심성은 Node의 중요도를 평가하는 여러 지표를 통틀어 지칭하는 개념이다.
중심성 지수 지표에는 연결중심성, 근접중심성, 매개 중심성이 가장 대표적으로 사용된다.
첫 번째로 연결 중심성은
그래프 이론 부분에서 소개한 차원(Degree)의 개념으로 설명할 수 있다.
단순하게 하나의 Node에 얼마나 많은 Edge가 연결 되었는지 알아보는 것이다.
그리고 Node들 중에서 가장 높은 연결 중심성을 가지는 것을 허브(Hub) 라 부른다.
연결 중심성은 네트워크 전체 구조를 분석할 때 가장 중요한 지표로 쓰인다.
두 번째로 근접 중심성이다.
근접 중심성은 한 Node와 모든 Node들의 거리를 계산함으로써
가장 최단 거리를 갖는 Node를 찾아내는 것이다.
근접 중심성을 통해 네트워크에서 가장 영향력 있는 사람을 식별할 수 있게 된다.
마지막으로 매개 중심성이다.
매개 중심성은 소수의 Edge만으로도 다른 Node들 사이를 매개하는 중개자를 알아내기 위해 사용된다.
Node와 Node 사이를 최단 경로로 연결하여 다리 역할을 하는 Node를 찾는 것이다.
그룹화
네트워크에서 동일한 경로를 갖거나 인접한 Node들을 그룹화 하여 분석할 수 있다.
비슷한 특성을 지닌 그룹을 구분하거나 Node들의 연결 관계만으로 분석에 어려움이 있을 때 유용하게 사용할 수 있으며, 이를 Clustering 분석 기법이라고 부른다.
💡http://math.ewha.ac.kr/~jylee/Finite/TextBook-2017/Chap10.pdf
💡https://namu.wiki/w/네트워크%20이론
💡https://www.kipa.re.kr/cmm/fms/FileDown.do?atchFileId=FILE_000000000008551&fileSn=10
상단의 자료를 참고하여 공부하고 정리했습니다.
