Re: algorithm for reducing rows/columns

[Kim Hansen]

On Sun, Dec 19, 2010 at 03:36, Mike Miller <address@hidden> wrote:
> This is probably more of a mathematical question than an Octave question,
> per se, but someone here might be interested...
>
> Here's the problem, in a simple form:  I have a square symmetrix matrix,
> M, with all elements either zero or one.  All diagonal elements are zero.
> I want to find a set of indices, I, such that M(I,I) is a zero matrix of
> the largest possible size.  There will usually be more than one I that
> maximizes size(M), but they are all equally good for my purposes, so I
> would choose one arbitrarily.  Maybe if I always delete one of the
> rows/cols with the largest number of ones, and repeat, that will do it,
> but I'm not sure of that.  Any ideas?

I just had some fun implementing the greedy approach, it is pasted in below.

You need to select max after each delete, if you just do a single sort
the result will be bad. I tried on the simple example from run.m
below, and the one-sort gave a clique of 9 nodes when greedy_clique()
gave a clique of 272 nodes.


address@hidden:~/octave/clique$ cat greedy_clique.m
## Copyright Kim Hansen <address@hidden>, BSD Licensed

## function clique = greedy_clique(a)
##
## clique is the boolean row that selects the greedy guess at the
maximal clique.

function clique = greedy_clique(a)

  sz = size(a,1);

  orig_indexes = 1:sz;
  clique = true(1, sz);
  count = sum(a);

  while (true)
    [max_count, max_pos] = max(count);
    if (max_count == 0) break; endif
    # Delete the non-member
    count -= a(orig_indexes(max_pos), clique);
    count(max_pos) = [];
    clique(orig_indexes(max_pos)) = false;
    orig_indexes(max_pos) = [];
  endwhile

endfunction

address@hidden:~/octave/clique$ cat run.m
#!/usr/bin/octave -q

sz = 8000;
prob = 0.01;

a = rand(sz);
a = a < prob;
a |= a.';
a &= ! eye(size(a));

tic;
cliq = greedy_clique(a);
toc

printf("Number of nodes in the clique: %d\n", sum(cliq));

printf("Validate that the clique selects a zero matrix: %d\n",
sum(a(cliq,cliq)(:)));

address@hidden:~/octave/clique$ ./run.m
Elapsed time is 6.8664 seconds.
Number of nodes in the clique: 266
Validate that the clique selects a zero matrix: 0

address@hidden:~/octave/clique$


-- 
Kim Hansen
Vadgårdsvej 3, 2.tv
2860 Søborg
Phone: +45 3091 2437