面向有向图的k-plex稠密子图挖掘算法

doi:10.11896/jsjkx.250400086

计算机科学 ›› 2026, Vol. 53 ›› Issue (3): 166-172.doi: 10.11896/jsjkx.250400086

• 数据库 & 大数据 & 数据科学 • 上一篇下一篇

面向有向图的k-plex稠密子图挖掘算法

侯景乐¹, 李振军², 代强强¹, 李荣华¹, 王国仁¹

1 北京理工大学计算机学院北京 100081
2 深圳城市职业学院广东深圳 518038

收稿日期:2025-04-18 修回日期:2025-09-10 发布日期:2026-03-12
通讯作者: 李振军(lizhenjun@szsit.edu.cn)
作者简介:(1779870177@qq.com)
基金资助:
广东省普通高校特色创新类项目(2024KTSCX260)

Research on Maximal Directed k-plex Enumeration Problem

HOU Jingle¹, LI Zhengjun², DAI Qiangqiang¹, LI Ronghua¹, WANG Guoren¹

1 School of Computer Science & Technology, Beijing Institute of Technology, Beijing 100081, China
2 Information and Communication College of Shenzhen City Polytechnic, Shenzhen, Guangdong 518038, China

Received:2025-04-18 Revised:2025-09-10 Online:2026-03-12
About author:HOU Jingle,born in 2000,master.His main research interests include graph data mining and cloud computing.
LI Zhenjun,born in 1979,Ph.D.His main research interests include deep learning,blockchain,privacy computing,etc.
Supported by:
Characteristic Innovation Project of Ordinary Universities in Guangdong Province(2024KTSCX260).

摘要/Abstract

摘要： 有向图的有向边可以表示关系的指向或数据的传递,在稠密子图挖掘中引入并拓展一些无向图的经典稠密子图模型对图挖掘工作有着重要帮助。为此,结合有向图的特点与k-plex的定义,称有向图中任意一个顶点的非出边邻居和非入边邻居均不超过k的子图结构为有向k-plex。已有工作给出了在无向图中枚举极大k-plex的输出敏感算法,然而它们无法直接应用于有向图。为了解决这一问题,提出了一种基于图分解的递归枚举算法。为了更进一步优化运行效率,引入了基于支撑点的剪枝策略,还提供了基于有向k-plex上界的优化算法来终止一些无效的搜索分支。在真实图数据上进行实验,结果表明,图分解算法与剪枝优化均取得了良好的效果,所提算法在处理真实图数据时具有很强的实用性,能在2 h内完成对KONECT数据集中数百组真实世界有向图的处理。

关键词: 稠密子图, 有向k-plex, 图分解, 支撑点剪枝, 上界预估剪枝

Abstract: The directed edge of a directed graph can represent the direction of a relationship or the transfer of data.It is of great help to introduce and expand some classical dense subgraph models of undirected graphs in dense subgraph mining.Therefore,combining the characteristics of digraphs with the definition of k-plex,the subgraph structure in which the nonoutgoing neighbors and nonincoming neighbors of any vertex in a digraph do not exceed k is called a directed k-plex.Output sensitive algorithms for enumerating maximal k-plex in undirected graphs have been proposed,but they cannot be applied directly to directed graphs.To solve this problem,a recursive enumeration algorithm based on graph decomposition is proposed for maximal directed k-plex enumeration problem.In order to further optimize the efficiency of the algorithm,a pruning strategy based on support points is introduced,and an optimization algorithm based on the upper bound of directed k-plex is provided to terminate some invalid search branches.Experimental results on real graph data show that both the graph decomposition algorithm and pruning optimization have achieved good results.The proposed algorithm has strong practicability in processing real graph data,and can complete the processing of hundreds of groups of real world digraphs in KONECT data set within 2h.

Key words: Dense subgraph, Directed k-plex, Graph decomposition, Support point pruning, Upper bound estimated pruning

中图分类号:

TP391

侯景乐, 李振军, 代强强, 李荣华, 王国仁. 面向有向图的k-plex稠密子图挖掘算法[J]. 计算机科学, 2026, 53(3): 166-172. https://doi.org/10.11896/jsjkx.250400086

HOU Jingle, LI Zhengjun, DAI Qiangqiang, LI Ronghua, WANG Guoren. Research on Maximal Directed k-plex Enumeration Problem[J]. Computer Science, 2026, 53(3): 166-172. https://doi.org/10.11896/jsjkx.250400086

参考文献

