Abstract:

Measuring distance or some other form of proximity between objects is a
standard data mining tool.  Connection subgraphs were recently proposed as a
way to demonstrate proximity between nodes in networks. We propose a new way
of measuring and extracting proximity in networks called "cycle free
effective conductance" (CFEC).  Our proximity measure can handle more than
two endpoints, directed edges, is statistically well-behaved, and produces
an effectiveness score for the computed subgraphs. We provide an efficient
algorithm. Also, we report experimental results and show examples for three
large network data sets: a telecommunications calling graph, the IMDB actors
graph, and an academic co-authorship network.
 

Joint work with Stephen North and Chris Volinsky