k-core: Theories and applications

Abstract

Abstract With the rapid development of science and technology, the world is becoming increasingly connected. The following dire need for understanding both the relationships amongst individuals and the global structural characteristics brings forward the study of network sciences and many interdisciplinary subjects in recent years. As a result, it is crucial to have methods and algorithms that help us to unveil the structural properties of a network. Over the past few decades, many essential algorithms have been developed by scientists from many different fields. This review will focus on one of the most widely used methods called the k -core decomposition. The k -core decomposition is to find the largest subgraph of a network, in which each node has at least k neighbors in the subgraph. The most commonly used algorithm to perform k -core decomposition is a pruning process that to recursively remove the nodes that have degrees less than k . The algorithm was firstly proposed by Seidman in 1983 and soon became one of the most popular algorithms to detect the network structure due to its simplicity and broad applicability. This algorithm is widely adopted to find the densest part of a network across a broad range of scientific subjects including biology, network science, computer science, ecology, economics, social sciences, etc., so to achieve the vital knowledge under different contexts. Besides, a few physicists find that an exciting phase transition emerges with various critical behaviors during the pruning process. This review aims at filling the gap by making a comprehensive review of the theoretical advances on k -core decomposition problem, along with a review of a few applications of the k -core decomposition from many interdisciplinary perspectives.