任意の2つのノードを含む三角形の数

Question

隣接行列があるとします。は、重み付けされていない無向グラフを表します。私はB、Bを計算したい

[iは] [J]はノードIとJを含む閉じた三角形の数です。

だけ線形代数を使用してからBを計算する方法はありますか？私はtheanoでこれを実装したいと思います。

Answer 1

iとjがお互いに隣接しているとします。次に、両方を含む三角形の数は、その両方に接続されている他の頂点kの数です。私。

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

これは、我々は唯一の0と1を使用しているため、隣接行列の対角は0ブール式が単一の製品に変換することができていることを前提としています

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

これはかなり行列のように見えます乗算とは確かにそれがある：

B = A^2 

しかし、我々はiとjが接続されているという仮定の下ではまだです。この仮定を最終的な公式に統合するには、Bの各成分に隣接行列のエントリーを掛けるだけでよい。これにより、すべてのエントリが0に設定され、iとjは接続されません。最終的な式は：^2自体と*と行列の積である

B = (A^2) * A, 

成分毎の乗算です。