About clique number estimates and exact enumeration in scale-free networks. (11th May 2020)

• Record Type: Journal Article
• Authors: Jursa, Andrej; Markošová, Mária; Rudolf, Boris
• Editors: Perc, Matjaz
• Is Part Of: Journal of complex networks. Volume 8:Number 2(2020)
• Publication Date: 2020-05-11
• Subjects: clique estimates -- clique finding algorithm -- scale-free networks; Numerical analysis -- Periodicals; Computer networks -- Periodicals; Social networks -- Periodicals; 518.05
• DOI: 10.1093/comnet/cnaa011
• Languages: English
• ISSNs: 2051-1310

Abstract

Abstract: In this article, we present several analytical methods for both correlated and uncorrelated scale-free networks to obtain the clique number upper bound estimate. To test these estimates, we developed several tools to construct networks with scale-free degree distribution. To compute an exact clique number of network in short time, we also developed a clique finder algorithm. As the empirical results show, the various estimate methods gives good upper bounding for the clique numbers. Our clique finder proves to be able to solve clique number problem of arbitrary graphs in a good computation time. To show this, we applied our clique finder on benchmark graphs from various known databases.