Best algorthm to get all combination pair of nodes in an undirected graph (need to improve time complexity)

Best algorthm to get all combination pair of nodes in an undirected graph
(need to improve time complexity)

I have an undirected graph A that has : no multiple-links between any two
nodes , no self-connected node, there can be some isolated nodes (nodes
with degree 0).
I need to go through all the possible combinations of pair of nodes in
graph A to assign some kind of score for non-existence links (Let say if
my graph has k nodes and n links, then the number of combination should be
(k*(k-1)/2 - n) of combinations). The way that I assign score is based on
the common neighbor nodes between the 2 nodes of combination.
Ex: score between A-D should be 1, score between G-D should be 0 ...
The biggest problem is that my graph has more than 100.000 nodes and it
was too slow to handle almost 10^10 combinations which is my first attempt
to approach the solution.
My second thought is since the algorithm is based on common neighbors of
the node, I might only need to look at the neighbors so that I can assign
score which is different from 0. The rest can be determined as 0 and no
need to compute. But this could possibly repeat a combination.
Any idea to approach this solution is appreciated. Please keep in mind
that the actual network has more than 100.000 nodes.