Maximum clique for massive sparse graphs

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 is the new application of BITSCAN and GRAPH libs available in biicode to solve the maximum clique problem.

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.

CategoryName|V||E|dmaxdavgwBBMCSPPMCPMC/ BBMCSP
Affiliationaff-orkut-user2groups873085732703742031826874.9261377.2329042.321.09
Infrastructureinf-germany_osm1154884512369181132.143>0.0012.882878.92
Infrastructureinf-great-britain_osm7733822815651782.113>0.0011.941939.6
Infrastructureinf-italy_osm6686493701397892.13>0.0011.541540.19
Scientific computingadaptive6815744136243204421.156.946.03
Scientific computingchannel-500x100x100-b0504802000426813721817.7845.2221.154.06
Scientific computingdelaunay_n2241943041258286923641.587.44.7
Scientific computingdelaunay_n2383886082516578428643.2914.874.52
Scientific computingdelaunay_n24167772165033160126646.8429.384.29
Scientific computinghugebubbles-0002021198119317901793323.6234.059.4
Scientific computinghugetrace-00000458848468791333320.695.27.54
Scientific computinghugetrace-0001012057441180821793321.8314.828.09
Scientific computinghugetric-00000582455487335233320.886.327.18
Scientific computinghugetric-00010659276598858543321.078.17.56
Scientific computinghugetric-000207122792106807773321.199.037.6
Scientific computingventuriLevel3402681980542376430.573.586.24
Socialsoc-friendster656083661806067135521455.061291027.257680.927.48
Socialsoc-livejournal075204176487097731501718.723580.016.34862.17
Socialsoc-livejournal-user-groups7489073112307315105374929.999717.733624550.5
Socialsoc-ljournal-20085363260495142711943218.4640007.227051.04
Socialsoc-orkut-dir30724411171850833331376.285155.78228.944.1
Socialsoc-sinaweibo586558492613210332784898.914494.84260527.47
Social (facebook)socfb-A-anon309716523667394491515.28259.0121.752.41
Social (facebook)socfb-konect.edges460096407204081449603.1360.6421.9234.36
Social (facebook)socfb-uci-uni587907829220819549603.1460.9233.0936.11
Web linksweb-ClueWeb09-50m4281366124465340583084772.09564.77635.72133.15
Web linksweb-indochina-2004-all741486615098481925642540.7268480.281137.244038.84
Web linksweb-it-2004-all412913181027474947132674449.7732220.19162.32832.67
Web linksweb-wikipedia_link_de39301096871406443773234.973390.0110.331587.48
Web linksweb-wikipedia_link_fr5115915104591689127464240.893320.1223.8206.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