How to measure the distance (in generalized sense) between geographical regions? I need to construct a distance matrix for a few U.S. counties that are adjacent to one or another, and choosing the definition of distance is very tricky. The shortest path (i.e the minimum number of times one has to cross county borders to walk from A to B) and the Vincenty distance between the most populous cities are not working well already. What are other options?

Also, I read somewhere and some time ago that distance between two geographical regions can be measured by the strength of "interaction". Volume of telephone calls, trajectories of trucks, and frequencies of flights were mentioned. Yet I can't any details about such modeling. Can somebody refer me to a paper or something? Are there open datasets of those souces available? 

Anybody help me out here?
In terms of interaction data, you might be thinking of this paper and this project

I love the idea of using flight data. You could start with this set hosted at Kaggle.

In terms of estimating distance between states, the simplest thing you could do that might work is to measure the distance between state capitals.