基于贪婪策略的紧密<i>k</i>核子图查询

doi:10.19678/j.issn.1000-3428.0062639

计算机工程 ›› 2022, Vol. 48 ›› Issue (10): 55-66. doi: 10.19678/j.issn.1000-3428.0062639

基于贪婪策略的紧密k核子图查询

赵丹枫¹, 姚贤标¹, 包晓光¹, 黄冬梅², 郭伟其³

1. 上海海洋大学信息学院, 上海 201306;
2. 上海电力大学电子与信息工程学院, 上海 200090;
3. 国家海洋局东海海洋环境调查勘察中心, 上海 200137

收稿日期:2021-09-08 修回日期:2021-11-01 发布日期:2022-10-09
作者简介:赵丹枫(1982—),女,讲师、博士,主研方向为图计算、大数据技术;姚贤标,硕士研究生;包晓光,讲师、博士;黄冬梅(通信作者)、郭伟其,教授。
基金资助:
国家自然科学基金青年科学基金项目（42106190）；上海市科委地方能力建设项目（20050501900）。

Closely Related k-Core Subgraph Query Based on Greedy Strategy

ZHAO Danfeng¹, YAO Xianbiao¹, BAO Xiaoguang¹, HUANG Dongmei², GUO Weiqi³

1. College of Information Technology, Shanghai Ocean University, Shanghai 201306, China;
2. College of Electronics and Information Engineering, Shanghai University of Electric Power, Shanghai 200090, China;
3. East China Sea Marine Environment Survey and Survey Center, State Oceanic Administration, Shanghai 200137, China

Received:2021-09-08 Revised:2021-11-01 Published:2022-10-09

摘要/Abstract

摘要： k核查询是一种社团查询，由于其可以在线性时间内被有效计算，因此在社团检测中具有较广泛的应用。图中边的权值在很多场景下具有较强的语义关系，但现有研究较少考虑图中边的权值。为提升k核查询的效率，在k核的基础上定义加权图中的紧密k核子图查询（CRKSQ）问题，并使用归约方法证明该问题是NP-难的。基于贪婪策略设计启发式算法CRK-G，通过迭代删除节点为CRKSQ问题找到一个近似解。在此基础上，从降低图规模和减少迭代次数两方面研究CRK-G算法的优化策略，分别提出使用图压缩策略的算法CRK-C及使用单次多节点删除策略的算法CRK-F。在Bio-GRID、Email-Enron、DBLP 3个数据集上的实验结果表明，相对于CRK-G算法，CRK-C、CRK-F算法在查询速度上有较大的提升，且平均误差均在8%以内。

关键词: 社团检测, k核, 加权图, 紧密子图, 贪婪策略

Abstract: k-core query is a type of community query because it can be calculated effectively in linear time and has a wide range of applications in community detection.In some scenarios, the weights of edges in graphs exhibit strong semantics, but the weights of edges in graphs were rarely considered in previous studies.First, the Closely Related k-core Subgraph Query(CRKSQ) problem in weighted graphs is defined based on the k-core, and the problem is confirmed to be Non-deterministic Polynomial-time hard(NP-hard) using the reduction method.Second, a heuristic algorithm CRK-G is designed based on the greedy strategy to obtain an approximate solution to the CRKSQ problem by iteratively deleting nodes.Finally, the optimization strategy of the CRK-G algorithm is evaluated based on two aspects:reducing the graph size and the number of iterations.This study proposes a CRK-C algorithm using the graph compression strategy and a CRK-F algorithm using the single-time multinode deletion strategy.The experimental results for three datasets (Bio-GRID, Email-Enron, and DBLP) show that compared with the CRK-G algorithm, the CRK-C and CRK-F algorithms exhibited significantly improved query speed, and the average error is within 8%.

Key words: community detection, k-core, weighted graph, closely related subgraph, greedy strategy

中图分类号:

TP18

赵丹枫, 姚贤标, 包晓光, 黄冬梅, 郭伟其. 基于贪婪策略的紧密k核子图查询[J]. 计算机工程, 2022, 48(10): 55-66.

ZHAO Danfeng, YAO Xianbiao, BAO Xiaoguang, HUANG Dongmei, GUO Weiqi. Closely Related k-Core Subgraph Query Based on Greedy Strategy[J]. Computer Engineering, 2022, 48(10): 55-66.

