Title :
A Parallel Algorithm for Enumerating All Maximal Cliques in Complex Network
Author :
Du, Nan ; Wu, Bin ; Xu, Liutong ; Wang, Bai ; Pei, Xin
Author_Institution :
Sch. of Comput. Sci. & Technol., Beijing Univ. of Posts & Telecommun.
Abstract :
Efficient enumeration of all maximal cliques in a given graph has many applications in graph theory, data mining and bio informatics. However, the exponentially increasing computation time of this problem confines the scale of the graph. Meanwhile, recent researches show that many networks in our world are complex networks involving massive data. To solve the maximal clique problem in the real-world scenarios, this paper presents a parallel algorithm Peamc (parallel enumeration of all maximal cliques) which exploits several new and effective techniques to enumerate all maximal cliques in a complex network. Furthermore, we provide a performance study on a true-life call graph with up to 2,423,807 vertices and 5,317,183 edges. The experimental results show that Peamc can find all the maximal cliques in a complex network with high efficiency and scalability
Keywords :
computational complexity; graph theory; parallel algorithms; complex network; graph-based link mining; maximal clique problem; parallel algorithm; Application software; Bioinformatics; Complex networks; Computer science; Data mining; Graph theory; Intelligent networks; Laboratories; Parallel algorithms; Telecommunication computing;
Conference_Titel :
Data Mining Workshops, 2006. ICDM Workshops 2006. Sixth IEEE International Conference on
Conference_Location :
Hong Kong
Print_ISBN :
0-7695-2702-7
DOI :
10.1109/ICDMW.2006.17