Abstract: The maximum $k$-club problem (M$k$CP) is an important clique relaxation problem with wide applications. Previous M$k$CP algorithms only work on small-scale instances and are not applicable for large-scale instances. For solving instances with different scales, this paper develops an efficient local search algorithm named Nu$k$CP for the M$k$CP which mainly includes two novel ideas. First, we propose a dynamic reduction strategy, which makes a good balance between the time efficiency and the precision effectiveness of the upper bound calculation. Second, a stratified threshold configuration checking strategy is designed by giving different priorities for the neighborhood in the different levels. Experiments on a broad range of different scale instances show that Nu$k$CP significantly outperforms the state-of-the-art M$k$CP algorithms on most instances.