We use cookies to improve your experience with our site.

邀请谁来参加:社交网络中规模受限的k核问题研究

Who Should Be Invited to My Party: A Size-Constrained k-Core Problem in Social Networks

  • 摘要: 通过结合社交网络中用户的亲密度和网络拓扑结构,本文提出一种规模受限的k-core群组查询(size constrained k-core group query,SCCGQ)。具体地,SCCGQ旨在查找一个规模大小为h的用户集合,使得该用户集合具有最高的用户亲密度,同时其诱导子图能构成k-core结构。SCCGQ问题可以广泛应用于事件规划、任务调度以及社会分析等其它领域。传统的k-core问题主要找出给定社交网络中的k-core结构,而SCCGQ问题不仅考虑k-core结构,同时还考虑用户群组的规模。传统的k-core问题具有多项式时间的解决算法,而SCCGQ问题具有指数级的复杂度。为了解决SCCGQ问题,本文提出一种辐散算法(blast scatter,BS)。BS以查询节点为中心进行向外扩展搜索。在每一次向外扩展中,BS采用贪心策略进行中心节点的更新,然后一次选取多个邻居节点进行扩展。为了进一步的加速查询处理,本文提出一种有界限制的搜索算法(Bounded Extension,BE)。BE采用一种有效的社会距离剪枝策略和紧密的亲密度上界来降低搜索空间。此外,为了加速查询处理,本文提出一种离线的社交感知索引。最后,本文在真实的社交网络数据集上进行大量的实验来表明本文所提出算法的性能。

     

    Abstract: In this paper, we investigate the problem of a size-constrained k-core group query (SCCGQ) in social networks, taking both user closeness and network topology into consideration. More specifically, SCCGQ intends to find a group of h users that has the highest social closeness while being a k-core. SCCGQ can be widely applied to event planning, task assignment, social analysis, and many other fields. In contrast to existing work on the k-core detection problem, which aims to find a k-core in a social network, SCCGQ not only focuses on k-core detection but also takes size constraints into consideration. Although the conventional k-core detection problem can be solved in linear time, SCCGQ has a higher complexity. To solve the problem of SCCGQ, we propose a Blast Scatter (BS) algorithm, which appoints the query node as the center to begin outward expansions via breadth search. In each outward expansion, BS finds a new center through a greedy strategy and then selects multiple neighbors of the center. To speed up the BS algorithm, we propose an advanced search algorithm, called Bounded Extension (BE). Specifically, BE combines an effective social distance pruning strategy and a tight upper bound of social closeness to prune the search space considerably. In addition, we propose an offline social-aware index to accelerate the query processing. Finally, our experimental results demonstrate the efficiency and effectiveness of our proposed algorithms on large real-world social networks.

     

/

返回文章
返回