http://www.ecice06.com/CN/Y2022/V48/I10/55

图/表 10

参考文献

[1] FANG Y X, HUANG X, QIN L, et al.A survey of community search over big graphs[J].The VLDB Journal, 2020, 29(1):353-392.
[2] 胡开先, 梁英, 苏立新, 等.基于完全子图的社交网络用户特征识别方法[J].模式识别与人工智能, 2016, 29(8):698-708. HU K X, LIANG Y, SU L X, et al.Method for social network user feature recognition based on clique[J].Pattern Recognition and Artificial Intelligence, 2016, 29(8):698-708.(in Chinese)
[3] LAPPAS T, LIU K, TERZI E.Finding a team of experts in social networks[C]//Proceedings of the 15th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining.New York, USA:ACM Press, 2009:467-476.
[4] YAN X, ZHOU X J, HAN J.Mining closed relational graphs with connectivity constraints[C]//Proceedings of the 21st International Conference on Data Engineering.Washington D.C., USA:IEEE Press, 2005:357-358.
[5] ASTHANA S, KING O D, GIBBONS F D, et al.Predicting protein complex membership using probabilistic network reliability[J].Genome Research, 2004, 14(6):1170-1175.
[6] 杜梅, 胡学钢, 李磊, 等.基于网络结构极值优化的半监督社团检测方法[J].模式识别与人工智能, 2015, 28(2):162-172. DU M, HU X G, LI L, et al.Network structure-enhanced extremal optimization based semi-supervised algorithm for community detection[J].Pattern Recognition and Artificial Intelligence, 2015, 28(2):162-172.(in Chinese)
[7] FANUEL M, ALAÍZ C M, SUYKENS J A K.Magnetic eigenmaps for community detection in directed networks[J].Physical Review E, 2017, 95(2):022302.
[8] 李国朋, 潘志松, 姚清, 等.融合先验信息的非负矩阵分解社区发现算法[J].模式识别与人工智能, 2016, 29(7):608-615. LI G P, PAN Z S, YAO Q, et al.Nonnegative matrix factorization algorithm with prior information for community detection[J].Pattern Recognition and Artificial Intelligence, 2016, 29(7):608-615.(in Chinese)
[9] SEIDMAN S B.Network structure and minimum degree[J].Social Networks, 1983, 5(3):269-287.
[10] MEDYA S, MA T, SILVA A, et al.K-core minimization:a game theoretic approach[EB/OL].[2021-08-08].https://arxiv.org/pdf/1901.02166v1.pdf.
[11] FANG Y X, WANG Z, CHENG R, et al.On spatial-aware community search[J].IEEE Transactions on Knowledge and Data Engineering, 2019, 31(4):783-798.
[12] CHU D M, ZHANG F, LIN X M, et al.Finding the best k in core decomposition:a time and space optimal solution[C]//Proceedings of the 36th IEEE International Conference on Data Engineering.Washington D.C., USA:IEEE Press, 2020:685-696.
[13] LI R H, QIN L, YU J X, et al.Finding influential communities in massive networks[J].The VLDB Journal, 2017, 26(6):751-776.
[14] FANG Y X, WANG Z R, CHENG R, et al.Effective and efficient community search over large directed graphs[J].IEEE Transactions on Knowledge and Data Engineering, 2019, 31(11):2093-2107.
[15] CHEN Y K, FANG Y X, CHENG R, et al.Exploring communities in large profiled graphs[J].IEEE Transactions on Knowledge and Data Engineering, 2019, 31(8):1624-1629.
[16] HABIB W M A, MOKHTAR H M O, EL-SHARKAWI M E.Weight-based K-truss community search via edge attachment[J].IEEE Access, 2020, 8:148841-148852.
[17] AKBAS E.Index based efficient algorithms for closest community search[C]//Proceedings of 2019 IEEE International Conference on Big Data.Washington D.C., USA:IEEE Press, 2020:701-710.
[18] YUAN L, QIN L, ZHANG W J, et al.Index-based densest clique percolation community search in networks[J].IEEE Transactions on Knowledge and Data Engineering, 2018, 30(5):922-935.
[19] BATAGELJ V, ZAVERSNIK M.An O(m) algorithm for cores decomposition of networks[J].Computer Science, 2003, 1(6):34-37.
[20] KHAOUID W, BARSKY M, SRINIVASAN V, et al.K-core decomposition of large networks on a single PC[J].Proceedings of the VLDB Endowment, 2015, 9(1):13-23.
[21] 李鸣鹏, 高宏, 邹兆年.基于图压缩的最大Steiner连通k核查询处理[J].软件学报, 2016, 27(9):2265-2277. LI M P, GAO H, ZOU Z N.Maximum steiner connected k-core query processing based on graph compression[J].Journal of Software, 2016, 27(9):2265-2277.(in Chinese)
[22] BARBIERI N, BONCHI F, GALIMBERTI E, et al.Efficient and effective community search[J].Data Mining and Knowledge Discovery, 2015, 29(5):1406-1433.
[23] CUI W Y, XIAO Y H, WANG H X, et al.Local search of communities in large graphs[C]//Proceedings of 2014 ACM SIGMOD International Conference on Management of Data.New York, USA:ACM Press, 2014:991-1002.
[24] ZHENG D, LIU J Q, LI R H, et al.Querying intimate-core groups in weighted graphs[C]//Proceedings of the 11th IEEE International Conference on Semantic Computing.Washington D.C., USA:IEEE Press, 2017:156-163.
[25] KARP R M.Reducibility among combinatorial problems[C]//Proceedings of IEEE International Conference on Complexity of Computer Computations.Washington D.C., USA:IEEE Press, 1972:85-103.
[26] LIANG Y Z, CHEN C, WANG Y K, et al.Reachability preserving compression for dynamic graph[J].Information Sciences, 2020, 520:232-249.
[27] MASERRAT H, PEI J.Neighbor query friendly compression of social networks[C]//Proceedings of the 16th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining.New York, USA:ACM Press, 2010:533-542.

