Or just have different sections/tabs for each of the detected cliques (detecting cliques is a (edit: somewhat) solved problem: http://en.wikipedia.org/wiki/Clique_(graph_theory) ). It'd be the onus of the user to name the cliques, with a suggested default of what others in the clique have named it.
That way if someone you don't want joins your clique, it shouldn't matter - if you're not friends with them.
Cliques should, ideally, correspond to smallish social circles. Such that you can easily monitor and make sure the right people are ending up in the 'right buckets.'
For example, excluding family and co-workers, I have two primary groups of friends. Those in my neighborhood, whom I know based on locality, and those scattered around the city, whom I know (and know each other) through mutual interests. One has nine individuals (with more - about 5-10 who are acquaintances, but not truly friends), and the other has eight individuals (with more - again, about 5-10 who are acquaintances).
Maybe I'm a-social or something. But. There is no overlap between these groups. I've introduced a few in one to a few in the other, but there's no reason for them to gel. They probably aren't friends on Facebook. Using cluster analysis, you could easily partition my groups of friends & acquaintances out.
Can you give an example of what kind of situation might confuse this system? What if it took further demographics into account as vertices with directed edges (whereas friendship, in the graph, is an undirected edge), such as age group, gender, location, employer?
I would assume that status updates only travel one hop on the graph, so that even if someone becomes a part of one of these clusters, if you don't have an explicit connection to them your status updates cannot be seen by them.
You could further weight the edges by how often you communicate with each other via the service.
What would probably happen - and pure conjecture here - is that you would be exposing your status updates to either the boundary of a cluster (you are on the outside of the cluster, with a few connections in), or to most of the cluster (you are in the center of the cluster, with many connections in it). Situation one is more likely with friends (unless they are very isolated friends indeed), while situation two is more likely with family and co workers. Likely, you (and perhaps your spouse) would be the only people in your family network that have direct connections to people in, say, a drinking-buddies network. Unless members of your family are also drinking buddies.
I think the first issue is solved by defaulting to a smaller circle, like Path or like I would expect Google Circles to have. Most of the people I know who use Facebook intend 80-95% of their updates to the same circle of friends, and would only do a full broadcast when asking for information or promoting themselves.
For the second problem of people receiving your more mundane messages as unwanted, tools should provide more advanced relevancy or even manual filters on the receiving end.
I think anything more complex than these solutions is overkill.
No idea if the whole circles concept will succeed though.
But once you've done that, then every time I post a status update (or tweet, or whatever you end up calling it I'll be forced to consider which circles(s) I want to share with. This significantly raises the cognitive burden of an update.
Unless you've got a really clever solution to this problem. In which case you've got something very interesting indeed and you should definitely keep going.