有向图上基于层次树索引的最大cycle truss社区搜索

doi:10.11772/j.issn.1001-9081.2023010071

《计算机应用》唯一官方网站 ›› 2024, Vol. 44 ›› Issue (1): 190-198.DOI: 10.11772/j.issn.1001-9081.2023010071

所属专题：数据科学与技术

有向图上基于层次树索引的最大cycle truss社区搜索

宗传玉, 张纯鹤(), 夏秀峰

沈阳航空航天大学计算机学院，沈阳 110136

收稿日期:2023-01-31 修回日期:2023-04-05 接受日期:2023-04-13 发布日期:2023-06-06 出版日期:2024-01-10
通讯作者: 张纯鹤
作者简介:宗传玉（1985—），男，山东潍坊人，副教授，博士，CCF会员，主要研究方向：数据清洗、数据溯源、查询处理与优化；
夏秀峰（1964—），男，山东胶南人，教授，博士，CCF会员，主要研究方向：数据库、数据仓库。
第一联系人：张纯鹤（1997—），男，黑龙江哈尔滨人，硕士研究生，主要研究方向：查询处理与优化；
基金资助:
国家自然科学基金资助项目(61802268);辽宁省自然科学基金资助项目(2022-MS-303)

Maximum cycle truss community search based on hierarchical tree index on directed graphs

Chuanyu ZONG, Chunhe ZHANG(), Xiufeng XIA

School of Computer Science，Shenyang Aerospace University，Shenyang Liaoning 110136，China

Received:2023-01-31 Revised:2023-04-05 Accepted:2023-04-13 Online:2023-06-06 Published:2024-01-10
Contact: Chunhe ZHANG
About author:ZONG Chuanyu， born in 1985， Ph. D.， associate professor. His research interests include data cleaning， data provenance， query processing and optimization.
XIA Xiufeng， born in 1964， Ph. D.， professor. His research interests include database， data warehouse.
Supported by:
National Natural Science Foundation of China(61802268);Natural Science Foundation of Liaoning Province(2022-MS-303)

摘要/Abstract

摘要：

社区搜索旨在从信息网络中找出包含用户查询顶点的高内聚连通子图，cycletruss是一种基于cycle三角形的社区搜索模型，而现有的基于索引的cycle truss社区搜索方法存在索引空间大、搜索效率低、社区内聚性低的缺点。为了解决这一问题，提出一种基于层次树索引的最大cycle truss社区搜索方法。首先，提出了k-cycle truss分解算法，并引入了两个重要的概念：cycle三角连通与k-层次等价。基于k-层次等价设计了层次树索引TreeCIndex与表结构索引SuperTable，在此基础上，并基于这两个新的索引，提出了两个高效的cycle truss社区搜索算法。在4个真实数据集上与已有的基于TrussIndex与EquiTruss的社区搜索算法进行了比较，实验结果表明，TreeCIndex与SuperTable比TrussIndex与EquiTruss节省至少41.5%的空间，索引构建的时间节省8.2%至98.3%，且搜索最大cycle truss社区的效率分别高出了一个和两个数量级。

关键词: 有向图, 社区搜索, cycletruss, cycle三角形, 层次等价, 层次树索引

Abstract:

Community search aims to find highly cohesive connected subgraphs containing user query vertices in information networks. Cycle truss is a community search model based on cycle triangle. However， the existing index-based cycle truss community search methods suffer from the drawbacks of large index space， low search efficiency， and low community cohesion. A maximum cycle truss community search method based on hierarchical tree index was proposed to address this issue. Firstly， a k-cycle truss decomposition algorithm was proposed， and two important concepts， cycle triangle connectivity and k-level equivalence were introduced. Based on k-level equivalence， the hierarchical tree index TreeCIndex and the table index SuperTable were designed. On this basis， two efficient cycle truss community search algorithms were proposed. The proposed algorithms were compared with existing community search algorithms based on TrussIndex and EquiTruss on four real datasets. The experimental results show that the space consumptions of TreeCIndex and SuperTable are at least 41.5% lower and the index construction time is 8.2% to 98.3% lower compared to TrussIndex and EquiTruss； furthermore， the efficiencies of searching for maximum cycle truss communities is increased by one and two orders of magnitude.

Key words: directed graph, community search, cycle truss, cycle triangle, hierarchical equivalence, hierarchical tree index

中图分类号:

TP391.1

宗传玉, 张纯鹤, 夏秀峰. 有向图上基于层次树索引的最大cycle truss社区搜索[J]. 计算机应用, 2024, 44(1): 190-198.

Chuanyu ZONG, Chunhe ZHANG, Xiufeng XIA. Maximum cycle truss community search based on hierarchical tree index on directed graphs[J]. Journal of Computer Applications, 2024, 44(1): 190-198.

图/表 14

图1 三角形结构实例

Fig. 1 Examples of triangle structures

表1 本文出现的符号

Tab. 1 Symbols appearing in this paper

