# New technique for dataset cluster detection

##### November 27, 2013

(Phys.org) —A persistent problem for mathematicians trying to understand the structures of networks – in datasets representing relationships among everything from galaxies to people – is community detection: finding groups of related data points, or nodes. A network that contains three groups of nodes is fundamentally different from a network that contains two groups.

"If you're looking at who eats whom in a food web, you need to understand how groups of predators depend on groups of prey. In an epidemic model, you need to know how fast a disease will spread in one community and how likely it is for it to cross to another community," says SFI Professor Cris Moore.

In a paper published this week in PNAS, Moore and collaborators at UC Berkeley and in Paris offer a twist on past approaches to cluster detection that seems to address weaknesses that traditional techniques have in dealing with sparse data—networks where most nodes have just a few links.

Traditionally, mathematicians find communities in one of two ways: statistical inference, a highly iterative method that reassesses network-wide probabilities at each step, and spectral analysis, a faster "random walk" technique that groups nodes by focusing on the flow of information or probability through a network.

To understand the latter approach, imagine taking a walk in a city. At each intersection you flip a coin to decide which way to turn. As time goes on, the likelihood that you are at another given point in the city can be expressed as a probability. If the city is divided by a river into two parts with just a few bridges between them, it will take a long time for your probability to flow from one side of the river to the other. This slow "flow of probability" helps reveal that the city is divided.

Both techniques – statistical inference and spectral analysis – work well for networks with many links between nodes. But in sparse networks where most nodes are related to only a few others – as in the case in many real-world networks – classic spectral techniques fall short.

Statistical inference, in fact, finds groupings as well as any algorithm can – all the way down to a theoretical limit revealed by Moore and collaborators in a 2011 paper. And it can handle networks with millions of nodes in minutes. But spectral techniques are even faster, partly because they rely on simpler linear equations to update their information rather than more complex and difficult-to-crunch nonlinear ones.

Further, statistical methods tend to slow down when a network features a large number of clusters. And statistical techniques can go off on wild tangents in situations where they get an early but erroneous picture of network structure; often, in fact, spectral techniques are used to provide a rough snapshot of a network that statistical methods can refine.

The challenge has been, then, to find a spectral method that is computationally efficient, but that also finds groupings in networks down to the theoretical limit.

In the paper, aptly titled "Spectral Redemption," the researchers try out a spectral method they call the "non-backtracking operator." Put simply, it specifies that during analysis, information flowing from node to node may not immediately return from whence it came.

Think of a pinball machine, with the ball as information and bumpers as nodes. Often the ball gets stuck dinging around inside a group of bumpers.Eventually it frees itself and rolls across the board, only to get trapped temporarily inside another localized group of bumpers.

"Traditional spectral methods get stuck on highly connected nodes, rattling back and forth between those and their neighbors," Moore says. "They get confused by localized structures in the network rather than finding the large-scale structures we care about."

In the pinball analogy, the non-backtracking rule would prohibit the ball from returning to a bumper it had just bounced from. In network clustering, this seemingly minor modification is enough to ensure that information doesn't get hung up in one area of the network for very long, and sooner paints a picture of the various clusters present in the system.

"Each hub gets the attention it deserves, but not more," he says.

The researchers tested their non-backtracking technique on several datasets commonly used to benchmark clustering methods, including several real-world networks. They found that their spectral method is reliable down to the .

"This work shows how crucial it is to build connections between scientific communities," says Elchanan Mossel, a key collaborator at UC Berkeley. "Bringing together concepts, methods and points of view from statistical physics [Santa Fe and Paris] and mathematics [Berkeley] gave us a whole that is much greater than the sum of the parts."

Explore further: Better models for studying the flow of information in networks

More information: "Phase transition in the detection of modules in sparse networks." Aurelien Decelle, Florent Krzakala, Cristopher Moore, Lenka Zdeborová. Phys. Rev. Lett. 107, 065701 (2011). DOI: 10.1103/PhysRevLett.107.065701

## Related Stories

#### Better models for studying the flow of information in networks

September 19, 2013

Physicist Atieh Mirshahvalad uses network models to better understand the connection between the flow of information and social structures. Among other things she has introduced a group formation model for social systems. ...

#### Network research needs to focus on temporality and weightedness

October 5, 2012

The study of complex networks in statistical physics and computational science has become more and more focused on so-called dynamic networks. Where traditional approaches have treated the links in networks as static, contemporary ...

#### Machine learning branches out

November 14, 2013

Much artificial-intelligence research is concerned with finding statistical correlations between variables: What combinations of visible features indicate the presence of a particular object in a digital image? What speech ...

#### Network theory expert sees Web pages as 19 clicks apart

February 20, 2013

(Phys.org)—The concept of its being a small world after all is now being placed in the scientific context of the wide, wide Web as a small Web after all. According to a physicist, Web pages are actually no greater than ...

#### Reliable communication, unreliable networks

August 5, 2013

Now that the Internet's basic protocols are more than 30 years old, network scientists are increasingly turning their attention to ad hoc networks—communications networks set up, on the fly, by wireless devices—where ...

#### Forget the needle, consider the haystack: Uncovering hidden structures in massive data collections

October 29, 2013

(Phys.org) —Advances in computer storage have created collections of data so huge that researchers often have trouble uncovering critical patterns in connections among individual items, making it difficult for them to realize ...

## Recommended for you

#### Energy from electric cars could power our lives—but only if we improve the system

November 22, 2017

Power stored in electric cars could be sent back to the grid - thereby supporting the grid and acting as a potential storage for clean energy - but it will only be economically viable if we upgrade the system first. In a ...

#### A 'half-hearted' solution to one-sided heart failure—Soft robotic system provides support

November 22, 2017

Soft robotic actuators, which are pneumatic artificial muscles designed and programmed to perform lifelike motions, have recently emerged as an attractive alternative to more rigid components that have conventionally been ...

#### Uber reveals cover-up of hack affecting 57M riders, drivers (Update)

November 22, 2017

Uber is coming clean about its cover-up of a year-old hacking attack that stole personal information about more than 57 million of the beleaguered ride-hailing service's customers and drivers.

#### US regulator unveils plan to end 'net neutrality' (Update)

November 21, 2017

The top US telecom regulator formally unveiled plans Tuesday to roll back "net neutrality" rules adopted in 2015 aimed at treating all online traffic equally.

#### New human mobility prediction model offers scalability, requires less data

November 21, 2017

A new method to predict human mobility—which can be used to chart the potential spread of disease or determine rush hour bottlenecks—has been developed by a team of researchers, including one from Arizona State University.

#### Volvo to supply Uber with self-driving cars (Update)

November 20, 2017

Swedish carmaker Volvo Cars said Monday it has signed an agreement to supply "tens of thousands" of self-driving cars to Uber, as the ride-sharing company battles a number of different controversies.