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). Importantly, the measured proximity is accompanied with a {\em proximity subgraph}, which allows assessing and understanding measured values. Our proximity calculation 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 to measure and extract proximity. Also, we report experimental results and show examples for four large network data sets: a telecommunications calling graph, the IMDB actors graph, an academic co-authorship network, and a movie recommendation system.