It would have to be not just decentralized - but federated in the same way that, say, email is. User is identified as user@facebook.com, or so forth, and other social networks could add said user as a connection to someone on their network (and vice versa) via an API.
Could wave/xmmp be used as an underlying protocol for this?