Fast and Accurate Community Search Algorithm for Attributed Graphs
Fast and Accurate Community Search Algorithm for Attributed Graphs
复制标题
DOI：
10.1007/978-3-030-59003-1_16
复制
发表时间：
2020-09
期刊：
影响因子：
--
通讯作者：
Shohei Matsugu;Hiroaki Shiokawa;H. Kitagawa
中科院分区：
文献类型：
--
作者：
Shohei Matsugu;Hiroaki Shiokawa;H. Kitagawa
社区搜索算法是一种基本的图形数据管理工具，用于识别适合用户指定的查询节点的社区。虽然社区搜索算法在各种应用中都很有用，但由于(1)传统算法忽略节点属性和(2)算法需要严格的拓扑约束来寻找社区，因此它们很难处理属性图。本文定义了一类新的属性图社区搜索问题，称为柔性属性桁架社区(F-ATC)问题。为了克服上述限制，F-ATC问题放松了拓扑约束，并评估了节点属性。由于F-ATC问题是NP-Hard问题，我们提出了两种贪婪算法来有效地解决它。我们在真实世界图形上的大量实验表明，我们的方法比最先进的方法获得了更高的效率和准确性。
The community search algorithm is an essential graph data management tool to identify a community suited to a user-specified query node. Although the community search algorithms are useful in various applications, it is difficult for them to handle attributed graphs since (1) traditional algorithms ignore node attributes and (2) algorithms require strict topological constraints to find a community. In this paper, we define a novel class of the community search problem on attributed graphs called the flexible attributed truss community (F-ATC) problem. To overcome the aforementioned limitations, the F-ATC problem relaxes the topological constraints and evaluates node attributes. Since the F-ATC problem is NP-hard, we propose two greedy algorithms to solve it efficiently. Our extensive experiments on real-world graphs clarify that our approach achieves higher efficiency and accuracy than the state-of-the-art method.