[1]DU N,WU B,PEI X,et al.Community detection in large-scale social networks[C]//Proceedings of the 9th WebKDD and 1st SNA－KDD 2007 Workshop on Web Mining and Social Network Analysis.2007:16-25.
[2]XIE J,KELLEY S,SZYMANSKI B K.Overlapping community detection in networks:The state-ofthe-art and comparative study[J].ACM Computer Surveys,2013,45(4):43:1-43:35.
[3]TANG G,PEI J,LUK W.Email mining:tasks,common techniques,and tools[J].Knowledge and Information Systems,2014,41(1):1-31.
[4]CAPOCCI A,SERVEDIO V D,COLAIORI F,et al.Preferentialattachment in the growth of social networks:The internet encyclopedia Wikipedia[J].Physical Review E,2006,74(3):036116.
[5]KLEINBERG J M.Authoritative sources in a hyperlinked environment[J].Journal of the ACM,1999,46(5):604-632.
[6]LI Z,XIONG H,LIU Y,et al.Detecting blackhole and volcano patterns in directed networks[C]//Proceedings of the 2010 IEEE International Conference on Data Mining.2010:294-303.
[7]ZHANG J,WANG C,WANG J.Who proposed the relation-ship?:recovering the hidden directions of undirected social networks[C]//Proceedings of the 23^rd International Conference on World Wide Web.ACM,2014:807-818.
[8]GIATSIDIS C,THILIKOS D M,VAZIRGIANNIS M.D-cores:measuring collaboration of directed graphs based on degeneracy[J].Knowledge and Information Systems,2013,35(2):311-343.
[9]MA C,FANG Y,CHENG R,et al.Efficient algorithms for densest subgraph discovery on large directed graphs[C]//Procee-dings of the 2020 ACM SIGMOD International Conference on Management of Data.ACM,2020:1051-1066.
[10]GUO G,YAN D,YUAN L,et al.Maximal directed quasi-clique mining[C]//Proceedings of the 38th IEEE International Confe-rence on Data Engineering.IEEE Computer Society,2022:1900-1913.
[11]ALBA R D.A graph-theoretic definition of a sociometric clique[J].Journal of Mathematical Sociology,1973,3(1):113-126.
[12]FREEMAN L C.The sociological concept of “group”:An empirical test of two models[J].American Journal of Sociology,1992,98(1):152-166.
[13]BALASUNDARAM B,BUTENKO S,HICKS I V.Clique relaxations in social network analysis:The maximum k-plex problem[J].Operations Research,2011,59(1):133-142.
[14]SEIDMAN S B,FOSTER B L.A graph-theoretic generalization of the clique concept[J].Journal of Mathematical sociology,1978,6(1):139-154.
[15]BRON C,KERBOSCH J.Algorithm 457:Finding all cliques of an undirected graph[J].Communications of the ACM,1973,16(9):575-576.
[16]WU B,PEI X.A parallel algorithm for enumerating all the maximal k-plexes[C]//Pacific-Asia Conference on Knowledge Discovery and Data Mining.2007:476-483.
[17]CONTE A,FIRMANI D,MORDENTE C,et al.Fast enumeration of large k-plexes[C]//Proceedings of the 23rd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining.2017:115-124.
[18]CONTE A,MATTEIS T D,SENSI D D,et al.D2K:scalablecommunity detection in massive networks via small-diameter k-plexes[C]//Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining.2018:1272-1281.
[19]CONTE A,KANTÉ M M,UNO T,et al.Maximal strongly connected cliques in directed graphs:algorithms and bounds[J].Discrete Applied Mathematics,2021,303:237-252.
[20]CHEN J J,DAI Q Q,LI R H,et al.Research on directed clique enumeration algorithms that satisfy strong connectivity[J].Computer Science and Exploration,2024,18(5):1211-1222.
[21]PEARCE D J,KELLY P H J,HANKIN C.Efficient field-sensitive pointer analysis of C[J].ACM Transactions on Programming Languages and Systems,2007,30(1):4.
[22]SAITO H,TOYODA M,KITSUREGAWA M,et al.A large-scale study of link spam detection by graph algorithms[C]//Proceedings of the 3rd International Workshop on Adversarial Information Retrieval on the Web.ACM,2007:45-48.

Metrics

Viewed

Full text

Abstract

Cited

Shared

Discussed

面向有向图的k-plex稠密子图挖掘算法

Research on Maximal Directed k-plex Enumeration Problem

PDF (PC)

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 0

Metrics

本文评价

推荐阅读 0