Does my algorithm work? There's no shortcut for community detection

May 4, 2017 by Jenna Marshall
Metadata is not ground truth. In the space of all possible partitions of a real-world social network, the lower peak corresponds to the social group partition given by the metadata. The higher peak corresponds to a leader-follower partition within the network. Image courtesy Peel, Larremore, and Clauset. Credit: Santa Fe Institute

Community detection is an important tool for scientists studying networks. It provides descriptions of the large-scale network by dividing its nodes into related communities. To test community detection algorithms, researchers run the algorithm on known data from a real-world network and check to see if their results match up with existing node labels—metadata—from that network.

But a new paper published this week in Science Advances calls that approach into question. 

Real-world networks are large and complex. Food webs, social networks, or genetic relationships may consist of hundreds, or even millions, of nodes. To understand the overarching layout of a large , scientists design algorithms to divide the network's nodes into significant groups, which make the network easier to understand.  In other words, community detection allows a researcher to zoom out, seeing big patterns in the forest, instead of being caught up in the trees. In the past, researchers have used metadata as a sort of answer key or "ground truth" to verify that their community detection algorithms are performing well. 

"Unfortunately, tempting as this practice is, with real-world data, there is no answer key, no ground truth," explains Daniel Larremore, one of two lead authors of the paper and an Omidyar Fellow at the Santa Fe Institute. "Our research rigorously shows that using metadata as ground truth to validate algorithms is fundamentally problematic and introduces biases without telling us what we really need to know: does my work?"

When scientists use metadata to validate algorithms, they limit the types of communities they can validate. Larremore likens this to a teacher leading a class discussion, and only responding to students who raise points the teacher is already familiar with. 

"If we want creative algorithms that can handle all kinds of challenges, then restricting the answers to one set of "ground truth" metadata means we're pushing our algorithms through this bottleneck of low diversity, and low creativity," he says. "We'll only ever get algorithms that solve a small and restricted set of problems."

Having exposed the shortcomings of metadata as a test for community detection, Larremore and co-authors Leto Peel (Université Catholique de Louvain) and Aaron Clauset (SFI, CU Boulder) go on to quash any hope of creating a universal algorithm for detecting communities by their network structures. The paper mathematically proves the first No Free Lunch Theorem for community detection: any algorithm that's exceptionally good at finding communities in one type of network must be exceptionally bad at finding communities in another. 

David Wolpert, also of the Santa Fe Institute, first posited a No Free Lunch Theorem for machine learning algorithms in 1997. 

The authors hope that by mathematically proving the futility of universal detection algorithms, they can, according to Larremore "free people up to work on specialist algorithms."

The new paper curbs enthusiasm for finding any single, universally optimal approach to understanding complex network datasets. Still, the authors do see a constructive side to their findings. In the final section of their paper, they reverse the usual script. Instead of using metadata to validate an algorithm's performance, as in the past, they introduce two new statistical approaches that use metadata in conjunction with the network itself to probe the more fundamental questions of network science: what are the deeper patterns between the nodes, links, and alike, and how can we use these to learn about the system that the network represents?

Explore further: Network paradox may help algorithms overcome 'universal limitation'

More information: Leto Peel et al. The ground truth about metadata and community detection in networks, Science Advances (2017). DOI: 10.1126/sciadv.1602548

Related Stories

Network traffic anomaly detection

December 27, 2016

"Diagnosing unusual events (called "anomalies") in a large-scale network like Internet Service Providers and enterprise networks is critical and challenging for both network operators and end users," explain Hiroyuki Kasai ...

Harnessing the predictive power of virtual communities

January 30, 2012

Scientists have created a new algorithm to detect virtual communities, designed to match the needs of real-life social, biological or information networks detection better than with current attempts. The results of this study ...

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

Recommended for you

When words, structured data are placed on single canvas

October 22, 2017

If "ugh" is your favorite word to describe entering, amending and correcting data on the rows and columns on spreadsheets you are not alone. Coda, a new name in the document business, feels it's time for a change. This is ...

Enhancing solar power with diatoms

October 20, 2017

Diatoms, a kind of algae that reproduces prodigiously, have been called "the jewels of the sea" for their ability to manipulate light. Now, researchers hope to harness that property to boost solar technology.

5 comments

Adjust slider to filter visible comments by rank

Display comments: newest first

Steelwolf
5 / 5 (1) May 04, 2017
TANSTAAFL, a saying memorialized in Robert A Heinlein's book 'The Moon is a Harsh Mistress', succinctly means 'There Ain't No Such Thing As A Free Lunch'. I guess they have the algorithm to prove it now.
Hyperfuzzy
not rated yet May 09, 2017
Suppose you tag a single "data"; then track its "seen by, responded to, new acts related to, ... " (The object allows any set, just separate attributes by commas)
Oh just do it for everything, the sort on any parameter, based upon the axiomatic data, that is any set of attributes that sufficiently define the data, logically and illogically. Are there dependencies using necessary and sufficient logic or ... juz som'n som'n
Hyperfuzzy
not rated yet May 09, 2017
Let the data tell you, allow it to structure itself, tag! You're it. Simply play tag!
antialias_physorg
not rated yet May 09, 2017
^^ And this is why you don't do drugs, kids.
Hyperfuzzy
not rated yet May 09, 2017
^^ And this is why you don't do drugs, kids.

The tag is either your thread or ... yeah, stay sober.

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.