1
$\begingroup$

I would like to find the two furthest pages of a big websites (+5millions pages).

(It's the degree of separation, the most links between the two pages)

$\endgroup$
4
  • $\begingroup$ Welcome to the site. What do you mean by furthest pages? $\endgroup$
    – Dawny33
    Commented Apr 14, 2016 at 15:33
  • $\begingroup$ Sorry. It's the degree of separation, the most links between the two pages. Thank you. $\endgroup$
    – Arktos
    Commented Apr 14, 2016 at 15:37
  • $\begingroup$ For reference, this is the diameter of the graph. $\endgroup$
    – Emre
    Commented Apr 14, 2016 at 16:36
  • 2
    $\begingroup$ In the context of what technology or representation? you've defined what it means but what are you asking about how to compute it? $\endgroup$
    – Sean Owen
    Commented Apr 14, 2016 at 16:46

2 Answers 2

2
$\begingroup$

This is a classic "graph database" question. I would do the following steps:-

  • Traverse all the pages using a webcrawler, or if you can interrogate the website server directly that may be qukcker.
  • Ensure you keep all links between pages, for later use.
  • Put the web pages into a neo4j database with connections between the pages

This will allow you to be able to do the query of pages with the maximum number of steps, or pages most frequently linked to, etc.

$\endgroup$
-1
$\begingroup$

Assume you have the data in a table containing a row for each link, storing the PAGE and the linked page (LINK_TO).

select * from page_link;

PAGE LINK_TO
---- -------
A    A       
A    B       
A    B       
A    C       
B    C       
B    C       
B    C       
C    A  

Than simple group on the two columns and count the occurences. This gives the number of links between any two linked pages, so you can see the most links between the two pages - if this is realy what you want...

select PAGE, LINK_TO, count(*) 
from page_link 
group by PAGE, LINK_TO order by 3 desc;

PAGE LINK_TO   COUNT(*)
---- ------- ----------
B    C                3 
A    B                2 
A    C                1 
A    A                1 
C    A                1 

A few milions of records should not be a problem for any database of your chioce.

$\endgroup$

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