Counting Number Of K-Stars in Graph, Efficiently

Question

I found a formula for counting 2-stars in a graph. Let $A$ be the adjacency matrix of a graph $\mathcal{G}$, then according to Snijders the number of 2-stars in is:

$$ \sum_{1 \leq i < j \leq g} \sum_{k \neq i,j} A_{i,k} \times A_{j,k} $$

where $g$ is the number of nodes in $\mathcal{G}$. This idea is easily extended to a three-stars:

$$ \sum_{1 \leq i < j < k \leq g} \sum_{l \neq i,j,k} A_{i,l} \times A_{j,l} \times A_{k,l} $$

and so on. Now continuing this approach should provide correct results, however it is computationally rather tedious, hence I wanted to ask if there is a more efficient way to calculate those numbers also for higher orders such as four-stars etc. Here is a simple python implementation:

def num_two_stars(A):
    n = A.shape[0]
    s = 0
    for i in range(n):
        for j in range(i+1, n):
            for k in range(n):
                if k != i and k!=j:
                    s += A[i,k] * A[j,k]
    return s

def num_three_stars(A):
    n = A.shape[0]
    t = 0
    for i in range(n):
        for j in range(i+1, n):
            for k in range(j+1, n):
                for l in range(n):
                    if l != i and l!=j and l != k:
                        t += A[i,l] * A[j,l] * A[k,l]
    return t

Answer 1

This is just a brute force algorithm $n^K$. You might find this paper useful. Also, you might possibly generate more interest in this on CS theory stack exchange (?)

Answer 2

A more efficient way to do this is to begin by computing the degrees of all the vertices. From the adjacency matrix, this is just an $O(n^2)$ algorithm: the degree of the $i^{\text{th}}$ vertex is $d_i = A_{i1} + A_{i2} + \dots + A_{in}$.

A vertex of degree $d$ is at the center of $\binom dk$ $k$-stars: we just have to choose $k$ of its neighbors. So the final count is $$\binom{d_1}{k} + \binom{d_2}{k} + \dots + \binom{d_n}{k}.$$

---

The above assumes a simple graph, where every $A_{ij}$ is either $0$ or $1$. If there can be multiple edges between two vertices, this calculation is not appropriate, because we must make sure that all $k$ edges chosen out of the central vertex lead to $k$ different vertices. For this, we'll need a slightly fancier tool to compute the sum of all products $A_{i,j_1} A_{i,j_2} \cdots A_{i,j_k}$ where $j_1 < j_2 < \dots < j_k$ without having to take $k$ nested loops.

Let $s_i(j,t)$ be the number of $t$-stars whose center is $i$ and whose leaves are chosen from $\{1,2,\dots,j\}$. This satisfies the recurrence $$s_i(j,t) = s_i(j-1,t) + A_{ij} \cdot s_i(j-1,t-1)$$ since there are $s_i(j-1,t)$ of these stars which don't have $j$ as a leaf, and $A_{ij} \cdot s_i(j-1,t-1)$ that do. (For the second one, think of these $t$-stars as $(t-1)$-stars using $\{1,2,\dots,j-1\}$ as leaves, together with one of the $A_{ij}$ edges from $i$ to $j$.) We should take the diagonal entry $A_{ii}$ to be $0$ even if there are loops, because loops can't be part of a star.

The recurrence can be used to compute the $k$-tuple $(s_i(j,1), s_i(j,2), \dots, s_i(j,k))$ starting from $j=1$ and ending at $j=n$. Note the base cases: $s_i(j,0)=1$ for all $j$ and $s_i(0,t)=0$ for all $t>0$. At the end, $s_i(n,k)$ is the number of $k$-stars centered at $i$, and $\sum_{i=1}^n s_i(n,k)$ is the total number of $k$-stars.