Computing Applications News

Analyzing Online Social Networks

Social network analysis explains why some sites succeed and others fail, how physical and online social networks differ and are alike, and attempts to predict how they will evolve.
  1. Introduction
  2. Social Networking Goes Online
  3. "I (almost) look like Brad Pitt"
  4. Author
  5. Footnotes
  6. Figures

The online social network seems like a new kid on the online block. Actually, the online social network stretches back years before the dot-com bust. The first major social network site,, launched in 1997. The rapid growth has come more recently—MySpace in 2003, Facebook in 2004, and Twitter in 2006—propelled by the ubiquity of broadband and cellular-messaging connections plus the golden touch of yet another Harvard dropout (Mark Zuckerberg of Facebook). Their expansion set off a secondary growth market in analyzing social network sites. Social network analysis (or social networking analysis, take your pick) helps us understand why Facebook and Flickr succeeded while Friendster didn’t; shows how physical and online social networks can be alike and different; and attempts to predict how they’ll evolve and, for beneficiaries of the research, how someone might get rich off the next wave. There’s also a good deal of research about how honest people are in describing themselves online.

The sites differ in who can join, who can see your profile and how much of it is visible, and their openness to Web crawlers and other applications. The sites also differ in their suitability for use on a cell phone and whether they can be universally accessed among the multitude of telecom companies. For instance, Twitter, the what-are-you-doing-now site, wouldn’t be a big hit if there wasn’t a mobile Web.

Online social networks also differ in size. Facebook’s magnitude, with 132 million unique visitors in June 2008, seems to fly in the face of the conventional wisdom that too much size makes a social networking site both impersonal and undesirable. (As Yogi Berrà quipped, “Nobody goes there anymore; it’s too crowded.”) More than a few sites evolve in unpredictable ways, sometimes because their infrastructure couldn’t handle geometric growth or because their rules annoyed existing members. Some died and others took on second lives. In 2002, Friendster was a dating service, competing against in the U.S., but it crashed and burned. Now, Friendster has re-emerged as a social network site, but its strongest markets are in Indonesia, Malaysia, the Philippines, and Singapore. Orkut started in the U.S. as a social network site, but flared out; today, 80% of its users reside in Brazil or India.

Back to Top

Social Networking Goes Online

Social network analysis, of course, predates online social networks. Some trace the roots of social network analysis to the early 20th century when sociologist Georg Simmel differentiated between social groups (a group with a specific focus such as a family, neighborhood, or job) and a social network (a looser, larger collection of people and groups with connections among groups). Later, psychologist Abraham Maslow’s hierarchy of needs (physiological, safety, love/belonging, esteem, and self-actualization) was used to understand social networks. Research accelerated in the two decades after World War II as the availability of computers allowed the study of social networks with thousands of nodes. It remained for the Internet to provide networks with millions of nodes. As the size of networks grew, it became more difficult to display a network as a plot of dots connected by relationship lines, and the visual description became points or formulas.

Psychologist Stanley Milgram’s small world, or six degrees of separation, experiments in the 1960s helped explain some aspects of social networks, including the finding that most pairs of nodes passed through 5.5 nodes to reach the targeted individual. (Don’t look for the phrase “six degrees of separation” in Milgram’s papers; it was coined by playwright John Guare in his 1992 book of the same name.) While six degrees of separation may be true offline, less than three degrees is more likely online.

The Erdos-Rényi models for generating random graphs, which place connections between pairs of nodes with equal probability, help explain some social networks, but later research indicates that random graph models may not scale to larger online networks.

While six degrees of separation may be true offline, less than three degrees is more likely online.

Work in recent years finds intriguing similarities among social network sites as well as with traditional social networks. In the Barabási-Albert model, networks have power-law, scale-free, growth and exhibit preferential attachment. A physics professor at Notre Dame University, Albert-László Barabási has applied the preferential attachment model to online social networks and found that future gains more often accrue to nodes with more connections. In other worlds, a rising tide lifts all yachts, oft-cited academic papers are cited even more often, and a newbie to an online community connects more often to a well-known member.

Ravi Kumar, Jasminie Novak, and Andrew Tomkins at Yahoo! Research studied growth patterns at the Flickr photo-sharing site and the Yahoo! 360 social networking site. In both, they found the network density, or the interconnections per person, followed similar patterns: rapid growth through early adopters, decline in the wake of fewer friendships developing relative to network growth, and slow and steady growth where both members and connections grow. The trio segmented the network in three ways: “singletons” who don’t take part; a large core of connected users; and a middle region of isolated communities that keep to themselves and display a star structure. The stars make up a third of Flickr users and 10% of Yahoo! 360 users; these communities may have a single charismatic activist linked to other users who have few connections outside the star.

