title: What's the best way of getting the next-nearest neighbors in a graph?
body: <p>I need to calculate something whose value is given by the following inneficient pseudo python code:</p>
  
  <pre><code>def foo(a,b):
     tmp = 0
     for i in graph.nodes():
         for j in graph.nodes():
            tmp += c
            if (i and j are neighbors):
                tmp += a - c
            elif (i and j are next-neighbors):
                tmp += b - c
     return tmp
  </code></pre>
  
  <p>In other words, given all the pairs of nodes, foo = a * (E = number of edges) + b * (EE = number of pairs who are not neighbors but have a common neighbor) + c * ( N(N-1)/2 - EE - E). </p>
  
  <p>I tried to think on some kind of breadth first search but I couldn't. </p>
  
  <p>EDIT: more info</p>
  
  <ul>
  <li>the graph is not static. I constantly add and remove edges, so I can't calculate this only once. I must constantly update the "list of next neighbors". </li>
  <li>I store the graph as an adjacency matrix. </li>
  </ul>