Search

Finding cohesive subgroups is an important issue in studying social networks. Many models exist for defining cohesive subgraphs in social networks, such as clique, $$k$$-clique, and $$k$$-clan. The concept of $$k$$- club is one of them. A $$k$$-club of a graph is a maximal subset of the vertex set which induces a subgraph of diameter $$k$$. It is a relaxation of a clique, which induces a subgraph of diameter $$1$$. We conducted algorithmic studies on finding a $$k$$-club of size as large as possible. In this paper, we show that one can find a $$k$$-club of maximum size in $$O^{*}(1.62^n)$$ time where $$n$$ is the number of vertices of the input graph. We implemented a combinatorial branch-and-bound algorithm that finds a $$k$$-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 $$k$$-DN which, under deletion of vertices from a graph, maintains for a given vertex $$v$$ the set of vertices at distances at most $$k$$. From the experimental results that we obtained, we concluded that a $$k$$-club of maximum size can be easily found in sparse graphs and dense graphs. Our heuristic algorithm finds, within reasonable time, $$k$$-clubs of maximum size in most of experimental instances. The gap between the size of a $$k$$-club of maximum size and a $$k$$-club found by IDROP is a constant for the number of vertices that we are able to test. [ABSTRACT FROM AUTHOR]