Graph explorer

Generalized Erdos Numbers

We propose a simple real-valued generalization of the well known integer-valued Erdos number as a topological, non-metric measure of the `closeness' felt between two nodes in an undirected, weighted graph. These real-valued Erdos numbers are asymmetric and are able to distinguish between network topologies that standard distance metrics view as identical. We use this measure to study some simple analytically tractable networks, and show the utility of our measure to devise a ratings scheme based on the generalized Erdos number that we deploy on the data from the NetFlix prize, and find a significant improvement in our ratings prediction over a baseline.