SGEQ: A New Social Group Enlarging Query with Size Constraints

In recent years, the problem of $k$ -core has attracted wide-spread research attention due to the popularity of the graph-related applications, such as social network analysis, community detection, and collaboration networks. To efficiently support group-based activity planning, the organizers need to guarantee the size and closeness of the group. Current applications of the $k$ -core only support searching for the maximum $k$ -core group or adding the minimum number of edges to obtain the $k$ -core. However, no research has focused on the problem of enlarging the $k$ -core. In reality, when new tasks arrive, a work team needs to not only recruit new team members based on the requirements but also guarantee sufficient closeness among the members for good cooperation. In this paper, we first formalize a new query, a social group enlarging query with size constraints (SGEQ), which aims to find $n$ users to enlarge a subgraph from a $k$ -core of size $m$ to a ( $k+\Delta $ )-core of size ( $m+n$ ) by inserting the minimum number of edges. We prove that the SGEQ problem is NP-hard. To solve this problem, we first propose a novel algorithm, namely, the maximum connection edges algorithm (MCEA), which searches for the inserted vertex that has the most edges with an induced subgraph every time. Then, we develop an optimizing algorithm, namely, the maximum contribution degree algorithm (MCDA), which on average adds a number of edges in the expanded query less than that obtained by the MCEA. Finally, we conduct extensive experiments on two real-world datasets, and the results demonstrate the efficiency of the proposed algorithms.