DocumentCode :
3259955
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.
fYear :
2006
fDate :
Dec. 2006
Firstpage :
320
Lastpage :
324
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;
fLanguage :
English
Publisher :
ieee
Conference_Titel :
Data Mining Workshops, 2006. ICDM Workshops 2006. Sixth IEEE International Conference on
Conference_Location :
Hong Kong
Print_ISBN :
0-7695-2702-7
Type :
conf
DOI :
10.1109/ICDMW.2006.17
Filename :
4063647
Link To Document :
بازگشت