符号	描述
$G V G, E G$	一个有向图G
$H V H, E H$	一个子图H
$q$	一个查询顶点
$u, v, w$	$V G$ 中的顶点
$△ u v w c$	一个由顶点u、v、w组成的cycle三角形
$e = 〈 u, v 〉$	一条由顶点u指向顶点v的有向边
$C s u p e$	边e的cycle支持度
$τ e$	边e的cycle trussness值
$△ s c ↔ △ t c$	三角形 $△ s c$ 与 $△ t c$ 是cycle三角连通的
$e i$ $⇔ k$ $e j$	边 $e i 与 e j 是$ k-层次等价的
$N$	树节点，即一组k-层次等价集合

表1 本文出现的符号

Tab. 1 Symbols appearing in this paper

符号	描述
$G V G, E G$	一个有向图G
$H V H, E H$	一个子图H
$q$	一个查询顶点
$u, v, w$	$V G$ 中的顶点
$△ u v w c$	一个由顶点u、v、w组成的cycle三角形
$e = 〈 u, v 〉$	一条由顶点u指向顶点v的有向边
$C s u p e$	边e的cycle支持度
$τ e$	边e的cycle trussness值
$△ s c ↔ △ t c$	三角形 $△ s c$ 与 $△ t c$ 是cycle三角连通的
$e i$ $⇔ k$ $e j$	边 $e i 与 e j 是$ k-层次等价的
$N$	树节点，即一组k-层次等价集合

图2 k-cycle truss实例

Fig. 2 Example of k-cycle truss

图3 cycle三角连通样例

Fig. 3 Example of cycle triangle connectivity

图4 G的cycle truss分解

Fig. 4 Cycle truss decomposition of G

图5 有向图G的TreeCIndex

Fig. 5 TreeCIndex for directed graph G

表2 SuperTable的样例

Tab. 2 Example of SuperTable

$N$	$τ N$	Set	$N$	$τ N$	Set
1	2	1	3	1	1，2，3
2	2	2	4	1	4

表2 SuperTable的样例

Tab. 2 Example of SuperTable

$N$	$τ N$	Set	$N$	$τ N$	Set
1	2	1	3	1	1，2，3
2	2	2	4	1	4

表3 实验数据集的信息

Tab. 3 Information of experiment datasets

数据集名称	$V G$ /10³	$E G$ /10³	$D e g r e e m a x$	$k m a x$	$t r i a n g l e$ /10³
Wiki	7.1	103.7	1 167	6	608.4
Soc	75.9	508.8	3 079	18	1 624.5
Email	265.2	420.0	7 636	12	267.3
Stanford	281.9	2 312.5	38 626	40	11 329.5

表3 实验数据集的信息

Tab. 3 Information of experiment datasets

数据集名称	$V G$ /10³	$E G$ /10³	$D e g r e e m a x$	$k m a x$	$t r i a n g l e$ /10³
Wiki	7.1	103.7	1 167	6	608.4
Soc	75.9	508.8	3 079	18	1 624.5
Email	265.2	420.0	7 636	12	267.3
Stanford	281.9	2 312.5	38 626	40	11 329.5

表4 索引构建时间

Tab. 4 Index building time

数据集名称	数据集大小/MB	构建时间/s
数据集名称	数据集大小/MB	TrussIndex	EquiTruss	TreeCIndex	SuperTable
Wiki	1.04	8.53	14.73	13.53	13.86
Soc	5.40	97.29	721.69	140.43	146.48
Email	4.76	111.78	195.38	131.25	136.96
Stanford	31.30	131.21	9 624.80	166.55	172.47

表5 索引占用的空间 ( MB)

Tab. 5 Index space consumption

数据集名称	数据集大小	空间占用
数据集名称	数据集大小	TrussIdex	EquiTruss	TreeCIndex	SuperTable
Wiki	1.04	0.98	0.72	0.18	0.16
Soc	5.40	5.25	4.80	2.81	1.99
Email	4.76	4.81	3.23	1.60	1.51
Stanford	31.30	25.40	13.90	7.02	6.41

图6 查询顶点度数对执行时间的影响

Fig. 6 Influence of query vertexes degree on execution time

图7 k值对执行时间的影响

Fig. 7 Influence of k on execution time

图8 子图大小对执行时间的影响

Fig. 8 Influence of subgraph sizeon execution time

图9 三角形个数对执行时间的影响

Fig. 9 Influence of triangle numberon execution time

参考文献 16

1	杜明，顾万里，周军锋，等.基于motif连通性的社区搜索方法［J］.计算机应用， 2023， 43（7）： 2190-2199.
	DU M， GU W L， ZHOU J F， et al. Community search method based on motif connectivity ［J］. Journal of Computer Applications， 2023， 43（7）： 2190-2199.
