Analyzing the outgoing and incoming messages, Gmail creates a social graph for each user. "We call the hypergraph composed of all of the edges leading into or out of a single user node that user's egocentric network. (...) Edges in the implicit social graph have both direction and weight. The direction of an edge is determined by whether it was formed by an outgoing email sent by the user, or an incoming email received by the user. There may be both outgoing and incoming edges joining a user and an implicit group, if the user has both sent and received email from the group. We consider a user to have received mail from a group by joining the sender of the mail and the other co-recipients into an implicit group. (...) The weight of an edge is determined by the recency and frequency of email interactions between the user and the group."
The social graph exists, even if it's not very obvious and not many Gmail features use it. The Friend Suggest algorithm uses the implicit groups to suggest contacts when you send a message to multiple recipients ("Don't forget Bob!") and to find contacts that are added by mistake to a list of recipients ("Got the wrong Bob?"). The two features have recently graduated from Gmail Labs.
"Our algorithm is inspired by the observation that, although users are reluctant to expend the eff ort to create explicit contact groups, they nonetheless implicitly cluster their contacts into groups via their interactions with them."
According to Google, more than 10% of the Gmail messages are sent to more than one recipient and more than 4% of the messages are sent to 5 or more recipients. All of these messages allow Google to automatically cluster contacts into groups that change dynamically.
Google says that Friend Suggest could have many other uses, "such as identifying trusted recommenders for online recommendation systems, or improving content sharing between users in various online contents."
{ via Greg Linden }