AIB 섹션 5 컴퓨터공학 N532 Graph

• 그래프 자료구조의 파생, 왜 필요한지
  • 노드와 노드가 연결. 두 노드가 왜 연결되는지, 어떤 관계가 있는지의 상황에서.
  • 풀어서 얘기하자면 노드 즉 자료 구조 안의 항목들이 서로 복잡한 관계가 있을 때 서로를 연결해주는 자료구조이다.
• 순회?
  • 모든 항목을 다 방문하는 방법. DFS와 BFS가 있어서, 하나의 노드를 타고 끝까지 간 다음 아직 방문하지 않은 노드를 다시 끝까지 타는 것이나, 하나의 노드에 인접한 노드들을 한 번씩 방문하고 다시 그 인접 노드들의 인접 노드를 방문하여 반복하는 방법이 있다.
• 그래프와 트리의 연관성
  • 노드들이 서로 연결되는 부분에서 공통점이 있다. 차이점으로는 트리는 부모(루트)노드에서 자식 노드로 방향이 정해져 있다는 점, 계층구조가 명확하다는 점, 그래프에서는 계층이 없이 노드들이 서로 연결되고 방향도 일방 또는 무방향이 있을 수 있다.

그래프. 조금 더 고도화된 데이터구조.

페이스북의 예제. 페이스북/SNS 친구. 친구의 친구도 있을 수 있는데, 나로부터 몇 번을 거쳐서 친구를 찾을 수 있는지를 생각해볼 수도 있다.

트리는 위에서부터 루트, 부모, 자녀로 구분되는 것이 있는데, 그래프는 루프/순회/사이클를 만들 수 있다. 꼭 위에서부터 내려오는 계층보다 다른 방향에서의 오브젝트 간의 관계를 나타낼 수 있다.

용어: vert(node, 정점), edge(연결선, 간선).

인접: 인접 관계, 이웃이라는 표현.

그래프는 방향이 있을 수 있다. 흐르는 방향으로 Directed(one-way 또는 bidirectional). 방향으로 흘러 끝에 도달할 수 있기 때문에 leaf도 있다. 마지막 노드의 leaf.

방향이 없는 undirected. 상호 교환의 관계. 모든 관계가 양방향이라면 상호 교환이라고 생각해볼 수 있다. 어디로든 모든 노드로 순환할 수 있어서 역시 순환 그래프.

순환/비순환 그래프: 방문했던 노드에 다시 방문하는 순환 그래프 또는 그럴 수 없는 acyclic(루프가 없이 leaf 노드로 흘러감.)

가중 그래프: 가중치에 대한 코드를 별도로 작성해야 함. edge에 가중치의 값이 있음. 예를 들면 도로로 연결되어 있을 때 도로 거리를 가중치라고 생각해볼 수 있다. 그래프를 만들 때 어떤 개념에 가중치를 도입해야 할지 생각해보아야 한다. 효율성과 직결된다.

순회: 그래프에 연결된 노드를 탐색하는 개념. 아직 방문하지 않은 노드가 있을 때 순회 순서가 있을 것이다. DFS, BFS 순회 알고리즘을 나중에 배울 것.

directed acyclic graphs: 순환되지 않는 특정한 단방향 그래프. 데이터 사이언스에 많이 사용된다. 어떤 노드를 스킵한다고 생각해볼 수 있다.

그래프 나타내는 방법: 인접리스트 또는 인접행렬.

인접리스트: 전체 노드 목록을 저장한다. 파이썬에서 딕셔너리로 표현할 수 있다. 각각의 노드가 어디로 갈 수 있는지 해당 노드를 키, 갈 수 있는 인접노드를 밸류로 설정해볼 수 있다. 인접 노드로 이동할 때 상수시간, 특정 노드 간 관계를 확인하기 위해 선형 이상의 시간이 걸릴 수 있음.

인접행렬: 2차원 행렬로 만들었을 때 노드와 노드 간에 연결이 있을 때 가중치 1/2/3, 없으면 0으로 표현해볼 수 있다. 그래서 구현 자체는 쉽다. 그런데 array value 자체만 보고는 행과 열이 무엇을 나타내는지 알 수 없어서 그림을 그려보아야 한다는 단점 있음. 그리고 노드 방문을 확인하기 위해서는 모든 노드를 확인해야 한다고 함. 아마 인접한 노드를 알기 위해서 모든 노드를 확인해야 한다 표현하는 것이 더 맞지 않을까 싶음.

순회

순회: 그래프/트리 구조에서 노드를 한 번씩 탐색하는 개념. traversal time. 특정 노드를 방문하는 방법 찾는 것

• 그래프: 깊이우선 DFS, 너비 우선 BFS. 내일 배울 예정
• 트리: 전위, 중위, 후위
  • 전위: 루트 먼저 방문.
  • 중위: 왼쪽 서브트리 방문 후 루트 방문
  • 후위: 서브트리 모두 방문 후 루트 방문

오전

딥러닝 네트워크 구조: 그래프를 활용한 것

오후

RDB와 NoSQL로 구분하면 그래프는 NoSQL에 해당한다고 볼 수 있다.

자습자료 꼭 확인해보기.

예제

neo4j

그래프의 활용

그래프는 관계 파악이 어렵다. RDB는 칼럼이나 로 추가하면 되는데 그래프는 어디에 어떤 관계를 가지도록 추가해야 하는지 잘 모름

새로운 딥러닝 모델에 그래프를 활용할 수 있을지 생각해보기

데이터 개수가 커지면 배열보다는 리스트를 사용해서 그래프를 나타낸다. 왜냐하면 비어 있는 공간이 엄청 많을거기 때문에 비효율적이라서.

link prediction(knowledge graphs)

relation을 맞추는 과정. TransE 모델. 노드에서 노드를 빼면 그 관계만 남을 것이다. 마치 벡터합(차)처럼. 이미지로도 가능함.

그래프 데이터베이스

그래프 데이터베이스는 데이터와 함께 연결을 같이 저장하고, 복잡하게 연결된 데이터를 관리하는 것에 적합함. neo4j, dgraph, neptune, cassandra.