Querying Tenuous Group in Attributed Networks

Finding groups in networks is very common in many practical applications, and most work mainly focus on dense groups. However, in scenarios like reviewer selection or weak social friends recommendation, we need to emphasize the privacy of individuals or minimize the possibility of information dissemination. So the internal relationship between individuals should be as tenuous as possible, but existing works cannot suit well to the requirement. Some works have focused on finding tenuous groups. However, these works only aim to find the most tenuous group and do not consider containing certain vertices. In this paper, we study the problem of finding tenuous groups in attributed networks that contain specific vertices. We first propose a new problem called Tenuous Attributed Group Query, and a new indicator, k-tenuity, to measure the structural tenuity of a group. Then we propose a method TAG-Basic to find proper groups by gradually selecting the vertices with optimal influence. We further design an advanced method TAG-ADV to improve the efficiency by forming a candidate set before selecting the optimal vertex. Experiment results show that k-tenuity is more effective than other state-of-the-art measurements, and our methods obtain the best result on group quality compared with other benchmark methods.