MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I have extracted URL links from a number of webpages and many of the webpages contain the same set of links (or subsets) as other webpages. I have ~1000 webpages and ~10 links per webpage.

What is an efficient way to find the minimum set of webpages that will still cover the complete set of links?

share|cite|improve this question

closed as off topic by Scott Morrison Nov 12 '09 at 2:40

Questions on MathOverflow are expected to relate to research level mathematics within the scope defined by the community. Consider editing the question or leaving comments for improvement if you believe the question can be reworded to fit within the scope. Read more about reopening questions here.If this question can be reworded to fit the rules in the help center, please edit the question.

closed as off topic - how come? The application is non-math but the principles certainly are. – hoju Nov 12 '09 at 3:08
Sorry, as asked it looks like a scientific visualisation or graphics design problem. If there's something mathematical you'd like to ask about, edit and I'll reopen. – Scott Morrison Nov 12 '09 at 5:02
fair enough. Have rephrased it now - is that sufficiently 'mathy'? – hoju Nov 13 '09 at 0:03
the question is closed, so I can't answer, but this sounds like classic set cover. the atoms are the links, and the webpages are the sets. – Suresh Venkat Jul 7 '10 at 9:03

Let me try a preliminary answer to see if I've understood what you're after.

You have, let's say, 1000 web pages, each containing some outbound links. You might define a 1000x1000 matrix D by $$ D_{ij} = \mbox{number of links in common between the }i\mbox{th and }j\mbox{th pages}. $$ Then you want to extract from $D$ a single number, the 'level of overlap', which broadly speaking will be large if most entries of $D$ are large, and small if most entries of $D$ are small.

I can think of some ways of doing that, but before I go into it, let me check: is that the kind of thing you want?

share|cite|improve this answer
Yes that is what I am after. But I am not sure how to present it. As Martin said a Venn diagram is out of the question! – hoju Nov 12 '09 at 3:12

One approach is to represent your data as a graph, and use a network diagram tool to draw it. Variant 1: nodes are websites, weighted edges represent number of common links. Variant 2: a bipartite graph with nodes being either web sites or links, and unweighted edges indicating "web site A contains link B." The magic google phrase to find examples related to your example is "citation visualization".

The problem with this technique is that big graphs sometimes turn into hairballs in a graph layout tool, so you may need to prune or filter your data set for it to be intelligible.

There are other techniques: you could draw a grid where rows correspond to web pages, and columns to links they contain, and fill in cells (X,Y) where link X appears in web site Y. If you reorder the rows and columns to put related pages near each other and related links near each other this can be an effective analytic tool, but it might not be right for non-technical readers.

A lot of this depends on the details of your data. If you have any kind of metadata (a categorization of web pages or links) that could suggest other approaches--feel free to add details in your question. About the only thing you can say for sure is a big Venn diagram is going to be a mess!

share|cite|improve this answer

Not the answer you're looking for? Browse other questions tagged or ask your own question.