满足强连通性的有向团枚举算法研究

doi:10.3778/j.issn.1673-9418.2303079

摘要/Abstract

摘要： 有向图的有向边可以表示关系的指向或者数据的传递，在稠密子图的挖掘中引入连通性的约束可以增加顶点之间的联系。为此，结合极大团与强连通分量的定义，底图是完全子图且顶点之间满足强连通性的子图结构被称为有向团。已有工作给出了枚举极大有向团的输出敏感算法，然而其存在大量重复枚举和判重操作复杂等不足之处。为了解决这些问题，基于深度优先搜索的思想和有向团的扩展性质，提出一种新颖的递归枚举算法。算法对于出边邻居和入边邻居分别划分候选集与排除集，维护完全子图结构的同时，不断尝试扩展有向团并保证满足强连通性，并且引入基于共同邻居的支撑点剪枝策略，在稠密图上获得上千倍的效率优化。算法还针对搜索空间给出两种优化设计：一是添加了分割子图的预处理，限制递归调用的搜索范围；二是基于位向量压缩表示顶点集合，提高集合运算的效率。在真实图数据上的实验结果表明，相比现有工作中的输出敏感算法，提出的算法具有50倍以上的加速比。

关键词: 图数据挖掘, 有向团, 强连通性, 支撑点剪枝, 位向量压缩

Abstract: Directed edges in a directed graph can represent the direction of relationships or the transmission of data. Introducing connectivity constraints in the mining of dense subgraphs can enhance the connections between vertices. Accordingly, by combining the definitions of maximal cliques and strongly connected components, a directed clique is a subgraph structure where the underlying graph is a complete subgraph and the vertices are strongly connected. Existing work has proposed an output-sensitive algorithm for enumerating maximal directed cliques, but it suffers from lots of repeated enumerations and complex deduplication operations. To address these issues, a novel recursive enumeration algorithm based on depth-first search and the characteristics of directed clique extension is proposed. The algorithm divides the outgoing and incoming neighbors into candidate and excluded sets respectively. While preserving the structure of complete subgraph, it constantly tries to extend the directed cliques and ensures that they are strongly connected. Additionally, the algorithm adopts a pivot pruning strategy based on common neighbors, achieving efficiency optimization of over a thousand times on dense graphs. Furthermore, the algorithm utilizes two optimization designs for the search space: firstly, a pre-processing step is introduced to divide subgraphs and narrow the search for the recursion; secondly, a bitwise compression representation is proposed for vertex sets to improve the efficiency of set operations. Experimental results on real-world graphs demonstrate that the proposed algorithm achieves a speedup of more than 50x compared with the existing output-sensitive algorithm.

Key words: graph data mining, directed clique, strongly connected, pivot pruning, bitwise compression

陈久健, 代强强, 李荣华, 王国仁. 满足强连通性的有向团枚举算法研究[J]. 计算机科学与探索, 2024, 18(5): 1211-1222.

CHEN Jiujian, DAI Qiangqiang, LI Ronghua, WANG Guoren. Research on Directed Clique Enumeration with Strongly Connected Constraint[J]. Journal of Frontiers of Computer Science and Technology, 2024, 18(5): 1211-1222.

参考文献

[1] JAVA A, SONG X, FININ T, et al. Why we Twitter: understanding microblogging usage and communities[C]//Proceedings of the 9th WebKDD and 1st SNA-KDD 2007 Workshop on Web Mining and Social Network Analysis, San Jose, Aug 12-15, 2007. New York: ACM, 2007: 56-65.
[2] TANG G, PEI J, LUK W. Email mining: tasks, common techniques, and tools[J]. Knowledge and Information Systems, 2014, 41(1): 1-31.
[3] CAPOCCI A, SERVEDIO V D, COLAIORI F, et al. Preferential attachment in the growth of social networks: the Internet encyclopedia Wikipedia[J]. Physical Review E, 2006, 74(3): 036116.
[4] KLEINBERG J M. Authoritative sources in a hyperlinked environment[J]. Journal of the ACM, 1999, 46(5): 604-632.
[5] 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, Sydney, Dec 14-17, 2010. Washington: IEEE Computer Society, 2010: 294-303.
[6] ZHANG J, WANG C, WANG J. Who proposed the relationship?: recovering the hidden directions of undirected social networks[C]//Proceedings of the 23rd International Conference on World Wide Web, Seoul, Apr 7-11, 2014. New York: ACM, 2014: 807-818.
[7] 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.
[8] MA C, FANG Y, CHENG R, et al. Efficient algorithms for densest subgraph discovery on large directed graphs[C]//Proceedings of the 2020 ACM SIGMOD International Conference on Management of Data, Portland, Jun 14-19, 2020. New York: ACM, 2020: 1051-1066.
[9] GUO G, YAN D, YUAN L, et al. Maximal directed quasi-clique mining[C]//Proceedings of the 38th IEEE International Conference on Data Engineering, Kuala Lumpur, May 9-12, 2022. Washington: IEEE Computer Society, 2022: 1900-1913.
[10] 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.
[11] 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, Banff, May 8, 2007. New York: ACM, 2007: 45-48.
[12] 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.
[13] BRON C, KERBOSCH J. Finding all cliques of an undirected graph (algorithm 457)[J]. Communications of the ACM, 1973, 16(9): 575-576.
[14] TARJAN R E. Depth-first search and linear graph algorithms[J]. SIAM Journal on Computing, 1972, 1(2): 146-160.
[15] KOCH I. Enumerating all connected maximal common subgraphs in two graphs[J]. Theoretical Computer Science, 2001, 250(1/2): 1-30.
[16] TOMITA E, TANAKA A, TAKAHASHI H. The worst-case time complexity for generating all maximal cliques and computational experiments[J]. Theoretical Computer Science, 2006, 363(1): 28-42.
[17] EPPSTEIN D, L?FFLER M, STRASH D. Listing all maximal cliques in sparse graphs in near-optimal time[C]//Proceedings of the 21st Annual International Symposium on Algorithms and Computations, Jeju Island, Dec 15-17, 2010. Berlin, Heidelberg: Springer, 2010: 403-414.
[18] ZHANG Y, ABU-KHZAM F N, BALDWIN N E, et al. Genome-scale computational approaches to memory-intensive applications in systems biology[C]//Proceedings of the 2005 ACM/IEEE Conference on Supercomputing, Seattle, Nov 12-18, 2005. Washington: IEEE Computer Society, 2005: 12.
[19] DAS A, SANEI-MEHRI S, TIRTHAPURA S. Shared-memory parallel maximal clique enumeration[C]//Proceedings of the 25th IEEE International Conference on High Performance Computing, Bengaluru, Dec 17-20, 2018. Piscataway: IEEE, 2018: 62-71.
[20] FANG Y, WANG Z, 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.
[21] KUNEGIS J. KONECT: the Koblenz network collection[C]//Proceedings of the 22nd International Conference on World Wide Web, Rio de Janeiro, May 13-17, 2013. New York: ACM, 2013: 1343-1350.
[22] TANG J, ZHANG J, YAO L, et al. ArnetMiner: extraction and mining of academic social networks[C]//Proceedings of the 14th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, Las Vegas, Aug 24-27, 2008. New York: ACM, 2008: 990-998.