Fast Algorithm for Attributed Community Search
Fast Algorithm for Attributed Community Search
复制标题
DOI：
10.2197/ipsjjip.29.188
复制
发表时间：
2021
期刊：
影响因子：
--
通讯作者：
Shohei Matsugu;Hiroaki Shiokawa;H. Kitagawa
中科院分区：
文献类型：
--
作者：
Shohei Matsugu;Hiroaki Shiokawa;H. Kitagawa
：近年来，在属性图上搜索社区引起了人们的广泛关注。社区搜索算法目前是一种基本的图形数据管理工具，用于找到适合用户指定的艾德查询节点的社区。虽然社区搜索算法在各种基于Web的应用和服务中是有用的，但由于传统算法的严格拓扑约束，它们在处理属性图时存在问题。在本文中，我们提出了一个精确的社区搜索算法的属性图。为了放松拓扑约束，我们提出了一种新的社区模型。我们在一个名为灵活属性桁架社区（F-ATC）的属性图类中定义了找到它们的问题。F-ATC问题具有适用于许多情况的优点，因为它可以探索不同的社区。因此，与传统的社区搜索算法相比，社区搜索的准确性得到了提高。此外，我们提出了一种新的启发式算法来解决F-ATC问题。与传统算法相比，该算法能更准确地从属性图中发现社区.为了进一步优化，我们对查询响应进行了预处理，使其更快。最后，我们用真实世界的属性图进行了大量的实验，以证明我们的方法优于最先进的方法。
: Searching communities on attributed graphs has attracted much attention in recent years. The community search algorithm is currently an essential graph data management tool to find a community suited to a user-specified query node. Although community search algorithms are useful in various web-based applications and services, they have trouble handling attributed graphs due to the strict topological constraints of traditional algorithms. In this paper, we propose an accurate community search algorithm for attributed graphs. To relax the topological constraints, we proposed a new model of the community. And we defined the problem of finding them in an attributed graph class called the Flexible Attributed Truss Community (F-ATC). The F-ATC problem has the advantage of being applicable in many situations because it can explore diverse communities. Consequently, the community search accuracy is enhanced compared to traditional community search algorithms. Additionally, we present a novel heuristic algorithm to solve the F-ATC problem. This e ff ective algorithm detects more accurate communities from attributed graphs than the traditional algorithms. For further optimization, we pre-processed the query response to make it faster. Finally, we conducted extensive experiments with real-world attributed graphs to demonstrate that our approach outperforms state-of-the-art methods.