Hello,

We noticed you're browsing in private or incognito mode.

To continue reading this article, please exit incognito mode or log in.

Not an Insider? Subscribe now for unlimited access to online articles.

Christopher Mims

A View from Christopher Mims

Software Identifies Social Cliques You Didn't Even Know You Had

A new algorithm for detecting social networks handles dolphins, karate students, and Chinese computer scientists with equal aplomb.

  • October 15, 2010

Led by a engineers at Microsoft research, a team of computer scientists has come up with what may be the most accurate method of identifying social cliques within social networks.

Communities within a pod of 64 dolphins

Their software (pdf) uses a totally novel approach built on game theory, in which every member of a social network is treated as a rational actor attempting to maximize their own utility in the face of the benefits and costs of maintaining membership in social cliques. (For those of you who are really into this stuff, they found the Nash equilibrium for the cost / benefit calculus of each individual.)

It’s well known that humans derive many benefits from belonging to a community, but maintaining those ties is costly in terms of time or other resources, for instance when a professional community has a membership fee.

This work could aid studies of urban development, criminal networks, marketing and many other areas of research enabled by the data readily available from online social networks such as Facebook and Twitter.

Intriguingly, two of the data sets the researchers tested their work on, which are apparently standard for this kind of research, were data gathered by anthropologists about a Karate academy, and data gathered by marine biologists about a pod of 64 dolphins. Applying their game-theoretic approach to both networks, they were able to resolve cliques that other approaches missed entirely.

Communities in Zachary’s karate club

In a world where the boundaries of cliques can be so fuzzy that even the individuals within them might not recognize they belong to a group, this work could some day help us to make explicit the social landscapes in which we are participating. Anyone who has had the experience of realizing that two friends whom you didn’t know were also friends with each other has experienced the real-world equivalent of the fruits of this clique-resolving algorithm.

With help from Zhenming Liu of Harvard and Xiaorui Sun of Shanghai Jiao Tong University, Wei Chen and Yajun Wang of Microsoft also successfully applied the algorithm to a common problem in academic citations: figuring out who is who among the many Chinese researchers whose names are spelled the same when romanized. For example, there are more than 20 people named Wei Chen in the DBLP computer science bibliography. (Not coincidentally, one of them is an author of this paper.)

Using a map of 20,000 nodes from the bibliography, where each node is a person, they discovered all the communities to which authors with that name belonged. Knowing how unlikely it is that any two Wei Chens would belong to the exact same set of cliques, they were able to disambiguate the various Wei Chens in the DBLP.

Follow Mims on Twitter or contact him via email.

Couldn't make it to Cambridge? We've brought EmTech MIT to you!

Watch session videos

Uh oh–you've read all of your free articles for this month.

Insider Premium
$179.95/yr US PRICE

Want more award-winning journalism? Subscribe and become an Insider.
  • Insider Plus {! insider.prices.plus !}* Best Value

    {! insider.display.menuOptionsLabel !}

    Everything included in Insider Basic, plus the digital magazine, extensive archive, ad-free web experience, and discounts to partner offerings and MIT Technology Review events.

    See details+

    What's Included

    Unlimited 24/7 access to MIT Technology Review’s website

    The Download: our daily newsletter of what's important in technology and innovation

    Bimonthly print magazine (6 issues per year)

    Bimonthly digital/PDF edition

    Access to the magazine PDF archive—thousands of articles going back to 1899 at your fingertips

    Special interest publications

    Discount to MIT Technology Review events

    Special discounts to select partner offerings

    Ad-free web experience

  • Insider Basic {! insider.prices.basic !}*

    {! insider.display.menuOptionsLabel !}

    Six issues of our award winning print magazine, unlimited online access plus The Download with the top tech stories delivered daily to your inbox.

    See details+

    What's Included

    Unlimited 24/7 access to MIT Technology Review’s website

    The Download: our daily newsletter of what's important in technology and innovation

    Bimonthly print magazine (6 issues per year)

  • Insider Online Only {! insider.prices.online !}*

    {! insider.display.menuOptionsLabel !}

    Unlimited online access including articles and video, plus The Download with the top tech stories delivered daily to your inbox.

    See details+

    What's Included

    Unlimited 24/7 access to MIT Technology Review’s website

    The Download: our daily newsletter of what's important in technology and innovation

/
You've read all of your free articles this month. This is your last free article this month. You've read of free articles this month. or  for unlimited online access.