이번에 더 배울 것
인접 행렬 A를 자기 자신과 곱한 A²의 (i, j) 칸은 Σ_k A[i][k]×A[k][j]입니다. 곱 A[i][k]×A[k][j]는 i–k와 k–j가 모두 있을 때만 1이므로, 이 합은 i에서 출발해 정확히 두 걸음 만에 j에 닿는 걸음(walk)의 개수입니다. 무방향 그래프에서 i와 j가 다르면 이 값은 두 노드의 공통 이웃 수와 같습니다.
대각선 칸 A²[i][i]는 i에서 나갔다가 바로 돌아오는 두 걸음의 수, 즉 차수입니다. 같은 방식으로 Aᵏ의 (i, j) 칸은 길이 k인 걸음의 수입니다. 걸음은 같은 노드를 다시 지나도 되므로 경로와 다릅니다. A³의 대각선 i칸은 i에서 세 걸음 만에 돌아오는 수인데, 삼각형 하나가 두 방향으로 세어지므로 ‘i가 속한 삼각형 수×2’입니다. 그래서 그래프 전체의 삼각형 수는 A³ 대각선 합÷6입니다.
공통 이웃 수는 ‘친구의 친구’ 추천의 기본 점수로 쓰이고, 79회차의 링크 예측으로 이어집니다. 다만 A²은 원래 A보다 훨씬 빽빽해집니다. 이웃이 1만 명인 허브 하나만 있어도 그 이웃끼리 두 걸음으로 이어지는 칸이 1만×1만=1억 개 생기므로, 실제로는 필요한 행만 계산하거나 희소 행렬 곱을 씁니다.
작은 예제로 따라가기
동아리 네트워크에서 A²[민수][하린] = 2입니다. 공통 이웃이 지아·서준 두 명이라 민수→지아→하린, 민수→서준→하린 두 걸음이 있습니다.
A²[하린][유나] = 1(공통 이웃 도윤), A²[민수][도윤] = 0(두 걸음으로는 닿지 않으며 실제 거리는 3)이고, 대각선 A²[하린][하린] = 3은 하린의 차수입니다.
A³의 대각선은 민수 2, 지아 4, 서준 4, 하린 2, 도윤 2, 유나 4, 태오 4, 보라 2로 합이 24이고, 24÷6=4가 동아리 네트워크의 삼각형 수입니다.
곱할수록 퍼지는 걸음
A, A², A³에서 민수 행의 0이 아닌 칸이 몇 개가 될지 먼저 예상하세요.
한 걸음으로는 직접 이웃인 지아와 서준에만 닿습니다.
학습을 시작하면 새 문제를 직접 풀고 확인 퀴즈를 마친 뒤 선택한 본과정 회차로 돌아갑니다.