论文标题
临时网络上的重要参与社区搜索：概念和算法
Significant Engagement Community Search on Temporal Networks: Concepts and Algorithms
论文作者
论文摘要
在过去几十年中，社区搜索检索包含查询顶点的凝聚力子图已被广泛感动。现有的社区搜索研究主要集中在静态网络上。但是，现实世界网络通常是时间网络，每个边缘都与时间戳关联。处理时间网络时，先前的方法不起作用。我们研究了确定用户指定查询所属的重要参与社区的问题。具体来说，给定一个整数k和一个查询顶点u，然后我们搜索满足（i）u $ \ in $ h的子图h； （ii）h的临时图是连接的k核； （iii）在h中，u具有最大参与度。为了解决我们的问题，我们首先开发了一种名为TDGP的自上而下的贪婪剥离算法，该算法迭代地以最大的时间程度去除顶点。为了提高效率，我们设计了一种名为Buls的自下而上的本地搜索算法及其增强版本Buls+和Buls*。最后，我们从经验上显示了我们提出的解决方案在六个真实世界图表上的优越性。
Community search, retrieving the cohesive subgraph which contains the query vertex, has been widely touched over the past decades. The existing studies on community search mainly focus on static networks. However, real-world networks usually are temporal networks where each edge is associated with timestamps. The previous methods do not work when handling temporal networks. We study the problem of identifying the significant engagement community to which the user-specified query belongs. Specifically, given an integer k and a query vertex u, then we search for the subgraph H which satisfies (i) u $\in$ H; (ii) the de-temporal graph of H is a connected k-core; (iii) In H that u has the maximum engagement level. To address our problem, we first develop a top-down greedy peeling algorithm named TDGP, which iteratively removes the vertices with the maximum temporal degree. To boost the efficiency, we then design a bottom-up local search algorithm named BULS and its enhanced versions BULS+ and BULS*. Lastly, we empirically show the superiority of our proposed solutions on six real-world temporal graphs.
