Find maximum clique with recursive function

I am solving an problem which has been stated and discussed here: maximum clique problem solve

As the OP showed in the above thread, the original version is inefficient because it is checking a bunch of sets of nodes that cannot possibly be part of a clique. So we need a smarter way to pick which nodes to check.

Therefore, based the tiny improvement in the accepted answer in maximum clique problem solve, I also tried:

1. disregard nodes with length < length(clique)
2. disregard nodes with the first element > clique(1)
3. disregard nodes with the last element < clique(end)
4. disregard nodes that are not in the follow list of first elemnt in the current clique

So my version of modification based on what @Jan wrote is changing line 15 to:

if ~any(node == clique) && length(graph{node}) >= length(clique) && graph{node}(1) <= clique(1) && graph{node}(end) >= clique(end) && any(node == graph{clique(1)})

Unfortunately, this runs for ~60 seconds on my computer, which is still not fast enough to pass the grader...

I also come up with the order of operands of && operator. So I change the above line to:

if any(node == graph{clique(1)}) && length(graph{node}) >= length(clique) && graph{node}(1) <= clique(1) && graph{node}(end) >= clique(end) && ~any(node == clique)

Although this gets a bit faster and runs for ~40 seconds on my computer, unfortunately this is still not fast enough to pass the grader...

I HOPE SOMEONE COULD PROVIDE SOME ADVICES.

ANY SUGGESTIONS WILL BE APPRECIATED.

[Jan]

I had the problem in the linked question already: The text of the question does not mention explicitly, what the code should calculate. I have to guess the intention from the result given by the slow example code. If I get such a question as a student, I'd refuse to solve it and ask for a clear problem description at first.

I'd just optimized the code blindly without understanding, what it does. I get the result

1769        1773        1774        1833        2222

but do not have the faintest idea, what this should be. In consequence I cannot rewrite the code in an efficient way, because the most important part of the description is missing.

Sorry, maybe it is only a langauge problem, because I'm not a native speaker.

[hmhuang]

@Jan Your result is correct with the input graph sn.mat. What the code should calculate is to find the maximal clique in a given social network, i.e., everyone in the clique should follow everyone else in the clique. The input argument "graph" is a cell array (in your case call sn): the ii th element of sn is a vector that contains a list of IDs the person with ID ii follows. You may assume that everyone has an unique ID and these lists are ordered in ascending order by ID. The original inefficient version autually take ~3 mins to complete, which is quite slow. Our task is to find a smarter way to pick nodes for checking (there are a bunch of sets of nodes that cannot possibly be part of a clique), rather than checking EVERY node like the original version did.

The problem is actually coming from Week 4 Problem 3 of the course "Mastering Programming with MATLAB" on Coursera.

(Mastering Programming with MATLAB | Coursera)

If you are still interested in solving this problem, you will find the detailed problem descriptions there.

But I think the descriptions of mine and the linked question are enough. If you still feel unclear, please let me know. Thanks.

I hope someone could give me some hints.

[Jan]

@hmhuang: Thanks for mentioning the source of the question and for your explanations.

sn{5} starts with the number 5. This means, that the ID=5 follows itself. This happens for 373 other IDs also. Does this count as an element of a clique?

[hmhuang]

@Jan Thanks for asking. Yes, everyone can also follow themselves. The array was randomly generated. But to be qualified as an element of the clique, everyone should follow everyone else in the clique, following themselves isn't enough to be an element of a clique. For example, by the result: [ 1769 1773 1774 1833 2222 ], this means 1769 must follow 1773, 1774, 1833, 2222 and 1773 must follow 1769, 1774, 1833, 2222, and so on.

I hope this makes things more clear.

[Jan]

Okay, it's clear now.

Answer 1

[Jan]

I've reduced the run time from 60 to 2 seconds using this method:

• Convert the {1 x N} cell array of vectors to a [N x N] logical array X, which is true, if an ID in a specific column follows an ID in a specific row.
• Omit elements of X if the corresponding elements of X.' are not true: A following cannot belong to a clique, if it points it is not mutual.
• Run a loop over the rows (or columns - X is symmetric now). Select the sumbatrix:

v = X(k, :);
Y = X(v, v);

• Convert this back to the original represantation using a cell vector and indices.
• Call the original function as suggested in the other thread

An alternative description of the idea: I do not search the complete graph, but for the k'th ID only the elements of graph(graph{k}) are considered. The others cannot be part of a clique, which contains the k'th node of the graph.

I do not post the code, because this is a question of a course. A clean solution would stay at the representation as logical array to apply the recursive search. But my lazy method yields an acceleration of factor 30 already by a divide and conquer approach without touching the actual algorithm.

[hmhuang]

@Jan Thank you for the solution.

Two questions:

1. How do you omit elements of X if the corresponding elements of X.' are not true in the second step? By omitting, do you set those unqualified elements to zero? e.g., X(X ~= X.') = 0
2. Do you convert the original graph to a modified graph outside of the max_clique function and then pass it to the original function by calling max_clique(modified_graph) for example?

[Jan]

@hmhuang: If X is a logical square matrix:

Y = (X .* X.');

Now Y is true, when X and X.' are true, or in other words: Y(i,j) is true, if ID i and ID j are following eachother. A slower alternative:

Y = (X == X.') & X;

I was too lazy to modify the original code, except for the acceleration I've posted in the opther thread. I wrote an additional function for converting between the cell array and the matrix representation. Because I provide a small subproblem to the original max_clique() function, I have to care for replacing the output by the original indices.

There is an easier solution without converting the data.

[hmhuang]

@Jan Thank you for the reply. I did successfully write a helper function to tranform the original graph representation to a logical array and then convert it back to a new graph as a cell array. And there is a significant speedup with your approach - without modifying the original code.

I also want to share my approach with modifying the original code: It's surprisingly simple. Just consider nodes that are followed by the first node in the clique. Because any potential candidates must also exist in the follow list of the first node in the clique. This only requires to change only one line in the original code.

Anyway, thank you very much for participating in this thread and giving me useful ideas!

[Jan]

Nice. This was a useful discussion.

If the data are converted to a logical matrix, the problem can be formulated as: Find the set of column and row permutations to get the matrix with the largest block diagonal structure. Therefore I've asked for the diagonal elements.

[Mehrail Nabil]

Please give me the code???

[Jan]

@Mehrail Nabil: Sorry, no. The question is part of a course. If a solution is found in the net, the homework question is not useful anymore.

I've explained a solution and hmhuang has mentioned, that you need to change one line of the original code only. Please read his last comment and find the solution by your own.

[breksam Amr]

@Mehrail Nabil did you find the answer i still don't understand it yet