The maximum clique problem in graph theory concerns finding the largest subset of vertices in which all vertices are connected with an edge. Computation of such subset is a well-known NP-hard problem and there exist many algorithms to solve it. For our purposes we created an algorithm specially targeted for solving this problem in scale-free networks, where many significant search improvements may be introduced. We use the general purpose algorithm developed by Östergård in 2002 as subroutine for our new algorithm. We improved the search process by initial heuristic. Firstly we compute preliminary clique size and then reduce the graph by k-core decomposition of this size. Subsequently, we employ greedy algorithm for coloring of chosen vertex as well as its neighbors. Our algorithm is able to solve maximum clique problem for arbitrary graphs, but together with these and some other, less significant pruning techniques, the overall algorithm performs exceptionally well on scale-free networks, which was tested on many real graphs as well as randomly generated graphs.
For our study of functional brain networks we needed
an algorithm to solve maximum clique problem in these
graphs to compare networks of three classes of
participants. We realize that using a general purpose algorithm
for this task may lead to very long computation times.
According to the scale-free structure of functional brain
networks we can implement several pruning techniques
to make the search process faster. Functional brain
networks we have data for are simple undirected graphs. Off
course there exists randomized or heuristic algorithms like
[
Undirected graph is combinatorial structure which we can denote as G = (V, E), where V is set of vertices and E is set of edges or pairs of vertices. We can say that two vertices are adjacent, if there is edge between them. The number of edges which are connecting vertex v with other vertices is denoted as degree k of vertex v (we are denoting this as deg(v) = k). For vertex v we can get his open set of neighbors N(v) = {u|u ∈ V ∧ (u, v) ∈ E} or close set of neighbors N[v] = N(v) ∪ { }
v .
Simple graph does not have loops from - to the same vertices, does not have multiple edges between the same pair of vertices and does not have weighted edges. Our algorithm is targeted to solve maximum clique problem for simple undirected graphs. For simple undirected graph 2 E | | . we can compute density of that graph as D = |V |(|V |−1)
A clique in simple undirected graph is an subset of vertices V ′ ⊆ V so that ∀v ∈ V ′, ∀u ∈ V ′ : u 6= v =⇒ (v, u) ∈ E. The maximum clique is largest clique in undirected simple graph. The size of maximum clique is also called clique number of graph G and can be denoted as ω(G).
Scale-free networks are simple undirected graphs whose degree distribution asymptotically follows power law. There is no specific scale in degree distribution. Fraction P(k) of vertices having degree equal to k scales for large values of k as P(k) ∼ k−γ , where γ is typically in range 2 < γ < 3. For given graph G we can compute degree distribution. It can be done by counting how many vertices in G have particular degree. We can visualize this distribution for scale-free networks in a log-log plot (it can be seen on figure 1 in part (a)).
The k-core decomposition of the graph G forms an induced subgraph H, where all vertices have the degree at least k. When we compute k-core decomposition from the scale-free network, we can remove large amount of vertices with the degree lower than k. In the diagram in (b) part of figure 1 the red area represents all vertices removed from scale-free network due to k-core decomposition. By computing new k-core decomposition each time we know new size of clique, we can reduce search space for next iteration of searching. 2
Östergård’s algorithm
The original algorithm is processing graphs vertices from the highest index to the lowest one. During this process it also maintains array called c[i], where i is the index of already processed vertex. It stores value of max in the array c[i] after vertex i and his neighborhood is processed. This algorithm is using subroutine CLIQUE for branching over neighbors of the initial vertex. To get this neighbors it is using sets defined as Si = {vi, vi+1, vi+2, . . . , v|V |}, where i is an index of starting vertex.
In algorithm 1 one can see pseudo-code of this original algorithm. At line 8 there is condition for number of vertices remaining in set U with respect of current clique size. If this condition holds, algorithm is unable to find clique with size higher than max, so it can return from subroutine. Also similar test is introduced at line 11. In this case it is testing if previous search from vertex with index i have founded clique size hight enough that with respect to current clique size algorithm can find clique higher than max. If this condition does not hold, it will return from subroutine as well.
This algorithm can be used for arbitrary simple undirected graph and it will find maximum clique size. The values of array c behaves following: c[i] = c[i + 1] if algorithm does not find new, higher, clique size, otherwise c[i] = c[i + 1] + 1. 3
Our solution is using original Östergård’s algorithm1
[
Our algorithm is split in two phases. In the first phase, which is called initialization phase, the algorithm is using heuristic function to find preliminary clique size. This process may return clique size close to maximum clique size2. The preliminary size returned by heuristic is set into variable max. When the initialization phase know this value the algorithm reduces the search space of graph by computing max-core decomposition3. At the end of this phase it computes new isomorphic graph, where all vertices are indexed again from 1 to |Vk| but also the vertex degree is raising with indexes4. The Vk ⊆ V is the set of vertices of the graphs k-core decomposition.
First step of the initialization phase is to compute preliminary clique size by heuristic function. Similar method 1Östergård’s subroutine CLIQUE is used in our algorithm.
2But there is also chance for returning very small size compared to maximum clique size in graph.
3It is k-core decomposition of graph, where k = max.
4Vertex with index 1 have minimum degree in a graph and vertex with index |Vk| have maximum degree in a graph.
Algorithm 1 Östergård’s original algorithm.
Input: Simple undirected graph G.
Output: Clique number ω(G) in global variable max. 1: procedure CLIQUE(U, size) 2: if |U | = 0 then 3: if size > max then 4: max ← size 5: found ← true 6: return 7: while U 6= 0/ do 8: if size +|U | ≤ max then 9: return ⊲ Nothing better can be found. i ← min{ j|v j ∈ U } if size + c[i] ≤ max then
return ⊲ Nothing better can be found.
U ← U \ {vi} CLIQUE(U ∩ N(vi), size + 1) if found = true then
return ⊲ Higher clique size was found,
return to main loop.
17: procedure MAIN
18: max ← 0
19: for i ← |V | downto 1 do
20: found ← false
21: CLIQUE(Si ∩ N(vi), 1)
22: c[i] ← max ⊲ Store clique size for next
iteration, this is used for pruning.
was used in [
Heuristic iteration of finding clique is a greedy function which adds vertices with maximum degree to the forming clique and when there is no more vertex to be added the clique is found. Repeating this for more starting vertices this process can find clique size very close to clique number of input graph G. On the other hand the ratio between clique size of graph G and size found by the heuristic can be also close to zero in some cases.
Algorithm 2 Preliminary clique size heuristic function. Input: Simple undirected graph G.
Output: Preliminary clique size in graph G.
1: function CLIQUEHEURISTICSTARTINVER
TEX(G, i, lastMax) 2: Clique ← {vi}, Nb ← N(vi) ⊲ Initialize clique and neighbor sets. 3: while true do 4: if |Clique| +|Nb| ≤ lastMax then ⊲ Higher clique size can not be found. 5: return lastMax 6: if |Nb| = 0 then ⊲ All possible vertices are processed. 7: 8: 9:
return |Clique| j ← index of vertex w j ∈ Nb which have maximum degree
Clique ← Clique ∪ {v j}, Nb ← Nb ∩ N(v j) ⊲
Update clique and neighbor sets. 16: 10: function CLIQUEHEURISTIC(G) 11: 12: 13: 14: 15: degthreshold ← ⌊0.95 · max deg(u)|u ∈ GS ⌋ heurMax ← 0 for i ← 1 to |V | do if deg(vi) ≥ degthreshold then
max ← CLIQUEHEURISTICSTARTINVERTEX(G, i, heurMax)
return heurMax
After heuristic search is completed the algorithm knows preliminary size of the clique and it saves it to the variable max. For next phase it is necessary to compute max-core decomposition which removes possibly large amount of vertices and effectively reduces search space5. Because algorithm is processing vertices by their indices from higher to lower we run renumbering procedure on new max-core decomposition so that vertices will be sorted by their degree. This sorting can improve search process because it allows to skip several vertices with higher degrees whose neighbor sets are smaller or equal to the current max.
The process of computing k-core decomposition is very simple iterative deletion of vertices which degree is lower than k and it is described on the algorithm 3. In this algo5In some cases heuristic can find maximum clique size and max-core decomposition can be empty. rithm V (G) denotes the set of vertices V belonging to the graph G.
8: 9: Algorithm 3 k-core decomposition of graph G. Input: Simple undirected graph G, desired value k. Output: k-core decomposition of graph G.
1: function COMPUTEKCORE(G, k) 2: Gk-core ← G 3: repeat 4: Gtmp ← Gk-core 5: for all v ∈ Gk-core do 6: if deg(v) < k then 7:
V (Gk-core) ← V (Gk-core) \ {v} until V (Gtmp) 6= V (Gk-core) ⊲ If there is no change in graph then the k-core decomposition is finished.
return Gk-core
After completion of the initialization phase the main search phase follows. The algorithm works with two nested loops, first is iterating over last k-core decomposition (line 7 in algorithm 4) and starting the second loop. Here is the algorithm processing vertices from higher index to lower (inside last computed k-core decomposition, line 8 in algorithm 4). For each vertex vi is testing number of colors needed to color vertices from N[vi] which forms induced subgraph. If this number of colors is higher than currently know max, there can be clique with higher size than max.
To obtain neighbors set of vertex vi new metric is introduced. We call it internal degree and it is defined in equation 1.
degv(u) = w|w ∈ N[v] ∧ (u, w) ∈ E (1)
In the search process our algorithm will processes each vertex only once. This is guaranteed by checking the array c (line 10) from the Östergård’s algorithm. If this array is already set for the given index, then we know that the vertex with this index was processed before.
In the main loop, where the algorithm is iterating through all unprocessed vertices, it is running greedy function for coloring6. Result of this coloring function is suboptimal number of minimum colors needed to color vertex and it neighborhood, which can be performed quickly. It gives us a good information whether it is promising to find better clique size when the algorithm starts branching from this vertex. The process of coloring vertex v and it neighborhood Nv = {v} ∪ { |
u u ∈ N(v) ∧ deg(u) ≥ max ∧ arg u > arg v} is described in algorithm 5.
6This function is similar to one mentioned in [
CLIQUE(Nvi , 1) c[i] ← max if found = true then
return if lastMax = max then ⊲ All vertices are processed and there is no better solution.
break ← else lastMax ← max
Gmax-core ← COMPUTEKCORE(G, max) 4
Our algorithm is able to solve maximum clique problem, as well as Östergård’s algorithm, for all sorts of simple undirected graphs. But for all graphs with scale-free property it is our algorithm able to do so much faster. Most useful improvement here is the heuristic function which finds preliminary clique size in initialization phase, with subsequent k-core decomposition throughout whole process of searching. By decomposition the algorithm is able to reduce the graph size by removing vertices which can not be part of a maximum clique. Also degree distribution after each decomposition step is changing from original (asymptotically following power law) to linear looking one. When the final clique is found7 and last computation of max-core decomposition the remaining vertices does not forms scale-free network anymore and they must be processed all to confirm found clique number. It is also possible that the last max-core decomposition will return 7The one representing one of maximum cliques in graph.
Algorithm 5 Greedy algorithm used to find minimum colors needed to color vertex i and it’s neighbors.
Input: Simple undirected graph G, index of vertex i. Output: Suboptimal number of minimum colors needed to color vi and it immediate neighborhood. 1: function GETMINCOLORS(G, i, minDegree) 2: colors ← 1, colorMap[vi] ← 1 3: Neighbors ← {u|u ∈ N(vi) ∧ deg(u) ≥ minDegree ∧ arg u > i} 4: AllNodes ← Neighbors ∪ {vi} 5: for all u ∈ Neighbors do ⊲ Iterate over neighbors u of vertex vi. 6: Nu ← N(u) ∩ AllNodes ⊲ Assemble set of neighbors of u within neighbors of vi. 7: minColor ← 1, UsedColors ← {} 8: for all w ∈ Nu do ⊲ Iterate over all neighbors w of vertex u ... 9: if colorMap[w] 6= null then ⊲ ... and collect all colors already used. 10: UsedColors UsedColors ← empty graph, this means immediate finish of the algorithm without additional need to confirm found clique number.
In the search phase an additional pruning techniques were introduced. First was computation of minimum colors needed to color starting vertex and his neighborhood. This is greedy function so it can not compute optimal solution, but approximative solution is good to decide if processing of neighbors of the starting vertex is promising to find higher clique size. Second pruning here is neighbors node selection by testing their internal degree (according to equation (1)). Because connections outside neighborhood of the starting vertex does not contribute any vertex to the clique that we look for inside this neighborhood, we may omit these vertices when we deciding if vertex from neighborhood have to be added to the set of neighbors used for branching. This can reduce search space for each starting vertex and speed up the algorithm.
We have tested our algorithm on our FMRi data of
functional brain networks as well as on simple
undirected graphs from the database which can be found
on https://snap.stanford.edu/data/8 and on some graphs
from DIMACS dataset. We also generated some
test8Stanford dataset and FMRi functional brain networks represents
real world graphs.
ing graphs using Bernoulli graph distribution,
BarabáshiAlbert graph distribution [
Table 1 contains some results from test runs. The graph name is represented by G, D is the density of edges inside graph G. |V | and |E| represents the sizes of vertices and edges set of graph G. Preliminary size of clique is denoted here as sp while maximum clique size is denoted as clique number of graph ω(G). There is also ratio between sp and ω(G) which represents how close the initialization phase heuristic search was to the real maximum clique in the given graph. Also times are displayed here, the „Time of phase 1” is time needed to compute preliminary clique size9 and „Time of phase 2” is time needed to complete iterative branching of search phase.
The graph „C125.9” is from DIMACS dataset. It is the smallest one from DIMACS and it does not represent the scale-free network. It is random graph with edge probability of 0.9, with 125 vertices and 6963 edges. It takes 1637 seconds for our algorithm to process this graph. This is clear demonstration that our algorithm is able to find a maximum clique in an arbitrary undirected graph, but the time to process it is not better than the time needed by Östergård’s algorithm10. Also graphs called „BG_n_p” are random graph, generated by Bernoulli graph distribution, where n is number of vertices and 10p0 is probability of edge between two vertices. The time needed to solve these graphs is exponentially rising with number of vertices (the probability of edge is the same for both of them).
The graph called „facebook”, as well as „asskitter”, „Email-Enron”, „CA-AstroPh”, „CA-CondMat” and „CA-HepPh” represent scale-free networks from Stanford snap datasets. One may see that the „facebook” graph have higher density than other graphs from dataset and the time needed to compute the maximum clique is around 379 seconds for just 4039 vertices and 88234 edges. On the other hand graph „as-skitter” with has 1696415 vertices and 11095298 edges, and very low density is processed in only 99 seconds. Initialization phases heuristic time for this graph is 28.6 seconds due to the large amount of vertices. We may say that number of vertices and the edges density is the key factor of the algorithm speed. Graph „CA-HepPh” is an example of a graph, where heuristic function finds maximum clique size and resulting k-core decomposition forms an empty graph. We also tested some randomly generated graphs by BarabásiAlbert graph distribution. These graphs are „BA_n_k”, where n is number of vertices and each new vertex is con9Graph loading and construction as well as post heuristic renumbering of graph and k-core decomposition is not included in this time.
10Actually by using additional techniques like k-core decomposition and others which are not included in Östergård’s algorithm, the run time of our algorithm for graphs of these types is higher than time needed by original algorithm. nected with k edges. These graphs was also solved quite fast and initial heuristic have found preliminary clique sizes very close to graphs clique numbers.
Graphs „awith_*”, „awout_*” and „young_*” represents FMRi functional brain networks for adult participants with Alzheimer disease, without this disease and young participants without disease. All are scale-free networks having from 5400 to 8200 vertices. Here we can also see that the key factor is a density of edges and the number of vertices. We can see that some graphs were processed under one second by our algorithm. We also tested the performance of the original Östergård’s algorithm on these graphs, which needs tens of minutes or several hours to process them.
Last dataset of graphs are named „WS_n_p_k”, these are random graphs generated using Watts–Strogatz graph distribution, where n is number of vertices, 10p0 is rewiring probability starting from 2k-regular graphs. One can see that our algorithm is also performing well on small-world networks even it was not designed for this type of graphs. Results of heuristic here is also very close to final graph clique numbers.
For our scale-free brain functional networks or other graphs with scale-free property our algorithm gives us exact results much faster than the Östergård’s one. That means we are able to analyze scale-free graphs for our purposes very quickly. |V | |E|