Contextual Community Search Over Large Social Networks
Contextual Community Search Over Large Social Networks
复制标题
DOI：
10.1109/icde.2019.00017
复制
发表时间：
2019-04
期刊：
影响因子：
--
通讯作者：
Lu Chen;Chengfei Liu;Kewen Liao;Jianxin Li;Rui Zhou
中科院分区：
文献类型：
--
作者：
Lu Chen;Chengfei Liu;Kewen Liao;Jianxin Li;Rui Zhou
属性网络上的社区搜索最近吸引了大量的研究兴趣。然而，大多数现有的工作需要查询用户指定一些社区结构参数。这可能并不总是实用的，因为有时用户没有知识和经验来决定合适的参数。在本文中，我们提出了一种新的无参数上下文社区模型的属性社区搜索。所提出的模型仅需要查询上下文，即，一组描述所需匹配社区上下文的关键字，而返回的社区是结构和属性内聚的w.r.t.提供的查询上下文。我们从理论上表明，我们的精确和近似的上下文社区搜索算法可以在最坏情况下的多项式时间内执行。精确的算法是基于一个优雅的参数最大流技术和近似算法，显着提高了搜索效率进行了分析，有一个近似因子为1/3。在实验中，我们使用六个真实的网络与地面真相社区来评估我们的上下文社区模型的有效性。实验结果表明，该模型可以找到接近地面实况社区。我们还测试了我们的精确和近似算法使用8个大型真实的网络，以证明所提出的算法的高效率。
Community search on attributed networks has recently attracted great deal of research interest. However, most of existing works require query users to specify some community structure parameters. This may not be always practical as sometimes a user does not have the knowledge and experience to decide the suitable parameters. In this paper, we propose a novel parameter-free contextual community model for attributed community search. The proposed model only requires a query context, i.e., a set of keywords describing the desired matching community context, while the community returned is both structure and attribute cohesive w.r.t. the provided query context. We theoretically show that both our exact and approximate contextual community search algorithms can be executed in worst case polynomial time. The exact algorithm is based on an elegant parametric maximum flow technique and the approximation algorithm that significantly improves the search efficiency is analyzed to have an approximation factor of 1/3. In the experiment, we use six real networks with ground-truth communities to evaluate the effectiveness of our contextual community model. Experimental results demonstrate that the proposed model can find near ground-truth communities. We also test both our exact and approximate algorithms using eight large real networks to demonstrate the high efficiency of the proposed algorithms.