# 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: Network research needs to focus on temporality and weightedness

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

#### 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 ...

#### 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 ...

#### 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. ...

#### 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 ...

#### 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 ...

## Recommended for you

#### Computer model demonstrates how human spleen filters blood

June 27, 2016

Researchers, led by Carnegie Mellon University President Subra Suresh and MIT Principal Research Scientist Ming Dao, have created a new computer model that shows how tiny slits in the spleen prevent old, diseased or misshapen ...

#### Mapping coal's decline and the renewables' rise

June 23, 2016

Even as coal-fired power plants across the U.S. are shutting down in response to new environmental regulations and policy mandates, defenders of the emissions-heavy fuel still have cost on their side. Coal, after all, is ...

#### Driverless cars: Who gets protected? Study shows public deploys inconsistent ethics on safety issue

June 23, 2016

Driverless cars pose a quandary when it comes to safety. These autonomous vehicles are programmed with a set of safety rules, and it is not hard to construct a scenario in which those rules come into conflict with each other. ...

#### Electric racing car breaks world record

June 23, 2016

The Formula Student team at the Academic Motorsports Club Zurich (AMZ) accomplished its mission today: the grimsel electric racing car accelerated from 0 to 100 km/h in just 1.513 seconds and set a new world record. It reached ...

#### Flower power—photovoltaic cells replicate rose petals

June 24, 2016

With a surface resembling that of plants, solar cells improve light-harvesting and thus generate more power. Scientists of KIT (Karlsruhe Institute of Technology) reproduced the epidermal cells of rose petals that have particularly ...

#### Borophene could be an extraordinary sodium anode material for sodium-based batteries

June 24, 2016

Sodium-based batteries are a prospective alternative to lithium-based batteries due to the abundance and low price of sodium. However, finding a suitable anode material has been a longstanding hurdle to the commercialization ...