Maximum size sub-matrix with all 1s

[Ofrit Lesser]

 

Hi,

 

I've got a binary table/matrix of users-items data, where 1 indicates that the user uses the item.

I'd like to extract a sub-matrix  of users-items with 1's only (meaning all users in this matrix use all the items).

I'm looking for the largest possible sub-matrix (an approximation is fine as well) .

 

An example:

        item1  item2  item3  item4

person1   1       0       0       1

person2   0       1       1       1

person3   1       1       0       1

person4   0       1       1       1

 

So the sub-matrix would be:

          item2  item3  item4

person2   1       1       1

person4   1       1       1

 

 

One option is to convert the matrix into a graph and find the largest clique. Maximal clique is an NP-hard problem, but there are several heuristic algorithms that solve it (e.g. . The igraph function: largest.cliques).

 

However,  I prefer other alternatives that work directly on the table/matrix without the need to manipulate the structure.

Any ideas?

 

Thanks,

Ofrit

 

---

This email is free from viruses and malware because avast! Antivirus protection is active.

[amit gal]

since your problem is equivalent to maximal clique problem, solving it will be NP as well. Also, I don't remember what is the exact algorithm for solving the clique finding, but I guess they do some manipulation of the adjacency matrix directly, which is exactly what you are looking for.

still looking at the graph theoretic approach, a nice approximation would be the k-core algorithm. which can identify quite fast who are the candidate nodes for that.

this would work only if your matrix is indeed an adjacency matrix (e.g. symmetric and square)

--
You received this message because you are subscribed to the Google Groups "Israel R User Group" group.
To unsubscribe from this group and stop receiving emails from it, send an email to israel-r-user-g...@googlegroups.com.
For more options, visit https://groups.google.com/d/optout.

[Ofrit Lesser]

Thanks Amit.

A code example would be very helpful to me.

[amit gal]

אה... נו טוב, זה יצריך יותר מאמץ. אין לי בשליפה מהמותן ואני כרגע בין ישיבות. אם אף אחד אחר לא יגיב עם הצעה אחרת, אנסה לענות בהמשך היום.

[amit gal]

בכל מקרה, k-core מיושם בחבילת igraph אז אפשר לקרוא מה זה עושה ולהשתמש בזה או באדפטציה מסויימת של זה.