Heuristic Algorithms for finding 2-clubs in an undirected graph

Abstract

In a graph G, a k-club is a node set inducing a subgraph of diameter at most k. The structure is useful to define a community or friend group on a social network. However, similar to the maximum clique problem, finding the largest k-club for any fixed k 1 is NP-hard. In this paper, we propose a new heuristic algorithm to determine a largest 2-club. To compare the performance, we also implement the other three methods. The experimental results show that our method indeed improves the previous algorithms.