实例簇驱动的图结构聚类参数计算算法

doi:10.11772/j.issn.1001-9081.2022010082

《计算机应用》唯一官方网站 ›› 2023, Vol. 43 ›› Issue (2): 398-406.DOI: 10.11772/j.issn.1001-9081.2022010082

• 数据科学与技术 • 上一篇

实例簇驱动的图结构聚类参数计算算法

宗传玉, 宪超(), 夏秀峰

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

收稿日期:2022-01-21 修回日期:2022-04-06 接受日期:2022-04-11 发布日期:2022-04-25 出版日期:2023-02-10
通讯作者: 宪超
作者简介:宗传玉（1985—），男，山东潍坊人，副教授，博士，CCF会员，主要研究方向：数据清洗、数据溯源、查询处理与优化
夏秀峰（1964—），男，山东胶南人，教授，博士，CCF会员，主要研究方向：数据库、数据仓库。
基金资助:
国家自然科学基金资助项目(61802268)

Parameter calculation algorithm of structural graph clustering driven by instance clusters

Chuanyu ZONG, Chao XIAN(), Xiufeng XIA

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

Received:2022-01-21 Revised:2022-04-06 Accepted:2022-04-11 Online:2022-04-25 Published:2023-02-10
Contact: Chao XIAN
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)

摘要/Abstract

摘要：

pSCAN算法的聚类结果受密度约束参数和相似度阈值参数的影响，如果用户提供的聚类参数得到的聚类结果无法满足需求，那么用户可以通过实例簇表达自己的聚类需求。针对实例簇表达聚类查询需求的问题，提出一种实例簇驱动的图结构聚类参数计算算法PART及其改进算法ImPART。首先，分析两个聚类参数对聚类结果的影响，并提取实例簇的相关子图；其次，对相关子图进行分析得到密度约束参数的可行区间，并根据当前密度约束参数和节点之间的结构相似度将实例簇内节点划分为核心节点和非核心节点；最后，依据节点划分结果计算出当前密度约束参数对应的最优相似度阈值参数，并在相关子图上对得到的参数进行验证和优化，直到得到满足实例簇需求的聚类参数。在真实数据集上的实验结果表明，所提算法能够为用户实例簇返回一组有效参数，且所提改进算法ImPART的运行时间比PART缩短了20%以上，能够快速有效地为用户返回满足实例簇要求的最优聚类参数。

关键词: 图结构聚类, 实例簇, 参数计算, 节点划分, 最优参数

Abstract:

Clustering results of the pSCAN （pruned Structural Clustering Algorithm for Network） algorithm are influenced by the density constraint parameter and the similarity threshold parameter. If the requirements cannot be satisfied by the clustering results obtained by the clustering parameters provided by the user， then the user’s own clustering requirements can be expressed through instance clusters. Aiming at the problem of instance clusters expressing clustering query requirements， an instance cluster-driven structural graph clustering parameter calculation algorithm PART and its improved algorithm ImPART were proposed. Firstly， the influences of two clustering parameters on the clustering results were analyzed， and correlation subgraph of instance cluster was extracted. Secondly， the feasible interval of the density constraint parameter was obtained by analyzing the correlation subgraph， and the nodes in the instance cluster were divided into core nodes and non-core nodes according to the current density constraint parameter and the structural similarity between nodes. Finally， according to the node division result， the optimal similarity threshold parameter corresponding to the current density constraint parameter was calculated， and the obtained parameters were verified and optimized on the relevant subgraph until the clustering parameters that satisfy the requirements of the instance cluster were obtained. Experimental results on real datasets show that a set of effective parameters can be returned for user instance clusters by using the proposed algorithm， and the proposed improved algorithm ImPART is more than 20% faster than the basic algorithm PART， and can return the optimal clustering parameters that satisfy the requirements of instance clusters quickly and effectively for the user.

Key words: structural graph clustering, instance cluster, parameter calculation, node division, optimal parameter

中图分类号:

TP391.1

宗传玉, 宪超, 夏秀峰. 实例簇驱动的图结构聚类参数计算算法[J]. 计算机应用, 2023, 43(2): 398-406.

Chuanyu ZONG, Chao XIAN, Xiufeng XIA. Parameter calculation algorithm of structural graph clustering driven by instance clusters[J]. Journal of Computer Applications, 2023, 43(2): 398-406.

图/表 11

图1 图结构聚类实例

Fig. 1 Example of structural graph clustering

图2 实例簇驱动的图结构参数计算算法框架

Fig. 2 Framework of instance-cluster-driven structural graph parameter calculation algorithm

图3 不同参数下的聚类结果

Fig. 3 Clustering results under different parameters

图4 算法1的实例

Fig. 4 Example of Algorithm 1

