A fast and complete algorithm for enumerating pseudo-cliques in large graphs
A fast and complete algorithm for enumerating pseudo-cliques in large graphs
复制标题
DOI：
10.1007/s41060-016-0022-1
复制
发表时间：
2016-09
影响因子：
2.4
通讯作者：
Hongjie Zhai;M. Haraguchi;Yoshiaki Okubo;E. Tomita
中科院分区：
文献类型：
--
作者：
Hongjie Zhai;M. Haraguchi;Yoshiaki Okubo;E. Tomita
This paper discusses a complete and efficient algorithm for enumerating densely connected-Plexes in networks. A-Plex is a kind of pseudo-clique which imposes a disconnection upper bound (DUB) involving a parameterkfor each constituent vertex. However, because the parameter value is usually set independently of the sizes of the targeted pseudo-cliques, we often obtain-Plexes that are not densely connected. To overcome this drawback, we introduce another constraint, the connection lower bound (CLB), which involves a parameterj. Using the CLB, we can enjoy monotonicj-core operations and can design an efficient depth-first algorithm, which can exclude both search branches that generate duplicate search nodes and “hopeless” nodes that yield no targets satisfying both DUB and CLB. Our experimental results show that the algorithm can be a useful tool for detecting densely connected pseudo-cliques in large networks, including an example with over 800, 000 vertices.
