The Maximum Influence k-Plex Problem and its Branch-and-Bound Algorithm

The [Formula: see text]-plex is a relaxation of the classical clique structure, which is usually used to characterize the cohesiveness of a subgroup in social networks. In this paper, we propose a new notion called the [Formula: see text]-plex influence to depict the outward connection of a [Formula: see text]-plex. The influence of a [Formula: see text]-plex is defined as the number of outside vertices adjacent to the vertices of the [Formula: see text]-plex. With the new notion, we can distinguish different [Formula: see text]-plexes and find more pivotal subgroups in networks. We propose an exact algorithm to find the [Formula: see text]-plex with the maximum influence. The algorithm implements a branch-and-bound approach, in which we integrate a novel upper bound and an effective preprocessing strategy. We conducted experiments to evaluate the performance of the algorithm and compared it with the general mixed integer linear programming approach. The results show that both the preprocessing strategy and the upper bound can effectively reduce the search space, and the proposed branch-and-bound algorithm can solve the problem in massive graphs effectively and has a significant performance advantage over the general mixed integer linear programming approach.