Yehuda Koren, Stephen North and Chris Volinsky have an interesting paper in KDD 2006 on Measuring and Extracting Proximity in Networks. They looked at the problem of measuring the ‘distance’ between two node in a large graph, such as DBLP co-author graph. The desired distance measure is not a simple shortest path, but a metric that takes into account all of the paths between the two node. Building on work by Chris Faloutsos, they propose a model based on conductance and show that it has many desirable properties. They have a demostration web page that allows one to apply the algorithm on the DBLP co-author database as well as the IMDB database.

The algorithm computes a “connection subgraph” which is small portion of a network that capture the relationships between the nodes. In addition to helping visualize and explain the result, the connection subgraph could have many other uses.

As an example, consider the problem of deciding which A. Joshi is the co-pi on a proposal with Deborah McGuiness. The following shows the proximity scores for two of the A. Joshi’s to McGuiness in the DBLP data.

Aravind Joshi to Deborah McGuiness d = 0.001846 [RUN]
Anupam Joshi to Deborah McGuiness d = 0.3511 [RUN]

The demo page is fun to play with and experimenting with it complements reading the paper as a way to understand the algorithm.

Related posts:

1. Faceted search for DBLP bibliographic data
2. Gossip-Based Outlier Detection for Mobile Ad Hoc Networks
3. Visualizing social networks
4. Analyzing covert social networks
5. Economist on mining social networks