{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,7,30]],"date-time":"2025-07-30T11:46:00Z","timestamp":1753875960587,"version":"3.41.2"},"reference-count":24,"publisher":"Oxford University Press (OUP)","issue":"2","license":[{"start":{"date-parts":[[2020,4,1]],"date-time":"2020-04-01T00:00:00Z","timestamp":1585699200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/academic.oup.com\/journals\/pages\/open_access\/funder_policies\/chorus\/standard_publication_model"}],"funder":[{"name":"Vedeck\u00e1 grantov\u00e1 agent\u00fara M\u0160VVa\u0160 a SAV","award":["1\/0039\/17"],"award-info":[{"award-number":["1\/0039\/17"]}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2020,4,1]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>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.<\/jats:p>","DOI":"10.1093\/comnet\/cnaa011","type":"journal-article","created":{"date-parts":[[2020,2,25]],"date-time":"2020-02-25T20:15:34Z","timestamp":1582661734000},"source":"Crossref","is-referenced-by-count":0,"title":["About clique number estimates and exact enumeration in scale-free networks"],"prefix":"10.1093","volume":"8","author":[{"given":"Andrej","family":"Jursa","sequence":"first","affiliation":[{"name":"Department of Applied Informatics, Faculty of Mathematics, Physics and Informatics, Comenius University, Mlynsk\u00e1 dolina F1, 842 48 Bratislava, Slovakia"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"M\u00e1ria","family":"Marko\u0161ov\u00e1","sequence":"first","affiliation":[{"name":"Department of Applied Informatics, Faculty of Mathematics, Physics and Informatics, Comenius University, Mlynsk\u00e1 dolina F1, 842 48 Bratislava, Slovakia"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Boris","family":"Rudolf","sequence":"first","affiliation":[{"name":"Institute of Computer Science and Mathematics, Faculty of Electrical Engineering and Information Technology, Slovak University of Technology, Ilkovi\u010dova 3, 812 19 Bratislava, Slovakia"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"286","published-online":{"date-parts":[[2020,5,11]]},"reference":[{"key":"2020061312231821000_B1","doi-asserted-by":"crossref","first-page":"575","DOI":"10.1145\/362342.362367","article-title":"Algorithm 457: finding all cliques of an undirected graph","volume":"16","author":"Bron,","year":"1973","journal-title":"Commun. ACM"},{"key":"2020061312231821000_B2","doi-asserted-by":"crossref","first-page":"375","DOI":"10.1016\/0167-6377(90)90057-C","article-title":"An exact algorithm for the maximum clique problem","volume":"9","author":"Carraghan,","year":"1990","journal-title":"Oper. Res. Lett."},{"key":"2020061312231821000_B3","doi-asserted-by":"crossref","first-page":"197","DOI":"10.1016\/S0166-218X(01)00290-6","article-title":"A fast algorithm for the maximum clique problem","volume":"120","author":"\u00d6sterg\u00e5rd,","year":"2002","journal-title":"Discrete Appl. Math."},{"key":"2020061312231821000_B4","doi-asserted-by":"crossref","first-page":"610","DOI":"10.1007\/s004530010074","article-title":"Reactive local search for the maximum clique problem","volume":"29","author":"Battiti,","year":"2001","journal-title":"Algorithmica"},{"key":"2020061312231821000_B5","doi-asserted-by":"crossref","first-page":"503","DOI":"10.1016\/j.ipl.2005.05.010","article-title":"An effective local search for the maximum clique problem","volume":"95","author":"Katayama,","year":"2005","journal-title":"Inf. Process. Lett."},{"key":"2020061312231821000_B6","doi-asserted-by":"crossref","first-page":"156","DOI":"10.1007\/978-3-319-03536-9_13","volume-title":"Algorithms and Models for the Web Graph","author":"Pattabiraman,","year":"2013","edition":"2nd edn."},{"key":"2020061312231821000_B7","volume-title":"Introduction to Graph Theory","author":"West,","year":"2000","edition":"2nd edn."},{"key":"2020061312231821000_B8","article-title":"An o(m) algorithm for cores decomposition of networks","author":"Batagelj,","year":"2003","journal-title":"CoRR"},{"key":"2020061312231821000_B9","doi-asserted-by":"crossref","first-page":"1082","DOI":"10.4153\/CJM-1970-125-1","article-title":"$k$-Degenerate graphs","volume":"22","author":"Lick,","year":"1970","journal-title":"Can. J. Math."},{"key":"2020061312231821000_B10","doi-asserted-by":"crossref","first-page":"417","DOI":"10.1145\/2402.322385","article-title":"Smallest-last ordering and clustering and graph coloring algorithms","volume":"30","author":"Matula,","year":"1983","journal-title":"J. ACM"},{"key":"2020061312231821000_B11","doi-asserted-by":"crossref","first-page":"509","DOI":"10.1126\/science.286.5439.509","article-title":"Emergence of scaling in random networks","volume":"286","author":"Barab\u00e1si,","year":"1999","journal-title":"Science"},{"volume-title":"Network Science","year":"2016","author":"Barab\u00e1si,","key":"2020061312231821000_B12"},{"key":"2020061312231821000_B13","first-page":"451","article-title":"Analysis of Facebook social network","author":"Akhtar,","year":"2013","journal-title":"5th International Conference and Computational Intelligence and Communication Networks., Mathura, India. IEEE"},{"key":"2020061312231821000_B14","article-title":"Coauthorship and citation networks for statisticians","author":"Ji,","year":"2014","journal-title":"CoRR"},{"key":"2020061312231821000_B15","doi-asserted-by":"crossref","first-page":"e41","DOI":"10.1002\/itl2.41","article-title":"Emerging topics in internet technology: a complex networks approach","volume":"1","author":"Khan,","year":"2018","journal-title":"Internet Technol. Lett."},{"key":"2020061312231821000_B16","doi-asserted-by":"crossref","first-page":"611","DOI":"10.1145\/1150402.1150476","article-title":"Structure and evolution of online social networks","volume-title":"Proceedings of the 12th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining","author":"Kumar,","year":"2006"},{"key":"2020061312231821000_B17","doi-asserted-by":"crossref","first-page":"301","DOI":"10.3389\/fnagi.2014.00301","article-title":"The age-related posterior-anterior shift as revealed by voxelwise analysis of functional brain networks","volume":"6","author":"Mccarthy,","year":"2014","journal-title":"Front. Aging Neurosci."},{"key":"2020061312231821000_B18","doi-asserted-by":"crossref","first-page":"S10","DOI":"10.1186\/1471-2105-15-S7-S10","article-title":"Reconstruction of gene co-expression network from microarray data using local expression patterns","volume":"15","author":"Roy,","year":"2014","journal-title":"BMC Bioinformatics"},{"key":"2020061312231821000_B19","doi-asserted-by":"crossref","first-page":"205","DOI":"10.1140\/epjb\/e2004-00038-8","article-title":"Cut-offs and finite size effects in scale-free networks","volume":"38","author":"Bogu\u00f1\u00e1,","year":"2004","journal-title":"Eur. Phys. J. B"},{"journal-title":"Personal communication","year":"2018","author":"Bogu\u00f1\u00e1,","key":"2020061312231821000_B20"},{"key":"2020061312231821000_B21","doi-asserted-by":"crossref","first-page":"20","DOI":"10.1201\/b19731","volume-title":"Graphs & Digraphs","author":"Chartrand,","year":"2015","edition":"6th edn."},{"key":"2020061312231821000_B22","doi-asserted-by":"crossref","first-page":"046103","DOI":"10.1103\/PhysRevE.81.046103","article-title":"Asymptotic properties of degree-correlated scale-free networks","volume":"81","author":"Menche,","year":"2010","journal-title":"Phys. Rev. E"},{"journal-title":"SNAP datasets: Stanford large network dataset collection","year":"2014","author":"Leskovec,","key":"2020061312231821000_B23"},{"key":"2020061312231821000_B24","doi-asserted-by":"crossref","DOI":"10.1609\/aaai.v29i1.9277","article-title":"The network data repository with interactive graph analytics and visualization","author":"Rossi,","year":"2015","journal-title":"Proceedings of the Twenty-Ninth AAAI Conference on Artificial Intelligence"}],"container-title":["Journal of Complex Networks"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/academic.oup.com\/comnet\/article-pdf\/8\/2\/cnaa011\/33386552\/cnaa011.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"http:\/\/academic.oup.com\/comnet\/article-pdf\/8\/2\/cnaa011\/33386552\/cnaa011.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,10,16]],"date-time":"2022-10-16T14:26:51Z","timestamp":1665930411000},"score":1,"resource":{"primary":{"URL":"https:\/\/academic.oup.com\/comnet\/article\/doi\/10.1093\/comnet\/cnaa011\/5835570"}},"subtitle":[],"editor":[{"given":"Matjaz","family":"Perc","sequence":"additional","affiliation":[],"role":[{"role":"editor","vocabulary":"crossref"}]}],"short-title":[],"issued":{"date-parts":[[2020,4,1]]},"references-count":24,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2020,4,1]]}},"URL":"https:\/\/doi.org\/10.1093\/comnet\/cnaa011","relation":{},"ISSN":["2051-1310","2051-1329"],"issn-type":[{"type":"print","value":"2051-1310"},{"type":"electronic","value":"2051-1329"}],"subject":[],"published-other":{"date-parts":[[2020,4]]},"published":{"date-parts":[[2020,4,1]]},"article-number":"cnaa011"}}