3 ms·
Wonder if you'd have enough user data exposed through the API to actually map out the relevant network... computationally it'd be fairly trivial to verify the u
by ed 19y ago
Wonder if you'd have enough user data exposed through the API to actually map out the relevant network... computationally it'd be fairly trivial to verify the user's guess, but you'd have a hell of a time actually calculating minimum distance with a dataset as large as Facebook's. That's why for the most part you won't see a social network telling you how two users are connected beyond a distance of two hops.
- ed 19y agoJust for fun i calculated the worst-case state space for a network assuming that the average node has 150 peers -- out to 6 hops you have roughly 10^13 unique paths. Not impossible to work with, but you'd have to get pretty clever to reduce the computing time to something practical.
- danteembermage 19y agoDidn't we just see a post about a quantum computer designed to address the traveling salesman problem? Maybe that was reddit...
- eru 19y agoPretty clever? Findind the shortest path between two nodes in a graph is more or less a solved problem..
- brett 19y agoI seem to remember Max Levchin talking about this exact problem at Startup School. He was talking about how Friendster shot themselves in the foot by calculating all the hops between you and whomever's profile you were viewing, slowing page load significantly. He pointed out that Myspace provided similar user experience by simply slapping "Is in your extended network" on all pages.