Method and system for trawling the World-wide Web to identify implicitly-defined communities of web pages

• US 6,886,129 B1
• Filed: 11/24/1999
• Issued: 04/26/2005
• Est. Priority Date: 11/24/1999
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Ravikumar, Shanmugasundaram, Tomkins, Andrew S., Rajagopalan, Sridhar, Raghavan, Prabhakar
• Primary Examiner(s): Hong, Stephen S.
• Assistant Examiner(s): LUDWIG, MATTHEW J
• Application Number:
  US09/449,697
• Time in Patent Office: 1,980 Days
• Field of Search: 707/5, 707/6, 707/237, 715/500.1
• US Class Current: 715/205
• CPC Class Codes: G06F 16/355 Class or cluster creation or modification
• CPC Class Codes: G06F 16/954 Navigation, e.g. using categorised browsing
• CPC Class Codes: Y10S 707/99932 Access augmentation or optimizing
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching

Abstract

A method and system for identifying groups of pages of common interest from a collection of hyper-linked pages are disclosed. A plurality of community cores are identified from the collection where each core includes first and second sets of pages, and each page in the first set points to every page in the second set. Each identified core is expanded into a full community which is a subset of the pages regarding a particular topic. The identification community cores is based on the analysis of the Web graph in which the communities correspond to instances of Web subgraphs. Extraneous pages are then pruned to improve the quality of the resulting communities.

Claims

1. A method for pre-identifying implicitly defined communities including groups of pages of common interest from a collection of hyper-linked pages, wherein the communities have not been previously identified, comprising the steps of:

identifying a collection of hyperlinked pages from a plurality of sites, wherein each of the sites includes one or more hyper-linked pages;

identifying hyper-links between any two pages on a same site, wherein the same site is included within the plurality of sites;

removing the identified hyper-links between the two pages on a same site;

identifying a plurality of (i,j)-cores within the identified collection, the (i,j)-cores including a first set of hyperlinked pages and a second set of hyper-linked pages, wherein each page in the first set of hyperlinked pages points to every page in the second set of hyperlinked pages, and where i and i are the numbers of hyper-linked pages in the first set and hyper-linked pages in the second set, respectively, that appear in each of the identified (i,j)-cores; and

expanding each of the identified (i,j)-cores into a fully community, the full community being a subset of the pages reading a particular topic.

2. The method as recited in claim 1 further comprising the step of discarding the pages of predetermined sites.

3. The method as recited in claim 1 further comprising the steps of:

finding highly similar pages that have different names;

replacing the highly similar pages with a single representative page; and

redirecting any hyper-links that pointed to one of the highly similar pages so that the redirected hyper-links now point to the representative page.

4. The method as recited in claim 1, wherein the step of discarding includes the steps of:

determining candidate fan pages, the candidate fan pages being those pointing to at least a predetermined number of different sites;

determining candidate center pages, the candidate center pages being those pointed to by one or more candidate fan pages; and

discarding all pages in the collection except the candidate fan pages and candidate center pages.

5. The method as recited in claim 4, wherein the determination of candidate fan pages is based on page content and the hyper-links pointing therefrom.

6. The method as recited in claim 1, wherein the step of finding a plurality of (i,j)-cores includes the steps of:

(a) discarding all candidate center pages that have fewer than i hyper-links pointing thereto;

(b) determining all candidate center pages that have i hyper-links pointing thereto and determining whether the i hyper-links represents a valid community core; and

(c) if the i hyper-links represents a valid community core, then outputting the valid core, otherwise, discarding the determined candidate center pages.

7. The method as recited in claim 6 further comprising the steps of:

(d) discarding all candidate fan pages that have fewer than j hyper-links pointing therefrom;

(e) determining all candidate fan pages that have j hyper-links pointing therefrom and determining whether the j hyper-links represent a valid community core; and

(f) if the j hyper-links represents a valid community core, then outputting the valid core, otherwise, discarding the determined candidate fan pages.

8. The method as recited in claim 7 further comprising the step of repeating steps (a)-(f) until every candidate fan page has more than j hyper-links pointing therefrom and every candidate center page has more than i hyper-links pointing thereto.

