Anzahl der Dreiecke mit zwei beliebigen Knoten

Question

Nehmen wir an, ich habe eine Adjazenzmatrix A, die einen ungewichteten, ungerichteten Graph darstellt.

Ich möchte B berechnen, wobei B [ i] [j ] die Anzahl der Dreiecke, die geschlossene Knoten i und j umfassen.

Gibt es eine Möglichkeit B von A mit nur linearen Algebra zu berechnen? Ich würde das gerne in theano umsetzen.

Answer 1

Angenommen, dass i und j nebeneinander liegen. Dann ist die Anzahl der Dreiecke, die beide enthalten, die Anzahl der anderen Knoten k, die mit beiden verbunden sind. I.e.

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

Dies setzt voraus, dass die Diagonale der Adjazenzmatrix ist 0. Der Boolesche Ausdruck auf ein einzelnes Produkt umgewandelt werden können, weil wir nur 0 und 1 verwenden:

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

Diese wie Matrix ziemlich aussieht Multiplikation und in der Tat ist es:

B = A^2 

wir jedoch nach wie vor unter der Annahme, dass i und j verbunden sind. Um diese Annahme in die endgültige Formel zu integrieren, müssen wir einfach jede Komponente von B mit dem entsprechenden Eintrag der Adjazenzmatrix multiplizieren. Dies setzt alle Einträge auf Null, wenn i und j nicht verbunden sind. So dass die endgültige Formel lautet:

B = (A^2) * A, 

wo ^2 ist das Matrixprodukt mit sich selbst und * ist komponentenweise Multiplikation.