maximum clique problem solve

Maximum Clique

People in the social network are identified by unique IDs, consecutive integers from 1 to N. Who follows who is captured in a cell array called 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 these lists are ordered in ascending order by ID. Note that the follows relationship is not necessarily symmetrical: if person A follows person B, person B may or may not follow person A. :

function clique = max_clique(graph, clique)
if nargin < 2
    clique = [];
end
max_clq = clique;
if isempty(clique)
    for ii= 1:length(graph)
        clq = max_clique(graph,ii);
        if length(clq) > length(max_clq)
            max_clq = clq;
        end
    end
else
    for node=1:length(graph)
        if isempty(find(node==clique))
            if check_clique(clique,node,graph)
                clq = max_clique(graph, [clique node]);
                if length(clq) > length(max_clq)
			max_clique == clq
                end
            end
        end
    end
end
clique = max_clq;
end
function ok = check_clique(clq,node,graph)
    ok = false;
    for ii=1:length(clq)
        if isempty(find(clq(ii) == graph{node})) || isempty (find(node == graph{clq(ii)}))
            return;
        end
    end
    ok = true;
end

Unfortunately, it is too slow and the grader will time out. Your task is to modify the code to speed it up. Remember, the question to ask: am I doing any unncessary work? Call the modified function max_clique. (Hint: when we try to expand the current clique, do we really need to consider all the nodes?)

Please solve this problem with entire new code that is fast.

[Parth Tushar Deodhar]

Here is the mat file with the example social network: sn.mat

[Steven Lord]

Since this is a homework assignment, show us the code you've written to try to solve the problem and ask a specific question about where you're having difficulty and we may be able to provide some guidance.

