k-core: Theories and applications

Publication date: Available online 7 November 2019Source: Physics ReportsAuthor(s): Yi-Xiu Kong, Gui-Yuan Shi, Rui-Jie Wu, Yi-Cheng ZhangAbstractWith 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...
Source: Physics Reports - Category: Physics Source Type: research