0
$\begingroup$

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?

Improve this question
$\endgroup$
4
  • $\begingroup$ closed as off topic - how come? The application is non-math but the principles certainly are. $\endgroup$
    – hoju
    Commented Nov 12, 2009 at 3:08
  • 2
    $\begingroup$ 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. $\endgroup$
    – Kim Morrison
    Commented Nov 12, 2009 at 5:02
  • 1
    $\begingroup$ fair enough. Have rephrased it now - is that sufficiently 'mathy'? $\endgroup$
    – hoju
    Commented Nov 13, 2009 at 0:03
  • $\begingroup$ 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. $\endgroup$
    – Suresh Venkat
    Commented Jul 7, 2010 at 9:03

2 Answers 2

Reset to default
3
$\begingroup$

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?

Improve this answer
$\endgroup$
1
  • $\begingroup$ 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! $\endgroup$
    – hoju
    Commented Nov 12, 2009 at 3:12
1
$\begingroup$

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!

Improve this answer
$\endgroup$

Not the answer you're looking for? Browse other questions tagged .