- Measuring and extracting proximity in networks
- Yehuda Koren, Stephen North, and Chris Volinsky
- KDD pp. 245-255, 2006.
PDF (212K)
- 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.
|
