Finding large -clubs in undirected graphs
Finding cohesive subgroups is an important issue in studying social networks. Many models exist for defining cohesive subgraphs in social networks, such as clique, -clique, and -clan. The concept of -club is one of them. A -club of a graph is a maximal subset of the vertex set which induces a subgraph of diameter . It is a relaxation of a clique, which induces a subgraph of diameter . We conducted algorithmic studies on finding a -club of size as large as possible. In this paper, we show that one can find a -club of maximum size in time where is the number of vertices of the input graph. We implemented a combinatorial branch-and-bound algorithm that finds a -club of maximum size and a new heuristic algorithm called IDROP given in this paper. To speed up the programs, we introduce a dynamic data structure called -DN which, under deletion of vertices from a graph, maintains for a given vertex the set of vertices at distances at most . From the experimental results that we obtained, we concluded that a -club of maximum size can be easily found in sparse graphs and dense graphs. Our heuristic algorithm finds, within reasonable time, -clubs of maximum size in most of experimental instances. The gap between the size of a -club of maximum size and a -club found by IDROP is a constant for the number of vertices that we are able to test.
branch and bound k-club k-neighborhood