表1 实验中使用的实例簇

Tab. 1 Instance clusters used in experiments

实例簇	节点数	实例簇	节点数	实例簇	节点簇
C1	340	C5	370	C9	838
C2	851	C6	275	C10	132
C3	653	C7	103	C11	610
C4	144	C8	621	C12	395

图5 不同实例簇下PART和ImPART的运行时间

Fig. 5 Running times of PART and ImPART under different instance clusters

图6 数据集大小不同时PART和ImPART的运行时间

Fig. 6 Running times of PART and ImPART under different data sizes

图7 不同量级数据集上ImPART的运行时间

Fig. 7 Running time of ImPART on datasets with different magnitudes

表2 不同量级的实例簇

Tab. 2 Instance clusters with different magnitudes

实例簇	节点数	实例簇	节点数	实例簇	节点数
C21	34	C24	67	C27	31
C22	310	C25	343	C28	359
C23	3 520	C26	3 801	C29	3 127

图8 不同量级实例簇下PART和ImPART的执行时间

Fig. 8 Running times of PART and ImPART under instance clusters with different magnitudes

图9 不同实例簇对应的最优聚类参数

Fig. 9 Optimal clustering parameters corresponding to different instance clusters

参考文献 22

1	CHANG L J， LI W， LI X M， et al. pSCAN： fast and exact structural graph clustering［C］// Proceedings of the IEEE 32nd International Conference on Data Engineering. Piscataway： IEEE， 2016： 253-264. 10.1109/icde.2016.7498245
2	SHEN Y， CHAKRABARTI K， CHAUDHURI S， et al. Discovering queries based on example tuples［C］// Proceedings of the 2014 ACM SIGMOD International Conference on Management of Data. New York： ACM， 2014： 493-504. 10.1145/2588555.2593664
3	XU X W， YURUK N， FONG Z D， et al. SCAN： a structural clustering algorithm for networks［C］// Proceedings of the 13th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. New York： ACM， 2007： 824-833. 10.1145/1281192.1281280
4	SHIOKAWA H， FUJIWARA Y， ONIZUKA M. SCAN++： efficient algorithm for finding clusters， hubs and outliers on large-scale graphs［J］. Proceedings of the VLDB Endowment， 2015， 8（11）： 1178-1189. 10.14778/2809974.2809980
5	RUAN B Y， GAN J H， WU H， et al. Dynamic structural clustering on graphs［C］// Proceedings of the 2021 ACM SIGMOD International Conference on Management of Data. New York： ACM， 2021： 1491-1503. 10.1145/3448016.3452828
6	SHIOKAWA H， TAKAHASHI T. DSCAN： distributed structural graph clustering for billion-edge graphs［C］// Proceedings of the 2020 International Conference on Database and Expert Systems Applications， LNCS 12391. Cham： Springer， 2020： 38-54.
7	YU D X， WANG D B， LUO Q， et al. Stable structural clustering in uncertain graphs［J］. Information Sciences， 2022， 586： 596-610. 10.1016/j.ins.2021.11.078
8	TSENG T， DHULIPALA L， SHUN J. Parallel index-based structural graph clustering and its approximation［C］// Proceedings of the 2021 ACM SIGMOD International Conference on Management of Data. New York： ACM， 2021： 1851-1864. 10.1145/3448016.3457278
9	LIANG Y J， HU T T， ZHAO P X. Efficient structural clustering in large uncertain graphs［C］// Proceedings of the IEEE 36th International Conference on Data Engineering. Piscataway： IEEE， 2020： 1966-1969. 10.1109/icde48307.2020.00215
10	ZONG C Y， XIA X F， XIAN C， et al. Effectively incremental structural graph clustering for dynamic parameter［C］// Proceedings of the 2020 IEEE International Symposium on Parallel and Distributed Processing with Applications/ Big Data and Cloud Computing/ Sustainable Computing and Communications/ Social Computing and Networking. Piscataway： IEEE， 2020： 529-536. 10.1109/ispa-bdcloud-socialcom-sustaincom51426.2020.00092
11	SEO J H， KIM M H. I/O efficient structural clustering and maintenance of clusters for large-scale graphs［J］. Expert Systems with Applications， 2021， 168： No.114221. 10.1016/j.eswa.2020.114221
12	FARIHA A， MELIOU A. Example-driven query intent discovery： abductive reasoning using semantic similarity［J］. Proceedings of the VLDB Endowment， 2019， 12（11）： 1262-1275. 10.14778/3342263.3342266
13	KHWILDI R， OULED ZAID A， DUFAUX F. Query-by-example HDR image retrieval based on CNN［J］. Multimedia Tools and Applications， 2021， 80（10）： 15413-15428. 10.1007/s11042-020-10416-4
14	SARWAR S M， ALLAN J. Query by example for cross-lingual event retrieval［C］// Proceedings of the 43rd ACM SIGIR International Conference on Research and Development in Information Retrieval. New York： ACM， 2020： 1601-1604. 10.1145/3397271.3401283
15	ADAMOU A， ALLOCCA C， D’AQUIN M， et al. SPARQL query recommendation by example： assessing the impact of structural analysis on star-shaped queries［C］// Proceedings of the 2nd Conference on Language Data and Knowledge. Wadern： Schloss Dagstuhl - Leibniz-Zentrum für Informatik， 2019： No.1. 10.1007/s00799-018-0235-0
16	REZIG E K， BHANDARI A， FARIHA A， et al. DICE： data discovery by example［J］. Proceedings of the VLDB Endowment， 2021， 14（12）： 2819-2822. 10.14778/3476311.3476353
17	QIN X D， CHAI C L， LUO Y Y， et al. Interactively discovering and ranking desired tuples without writing SQL queries［C］// Proceedings of the 2020 ACM SIGMOD International Conference on Management of Data. New York： ACM， 2020： 2745-2748. 10.1145/3318464.3384695
18	JIANG H D， WANG B， WANG X， et al. Example-driven virtual cinematography by learning camera behaviors［J］. ACM Transactions on Graphics， 2020， 39（4）： No.45. 10.1145/3386569.3392427
19	THAKKAR A， NAIK A， SANDS N， et al. Example-guided synthesis of relational queries［C］// Proceedings of the 42nd ACM SIGPLAN International Conference on Programming Language Design and Implementation. New York： ACM， 2021： 1110-1125. 10.1145/3453483.3454098
20	FARIHA A， BRUCATO M， HAAS P J， et al. SuDocu： summarizing documents by example［J］. Proceedings of the VLDB Endowment， 2020， 13（12）： 2861-2864. 10.14778/3415478.3415494
21	吴清寿，陈荣旺，余文森，等. 融合标签预处理与节点影响力的重叠社区发现算法［J］. 计算机应用， 2020， 40（12）： 3578-3585. 10.15888/j.cnki.csa.007712
	WU Q S， CHEN R W， YU W S， et al. Overlapping community detection algorithm fusing label preprocessing and node influence［J］. Journal of Computer Applications， 2020， 40（12）： 3578-3585. 10.15888/j.cnki.csa.007712
