Provided

The friends of a Facebook user's friends and the links between them. Two heavily linked clusters are obvious at 12 and 3 o'clock - perhaps the user's workplace and college pals. But notice the somewhat isolated person down around 7 o'clock, who shares links to many smaller clusters of the central user's friends. Computer analysis points to this person as the romantic partner.

Even if you’re not shouting it from the housetops, there’s a good chance the structure of your Facebook neighborhood will identify your romantic partner.

From a map of Facebook friends, a computer algorithm developed by Jon Kleinberg, the Tisch University Professor of Computer Science, and Lars Backstrom '04, Ph.D. ’09, now at Facebook, will correctly identify a person’s spouse, fiancé or other romantic partner about 70 percent of the time.

“We are trying to build up a sort of chemistry kit for finding different elements of a network,” Kleinberg said. The team will present their results at the ACM Conference on Computer Supported Cooperative Work and Social Computing, Feb. 15-19 in Baltimore.

As you might guess, the method works best when the couple is married, and works better the longer the relationship has been in force. On the dark side, if the algorithm does not select the person who is the relationship partner, there is a significantly increased chance that in a month or two the couple will break up.

The researchers tested their methods on anonymized data from 1.3 million randomly selected Facebook users aged 20 or older who listed their status as “married,” “engaged” or “in a relationship.” Along with a list of a Facebook user’s friends, the data also show how those friends are linked to one another.

The first guess was that the romantic partner would be “embedded” – that the couple would have many mutual friends. That works, the researchers found, but not very well, finding the partner about 25 percent of the time. So they introduced a concept they call “dispersion,” where the couple’s mutual friends are not highly connected among themselves, but rather are scattered over many aspects of the central user’s life. In real-world terms, your spouse goes where you go, and knows the people in your office, your church, your bridge club and so on, although those people seldom meet one another across group lines.

“You have to ask, ‘How did the relationship get that way?’” Kleinberg said. “Your spouse acts as a sort of time traveler in your life, who went back and met all those people.”

Combining embededness with dispersion boosted performance. The researchers then factored in the dispersiveness of the dispersed friends – whether the person your romantic partner knows at your office is also connected to some people in your church and your bridge club.

Finally, they added measures of interaction, such as how often people look at each other’s profiles, attend the same events or appear together in photos. Ultimately they were able to identify the partner 70.5 percent of the time. Others who might be chosen by the algorithm are most often family members or their partners.

As a spinoff, the researchers were able to determine, 68.3 percent of the time, whether a given user was or was not in a relationship at all, and with 79 percent accuracy if the relationship was a marriage.

There may be other applications for analysis based on dispersion, the researchers said, including grouping people into categories or, for social scientists, finding the person who just doesn’t fit a category. Backstrom, who developed Facebook’s friend recommender, is looking at ways to evaluate incoming messages to a Facebook user based on the user’s relationship with the source.

And identifying people with strong ties to one another may also show where to go to influence a group. “If you’re someone who bridges between groups it can be a source of power,” Kleinberg explained.

Kleinberg’s work is supported by the National Science Foundation and the Simons Foundation.