In a previous post we introduced the maximum clique problem (MCP) and reported performance of the efficient bit-parallel exact solver BBMC, implemented with BITSCAN and GRAPH libraries available in the Biicode repositories pablodev/bitscan and pablodev/graph respectively. BBMC is concerned with small and middle size graphs.

Also very challenging are real networks that arise from different fields such as social networks, infrastructure networks, scientific networks and so on. These graphs tend to have many thousands—even millions— of nodes but are usually very sparse —the Network Data Repository hosts more than 500 of such graphs—. An open problem is finding the clique number (the cardinality of a maximum clique) of such networks to get an insight into their structure. Unfortunately the problem is NP-hard and no polynomial algorithm is expected to be found; tailoring and exact solver for this task is as yet an open question [1].

## BBMCSP can quickly solve the maximum clique problem of sparse networks

Only just some months ago it has been possible to tailor BBMC for real networks. The main problem in successful exact solvers for the middle size case is that the majority of them encode the adjacency matrix in full, whereas real graphs require some form of compression—i.e. typically a list of edges—. The new BBMCSP algorithm uses the *sparse_graph* type available in GRAPH to compress the adjacency matrix, while still taking advantage of fast bit string operations between vertex sets.

As in the previous post we will not go into implementation details here —see the pablodev/copt block to look at some source code—but report performance of BBMCSP over a number of massive networks available in the Network Data Repository. Experiments have been run on a Linux workstation with an Intel(R) Xeon(R) CPU E5-2690 v2 multi-core processor and 128GB of main memory, using always a single-core. The table reports comparison results against previous best PMC algorithm over 30 massive graphs. In the table each row is a network. Header *dmax* and *davg *stand for maximum graph degree and average graph degree respectively; w is the cardinality of the maximum clique, *BBMCSP* and *PMC* gives search time performance in seconds for both algorithms and *PMC/BBMCSP *reports the time ratio.

Category | Name | |V| | |E| | dmax | davg | w | BBMCSP | PMC | PMC/ BBMCSP |
---|---|---|---|---|---|---|---|---|---|

Affiliation | aff-orkut-user2groups | 8730857 | 327037420 | 318268 | 74.92 | 6 | 1377.23 | 29042.3 | 21.09 |

Infrastructure | inf-germany_osm | 11548845 | 12369181 | 13 | 2.14 | 3 | >0.001 | 2.88 | 2878.92 |

Infrastructure | inf-great-britain_osm | 7733822 | 8156517 | 8 | 2.11 | 3 | >0.001 | 1.94 | 1939.6 |

Infrastructure | inf-italy_osm | 6686493 | 7013978 | 9 | 2.1 | 3 | >0.001 | 1.54 | 1540.19 |

Scientific computing | adaptive | 6815744 | 13624320 | 4 | 4 | 2 | 1.15 | 6.94 | 6.03 |

Scientific computing | channel-500x100x100-b050 | 4802000 | 42681372 | 18 | 17.78 | 4 | 5.22 | 21.15 | 4.06 |

Scientific computing | delaunay_n22 | 4194304 | 12582869 | 23 | 6 | 4 | 1.58 | 7.4 | 4.7 |

Scientific computing | delaunay_n23 | 8388608 | 25165784 | 28 | 6 | 4 | 3.29 | 14.87 | 4.52 |

Scientific computing | delaunay_n24 | 16777216 | 50331601 | 26 | 6 | 4 | 6.84 | 29.38 | 4.29 |

Scientific computing | hugebubbles-00020 | 21198119 | 31790179 | 3 | 3 | 2 | 3.62 | 34.05 | 9.4 |

Scientific computing | hugetrace-00000 | 4588484 | 6879133 | 3 | 3 | 2 | 0.69 | 5.2 | 7.54 |

Scientific computing | hugetrace-00010 | 12057441 | 18082179 | 3 | 3 | 2 | 1.83 | 14.82 | 8.09 |

Scientific computing | hugetric-00000 | 5824554 | 8733523 | 3 | 3 | 2 | 0.88 | 6.32 | 7.18 |

Scientific computing | hugetric-00010 | 6592765 | 9885854 | 3 | 3 | 2 | 1.07 | 8.1 | 7.56 |

Scientific computing | hugetric-00020 | 7122792 | 10680777 | 3 | 3 | 2 | 1.19 | 9.03 | 7.6 |

Scientific computing | venturiLevel3 | 4026819 | 8054237 | 6 | 4 | 3 | 0.57 | 3.58 | 6.24 |

Social | soc-friendster | 65608366 | 1806067135 | 5214 | 55.06 | 129 | 1027.25 | 7680.92 | 7.48 |

Social | soc-livejournal07 | 5204176 | 48709773 | 15017 | 18.72 | 358 | 0.01 | 6.34 | 862.17 |

Social | soc-livejournal-user-groups | 7489073 | 112307315 | 1053749 | 29.99 | 9 | 717.73 | 36245 | 50.5 |

Social | soc-ljournal-2008 | 5363260 | 49514271 | 19432 | 18.46 | 400 | 0 | 7.22 | 7051.04 |

Social | soc-orkut-dir | 3072441 | 117185083 | 33313 | 76.28 | 51 | 55.78 | 228.94 | 4.1 |

Social | soc-sinaweibo | 58655849 | 261321033 | 278489 | 8.91 | 44 | 94.84 | 2605 | 27.47 |

Social (facebook) | socfb-A-anon | 3097165 | 23667394 | 4915 | 15.28 | 25 | 9.01 | 21.75 | 2.41 |

Social (facebook) | socfb-konect.edges | 46009640 | 72040814 | 4960 | 3.13 | 6 | 0.64 | 21.92 | 34.36 |

Social (facebook) | socfb-uci-uni | 58790782 | 92208195 | 4960 | 3.14 | 6 | 0.92 | 33.09 | 36.11 |

Web links | web-ClueWeb09-50m | 428136612 | 446534058 | 308477 | 2.09 | 56 | 4.77 | 635.72 | 133.15 |

Web links | web-indochina-2004-all | 7414866 | 150984819 | 256425 | 40.72 | 6848 | 0.28 | 1137.24 | 4038.84 |

Web links | web-it-2004-all | 41291318 | 1027474947 | 1326744 | 49.77 | 3222 | 0.19 | 162.32 | 832.67 |

Web links | web-wikipedia_link_de | 3930109 | 68714064 | 437732 | 34.97 | 339 | 0.01 | 10.33 | 1587.48 |

Web links | web-wikipedia_link_fr | 5115915 | 104591689 | 1274642 | 40.89 | 332 | 0.12 | 23.8 | 206.31 |

These and other algorithms have been tested over more than 275 real graphs. The full raw data together with a BBMCSP binary is available here. **We believe BBMCSP results are clearly best on average for a stand-alone exact solver on massive graphs**. If this is not the case, please let us know.

If we get a favorable feedback from readers interested in BBMCSP and/or in the maximum clique problem tailored for very large or massive graphs we will explain the BBMCSP algorithm in full together with implementation details concerning BITSCAN and GRAPH.

Hope you enjoy this new BITSCAN and GRAPH application and, as always, we look forward to read what you think. Just click on the sidebar button to try biicode, check our docs, forum and/or Stackoverflow tag for questions and answers or comment below to tell us your enquiries.

[1] Pardalos, P. Rebennack, S.; Experimental Algorithms. Lecture Notes in Computer Science, Volume 6049, 2010, pp 13-22.

Related Posts

Pingback: Exact maximum clique for massive real graphs - biicode Blog()

Pingback: Four short links: 10 April 2015 - O'Reilly Radar()