22	李莎莎，梁冬阳，余杰，等. 基于师门关系的研究团队挖掘算法［J］. 计算机应用， 2020， 40（11）： 3198-3202.
	LI S S， LIANG D Y， YU J， et al. Research team mining algorithm based on teacher-student relationship［J］. Journal of Computer Applications， 2020， 40（11）： 3198-3202.

[1]	吴贵芳林青松孙秀明徐金梧徐科. 基于小样本的神经网络参数优化选择方法[J]. 计算机应用, 2008, 28(7): 1662-1664.
[2]	段崇雯成礼智. 有效提高SVM参数搜索效率的样本集缩减策略[J]. 计算机应用, 2007, 27(2): 363-365.

实例簇驱动的图结构聚类参数计算算法

Parameter calculation algorithm of structural graph clustering driven by instance clusters

RichHTML

PDF

可视化

摘要/Abstract

引用本文

使用本文

图/表 11

参考文献 22

相关文章 2

编辑推荐

Metrics

实例簇	节点数	实例簇	节点数	实例簇	节点簇
C1	340	C5	370	C9	838
C2	851	C6	275	C10	132
C3	653	C7	103	C11	610
C4	144	C8	621	C12	395

实例簇	节点数	实例簇	节点数	实例簇	节点簇
C1	340	C5	370	C9	838
C2	851	C6	275	C10	132
C3	653	C7	103	C11	610
C4	144	C8	621	C12	395

实例簇	节点数	实例簇	节点数	实例簇	节点簇
C1	340	C5	370	C9	838
C2	851	C6	275	C10	132
C3	653	C7	103	C11	610
C4	144	C8	621	C12	395

实例簇	节点数	实例簇	节点数	实例簇	节点簇
C1	340	C5	370	C9	838
C2	851	C6	275	C10	132
C3	653	C7	103	C11	610
C4	144	C8	621	C12	395

实例簇	节点数	实例簇	节点数	实例簇	节点簇
C1	340	C5	370	C9	838
C2	851	C6	275	C10	132
C3	653	C7	103	C11	610
C4	144	C8	621	C12	395

实例簇	节点数	实例簇	节点数	实例簇	节点簇
C1	340	C5	370	C9	838
C2	851	C6	275	C10	132
C3	653	C7	103	C11	610
C4	144	C8	621	C12	395