Jure Leskovec of Carnegie Mellon, Lars Backstrom of Cornell, and Ravi Kumar and Andrew Tomkins of Yahoo! Research studied large datasets from Flickr, Delicious (social bookmarking), Answers (reference), and Linked In (business contacts) to develop a model of network evolution following the preferential attachment model. For all, the number of connections among members drops off exponentially with more degrees of separation, particularly beyond two hops. Two people with a common friend (two hops away) close a triangle and become friends themselves. There were notable differences in new members: Flickr grows exponentially, Linked In grows quadratically, Delicious grows superlinearly, and Answers grows sublinearly.

Anthropologist Robin Dunbar has argued a person can sustain about 150 social relationships and that often was the comfortable size of settlements, farming villages, and the tactical unit of the Roman legion, the maniple. Online social networks with millions of users also work to keep human scale in mind.

At Facebook, users strive to mask the immense number of nodes with privacy settings, filters such as People You May Know, and the News Feed that shows on your page what your friends are doing and posting (so you don’t have to search dozens or hundreds of individual pages). The News Feed initially set off howls of protest about privacy concerns, but it turned out to be a key element in making Facebook more manageable and fueling its explosive growth. Just as size and density makes cities vibrant and attractive up to a point, Facebook research scientist Jeff Hammerbacher says, “We’ve noticed that people are more likely to become active users if they enter a dense, active network.”

The Facebook network now comprises more than 10,000 servers on a Web tier, about 2,000 servers on a MySQL tier, and about 1,000 servers on a MemCache tier. Every second, the site gets 10 million requests, about 500,000 of which are MySQL queries. Data volume was in the tens of gigabytes per day in early 2006, hit 1TB per day by mid-2007, and continues to grow.

Back to Top

“I (almost) look like Brad Pitt”

What man doesn’t suck in his gut when a good-looking woman walks by? Online, a user posts his or her best picture, usually in a setting that evokes how the user wants to be perceived, such as placing the Newport Yacht Club or a funky bar in the background. Some users resort to deception. Catalina Toma and Jeffrey Hancock of Cornell University and Nicole Ellison of Michigan State found that when it comes to online profiles on, Yahoo! Personals, Webdate, and American Singles, 81% of a survey group provided information that deviated from reality. “Deviations tended to be ubiquitous but small in magnitude. Men lied more about their height, and women lied more about their weight, with participants farther from the mean lying more,” they noted. “Overall, participants reported being the least accurate about their photographs and the most accurate about their relationship information.” The fact that you can update your profile if the misstatement becomes too pronounced may promote deception, although “a record of the presentation is preserved.” Because of the asynchronicity of social networking sites, “[Users] can plan, create, and edit their self-presentation, including deceptive elements, much more deliberately than they would in face-to-face first encounters,” they noted. “The reduction of communication cues, especially nonverbal and visual cues (with the exception of photographs), spares online daters some of the common predicaments faced by traditional daters trying to make a good first impression.”

According to Hancock, similar misstatements appear in email communications, too, and they may show similarities in phrasing. “We’re looking to see if there are any verbal features that might identify these lies,” he says. Which raises the question: Could a future social networking applet be a profile lie detector?

Toma, Hancock, and Ellison found that the online photograph is the information most likely to be less than accurate. The more accurate the photo, the more honest the person is in his or her other profile information. And the more friends who are aware of the online dater’s profile, the more accurate the photo. But beware of escalation once the first lie gets told. Hancock says, “There will be elevated lying if people suspect others are, too. Lying will still be constrained even in a ‘high-lie environment’—most people do not feel comfortable stating big lies.”

Social networks can even make you a fitter, healthier person. Sometimes. Nicole Ellison of Michigan State, Rebecca Heino of Georgetown University, and Jennifer Gibbs of Rutgers University found some respondents to social network and dating sites underreported their weight, then realized they’d better start losing weight to match their ideal self. One woman lost 44 pounds and said, “I can thank online dating for that.” Take that, Jenny Craig.

Back to Top

Back to Top

Back to Top


UF1 Figure. A detail from a painting of a Flickr network, consisting only of people with at least 50 mutual contacts, which reveals four distinct clusters.

Back to top

Join the Discussion (0)

Become a Member or Sign In to Post a Comment

The Latest from CACM

Shape the Future of Computing

ACM encourages its members to take a direct hand in shaping the future of the association. There are more ways than ever to get involved.

Get Involved

Communications of the ACM (CACM) is now a fully Open Access publication.

By opening CACM to the world, we hope to increase engagement among the broader computer science community and encourage non-members to discover the rich resources ACM has to offer.

Learn More