[자료구조]Network Analysis
카테고리: DataStructure
1. 특수한 유형의 Edge
엣지(Edge)는 그래프에 있는 여러 버텍스(Vertex)를 연결하여 이들 사이의 관계를 표현한다. 두 버텍스르르 잇는 간단한 형태의 엣지도 있는 반면 특수한 형태의 엣지도 존재한다. ### 1) Self-Edge(셀프 엣지) Self 즉 자기 자신과 관계를 형성한 버텍스의 엣지를 말한다.
- Ex)
- John이 개인용 계좌에서 사업용 계좌로 돈을 이체한다면 자기 자신에게 송금을 하는 것이다.
### 2) Hpyeredge(하이퍼 엣지) 엣지 하나가 셋 이상의 버텍스로 연결된 형태이다.
- Ex)
- Jonh, Mike, Sara는 친구이다.
그래프는 하나 이상의 특수한 유형의 엣지를 포함할 수 있다. 즉, 셀프 엣지와 하이퍼 엣지를 모두 가진 그래프도 존재한다.
2. 에고 중심 네트워크(Ego Centered Network)
특정한 버텍스 m에 대한 중요한 정보는 그와 연결된 다른 버텍스들에서 얻을 수 있을지도 모른다. 버텍스 m을 중심으로 한 에고 중심 네트워크는 m과, m에 직접적으로
연결된 이웃들로 구성된다. 이들은 도수(degree)가 1인 이웃이다.
- m 버텍스를 에고(ego)라 한다.
- 바로 인접한 이웃을 알터(alter)라 한다.
이 에고 중심 네트워크는 도수가 1인 이웃만 포함하지만, 도수가 n인 이웃까지 확장하는 것도 가능하다. 이 경우 m으로부터 n단계 멀리 위치한 이웃까지 네트워크를 구성하게 된다.
3. Social Network Analysis
1) 정의
소셜 네트워크 분석(Social Network Analysis, SNA)은 그래프 이론의 주요 활용 분야다. 다음과 같은 조건을 만족하는 네트워크 분석을 소셜 네트워크 분석이라 한다.
- 그래프를 구성하는 Vertex가 사람을 의미한다.
- Vertex로 연결하는 Edge는 친구, 친족, 연인 등 다양한 사회적 관계를 표현한다.
- 그래프 분석을 통해 도출한 결과는 강력한 사회적 파급 효과를 불러올 수 있다.
2) 예시
- 페이스북, 트위터, 링크드인과 같은 소셜 미디어 플랫폼 서비스상에 보이는 개인의 행동에 대한 이해
- 사기 범죄의 발생 경로에 대한 이해
- 사회 내 범죄 행위에 대한 이에
링크드인은 소셜 네트워크 분석 기법의 발달에 크게 기여한 기업이다. Graph Algorithm 분애를 선도하는 기업이다
4. Network Analysis Theory
그래프를 추상화하는 또 다른 방법은 이를 네트워크로 설정하고 네트워크 분석을 위해 고안된 알고리즘을 적용하는 것이다. 네트워크(Network)의 기본 단위는 버텍스(Vertex, 혹은 노드(Node)) 이다. 네트워크는 버텍스로 구성된 거미줄이다. 버텍스를 연결하는 선들은 이들 사이의 관계를 표현한다. 네트워크로 문제를 풀기 위해서는 버텍스가 가진 중요성 또는 유용성을 정량화 해야 한다.
1) 최단 경로(Minimum Path)
경로(Path)란 Initial Vertex와 End Vertex의 길이다. 즉, 시작 버텍스와 끝 버텍스 사이에 있는 일련의 연속적인 버텍스들을 의미한다. 경로 상에 있는 버텍스의 집합을 p라고 하면 경로에서 동일한 버텍스는 단 한번만 등장해야 하므로 p는 중복된 버텍스를 허용하지 않는다.
경로의 길이는 이를 구성하는 엣지의 개수이다. 모든 가능한 경로 중에서 가장 짧은 경로를 최단 경로라한다.
- 응용)
- BFS
- Dijkstra’s algorithm
2) 삼각형
세 개의 버텍스가 세 개의 엣지로 연결된 형태를 삼각형 그래프라고 한다. 주로 버텍스의 성향을 파악하는데 자주 활용한다.
- 버텍스 m을 ego
- 나머지 두 버텍스는 alter
- 두 알터 버텍스가 범죄에 연류되었다 가정
- 버텍스 m의 현재 상태는 모르지만 그래프에 의해 공범일 가능성 제기 가능
- 둘 중 하난의 알터만 범죄에 연류된 경우 m에 대한 경계 완화
3) 밀도
완전 연결 네트워크를 예로들면, 버텍스의 개수가 N인 완전 연결 네트워크의 엣지수는 다음과 같다.
여기서 밀도(Density)의 개념이 등장한다. 밀도란 그래프에서 관측된 엣지 개수와 최대 허용 가능한 엣지 개수의 비율이다. 네트워크에서 확인 가능한 엣지의 개수를 \(Edges_{observed}\)라 한다면 밀도식은 다음과 같다.
모든 버텍스가 상호 연결되어 있는 삼각형 네트워크의 밀도는 1이다. 여기에 엣지를 더 추가하는 것은 불가능하다. 밀도는 항상 1을 초과할 수 없다.
4) 중심성 지표
해당 버텍스가 그래프 내에서 얼마나 중요한지를 나타내는 것이 중심성 지표(Centrality)이다.
- 도수(degree)
- 매개(betweenness)
- 근접(closeness)
- 고유벡터(eigen vector)
도수 중심성(degree centrality)
특정 버텍스에서 연결된 엣지의 수를 도수(degree)라고 한다. 이는 네트워크 내에서 메세지를 얼마나 빠르게 전파할 수 있는지 표현한다. 학급 내에서 친한 친구가 많을수록 도수 중심성(degree centrality)이 높아진다.
버텍스 집합 V와 엣지 집합 Q로 된 그래프 qGraph가 있다고 할때, qGraph는 |V|개의 버텍스와 |q|개의 엣지를 가진다. 도수 중심성은 버텍스의 도수를 (|V|-1)로 나누 값이다.
이 그림에서 버텍스 C의 도수는 4이다. 버텍스 C의 도수 중심성은 다음과 같다.
매개 중심성(Betweeness Centrality)
그래프 내에서 버텍스가 다른 버텍스들 사이에 위치하는 정도를 표현한다. 학급 내에 여러 개의 작은 그룹이 있고, 매개 중심성이 높은 학생은 각 그룹마다 친한 친구들이 한명 씩 있다. 덕분에 친구가 많지 않아도 학급 내의 모든 소식과 소문을 알 수 있다. CS 분야에서는 통신 장애와 같은 부정적 효과를 매개 중심성(betweeness centrality)을 이용해 측정한다.
pGraph에 속한 버텍스 a의 매개 중심성을 계산하는 방식은 다음과 같다.
- 과정
- pGraph에 있는 버텍스들로 페어를 구성하고 페어 간 최단 경로를 계산한다. 이를 \(n_{shortest_Total}\)이라 한다.
- \(n_{shortest_Total}\)을 이용해 버텍스 a를 지나느 최단 경로의 개수를 센다. 이를 \(n_{shortest_a}\)라 한다.
- 계산 공식을 적용한다.
$$C_{betweenness_a} = \frac{n_{shortest_a}}{n_{shortest_Total}}$$
공정성과 근접 중심성(fairness & closeness centrality)
그래프 pGraph에서 버텍스 a의 공정성(fairness)은 자기 자신과 그래프 내 다른 버텍스와의 거리를 모두 더한 것이다. 도수 중심성과 달리 공정성은 직접 연결되어 있지 않은 버텍스와의 거리도 반영한다. 공정성에 역수를 취하면 근접 중심성(closeness centrality)이 된다.
- 계산 과정
- 버텍스 a와 다른 버텍스들을 잇는 최단 경로들을 구한다.
- 이 최단 경로의 거리를 모두 더한다. 이를 \(n_{sum_a}\)라 한다.
- 이 값에 역수를 취한다.
$$C_{closeness} = \frac{1}{n_{sum_a}}$$
고유벡터 중심성(Eigenvector Centrality)
고유벡터 중심성(eigenvector centrality)지표는 다른 버텍스의 중심성을 가중치로 반영한다. 학급 내에서 인기가 많은 학생들과 친하게 지내는 친구는 고유벡터 중심성이 노다. 구글에서 개발한 웹 페이지에 점수를 매기는 페이지랭크 알고리즘은 고유벡터 중심성 지표에서 파생됐다.
5. Python으로 중심성 지표 계산하기
1) Model 생성
import networkx as nx
import matplotlib.pyplot as plt
plt.close('all')
vertex = range(1,10)
edge = [(7,2),(2,3),(7,4),(4,5),(7,3),(7,5),(1,6),(1,7),(2,8),(2,9)]
G = nx.Graph()
G.add_nodes_from(vertex)
G.add_edges_from(edge)
nx.draw(G, with_labels = True, node_color = 'g', node_size = 800)
2) 도수 중심성(Degree Centrality)
[Input]
print(nx.degree_centrality(G))
[Output]
{1: 0.25,
2: 0.5,
3: 0.25,
4: 0.25,
5: 0.25,
6: 0.125,
7: 0.625,
8: 0.125,
9: 0.125}
3) 매개 중심성(Betweenness Centrality)
[Input]
print(nx.betweenness_centrality(G))
[Output]
{1: 0.25,
2: 0.46428571428571425,
3: 0.0,
4: 0.0,
5: 0.0,
6: 0.0,
7: 0.7142857142857142,
8: 0.0,
9: 0.0}
4) 근접 중심성(Closeness Centrality)
[Input]
print(nx.closeness_centrality(G))
[Output]
{1: 0.5,
2: 0.6153846153846154,
3: 0.5333333333333333,
4: 0.47058823529411764,
5: 0.47058823529411764,
6: 0.34782608695652173,
7: 0.7272727272727273,
8: 0.4,
9: 0.4}
5) 고유벡터 중심성(Eigenvector Cetrality)
[Input]
centrality = nx.eigenvector_centrality(G)
print(sorted((v, '{:0.2f}'.format(c)) for v, c in centrality.items()))
[Output]
[(1, '0.24'),
(2, '0.45'),
(3, '0.36'),
(4, '0.32'),
(5, '0.32'),
(6, '0.08'),
(7, '0.59'),
(8, '0.16'),
(9, '0.16')]
Reference
Book: 프로그래머가 알아야 할 알고리즘 40(임란 아미드 저)
댓글 남기기