Maximum Clique Algorithm and Library


Download Parallel Maximum Clique Library


Download PMC »


Social, Biological, and Information Networks

Graph |V| |E| |T| dmax davg κ Tmax Tavg K ω sec heu heu sec
diseasome 516 1.2k 4.1k 50 4 0.43 152 7.9 11 11 0.01 11 0.01
yeast 1.5k 1.9k 618 56 2 0.05 18 0.4 6 6 0.01 6 0.01
celegans 453 2.0k 9.9k 237 8 0.12 870 22 11 9 0.01 9 0.01
dmela 7.4k 26k 8.7k 190 6 0.01 225 1.2 12 7 0.06 7 0.01
netscience 379 914 2.8k 34 4 0.43 75 7.3 9 9 0.01 9 0.01
GrQc 4.2k 13k 143k 81 6 0.63 1.2k 34 44 44 0.01 44 0.01
CondMat 21k 91k 513k 279 8 0.26 1.6k 24 26 26 0.01 26 0.01
HepPh 11k 118k 10M 491 20 0.66 40k 899 239 239 0.01 239 0.01
AstroPh 18k 197k 4.1M 504 22 0.32 11k 226 57 57 0.01 57 0.01
dblp2010 226k 716k 4.8M 238 6 0.38 5.9k 21 75 75 0.05 75 0.05
citeseer 227k 814k 8.1M 1.4k 7 0.46 5.4k 36 87 87 0.06 87 0.06
MathSciNet 333k 821k 1.7M 496 4 0.14 1.6k 5.2 25 25 0.08 25 0.08
dblp2012 317k 1.0M 6.7M 343 6 0.31 8.3k 21 114 114 0.05 114 0.05
hollywood2009 1.1M 56M 15B 11k 105 0.31 4.0M 14k 2209 2209 1.69 2209 1.69
enrononly 143 623 2.7k 42 8 0.36 125 19 10 8 0.01 8 0.01
infecthyper 113 2.2k 51k 98 38 0.5 1.7k 448 29 15 0.01 15 0.01
infectdublin 410 2.8k 21k 50 13 0.44 280 52 18 16 0.01 16 0.01
emailuniv 1.1k 5.5k 16k 71 9 0.17 261 14 12 12 0.01 12 0.01
fbmessages 1.3k 6.5k 7.5k 112 10 0.04 242 5.9 12 5 0.01 5 0.01
reality 6.8k 7.7k 1.2k 261 2 0 52 0.2 6 5 0.05 5 0.01
emailEU 32k 54k 147k 623 3 0.03 1.6k 4.5 23 12 0.02 12 0.01
enronlarge 34k 181k 2.2M 1.4k 10 0.09 18k 65 44 20 0.03 20 0.01
wikiTalk 92k 361k 2.5M 1.2k 7 0.05 18k 27 59 15 0.09 14 0.02
roadNetPA 1.1M 1.5M 201k 9 2 0.06 8 0.2 4 3 0.5 3 0.21
roadNetCA 2.0M 2.8M 361k 12 2 0.06 7 0.2 4 4 0.25 4 0.25
retweet 96 117 36 17 2 0.07 6 0.4 4 4 0.01 4 0.01
twittercopen 761 1.0k 447 37 2 0.06 27 0.6 5 4 0.01 4 0.01
retweetcrawl 1.1M 2.3M 526k 5.1k 4 0 1.6k 0.5 19 13 0.58 13 0.23
wikiVote 889 2.9k 6.4k 102 6 0.13 251 7.2 10 7 0.01 7 0.01
epinions 27k 100k 479k 443 7 0.09 5.2k 18 33 16 0.02 16 0.01
brightkite 57k 213k 1.5M 1.1k 7 0.11 12k 26 53 37 0.05 37 0.01
slashdot 70k 359k 1.2M 2.5k 10 0.03 13k 17 54 26 0.06 25 0.02
twitterfollow 405k 713k 89k 626 3 0 1.7k 0.2 29 6 0.23 6 0.05
gowalla 197k 950k 6.8M 15k 9 0.02 94k 35 52 29 0.2 29 0.05
youtube 496k 1.9M 7.3M 25k 7 0.01 151k 15 50 16 0.55 14 0.18
youtubesnap 1.1M 3.0M 9.2M 29k 5 0.01 181k 8.1 52 17 0.84 16 0.27
flickr 514k 3.2M 176M 4.4k 12 0.15 525k 343 310 58 5.2 45 0.22
livejournal 4.0M 28M 251M 2.7k 13 0.14 80k 62 214 214 2.98 214 2.98
orkut 3.0M 106M 1.6B 27k 70 0.04 1.3M 525 231 47 48.49 44 14.39
friendster 66M 1.8B 13B 5.2k 55 0.02 158k 191 304 129 1205.47 129 548.04
CMU 6.6k 250k 6.9M 840 75 0.19 24k 1.0k 70 45 0.09 45 0.01
MIT 6.4k 251k 7.1M 708 78 0.18 28k 1.1k 73 33 0.1 32 0.01
UCSB37 15k 482k 9.2M 810 64 0.16 16k 619 66 53 0.03 52 0.01
Duke14 9.9k 506k 15M 1.9k 102 0.17 42k 1.6k 86 34 0.19 32 0.02
Stanford3 12k 568k 18M 1.2k 98 0.16 33k 1.5k 92 51 0.09 51 0.02
UConn 17k 605k 10M 1.7k 70 0.13 22k 596 66 50 0.07 49 0.02
UCLA 20k 748k 15M 1.2k 73 0.14 18k 750 66 51 0.1 49 0.03
OR 63k 817k 11M 1.1k 25 0.15 19k 166 53 30 0.09 29 0.03
Wisconsin87 24k 836k 15M 3.5k 70 0.12 47k 612 61 37 0.17 36 0.04
Berkeley13 23k 852k 16M 3.4k 74 0.11 70k 703 65 42 0.16 42 0.04
UIllinois 31k 1.3M 28M 4.6k 82 0.14 66k 911 86 57 0.18 56 0.05
Indiana 30k 1.3M 28M 1.4k 87 0.14 37k 948 77 48 0.21 46 0.06
Penn94 42k 1.4M 22M 4.4k 65 0.1 68k 521 63 44 0.24 43 0.06
UF 35k 1.5M 36M 8.2k 83 0.12 159k 1.0k 84 55 0.28 51 0.07
Texas84 36k 1.6M 34M 6.3k 87 0.1 141k 922 82 51 0.33 49 0.08
Banon 2.9M 21M 156M 4.4k 14 0.05 37k 53 64 24 5.52 23 2.1
Aanon 3.1M 24M 167M 4.9k 15 0.05 50k 54 75 25 6.3 23 2.56
uciuni 59M 92M 19M 5.0k 3 0 7.8k 0.3 17 6 33.86 6 18.49
routersrf 2.1k 6.6k 31k 109 6 0.23 588 15 16 16 0.01 16 0.01
WHOIS 7.5k 57k 2.3M 1.1k 15 0.31 22k 314 89 58 0.09 55 0.01
internetas 40k 85k 190k 3.4k 4 0.01 8.5k 4.7 24 16 0.05 16 0.01
p2pgnutella 63k 148k 6.1k 95 4 0 17 0.1 7 4 0.05 4 0.01
RLcaida 191k 608k 1.4M 1.1k 6 0.06 6.0k 7.1 33 17 0.13 17 0.05
asskitter 1.7M 11M 86M 35k 13 0.01 565k 51 112 67 1.2 66 0.67
polblogs 643 2.3k 9.0k 165 7 0.16 392 14 13 9 0.01 9 0.01
google 1.3k 2.8k 15k 59 4 0.53 189 12 18 18 0.01 18 0.01
edu 3.0k 6.5k 30k 104 4 0.27 523 10 30 30 0.01 30 0.01
BerkStan 12k 20k 31k 59 3 0.28 384 2.5 29 29 0.01 29 0.01
webbase2001 16k 26k 63k 1.7k 3 0.02 1.4k 3.9 33 33 0.01 33 0.01
spam 4.8k 37k 387k 477 15 0.15 6.3k 81 36 20 0.04 20 0.01
indochina2004 11k 48k 630k 199 8 0.57 1.5k 56 50 50 0.01 50 0.01
sk2005 121k 334k 3.0M 590 5 0.47 3.5k 24 82 82 0.02 82 0.02
arabic2005 164k 1.7M 65M 1.1k 21 0.95 5.9k 397 102 102 0.03 102 0.03
wikipedia2009 1.9M 4.5M 6.7M 2.6k 4 0.05 12k 3.6 67 31 1.16 31 0.69
it2004 509k 7.2M 1.0B 469 28 0.95 93k 2.0k 432 432 0.12 432 0.12
uk2005 130k 12M 2.5B 850 181 1 124k 19k 500 500 0.06 500 0.06

