Synopsis: Neighborly networks

A different way of modeling networks allows an exact derivation of their properties.
Synopsis figure
Illustration: M. Newman, Phys. Rev. Lett. (2009)

Many networks, from the Internet to Facebook, are transitive: neighbors of the same node are probably neighbors of each other, or in social terms, your friends are likely to be friends with each other too. Apart from a few special cases, mathematically modeling such clustered networks is difficult and calculating their properties almost always requires numerical rather than analytical solutions. But as Mark Newman of the University of Michigan, US, reports in Physical Review Letters, it is in fact possible to generalize random graph models to include clustering in a way that allows exact derivations of network behavior.

Conventional modeling of networks uses random configurations of vertices (nodes) in which the number of edges (connecting links) is specified for each vertex. Newman alters this by specifying how many triangles (the most elementary cluster consisting of three nodes) each vertex participates in, and how many single edges or “stubs” (apart from triangles) the vertex connects to. The network is then built out of triangles and stubs such that no edges or triangle corners are left hanging.

Constructing the network this way allows Newman to express the graph properties in the form of generating functions. These in turn allow derivation of such things as the “giant component” (the collection of nodes that can easily intercommunicate), the “small components” (the isolated groupings that are cut off from the rest of the nodes), and average path lengths from one node to another. Getting a handle on these characteristics should assist the analysis of real networks involved in the spread of disease, communications, and social interaction. – David Voss


Features

More Features »

Announcements

More Announcements »

Subject Areas

Interdisciplinary Physics

Previous Synopsis

Atomic and Molecular Physics

Heteronuclear tango

Read More »

Next Synopsis

Atomic and Molecular Physics

Atoms in a lattice keep time

Read More »

Related Articles

Focus: Drops Falling in Clouds Make More Drops
Fluid Dynamics

Focus: Drops Falling in Clouds Make More Drops

Experiments with a simplified version of the atmosphere show that falling drops seed many smaller droplets in their wake. Read More »

Synopsis: Friction Means Life or Death for Ants
Soft Matter

Synopsis: Friction Means Life or Death for Ants

Experiments show that the mass of an object determines whether it slides down a sandy slope, which may explain why insect predators called antlions can trap ants in sand pits. Read More »

Viewpoint: Language Boundaries Driven by Surface Tension
Interdisciplinary Physics

Viewpoint: Language Boundaries Driven by Surface Tension

A new model of language evolution assumes that changes in the spatial boundaries between dialects are controlled by a surface tension effect. Read More »

More Articles