2	FANG Y， HUANG X， QIN L， et al. A survey of community search over big graphs ［J］. The VLDB Journal， 2020， 29（1）： 353-392. 10.1007/s00778-019-00556-x
3	TAKAGUCHI T， YOSHIDA Y. Cycle and flow trusses in directed networks ［J］. Royal Society Open Science， 2016， 3（11）： No.160270. 10.1098/rsos.160270
4	WU Y， JIN R， LI J， et al. Robust local community detection： on free rider effect and its elimination ［J］. Proceedings of the VLDB Endowment， 2015， 8（7）： 798-809. 10.14778/2752939.2752948
5	LIU Q， ZHAO M， HUANG X， et al. Truss-based community search over large directed graphs ［C］// Proceedings of the 2020 ACM SIGMOD International Conference on Management of Data. New York： ACM， 2020： 2183-2197. 10.1145/3318464.3380587
6	AKBAS E， ZHAO P. Truss-based community search： a truss-equivalence based indexing approach ［J］. Proceedings of the VLDB Endowment， 2017， 10（11）： 1298-1309. 10.14778/3137628.3137640
7	SOZIO M， GIONIS A. The community-search problem and how to plan a successful cocktail party ［C］// Proceedings of the 16th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. New York： ACM， 2010： 939-948. 10.1145/1835804.1835923
8	LI D， ZENG L， HU R， et al. ITC： Influential-truss community search ［C］// Proceedings of the 2022 International Joint Conference on Neural Networks. Piscataway： IEEE， 2022： 1-8. 10.1109/ijcnn55064.2022.9892552
9	宋嘉祎.规模受限的影响力社区搜索方法研究［D］.上海：东华大学， 2022： 10-31.
	SONG J Y. A study of size-constrained influential community search ［D］. Shanghai： Donghua University， 2022： 10-31.
10	GUO G， YAN D， YUAN L， et al. Maximal directed quasi-clique mining ［C］// Proceedings of the IEEE 38th International Conference on Data Engineering. Piscataway： IEEE， 2022： 1900-1913. 10.1109/icde53745.2022.00188
11	LIU B， ZHANG F， ZHANG W， et al. Efficient community search with size constraint ［C］// Proceedings of the IEEE 37th International Conference on Data Engineering. Piscataway： IEEE， 2021： 97-108. 10.1109/icde51399.2021.00016
12	LIU Q， ZHU Y， ZHAO M， et al. VAC： vertex-centric attributed community search ［C］// Proceedings of the IEEE 36th International Conference on Data Engineering. Piscataway： IEEE， 2020： 937-948. 10.1109/icde48307.2020.00086
13	JIANG Y， HUANG X， CHENG H. I/O efficient k-truss community search in massive graphs ［J］. The VLDB Journal， 2021， 30（5）： 713-738. 10.1007/s00778-020-00649-y
14	YANG Z， LI X， ZHANG X， et al. k-truss community most favorites query based on top-t ［J］. World Wide Web， 2022， 25（2）： 949-969. 10.1007/s11280-021-00947-7
15	XIE X， SONG M， LIU C， et al. Effective influential community search on attributed graph ［J］. Neurocomputing， 2021， 444： 111-125. 10.1016/j.neucom.2020.08.088
16	WANG J， CHENG J. Truss decomposition in massive networks ［J］. Proceedings of the VLDB Endowment， 2012， 5（9）： 812-823. 10.14778/2311906.2311909

[1]	杜明, 顾万里, 周军锋, 王志军. 基于motif连通性的社区搜索方法[J]. 《计算机应用》唯一官方网站, 2023, 43(7): 2190-2199.
[2]	陈献, 胡丽莹, 林晓炜, 陈黎飞. 基于核非负矩阵分解的有向图聚类算法[J]. 《计算机应用》唯一官方网站, 2021, 41(12): 3447-3454.
[3]	李甲地, 马驰, 李德权, 王俊雅. 多个体切换网络分布式量化次梯度优化算法[J]. 计算机应用, 2018, 38(2): 509-515.
[4]	刘兴林. 改进的增量词集频率主题词提取算法[J]. 计算机应用, 2013, 33(09): 2546-2549.
[5]	党正军杜中军. 新的基于图搜索的工作流图验证算法[J]. 计算机应用, 2010, 30(3): 615-616.
[6]	范轶彦邬国锐. 动态僵尸网络模型研究[J]. 计算机应用, 2010, 30(3): 692-694.
[7]	张博刚张威陈月宁廖飞雄. 基于运行监测的图形用户界面自动化测试模型[J]. 计算机应用, 2010, 30(10): 2749-2753.
[8]	高文宇. 有向图最多叶子生成树问题研究[J]. 计算机应用, 2010, 30(06): 1431-1433.
[9]	李琳李琳张丽. 基于扩展有向图的工作流建模的设计与应用[J]. 计算机应用, 2008, 28(9): 2437-2439.
[10]	陈耀东，王挺. 基于有向图的双向匹配分词算法及实现[J]. 计算机应用, 2005, 25(06): 1442-1444.

有向图上基于层次树索引的最大cycle truss社区搜索

Maximum cycle truss community search based on hierarchical tree index on directed graphs

RichHTML

PDF

可视化

摘要/Abstract

引用本文

使用本文

图/表 14

参考文献 16

相关文章 10

编辑推荐

Metrics