"Or, alternatively, you store my whole friends graph on my device, which presents scalability and performance issues."

With all due respect, this is where you are incorrect. Devices today completely capable of handling a large amount of compressed plain text data. Media would will be links to external sources as storage capacities play catch up.

The CPU of the device would be able to map your entire social graph and do things that are not possible today being that calculating a social graph on a central server for each user is EXTREMELY expensive and basically impossible with high-load services. Kind of like the concept behind folding @ home.