Temporal Strongly Connected Components

Graph |V| |E| |T| dmax davg κ Tmax Tavg K ω sec heu heu sec
infecthyper 113 6.2k 671k 112 110 0.99 6.1k 5.9k 106 106 0.01 106 0.01
enrononly 151 9.8k 1.3M 145 130 0.96 9.7k 8.4k 120 120 0.01 120 0.01
retweet 18k 66k 11M 551 7 0.63 52k 592 175 166 0.02 165 0.01
fbforum 897 71k 22M 435 158 0.87 70k 24k 273 266 0.02 266 0.02
infectdublin 11k 176k 6.9M 219 32 0.74 9.1k 633 84 84 0.01 84 0.01
twittercopen 8.6k 474k 291M 1.5k 110 0.7 469k 34k 583 581 0.22 581 0.12
fbmessages 1.9k 532k 414M 1.3k 560 0.82 531k 218k 707 707 0.05 707 0.05
reality 6.8k 4.7M 6.6B 6.1k 1.4k 0.49 4.7M 972k 1236 1236 0.19 1236 0.19
mittromney 7.8k 108 198 25 0.1 0.29 38 0 5 5 0.01 5 0.01
bahrain 4.7k 129 555 20 0.1 0.53 66 0.1 8 8 0.01 8 0.01
barackobama 9.6k 226 1.5k 43 0.1 0.43 153 0.2 10 10 0.01 10 0.01
alwefaq 4.2k 355 4.4k 39 0.1 0.62 280 1.1 16 16 0.01 16 0.01
justinbieber 9.4k 442 6.8k 42 0.1 0.63 375 0.7 17 17 0.01 17 0.01
occupywallstn 3.6k 931 14k 112 0.1 0.39 809 4 18 18 0.01 18 0.01
gmanews 8.3k 1.1k 20k 114 0.1 0.45 950 2.5 22 22 0.01 22 0.01
lolgop 9.7k 4.5k 175k 249 0.1 0.49 4.2k 18 42 42 0.01 42 0.01

