3

Suppose I have an undirected adjacency matrix of social connections. Entry $(i,j)$ and $(j,i)$ equal 1 if $i$ and $j$ are friends, and 0 otherwise.

Suppose I want to find all the 2nd order peers and build an adjacency matrix of 2nd order peers such that $(k,m) = 1$ if $k$ and $m$ are second order peers (but not first order peers) and 0 otherwise.

In this case, since we know that the square of the adjacency matrix with diagonal elements equal to zero gives us the number of walks of length 2 between any two individuals, it should follow that if I square the matrix and transform all entries larger than 0 into 1, and subtract from the adjacency matrix of 2nd order peers the original adjacency matrix (to get rid of 2nd order peers who are also 1st order peers) and set all diagonal elements to zero, I get the desired result.

Is there a more elegant way of doing this?

user7530
  • 49,280
Daniel Pinto
  • 133

1 Answers1

2

I'd say your approach is already pretty elegant (and correct)!

Your method is very easy to implement and approximately $O(|V|^3)$. You can run breadth-first search with depth two, starting from each vertex, to compute the first- and second-order neighbors in $O(|V||E|)$; I might do this instead if the network is sparse ($|E| \ll |V|^2$) but since such a search is more complicated to implement I wouldn't necessarily say it's "better" than the simple manipulation of the adjacency matrix you describe.

user7530
  • 49,280