Measure the connection between two nodes in a graph This is a question about complex networks
We have various ways to measure the centrality or importance of a node.
$$\textrm{importance} :: \textrm{node} \rightarrow \mathbb{R}$$
The simplest such measure is the degree of the node. 
There are some more advanced measures of centrality like eigenvector/katz/alpha centrality, pagerank, betweenness, etc.... These can find important nodes (in some sense) even when they have low degree.
We can also ask about the connection between two nodes
$$\textrm{connection} :: (\textrm{node}, \textrm{node}) \rightarrow \mathbb{R}$$
What measures do we have here? The analog to degree, the simplest importance measure, would be the weight of the edge between the two nodes (if any). Are there analogs of the other various centrality measures? 
Question: What are known ways of computing the connection between two nodes?
Note - I am particularly interested in concepts which scale to very large graphs
 A: Given a graph $G$, you can make a graph $H$ where the vertices of $H$ are the edges of $G$, and two vertices in $H$ are joined by an edge if and only if the corresponding edges in $G$ meet at a vertex of $G$. Then you can apply your favorite measure of centrality to vertices of $H$, and you'll actually be applying it to edges in $G$. 
I don't know how good a measure of centrality you get this way, but I would think it would be worth a look. 
A: You are probably looking for something like the minimum number of edges (or vertices) that have to be removed from $G$ to destroy every path between two prescribed vertices $u$ and $v$.
For this purpose, running a max-flow algorithm suffices (see Max-flow min-cut theorem) for the edges version, but the same algorithm can be used to solve the problem for vertices, with a simple modification of the input graph.
A: There are a number of ways in which you can measure the connection between two nodes. Here are few:


*

*As you mentioned, the weight of the edge if there is any otherwise 0 (which can be thought of as the least value of the connection).

*Hitting time or Commute time (based on random walks).

*Personalized Pagerank.

*Shortest path length (or geodesic distance).


There are many more I guess. The method that you might want to use depends on what you're trying to do with that. Hope it helps.
A: I find a good solution proposed in here.
In a weighted, undirected graph, basically, the algorithm iteratively updates the value of a node by congregating its neighboring weighted values. After a few iterations, the difference between the values of node $i$ and $j$ indicates the coupling between them. The smaller difference stands for a stronger connection.
At $k$-th iteration, for node $i$, the algorithm firstly gathers its neighboring weighted values and takes a normalization.
$$\tilde{x}_{i}^{(k)} \leftarrow \sum_{j} w_{i j} x_{j}^{(k-1)} / \sum_{j} w_{i j}$$
Then updating the value of node $i$ (holding part of its previous state).
$$x^{(k)} \leftarrow(1-\omega) x^{(k-1)}+\omega \tilde{x}^{(k)}$$
Difference of two nodes can be measured like: $$s_{i j}^{(k)}:=\left|x_{i}^{(k)}-x_{j}^{(k)}\right|$$