If you aren't sure where to start because you're not familiar with how to write MATLAB code, I suggest you start with the MATLAB Onramp tutorial (https://www.mathworks.com/support/learn-with-matlab-tutorials.html) to quickly learn the essentials of MATLAB.

If you aren't sure where to start because you're not familiar with the mathematics you'll need to solve the problem, I recommend asking your professor and/or teaching assistant for help.

[Parth Tushar Deodhar]

I am not able to understand the problem Can show me the road map to solve it

[Parth Tushar Deodhar]

The auto grader is timimg out with my solution Can you give a more efficient algorithm

[Steven Lord]

Finding a way to improve the performance of the code is literally your assignment. "Unfortunately, it is too slow and the grader will time out. Your task is to modify the code to speed it up." We will not write the code for you.

If you're not sure what to do in terms of algorithm, contact your professor and/or teaching assistant.

[Parth Tushar Deodhar]

I know its my task my task but i am not able to contact the teacher

can you atleast study the code and give me tips

[Jan]

This line in the posted code is not useful:

max_clique == clq

This is a comparison, but it does not assign anything. In the screenshot of your code this line is:

max_clique = clq;

Which of the two versions is wanted? Please do not let the readers guess.

Remember that:

isempty(find(a == b))

can be simplified by

~any(a == b)

You get corresponding hints in the editor already. Do not ignore them.

[Jan]

@Parth Tushar Deodhar: You have set a flag:

"please delete this thread as it is an home work assignment and might lead to some one copying it."

With using this forum you agree to the Terms of Use. This implies that the posted contents is made available for the community. The nature of this forum is the sharing of problems and solutions. To support this, many voluntary Matlab users spend their time. Removing a question after an answer has been given, would not respect their work.

Please think twice before you post homework questions in the internet. Remember that even if the thread is deleted in the forum, you will still find a copy e.g. in Googles cache. Therefore I remove the flag without deleting the thread.

[Mehrail Nabil]

If you reach a code send it here to me ???

Answer 1

[Jan]

With replacing

if isempty(find(node==clique))
...
if isempty(find(clq(ii) == graph{node})) || isempty (find(node == graph{clq(ii)}))

by

if ~any(node==clique)
...
if ~any(clq(ii) == graph{node}) || ~any(node == graph{clq(ii)})

the processing time is reduced from 350 seconds to 193 seconds on my Matlab R2018b.

As next step inline the frequently called function check_clique in the main function:

function clique = max_clique(graph, clique)
if nargin < 2
   clique = [];
end
max_clq = clique;
if isempty(clique)
   for ii= 1:length(graph)
      clq = max_clique(graph, ii);
      if length(clq) > length(max_clq)
         max_clq = clq;
      end
   end
else
   for node = 1:length(graph)
      if ~any(node == clique)
         ok = true;  % Inlined check_clique:
         for ii = 1:length(clique)
            if ~any(clique(ii) == graph{node}) || ...
                  ~any(node == graph{clique(ii)})
               ok = false;
               break;
            end
         end
         
         if ok  % check_clique(clique,node,graph)
            clq = max_clique(graph, [clique, node]);
            if length(clq) > length(max_clq)
               max_clq = clq;
            end
         end
      end
   end
end
clique = max_clq;
end

This needs 72 seconds on my computer. 5 times faster with just tiny modifications.

[Parth Tushar Deodhar]

The AutoGrader is still timimg out and asking for a better and more efficient alogorithm with a hint that do we need to consider all nodes when we try to expand the current clique. Please Help

[Jan]

Are you aware that you didn't mention yet what the code should calculate?

[Fatema Saeed]

Hello Jan, I have tried the code however it still takes long computation time.

[Jan]

Yes, of course it is not much faster. I've suggested some obvious improvements only, but did not modify the algorithm in any way. The OP forgot to mention, what the code should compute. I stay away from guessing this very important detail.

Now you run the code again. Why? Did you get the same homework? If so, how can we help you?

[hmhuang]

Hello @Parth Tushar Deodhar, @Fatema Saeed, I hope you have successfully solved the problem.

I have been struggling with this assignment for quite a while. I think what the code should compute is a maximal social network clique where everyone follows everyone else. 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 above tiny improvement, 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 REALLY HAVE NO FURTHER IDEAS.

I HOPE SOMEONE COULD PROVIDE SOME ADVICES.

ANY SUGGESTIONS WILL BE APPRECIATED.

[Mehrail Nabil]

I want a code that can help me????

[Mehrail Nabil]

function clique = max_clique(graph, clique)
if nargin < 2
    clique = [];
end
max_clq = clique;
if isempty(clique)
    for ii= 1:length(graph)
        clq = max_clique(graph,ii);
        if length(clq) > length(max_clq)
            max_clq = clq;
        end
    end
else
    for node=1:length(graph)
        if  ~any(node==clique)
            if check_clique(clique,node,graph)
                clq = max_clique(graph, [clique node]);
                if length(clq) > length(max_clq)
			clique = max_clq;
                end
            end
        end
    end
end
clique = max_clq;
end
function ok = check_clique(clq,node,graph)
    ok = false;
    for ii=1:length(clq)
        if  ~any(clq(ii) == graph{node}) || ~any(node == graph{clq(ii)})
            return;
        end
    end
    ok = true;
end

[Mehrail Nabil]

i make this code but not run because of the time run out

[Mehrail Nabil]

can anyone help me to solve this problem?

[Walter Roberson]

I suspect you could write the code more efficiently using ismember() in check_clique

[Rawan Mohamed]

anyone reach the answer of this code ??

Answer 2

[Black Woods]

function clique = max_clique(g,clique)
    if nargin < 2
        clique = [];
    end
    max_clq = clique;
    if isempty(clique)
        for ii = 1:length(g)
            clq = max_clique(g,ii);
             if length(clq) > length(max_clq)
                max_clq = clq;
             end
        end
    else
        candidates = g{clique(1)};                           
        candidates = candidates(g{clique(1)} > max(clique)); 
        for ii = 1:length(candidates)
            if check_clq(clique,candidates(ii),g)
                clq = max_clique(g,[clique candidates(ii)]);
                if length(clq) > length(max_clq)
                    max_clq = clq;
                end
            end
        end
    end
    clique = max_clq;
end
        
function ok = check_clq(clq,id,g)
    ok = false;
    if ~isempty(find(id == clq))
        return;
    end
    for ii = 1:length(clq)
        if isempty(find(clq(ii) == g{id})) || isempty(find(id == g{clq(ii)}))
            return;
        end
    end
    ok = true;
end

Answer 3

[Mehrail Nabil]

Anyone can send me in comment the answer of it???? The code please

[Jonathan Paul Yuquilema Aldaz]

@Mehrail Nabil Were you able to solve the problem? I would appreciate if you help me with the code. Please.

[Cholla]

function clique = max_clique(g,clique)
    if nargin < 2
        clique = [];
    end
    max_clq = clique;
    if isempty(clique)
        for ii = 1:length(g)
            clq = max_clique(g,ii);
             if length(clq) > length(max_clq)
                max_clq = clq;
             end
        end
    else
        candidates = g{clique(1)};                           
        candidates = candidates(g{clique(1)} > max(clique)); 
        for ii = 1:length(candidates)
            if check_clq(clique,candidates(ii),g)
                clq = max_clique(g,[clique candidates(ii)]);
                if length(clq) > length(max_clq)
                    max_clq = clq;
                end
            end
        end
    end
    clique = max_clq;
end
        
function ok = check_clq(clq,id,g)
    ok = false;
    if ~isempty(find(id == clq))
        return;
    end
    for ii = 1:length(clq)
        if isempty(find(clq(ii) == g{id})) || isempty(find(id == g{clq(ii)}))
            return;
        end
    end
    ok = true;
end

Answer 4

[MR MB]

%if true
  function clique = max_clique(graph,clique)
  if nargin < 2                                       % originaly we call the function with just the graph
      clique = [];                                    % hence, the clique is initialized to an empty vector
  end
  max_clq = clique;                                   % max_clq will store the current largest clique
  if isempty(clique)                                  % when we first call the function
      ii = 1:length(graph);
      s = max_clique(graph,ii); %out of the loop
      for ii = 1:length(graph)                        % we need to test potential cliques starting from every possible node
          clq = s;
           if length(clq) > length(max_clq)           % if the new one is larger than the current
              max_clq = clq;                          % we store the new one
           end
      end
  else
      for node = 1:length(graph)                              % we are in a recursive call now: we test every node as a new member
          if isempty(find(node == clique))                    % unless it is already in the clique
              if check_clique(clique,node,graph)              % if adding this node is still a clique
                  clq = max_clique(graph,[clique node]);      % we call ourself with the new expanded clique
                  if length(clq) > length(max_clq)            % if what we get is larger the curent max
                      max_clq = clq;                          % we store the new one
                  end
              end
          end
      end
  end
  clique = max_clq;                                           % return the largest one
end

%if true
  function ok = check_clique(clq,node,graph)                      % adding node to clq still a clique?
  ok = false;
  for ii = 1:length(clq)                                      % for every current member
      if isempty(find(clq(ii) == graph{node})) || ...         % the member must be on the follows list of the new guy
              isempty(find(node == graph{clq(ii)}))           % the new guy must be on the follows list of the member
          return;
      end
  end
  ok = true;
end
end

It is so so so fast but with wrong answer Can any one help me to find the mistake?!?

[MR MB]

[ghazal]

anyone here can help me? I have problem and I get this Error

Undefined function 'max_clique' for input arguments of type 'cell'.

this is my code:

functuin clique = max_clique(graph,clique)
if nargin<2
    clique=[];
end
max_clq=clique;
if isempty(clique)
    for ii=1:length(graph)
        clq=max_clique(graph,ii);
        if length(clq)>length(max_clq)
            max_clq=clq;
        end
    end
else
    for node=1:length(graph)
        if ~any(node==clique)
            ok=true;
            for ii=1:length(clique)
                if ~any(clq(ii)==graph{node})||...
                        ~any(node==graph{clq(ii)})
                    ok=false;
                    break;
                end
            end
            if ok
                clq=max_clique(graph,[clique,node]);
                if length(clq)>length(max_clq)
                    max_clq=clq;
                end
            end
        end
    end
end
clique=max_clq;

[Jan]

Have you seen this: "functuin"?

[ghazal]

Thanks Jan, but now I get this error

Undefined function 'max_clique' for input arguments of type 'cell'.

[ghazal]

Thanks alot friend my problem solved

Answer 5

[Rajith]

function clique = max_clique(g,clique)
    if nargin < 2
        clique = [];
    end
    max_clq = clique;
    if isempty(clique)
        for ii = 1:length(g)
            clq = max_clique(g,ii);
             if length(clq) > length(max_clq)
                max_clq = clq;
             end
        end
    else
        candidates = g{clique(1)};                           % it is enough to check nodes that the first member of the clique follows
        candidates = candidates(g{clique(1)} > max(clique)); % since nodes are ordered, a potential new member must have a greater ID than current members
        for ii = 1:length(candidates)
            if check_clq(clique,candidates(ii),g)
                clq = max_clique(g,[clique candidates(ii)]);
                if length(clq) > length(max_clq)
                    max_clq = clq;
                end
            end
        end
    end
    clique = max_clq;
end
        
function ok = check_clq(clq,id,g)
    ok = false;
    if ~isempty(find(id == clq))
        return;
    end
    for ii = 1:length(clq)
        if isempty(find(clq(ii) == g{id})) || isempty(find(id == g{clq(ii)}))
            return;
        end
    end
    ok = true;
end

Answer 6

[Divyanshu]

function clique = max_clique(g,clique)
if nargin < 2
    clique = [];
end
max_clq = clique;
if isempty(clique)
    for ii = 1:length(g)
        clq = max_clique(g,ii);
        if length(clq) > length(max_clq)
            max_clq = clq;
        end
    end
else
    candidates = g{clique(1)};                           % it is enough to check nodes that the first member of the clique follows
    candidates = candidates(g{clique(1)} > max(clique)); % since nodes are ordered, a potential new member must have a greater ID than current members
    for ii = 1:length(candidates)
        if check_clq(clique,candidates(ii),g)
            clq = max_clique(g,[clique candidates(ii)]);
            if length(clq) > length(max_clq)
                max_clq = clq;
            end
        end
    end
end
clique = max_clq;
end

function ok = check_clq(clq,id,g)
ok = false;
if ~isempty(find(id == clq))
    return;
end
for ii = 1:length(clq)
    if isempty(find(clq(ii) == g{id})) || isempty(find(id == g{clq(ii)}))
        return;
    end
end
ok = true;
end

[Walter Roberson]

This is the same as what @Rajith posted, except for using slightly different number of spaces at the beginning of lines. There is no difference other than the spacing.