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

doi:10.11772/j.issn.1001-9081.2023010071

Journal of Computer Applications ›› 2024, Vol. 44 ›› Issue (1): 190-198.DOI: 10.11772/j.issn.1001-9081.2023010071

Special Issue: 数据科学与技术

• Data science and technology • Previous Articles Next Articles

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)

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

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

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

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

Abstract

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

摘要：

社区搜索旨在从信息网络中找出包含用户查询顶点的高内聚连通子图，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三角形, 层次等价, 层次树索引

CLC Number:

TP391.1

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.

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

Figures/Tables 14

Fig. 1 Examples of triangle structures

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-层次等价集合

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-层次等价集合

Fig. 2 Example of k-cycle truss

Fig. 3 Example of cycle triangle connectivity

Fig. 4 Cycle truss decomposition of G

Fig. 5 TreeCIndex for directed graph G

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

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

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

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

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

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

Fig. 6 Influence of query vertexes degree on execution time

Fig. 7 Influence of k on execution time

Fig. 8 Influence of subgraph sizeon execution time

Fig. 9 Influence of triangle numberon execution time

References 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]	Ming DU, Wanli GU, Junfeng ZHOU, Zhijun WANG. Community search method based on motif connectivity [J]. Journal of Computer Applications, 2023, 43(7): 2190-2199.
[2]	Xian CHEN, Liying HU, Xiaowei LIN, Lifei CHEN. Directed graph clustering algorithm based on kernel nonnegative matrix factorization [J]. Journal of Computer Applications, 2021, 41(12): 3447-3454.
[3]	QIN Qibing, TAN Long. Top-Rank-k frequent patterns mining algorithm based on TCM prescription database [J]. Journal of Computer Applications, 2017, 37(2): 329-334.
[4]	LIU Xinglin. Improved algorithm of thematic term extraction based on increment term-set frequency from Chinese document [J]. Journal of Computer Applications, 2013, 33(09): 2546-2549.
[5]	ZHANG Wei ZENG Rui-bi HU Ming-xiao. Weight-length consistent graph drawing algorithm for weighted undirected graphs [J]. Journal of Computer Applications, 2012, 32(04): 1116-1118.
[6]	. Research of dynamic Botnet model [J]. Journal of Computer Applications, 2010, 30(3): 692-694.
[7]	. New workflow verification algorithm based on graph-search [J]. Journal of Computer Applications, 2010, 30(3): 615-616.
[8]	. Graph user interface automatic testing model based on software monitoring [J]. Journal of Computer Applications, 2010, 30(10): 2749-2753.
[9]	. Design and application of workflow modeling based on extended-directed graph [J]. Journal of Computer Applications, 2008, 28(9): 2437-2439.
[10]	CHEN Yao-dong, WANG Ting. Using directed graph based BDMM algorithm for Chinese word segmentation [J]. Journal of Computer Applications, 2005, 25(06): 1442-1444.

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

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

RichHTML

PDF

Knowledge

Abstract

Cite this article

share this article

Figures/Tables 14

References 16

Related Articles 10

Recommended Articles

Metrics