두 노드를 포함하는 삼각형의 수

Question

인접 행렬이 있다고 가정 해 보겠습니다. 은 가중치가없고 방향이없는 그래프를 나타냅니다.

I은 ​​B [난]J]가 노드 I 및 J 포함 닫힌 삼각형의 개수 B를 계산하고 싶다.

단지 선형 대수를 사용하여 에서 B을 계산하는 방법이 있나요? 나는 이것을 theano에서 구현하고 싶다.

Answer 1

i과 j이 서로 인접한다고 가정하십시오. 그런 다음 두 가지를 모두 포함하는 삼각형의 수는 두 개의 꼭지점 모두에 연결된 두 번째 꼭지점 수인 k입니다. 나는.

B_i,j = Sum_k A_i,k * A_k,j 

이 거의 행렬과 같습니다

B_i,j = Sum_k (if A_i,k=1 and A_k,j=1 then 1 else 0) 

이것은 우리가 단지 0과 1을 사용하기 때문에 인접 행렬의 대각선은 부울 표현식이 하나의 제품으로 변환 할 수 있습니다 0이라고 가정 곱셈과 실제로 그 것이다 :

B = A^2 

그러나, 우리는 i 및 j가 연결되어 있다는 가정하에 여전히. 이 가정을 최종 공식에 통합하려면 B의 각 구성 요소에 인접 행렬의 항목을 곱하면됩니다. 모든 항목을 0으로 설정하면 i 및 j이 연결되지 않습니다. 그래서 최종 수식은 다음 ^2 자체 및 매트릭스와 * 제품이다

B = (A^2) * A, 

컴포넌트 와이즈 곱이다.