이번에 더 배울 것
CSR(Compressed Sparse Row)은 행렬에서 0이 아닌 칸만 행 순서대로 모아 저장합니다. 그래프로 말하면 노드 0의 이웃, 노드 1의 이웃, …을 한 줄로 이어 붙인 열 번호 배열(indices)과, 각 노드의 이웃이 그 배열 어디에서 시작하는지 적은 행 포인터 배열(indptr)을 씁니다. 가중 그래프라면 같은 위치에 가중치를 담는 값 배열(data)을 하나 더 둡니다.
노드 i의 이웃은 indices[indptr[i]]부터 indices[indptr[i+1]−1]까지입니다. 그래서 indptr의 길이는 N+1이고 마지막 값은 전체 항목 수입니다. 노드 i의 진출 차수는 indptr[i+1]−indptr[i]로 뺄셈 한 번이면 나옵니다. 이웃이 메모리에 연속으로 놓여 있어, 한 노드의 이웃을 훑거나 행렬과 벡터를 곱하는 계산(PageRank 반복 같은)이 빠릅니다.
대가는 수정 비용입니다. 중간 노드에 이웃 하나를 끼워 넣으면 그 뒤의 indices를 모두 한 칸씩 밀고 indptr 값을 고쳐야 합니다. SciPy 문서도 CSR이 산술 연산, 행 단위 조회, 행렬–벡터 곱에 효율적이지만 희소 구조를 바꾸는 작업은 비싸므로 LIL이나 DOK 형식을 쓰라고 안내합니다. 자주 바뀌는 그래프는 수정이 쉬운 구조에 모았다가 분석할 때 CSR로 바꾸는 방식이 흔합니다.
작은 예제로 따라가기
동아리 네트워크를 민수 0, 지아 1, 서준 2, 하린 3, 도윤 4, 유나 5, 태오 6, 보라 7로 번호 매기면 indptr = [0, 2, 5, 8, 11, 14, 17, 20, 22]입니다.
indices = [1,2, 0,2,3, 0,1,3, 1,2,4, 3,5,6, 4,6,7, 4,5,7, 5,6]으로 22개 항목입니다. 무방향 엣지 11개가 양쪽 노드의 목록에 한 번씩 들어갔습니다.
하린(3)의 이웃은 indptr[3]=8부터 indptr[4]=11 직전까지인 indices[8..10] = [1, 2, 4], 즉 지아·서준·도윤이고 차수는 11−8=3입니다.
저장 형식별로 드는 칸 세기
노드 수와 엣지 수가 바뀔 때 행렬과 CSR 중 어느 쪽의 칸 수가 더 빨리 늘어날지 먼저 예상하세요.
작은 그래프에서도 CSR이 절반 이하입니다. 다만 행렬은 칸 하나로 연결 여부를 바로 확인할 수 있다는 장점이 있습니다.
학습을 시작하면 새 문제를 직접 풀고 확인 퀴즈를 마친 뒤 선택한 본과정 회차로 돌아갑니다.