9. The method as recited in claim 7 further comprising the step of repeating steps (a)-(f) until a predetermined ending condition is satisfied.

10. The method as recited in claim 7 further comprising the steps of:

determining all (2,j) cores by examining all pairs of candidate fan pages;

for i=3 to n, where n is a predetermined value;

(i) finding all (i,j)-cores by examining the (i-1,j)-cores; and

(ii) for each (i-1,j)-core, determining whether any of the candidate fan pages may be added to the (i-1, j)-core to yield a (i,j)-core; and

removing all (i,j)-cores that appear as subsets of (i′

,j) cores, where i′

>

i.

11. A computer program product for use with a computer system for pre-identifying implicitly defined communities including groups of pages of common interest from a collection of hyper-linked pages, wherein the communities have not been previously identified, the computer program product comprising:

a computer-readable medium;

means, provided on the computer-readable medium, for identifying a collection of hyperlinked pages from a plurality of sites, wherein each of the sites includes one or more hyper-linked pages;

means, provided on the computer-readable medium, for identifying hyper-links between any two pages on a same site, wherein the same site is included within the plurality of sites;

means, provided on the computer-readable medium, for removing the identified hyper-links between the two pages on a same site;

means, provided on the computer-readable medium, for identifying a plurality of (i,j)-cores within the identified collection, the (i,j)-cores including a first set of hyperlinked pages and a second set of hyper-linked pages, wherein each page in the first set of hyperlinked pages points to every page in the second set of hyperlinked pages, and where i and j are the numbers of hyper-linked pages in the first set and hyper-linked pages in the second set, respectively, that appear in each of the identified (i,j)-cores; and

means, provided on the computer-readable medium, for expanding each of the identified (i,j)-cores into a full community, the full community being a subset of the pages regarding a particular topic.

12. The computer program product as recited in claim 11 further comprising means, provided on the computer-readable medium, for directing the system to discard the pages of predetermined sites.

13. The computer program product as recited in claim 11 further comprising:

means, provided on the computer-readable medium, for directing the system to find highly similar pages that have different names;

means, provided on the computer-readable medium, for directing the system to replace the highly similar pages with a single representative page; and

means, provided on the computer-readable medium, for directing the system to redirect any hyper-links that pointed to one of the highly similar pages so that the redirected hyper-links now point to the representative page.

14. The computer program product as recited in claim 11, wherein the means for directing to discard includes:

means, provided on the computer-readable medium, for directing the system to determine candidate fan pages, the candidate fan pages being those pointing to at least a predetermined number of different sites;

means, provided on the computer-readable medium, for directing the system to determine candidate center pages, the candidate center pages being those pointed to by one or more candidate fan pages; and

means, provided on the computer-readable medium, for directing the system to discard all pages in the collection except the candidate fan pages and candidate center pages.

15. The computer program product as recited in claim 14, wherein the determination of candidate fan pages is based on page content and the hyper-links pointing therefrom.

16. The computer program product as recited in claim 11, wherein the means for directing to find a plurality of (i, j)-cores includes:

(a) means, provided on the computer-readable medium, for directing the system to discard all candidate center pages that have fewer than i hyper-links pointing thereto;

(b) means, provided on the computer-readable medium, for directing the system to determine all candidate center pages that have i hyper-links pointing thereto and determining whether the i hyper-links represents a valid community core; and

(c) means, provided on the computer-readable medium, for directing the system to output the valid core if the i hyper-links represent a valid community core, otherwise, to discard the determined candidate center pages.

17. The computer program product as recited in claim 16 further comprising:

(d) means, provided on the computer-readable medium, for directing the system to discard all candidate fan pages that have fewer than j hyper-links pointing therefrom;

(e) means, provided on the computer-readable medium, for directing the system to determine all candidate fan pages that have j hyper-links pointing therefrom and determining whether the j hyper-links represents a valid community core; and

(f) means, provided on the computer-readable medium, for directing the system to output the valid core if the j hyper-links represents a valid community core, otherwise, discard the determined candidate fan pages.

18. The computer program product as recited in claim 17, wherein the operation of means (a)-(f) is repeated until every candidate fan page has more than j hyper-links pointing therefrom and every candidate center page has more than i hyper-links pointing thereto.

