A friend of a friend is... a dense network

December 1, 2016, Santa Fe Institute
A new theoretical model shows that networks evolve very differently depending on how often friend-of-a-friend connections occur. Credit: Pixabay

It's a familiar request in the digital age: one of your friends on social media has a friend who wants to be your friend. Frequent linking among friends of friends can cause a rapid increase in social network connectivity.

A new theoretical model shows that networks evolve very differently depending on how often these "second neighbor" connections occur. The work could offer a better understanding of how dense networks form.

Networks—like those based on social media or internet connections—are often characterized by their degree, which is the number of links per member, or node. Previous models of networks have tended to focus on sparse networks in which the degree remains finite as a network grows.

By including friend-of-friend interactions in their model, Renaud Lambiotte (University of Namur, Belgium), Paul Krapivsky (Boston University), and Uttam Bhat and Sid Redner (both Santa Fe Institute) could control the link density of the network.

"It's an incredibly simple model that can produce both sparse and dense networks," says Redner, a Santa Fe Institute professor.

In their recent paper published in Physical Review Letters, the researchers constructed a general network evolution in which every new node links to one target node already in the network, as well as to each of the neighbors of the target (that is, friends of friends), with copying probability p. The likelihood of each of these "copying" steps turns out to be the crucial factor in how the network evolves.

If copying is unlikely, the network evolves into a sparse, skeleton-like framework. But when the copying probability is greater than 1/2, the network becomes dense, with the number of links growing faster than the network itself. This "densifying" behavior has been observed in real world data, such as research paper citation lists, internet router maps, and other networks.

The researchers also investigated multiple-node connections, such as triangles that consist of three mutually-linked nodes. They found that the triangle count grew faster than the for a copying probability greater than 2/3. In fact, they discovered an unlimited number of these growth transitions related to copying.

"It's kind of exotic, but cool, that such a generic model has all these transitions in it," Redner says.

If similar transitions are identified as real networks evolve—like those in —the model's copying mechanism could be an allegory for many real friend-of-friend interactions. The model may also offer a way to study the role of triangles and other so-called "cliques" as information or diseases spread in a population.

Explore further: Researchers develop algorithm to maximize friendship acceptance by strangers on social networks

More information: R. Lambiotte et al, Structural Transitions in Densifying Networks, Physical Review Letters (2016). DOI: 10.1103/PhysRevLett.117.218301

Related Stories

New paper focuses on degree centrality in networks

February 26, 2015

Social networks such as Facebook, LinkedIn and Twitter play an increasingly central role in our lives. Centrality is also an important concept in the theory of social networks. Centrality of an individual, called a "node" ...

Uncovering complex network structures in nature

December 10, 2014

The global spread of Ebola is due to the complex interactions between individuals, societies, and transportation and trade networks. Understanding and building appropriate statistical and mathematical models of these interactions ...

Recommended for you

Researchers propose solutions for urine sample splash dilemma

November 19, 2018

Urinating into a cup may be a medical necessity for monitoring the health of the kidney and other issues, but it's often uncomfortable, embarrassing and messy—especially for women. But what if there were a way to comfortably ...

Swarmlike collective behavior in bicycling

November 19, 2018

Whether it's the acrobatics of a flock of starlings or the synchronized swimming of a school of fish, nature is full of examples of large-scale collective behavior. Humans also exhibit this behavior, most notably in pelotons, ...

Scientists explain how wombats drop cubed poop

November 18, 2018

Wombats, the chubby and beloved, short-legged marsupials native to Australia, are central to a biological mystery in the animal kingdom: How do they produce cube-shaped poop? Patricia Yang, a postdoctoral fellow in mechanical ...

Explaining a fastball's unexpected twist

November 18, 2018

An unexpected twist from a four-seam or a two-seam fastball can make the difference in a baseball team winning or losing the World Series. However, "some explanations regarding the different pitches are flat-out wrong," said ...

Helping Marvel superheroes to breathe

November 18, 2018

Marvel comics superheroes Ant-Man and the Wasp—nom de guerre stars of the eponymous 2018 film—possess the ability to temporarily shrink down to the size of insects, while retaining the mass and strength of their normal ...


Please sign in to add a comment. Registration is free, and takes less than a minute. Read more

Click here to reset your password.
Sign in to get notified via email when new comments are made.