DIMACS

Graph |V| |E| |T| dmax davg κ Tmax Tavg K ω sec heu heu sec
DSJC1000-5 1k 250k 62M 551 499 0.5 76k 62k 460 15 22.4 13 0.01
MANN-a27 378 71k 26M 374 373 0.99 69k 69k 365 126 0.44 125 0.01
MANN-a45 1.0k 533k 547M 1.0k 1.0k 1 529k 528k 1013 345 189.49 340 0.13
brock200-1 200 15k 1.6M 165 148 0.75 10k 8.2k 135 21 0.14 16 0.01
brock400-3 400 60k 13M 322 298 0.75 39k 33k 279 31 78.18 20 0.01
brock400-1 400 60k 13M 320 298 0.75 38k 33k 278 27 105.82 19 0.01
brock400-4 400 60k 13M 326 298 0.75 40k 33k 278 33 11.91 20 0.01
brock400-2 400 60k 13M 328 298 0.75 40k 33k 279 29 35.2 21 0.01
brock800-3 800 207k 70M 558 518 0.65 101k 87k 484 25 517.39 17 0.01
brock800-1 800 208k 70M 560 518 0.65 101k 87k 488 23 785.4 17 0.01
brock800-4 800 208k 70M 565 519 0.65 103k 87k 486 26 251.93 17 0.01
brock800-2 800 208k 70M 566 520 0.65 104k 88k 487 24 583.42 17 0.01
keller5 776 226k 98M 638 582 0.75 151k 126k 561 27 3362.05 23 0.01
p-hat300-3 300 33k 5.7M 267 222 0.76 27k 19k 181 36 0.68 27 0.01
p-hat500-2 500 63k 10M 389 251 0.58 41k 20k 171 36 0.12 25 0.01
p-hat500-3 500 94k 27M 452 375 0.77 77k 5.4k 304 50 41.07 38 0.01
p-hat700-2 700 122k 27M 539 347 0.58 79k 38k 236 44 0.77 36 0.01
p-hat1000-1 1k 122k 9.2M 408 244 0.28 23k 9.2k 164 10 0.06 9 0.01
p-hat1000-2 1k 245k 74M 766 489 0.57 158k 7.4k 328 46 40.65 35 0.01
p-hat1500-1 1.5k 285k 34M 614 379 0.29 53k 23k 253 12 0.33 10 0.01
sanr200-0-9 200 18k 2.9M 189 178 0.9 16k 14k 167 42 16.08 36 0.01
san200-0-9-2 200 18k 2.9M 188 179 0.9 16k 14k 170 60 0.01 40 0.01
san200-0-9-3 200 18k 2.9M 187 179 0.9 16k 14k 170 44 1.29 33 0.01
sanr400-0-5 400 40k 4.0M 233 199 0.5 14k 10k 178 13 0.07 11 0.01
san400-0-7-1 400 56k 11M 301 279 0.73 32k 28k 262 40 0.02 31 0.01
san400-0-7-2 400 56k 11M 304 279 0.73 33k 282 260 30 0.04 17 0.01
san400-0-7-3 400 56k 11M 307 279 0.72 34k 28k 254 22 0.58 16 0.01
sanr400-0-7 400 56k 11M 310 279 0.7 34k 27k 259 21 22.9 18 0.01
san400-0-9-1 400 72k 23M 374 359 0.9 63k 58k 345 100 0.31 58 0.01
san1000 1k 251k 86M 550 501 0.69 101k 86k 465 15 0.07 9 0.01
Graph |V| |E| |T| dmax davg κ Tmax Tavg K ω sec heu heu sec
DSJC500-5 500 63k 7.9M 286 250 0.5 21k 16k 226 13 0.3 12 0.01
DSJC1000-5 1k 250k 62M 551 499 0.5 76k 62k 460 15 25.66 13 0.01
MANN-a9 45 918 34k 41 40 0.92 757 75 41 16 0.01 16 0.01
brock200-2 200 9.9k 480k 114 98 0.49 3.2k 2.4k 85 12 0.01 9 0.01
brock200-3 200 12k 873k 134 120 0.61 5.4k 4.4k 106 15 0.01 12 0.01
brock200-4 200 13k 1.1M 147 130 0.66 7.0k 5.6k 118 17 0.02 14 0.01
brock800-3 800 207k 70M 558 518 0.65 101k 87k 484 25 523.79 17 0.01
brock800-1 800 208k 70M 560 518 0.65 101k 87k 488 23 792.29 17 0.01
brock800-2 800 208k 70M 566 520 0.65 104k 88k 487 24 606.26 17 0.01
c-fat200-1 200 1.5k 16k 17 15 0.73 100 81 15 12 0.01 12 0.01
c-fat200-2 200 3.2k 77k 34 32 0.76 429 384 33 24 0.01 24 0.01
c-fat500-1 500 4.5k 56k 20 17 0.74 141 111 18 14 0.01 14 0.01
c-fat200-5 200 8.5k 546k 86 84 0.77 2.8k 2.7k 84 58 0.01 58 0.01
c-fat500-2 500 9.1k 247k 38 36 0.76 534 494 36 26 0.03 26 0.01
c-fat500-5 500 23k 1.6M 95 92 0.77 3.4k 328 93 64 0.02 64 0.01
c-fat500-10 500 47k 6.7M 188 186 0.77 14k 13k 186 126 0.05 126 0.03
gen200-p0-9-44 200 18k 2.9M 190 179 0.9 16k 1.4k 168 44 0.71 35 0.01
gen200-p0-9-55 200 18k 2.9M 190 179 0.9 16k 14k 167 55 0.03 36 0.01
hamming6-4 64 704 2.9k 22 22 0.19 45 45 23 4 0.01 4 0.01
hamming6-2 64 1.8k 92k 57 57 0.9 1.4k 1.4k 58 32 0.01 32 0.01
hamming8-4 256 21k 2.0M 163 163 0.6 7.9k 7.9k 164 16 0.02 16 0.01
hamming8-2 256 32k 7.5M 247 247 0.97 29k 29k 248 128 0.01 128 0.01
hamming10-2 1.0k 519k 520M 1.0k 1.0k 0.99 508k 508k 1014 512 0.36 512 0.19
johnson8-2-4 28 210 1.3k 15 15 0.43 45 45 16 4 0.01 4 0.01
johnson8-4-4 70 1.9k 72k 53 53 0.74 1.0k 1.0k 54 14 0.01 14 0.01
johnson16-2-4 120 5.5k 360k 91 91 0.73 3.0k 3.0k 92 8 0.04 8 0.01
keller4 171 9.4k 650k 124 110 0.63 4.8k 38 103 11 0.01 11 0.01
keller5 776 226k 98M 638 582 0.75 151k 126k 561 27 3281.7 23 0.01
sanr200-0-7 200 14k 1.3M 161 138 0.7 8.9k 6.7k 125 18 0.06 15 0.01
san200-0-7-1 200 14k 1.4M 155 139 0.73 8.6k 7.0k 126 30 0.01 17 0.01
san200-0-7-2 200 14k 1.5M 164 139 0.74 9.8k 7.3k 123 18 0.02 13 0.02
san200-0-9-1 200 18k 2.9M 191 179 0.9 16k 14k 163 70 0.01 46 0.01
san400-0-5-1 400 40k 5.2M 225 199 0.66 16k 13k 184 13 0.01 8 0.01