Data & ML & AI
-
[NetwrokX] 방향그래프의 연결성분(Connected Components)Data & ML & AI/NetworkX 2022. 11. 16. 22:14
지난 글에서는 그래프의 연결성분에 대한 개념을 알아보았습니다. 특히 "무방향" 그래프에 대해서 알아보았습니다. [NetwrokX] 그래프 연결성분(연결요소, Connected Components) 그래프 연결성분(연결요소)이란 쉽게 말해서 서로 분리되어 있는 그래프를 뜻합니다. 위의 (A~O)그래프에서는 3개의 연결성분이 있는거죠. 연결성분의 조건 연결성분 안의 모든 노드들은 동일한 brain-nim.tistory.com 지난번의 포스트가 "무방향"임을 강조하는 이유는, 방향그래프에서의 연결성분을 확인하는 방식이 무방향그래프에서와는 조금 다를 수 있기 때문입니다. 방향그래프의 강연결(Strongly Connected)과 약연결(Weackly Connected) 아시다시피, 방향그래프에서의 엣지는 방향성을..
-
[NetwrokX] 그래프 연결성분(연결요소, Connected Components)Data & ML & AI/NetworkX 2022. 11. 15. 01:47
그래프 연결성분(연결요소)이란 쉽게 말해서 서로 분리되어 있는 그래프를 뜻합니다. 위의 (A~O)그래프에서는 3개의 연결성분이 있는거죠. 연결성분의 조건 연결성분 안의 모든 노드들은 동일한 성분 내의 다른 노드와 연결되어 있어야한다. 연결성분 밖에 있는 노드와 연결되면 안된다. 즉, 소외 되는 노드가 없으면서도 외부와의 접촉도 없는, 일종의 섬같은 성분을 연결성분이라고 부르는 겁니다. 위의 조건에 따라, 1번 : {A,E,F,G}는 연결성분이 아닙니다. (서로 분리되어 있으므로) 2번 : {K,L,O}는 연결성분이 아닙니다. (외부의 노드 M,L과 연결되어있으므로) 3번 : 오로지 {A,B,C,D,E}, {E,F,G,H,I}, {J,K,L,M,N,O}만 위 그래프의 연결성분입니다. 무방향 그래프 연결성분..
-
[NetworkX] 레이아웃으로 그래프 예쁘게 그리기 (nx layout)Data & ML & AI/NetworkX 2022. 11. 11. 14:58
NetworkX에서 그래프를 그려서 시각화 하는 가장 쉬운방법은 nx.draw_networkx()입니다. nx.draw_networkx(G) 하지만 결과는 처참합니다. 이게 어떻게 생겨먹은 그래프인가 싶습니다. 이럴 때 layout을 이용하면 편리합니다. kamada kawai layout NetworkX가 기본적으로 제공하는 레이아웃 중 가장 마음 편하게 쓸 수 있는 레이아웃 중 하나입니다. pos = nx.kamada_kawai_layout(G) nx.draw(G, pos, with_labels=True) 훨씬 깔끔해지고, 한눈에 들어옵니다. 그 외 다양한 레이아웃 pos G=nx.path_graph(15) G=nx.complete_graph(15) G=위의 그래프 kamada_kawai_layout..
-
[NetworkX] 네트워크 견고성(Robustness in Networks)Data & ML & AI/NetworkX 2022. 11. 9. 00:32
네트워크 견고성 (Robustness in Networks) The ability of a network to maintain its general structural properties whet it faces failures or attacks 출처 : Applied Social Network Analysis in Python(by Daniel Romero) 네트워크 견고성: 네트워크의 구조를 유지하는 능력, 연결성을 유지하는 능력 네트워크 견고성이란, 네트워크가 고장나거나 공격을 받더라도 연결성을 잃지 않는 능력이라는 뜻입니다. 즉, 노드나 엣지가 제거되더라도 네트워크가 제 기능을 할 수 있느냐는 뜻이죠. 인천공항에 사고가 생기면 김포공항으로 회항하면 되지만(견고성 확보) 제주공항에 사고가 생기면 ..
-
[NetworkX] 그래프를 거리(length)로 설명하는 방법(평균거리, 지름, 반지름, 둘레, 이심률)Data & ML & AI/NetworkX 2022. 11. 3. 22:30
그래프G를 간추려서 수치로 설명하는 방법은 여러가지가 있습니다. Average distance: 모든 노드 간 거리의 평균 nx.average_shortest_path_length(G) 위와 같은 그래프가 있다고 할 때, A로부터 다른 노드들 까지의 거리는 다음과 같습니다. nx.shortest_path_length(G,'A') # 결과 {'A': 0, 'B': 1, 'K': 1, 'C': 2, 'F': 3, 'E': 3, 'G': 4, 'H': 4, 'I': 4, 'D': 4, 'J': 5} A~J까지의 모든 노드들에 대해서 위의 방법을 실행하고, 그 평균을 내면되지만, 굳이 직접 평균을 계산할 필요는 없습니다. nx.average_shortest_path_length(G) # 2.52727272727..
-
[NetworkX] 너비 우선 탐색, 트리 구조 그리기Data & ML & AI/NetworkX 2022. 11. 2. 02:13
너비 우선 탐색 Breadth-First Search, BFS 너비 우선 탐색(Breadth-first search, BFS)은 맹목적 탐색 방법의 하나로 시작 정점을 방문한 후 시작 정점에 인접한 모든 정점들을 우선 방문하는 방법이다. 더 이상 방문하지 않은 정점이 없을 때까지 방문하지 않은 모든 정점들에 대해서도 너비 우선 검색을 적용한다. OPEN List는 큐를 사용해야만 레벨 순서대로 접근이 가능하다. (출처: 위키백과) 그래프의 한 노드에서 다른 모든 노드까지의 길이를 구하는 (그나마) 효율적인 방법 중 하나 아래는 A 노드가 다른 노드들과 얼마나 떨어져있는지 확인하기 위해 너비우선탐색을 진행한 결과입니다. A 본인의 주변 탐색 Distance1 : A와 연결되어있는 B, K의 주변 탐색 Di..
-
[NetworkX] 경로의 개념, 가장 짧은 경로 찾기Data & ML & AI/NetworkX 2022. 11. 1. 23:02
그래프를 그리고 나서 가장 유용하게 활용하는 방법 중 하나는 노드 간 거리를 활용하는 방법입니다. 어떤 노드가 가장 멀리 있는 노드인지, 이쪽 노드에서 저쪽 노드까지 얼마나 먼지를 계산할 수 있습니다. 그러러면 먼저 몇 가지 개념을 익혀야 하겠습니다. 경로 Path 단순히 선(엣지)에 의해 연결된 노드들의 순서를 의미함 X노드에서 Y노드로 가는 경로의 수는 다양함 예시) A에서 H로 가는 경로 A-B-C-E-H A-B-C-F-E-H A-K-B-C-F-E-H .... 경로의 길이 Path length 몇번 건너가면 도착하는가 즉, 몇개의 엣지로 이루어져 있는가 A-B-C-E-H (길이: 4) A-B-C-F-E-H (길이: 5) 노드 간의 길이 Distance between two nodes 노드 간 길이 ..
-
[NetworkX] Assignment 1 - Creating and Manipulating GraphsData & ML & AI/NetworkX 2022. 10. 30. 03:47
본 게시물은 Coursera의 Applied Social Network Analysis in Python(by Daniel Romero)를 통해 자습하며 작성한 게시물입니다. 이 Assignment는 Coursera Jupyter 콘솔에서만 제대로 진행할 수 있습니다. (데이터 파일을 따로 제공하지 않기 때문입니다.) 개괄 원본 Eight employees at a small company were asked to choose 3 movies that they would most enjoy watching for the upcoming company movie night. These choices are stored in the file `Employee_Movie_Choices.txt`. A secon..