选择文件类型/文献管理软件名称

选择包含的内容

基于贪婪策略的紧密k核子图查询

Closely Related k-Core Subgraph Query Based on Greedy Strategy

RichHTML

PDF

可视化

被引次数

摘要/Abstract

引用本文

使用本文

图/表 10

参考文献

相关文章 9

编辑推荐

Metrics

本文评价

[1]	孙登第, 凌媛, 丁转莲, 罗斌. 基于稀疏子空间聚类的多层网络社团检测[J]. 计算机工程, 2021, 47(10): 52-60.
[2]	刘宇廷,毕海滨,郭强,倪颖杰. 基于网络拓扑与节点元数据的社团检测算法[J]. 计算机工程, 2018, 44(11): 178-183.
[3]	蒋盛益，吴美玲，杨博泓. 基于网络社团检测的电信客户细分[J]. 计算机工程, 2014, 40(7): 312-316.
[4]	张可为, 申群太. 基于多级协同传播的交互式图像分割[J]. 计算机工程, 2013, 39(2): 225-228.
[5]	谷多玉，申浩，叶曙光，林喆，常红星. 基于图的航空图像与GIS模型匹配算法[J]. 计算机工程, 2013, 39(10): 187-191.
[6]	闫沫, 王瑜. 一种基于组件树的SAR图像分割算法[J]. 计算机工程, 2012, 38(22): 201-204.
[7]	程文斐, 谭小彬, 徐鹏. 基于贪婪策略的高效可靠多播路由协议[J]. 计算机工程, 2012, 38(21): 97-99,106.
[8]	易三莉, 陈真诚, 林红利. 稳健MM估计在扩散张量成像中的应用[J]. 计算机工程, 2011, 37(21): 191-193.
[9]	廖顺和;乐嘉锦. 一种基于无向加权图的距离检索和查询方法[J]. 计算机工程, 2008, 34(15): 80-82.

模态框（Modal）标题

选择文件类型/文献管理软件名称

选择包含的内容

基于贪婪策略的紧密k核子图查询

Closely Related k-Core Subgraph Query Based on Greedy Strategy

RichHTML

PDF

可视化

被引次数

摘要/Abstract

引用本文

使用本文

图/表 10

参考文献

相关文章 9

编辑推荐

Metrics

本文评价