<p>I am not a computer scientist so please bear with me if this is a naive question.</p>

<ol>
<li>Take any graph, pick a set S of vertices (by some criteria or random).</li>
<li>Find two vertices in set S with the most/least number of common neighbors.</li>
</ol>

<p>This feels like a "hard" problem to write an efficient algorithm for, because if set S has n vertices, I might need to make n choose 2 or n(n-1)/2 comparisons. I am hoping to do this "efficiently" in terms of time complexity.</p>

<p>Is there a similar problem in computer science that has been studied, which I can look up in textbooks or research papers?</p>

<p><strong>Edit - Additional Info</strong></p>

<p>Many thanks to the two comments. I should add that I am looking for non-matrix multiplication methods because I am working with a large dataset in a sparse graph format like edgelist or compressed sparse row.</p>

CC BY-SA 3.0
2013-02-07T17:25:53.413Z
for a graph with $n$ vertices this is equivalent to the closest pair problem in the hamming metric in $n$ dimensions. the naive algorithm is $O(n|S|^2)$. For $|S| = \Theta(n)$ you can do $O(n^\omega)$ ($\omega$ - the matrix multiplication exponent) with fast matrix multiplication.
Sasho Nikolov
CC BY-SA 3.0
2013-02-07T19:24:13.973Z
To add more to Sasho's comment: you can also do it in the time that it takes to multiply an $|S|\times n$ by an $n\times |S|$ matrix. You can do this by blocking the columns for instance in time $O(n/|S|\cdot |S|^\omega)=O(n |S|^{\omega-1})$ time. There are also some (theoretically) faster algorithms for rectangular matrix multiplication that you can use to slightly improve this.
virgi
CC BY-SA 3.0
2013-02-07T21:08:42.167Z
@SashoNikolov - Is there any non-matrix multiplication methods? E.g. Edgelist or Compressed Sparse Row? I need to do this for a large dataset. Will update the question!
Legendre
CC BY-SA 3.0
2013-02-07T22:01:05.943Z
@Legendre: Viewing your problem as matrix multiplication is a very natural approach.  More concretely, computing the number of common neighbors for _every_ pair of vertices in S at the same time is equivalent to multiplication between a 0/1 matrix of size |S|×|V| and its transpose.  Therefore, forbidding matrix multiplication approaches to your question sounds an unnatural restriction to me.  Of course, there might be an algorithm which finds the best pair of vertices more efficiently than computing the number of common neighbors for every pair, but I cannot see how to do it.
Tsuyoshi Ito
CC BY-SA 3.0
2013-02-07T23:32:25.217Z
well there is sparse matrix multiplication. i am not sure what you can do there aside from the obvious algorithm. @virgi should know more
Sasho Nikolov
<graph-theory><graph-algorithms><time-complexity>
Finding two vertices with the most/least common neighbors
Legendre
# Finding two vertices with the most/least common neighbors

(Asked by: username_0 on 2013-02-07)

I am not a computer scientist so please bear with me if this is a naive question.

1. Take any graph, pick a set S of vertices (by some criteria or random).
2. Find two vertices in set S with the most/least number of common neighbors.

This feels like a "hard" problem to write an efficient algorithm for, because if set S has n vertices, I might need to make n choose 2 or n(n-1)/2 comparisons. I am hoping to do this "efficiently" in terms of time complexity.

Is there a similar problem in computer science that has been studied, which I can look up in textbooks or research papers?

**Edit - Additional Info**

Many thanks to the two comments. I should add that I am looking for non-matrix multiplication methods because I am working with a large dataset in a sparse graph format like edgelist or compressed sparse row.

**Tags:** graph-theory, graph-algorithms, time-complexity
> **Comments:**
> **username_1**: for a graph with $n$ vertices this is equivalent to the closest pair problem in the hamming metric in $n$ dimensions. the naive algorithm is $O(n|S|^2)$. For $|S| = \Theta(n)$ you can do $O(n^\omega)$ ($\omega$ - the matrix multiplication exponent) with fast matrix multiplication.  
> **username_2**: To add more to Sasho's comment: you can also do it in the time that it takes to multiply an $|S|\times n$ by an $n\times |S|$ matrix. You can do this by blocking the columns for instance in time $O(n/|S|\cdot |S|^\omega)=O(n |S|^{\omega-1})$ time. There are also some (theoretically) faster algorithms for rectangular matrix multiplication that you can use to slightly improve this.  
> **username_0**: @SashoNikolov - Is there any non-matrix multiplication methods? E.g. Edgelist or Compressed Sparse Row? I need to do this for a large dataset. Will update the question!  
> **username_3**: @Legendre: Viewing your problem as matrix multiplication is a very natural approach.  More concretely, computing the number of common neighbors for _every_ pair of vertices in S at the same time is equivalent to multiplication between a 0/1 matrix of size |S|×|V| and its transpose.  Therefore, forbidding matrix multiplication approaches to your question sounds an unnatural restriction to me.  Of course, there might be an algorithm which finds the best pair of vertices more efficiently than computing the number of common neighbors for every pair, but I cannot see how to do it.  
> **username_1**: well there is sparse matrix multiplication. i am not sure what you can do there aside from the obvious algorithm. @virgi should know more  

---

## 0 answers