19. The computer program product as recited in claim 17, wherein the operation of means (a)-(f) is repeated until a predetermined ending condition is satisfied.

20. The computer program product as recited in claim 17 further comprising:

means, provided on the computer-readable medium, for directing the system to determine all (2,j) cores by examining all pairs of candidate fan pages;

for i=3 to n, where n is a predetermined value;

(i) means, provided on the computer-readable medium, for directing the system to find all (i,j)-cores by examining the (i-1,j)-cores; and

(ii) for each (i-1, j)-core, means, provided on the computer-readable medium, for directing the system to determine whether any of the candidate fan pages may be added to the (i-1, j)-core to yield a (i,j)-core; and

means, provided on the computer-readable medium, for directing the system to remove all (i,j)-cores that appear as subsets of (i′

,j) cores, where i′

>

i.

21. A system for pre-identifying implicit defined

communities including groups of pages of common interest from a collection of hyper-linked pages, wherein the communities have not been previously identified, comprising:

means for identifying a collection of hyperlinked pages from a plurality of sites, wherein each of the sites includes one or more hyper-linked pages;

means for identifying hyper-links between any two pages on a same site, wherein the same site is included within the plurality of sites;

means for removing the identified hyper-links between the two pages on a same site;

means for identifying a plurality of (i,j)-cores with the identified collection, the (i,j)-cores including a first set of hyperlinked pages and a second set of hyper-linked pages, wherein each page in the first set of hyperlinked pages points to every page in the second set of hyperlinked pages, and where i and j are the numbers of hyper-inked pages in the first set and hyper-linked pages in the second set, respectively, that appear in each of the identified (i,j)-cores; and

means for expanding each of the identified (i,j)-cores into a full community, the full community being a subset of the pages regarding a particular topic.

22. The system as recited in claim 21 further comprising means for discarding the pages of predetermined sites.

23. The system as recited in claim 21 further comprising:

means for finding highly similar pages that have different names;

means for replacing the highly similar pages with a single representative page; and

means for redirecting any hyper-links that pointed to one of the highly similar pages so that the redirected hyper-links now point to the representative page.

24. The system as recited in claim 21, wherein the means for discarding includes:

means for determining candidate fan pages, the candidate fan pages being those pointing to at least a predetermined number of different sites;

means for determining candidate center pages, the candidate center pages being those pointed to by one or more candidate fan pages; and

means for discarding all pages in the collection except the candidate fan pages and candidate center pages.

25. The system as recited in claim 24, wherein the determination of candidate fan pages is based on page content and the hyper-links pointing therefrom.

26. The system as recited in claim 21, wherein the means for finding a plurality of (i, j)-cores includes:

(a) means for discarding all candidate center pages that have fewer than i hyper-links pointing thereto;

(b) means for determining all candidate center pages that have i hyper-links pointing thereto and determining whether the i hyper-links represent a valid community core; and

(c) means for outputting the valid core if the i hyper-links represent a valid community core, otherwise, discarding the determined candidate center pages.

27. The system as recited in claim 26 further comprising:

(d) means for discarding all candidate fan pages that have fewer than j hyper-links pointing therefrom;

(e) means for determining all candidate fan pages that have j hyper-links pointing therefrom and determining whether the j hyper-links represent a valid community core; and

(f) means for outputting the valid core if the j hyper-links represents a valid community core, otherwise, discarding the determined candidate fan pages.

28. The system as recited in claim 27, wherein the operation of means (a)-(f) is repeated until every candidate fan page has more than j hyper-links pointing therefrom and every candidate center page has more than i hyper-links pointing thereto.

29. The system as recited in claim 27, wherein the operation of means (a)-(f) is repeated until a predetermined ending condition is satisfied.

30. The system as recited in claim 27 further comprising:

means for determining all (2,j) cores by examining all pairs of candidate fan pages;

for i=3 to n, where n is a predetermined value;

(i) means for finding all (i,j)-cores by examining the (i-1,j)-cores; and

(ii) for each (i-1, j)-core, means for determining whether any of the candidate fan pages may be added to the (i-1, j)-core to yield a (i,j)-core; and

means for removing all (i,j)-cores that appear as subsets of (i′

,j) cores, where i′

>

i.