In This Issue

Researchers who study networks, whether social, biological, or technological, analyze datasets for clustering to detect communities of related nodes or boundaries between dissimilar groups. One common, computationally efficient approach uses a class of techniques known as spectral algorithms, but applying the standard versions of these algorithms to sparse networks often yields suboptimal results. To address this problem, Florent Krzakala et al. (pp. 20935–20940) present a technique that uses a so-called “nonbacktracking” matrix to encode sparse data prior to analysis and thus redeems the efficacy of spectral algorithms for many popular models of network behavior. Supported by theoretical arguments and analogies from probability theory, statistical physics, and the theory of random matrices, the authors demonstrate the advantages of the nonbacktracking matrix by applying it to a number of real-world networks, including several established benchmarks for community detection. Furthermore, the technique was found to be applicable to a recently discovered phase transition for community detectability in cluster models. In addition to network theory, the nonbacktracking matrix can be generalized and applied to other types of sparse data, according to the authors. — T.J.