Computer Science

Computer Science ›› 2026, Vol. 53 ›› Issue (3): 166-172.doi: 10.11896/jsjkx.250400086

• Database & Big Data & Data Science • Previous Articles     Next Articles

Research on Maximal Directed k-plex Enumeration Problem

HOU Jingle1, LI Zhengjun2, DAI Qiangqiang1, LI Ronghua1, WANG Guoren1   

  1. 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 Published: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).

PDF (PC)

105

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

CLC Number: 

  • TP391
[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 23rd 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.
[1] LIU Lilong, LIU Guoming, QI Baoyuan, DENG Xueshan, XUE Dizhan, QIAN Shengsheng. Efficient Inference Techniques of Large Models in Real-world Applications:A Comprehensive Survey [J]. Computer Science, 2026, 53(1): 12-28.
[2] LIU Dayong, DONG Zhiming, GUO Qisheng, GAO Ang, QIU Xuehuan. Research on Architecture and Technology Pathways for Empowering Tactical AdversarialSimulation Experiments with LLMs [J]. Computer Science, 2026, 53(1): 39-50.
[3] WANG Cheng, JIN Cheng. KAN-based Unsupervised Multivariate Time Series Anomaly Detection Network [J]. Computer Science, 2026, 53(1): 89-96.
[4] LIU Hongjian, ZOU Danping, LI Ping. Pedestrian Trajectory Prediction Method Based on Graph Attention Interaction [J]. Computer Science, 2026, 53(1): 97-103.
[5] XUE Jingyan, XIA Jianan, HUO Ruili, LIU Jie, ZHOU Xuezhong. Review of Retinal Image Analysis Methods for OCT/OCTA Based on Deep Learning [J]. Computer Science, 2026, 53(1): 128-140.
[6] ZHAO Wenhao, MEI Meng, WANG Xiaoping, LUO Hangyu. PKHOI:Enhancing Human-Object Interaction Detection Algorithms with Prior Knowledge [J]. Computer Science, 2026, 53(1): 141-152.
[7] ZHOU Bingquan, JIANG Jie, CHEN Jiangmin, ZHAN Lixin. EvR-DETR:Event-RGB Fusion for Lightweight End-to-End Object Detection [J]. Computer Science, 2026, 53(1): 153-162.
[8] LI Fangfang, KONG Yuqiu, LIU Yang , LI Pengyue. Co-salient Object Detection Guided by Category Labels [J]. Computer Science, 2026, 53(1): 163-172.
[9] LI Ang, ZHANG Jieyuan, LIU Xunyun. Camouflaged Object Detection for Aerial Images Based on Bidirectional Cross-attentionCross-domain Fusion [J]. Computer Science, 2026, 53(1): 173-179.
[10] BU Yunyang, QI Binting, BU Fanliang. Multimodal Sentiment Analysis for Interactive Fusion of Dual Perspectives Under Cross-modalInconsistent Perception [J]. Computer Science, 2026, 53(1): 187-194.
[11] LYU Jinggang, GAO Shuo, LI Yuzhi, ZHOU Jin. Facial Expression Recognition with Channel Attention Guided Global-Local Semantic Cooperation [J]. Computer Science, 2026, 53(1): 195-205.
[12] CHEN Jiwei, CHEN Zebin, TAN Guang. Visual Floorplan Localization Based on BEV Perception [J]. Computer Science, 2026, 53(1): 216-223.
[13] KALZANG Gyatso, NYIMA Tashi, QUN Nuo, GAMA Tashi, DORJE Tashi, LOBSANG Yeshi, LHAMO Kyi, ZOM Kyi. Data Augmentation Methods for Tibetan-Chinese Machine Translation Based on Long-tail Words [J]. Computer Science, 2026, 53(1): 224-230.
[14] JIA Jingdong, HOU Xin, WANG Zhe, HUANG Jian. Research on User Data-driven App Fading Functions [J]. Computer Science, 2026, 53(1): 262-270.
[15] CHEN Zhuangzhuang, DENG Yichen, YU Dunhui, XIAO Kui. Cross-language Knowledge Graph Entity Alignment Based on Meta-learning [J]. Computer Science, 2026, 53(1): 271-277.
Viewed
Full text


Abstract

Cited
  Shared   
  Discussed   
No Suggested Reading articles found!
渝ICP备16013121号-4
Add:18# Honghu West Rd., Yubei ,Chongqing,China    Post Code: 401121
Tel: 023-63500828/023-67039612/023-67039623
E-mail: jsjkx12@163.com
Powered by Beijing Magtech Co., Ltd.