most recent 30 from http://mathoverflow.net 2013-05-22T13:51:49Z http://mathoverflow.net/feeds/question/5133 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/5133/how-to-present-overlap-of-related-sets Richard 2009-11-12T01:10:43Z 2010-07-07T06:51:44Z

<p>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.</p> <p>What is an efficient way to find the minimum set of webpages that will still cover the complete set of links? </p>

http://mathoverflow.net/questions/5133/how-to-present-overlap-of-related-sets/5135#5135 Martin M. W. 2009-11-12T01:30:05Z 2009-11-12T01:35:41Z

<p>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".</p> <p>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.</p> <p>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.</p> <p>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!</p>

http://mathoverflow.net/questions/5133/how-to-present-overlap-of-related-sets/5136#5136 Tom Leinster 2009-11-12T01:32:42Z 2009-11-12T01:32:42Z

<p>Let me try a preliminary answer to see if I've understood what you're after.</p> <p>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.</p> <p>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?</p>