Systems and methods to provide local suggestions based on spectral clustering

1. A computer-implemented method comprising:

applying, by a computing system, a spectral clustering technique to at least a portion of a similarity graph to generate clusters of geogra phic sub-regions constituting geographic regions in a geogra phic area, wherein two geogra phic sub-regions, represented as vertices in the similarity graph, are linked through a connection in the similarity graph based on a condition relating to whether the two geographic sub-regions are within a selected number of nea rest cities of one another, wherein the geographic sub-regions are cities, wherein the connection is weighted based on a product of a first factor and a second factor, the first factor associated with a distance between the two geographic sub-regions and the second factor associated with check-ins by users in the two geographic sub-regions;

performing, by the computing system, a tf-idf technique to determine pages associated with a geographic region as potential local suggestions for a user associated with a geographic sub-region in the geographic region; and

presenting, by the computing system, references to at least a portion of the pages as local suggestions to the user.

2. The computer-implemented method of claim 1 , wherein the geographic regions are metropolitan areas including the cities.

3. The computer-implemented method of claim 1 , wherein the applying the spectral clustering technique comprises:

determining a first list of a selected number of cities nearest to a first city;

determining a second list of the selected number of cities nearest to a second city; and

determining satisfaction of the condition based on the second city appearing in the first list and the first city appearing in the second list.

4. The computer-implemented method of claim 1 , further comprising:

partitioning the similarity graph by country.

5. The computer-implemented method of claim 1 , wherein the geographic regions correspond to documents, pages relating to a geographic region correspond to terms in a document, and a number of users who like a page correspond to term frequency in the tf-idf technique.

6. The computer-implemented method of claim 1 , wherein the performing a tf-idf technique comprises:

normalizing a tf term by m f , where m f is a maximum number of likes by users in a metropolitan area for a page over all pages in the metropolitan area.

7. The computer-implemented method of claim 1 , wherein the performing a tf-idf technique comprises:

adjusting a value of a constant k to tune a ratio between a number of relatively small pages and a number of relatively large pages in the pages.

8. The computer-implemented method of claim 1 , wherein the performing a tf-idf technique comprises:

counting only metropolitan areas in which a number of users who like a page satisfies a selected threshold amount for n p , where n p is a number of metropolitan areas with users who like a page.

9. The computer-implemented method of claim 1 , further comprising:

applying to the pages a second condition relating to a desired degree of locality of a page in relation to a city to determine the at least a portion of the pages for which the references are presented as local suggestions to the user.

10. The computer-implemented method of claim 9 , wherein the second condition is associated with a distance based on latitude and longitude values of the city and the page being less than a threshold based on a selected radius from a center of the city and a selected radius from a centroid of the page.

11. A system comprising:

at least one processor; and

a memory storing instructions that, when executed by the at least one processor, cause the system to perform:

applying a spectral clustering technique to at least a portion of a similarity graph to generate clusters of geographic sub-regions constituting geographic regions in a geographic area, wherein two geographic sub-regions, represented as vertices in the similarity graph, are linked through a connection in the similarity graph based on a condition relating to whether the two geographic sub-regions are within a selected number of nearest cities of one another, wherein the geographic sub-regions are cities, wherein the connection is weighted based on a product of a first factor and a second factor, the first factor associated with a distance between the two geographic sub-regions and the second factor associated with check-ins by users in the two geographic sub-regions;

performing a tf-idf technique to determine pages associated with a geographic region as potential local suggestions for a user associated with a geographic sub-region in the geographic region; and

presenting references to at least a portion of the pages as local suggestions to the user.

12. The system of claim 11 , wherein the geographic sub-regions are cities and the geographic regions are metropolitan areas including the cities.

13. The system of claim 11 , further comprising:

partitioning the similarity graph by country.

14. The system of claim 11 , wherein the geographic regions correspond to documents, pages relating to a geographic region correspond to terms in a document, and a number of users who like a page correspond to term frequency in the tf-idf technique.

15. The system of claim 11 , further comprising:

applying to the pages at least one condition relating to a desired degree of locality of a page in relation to a city to determine the at least a portion of the pages for which the references are presented as local suggestions to the user.

16. A non-transitory computer-readable storage medium including instructions that, when executed by at least one processor of a computing system, cause the computing system to perform a method comprising:

applying a spectral clustering technique to at least a portion of a similarity graph to generate clusters of geographic sub-regions constituting geographic regions in a geographic area, wherein two geographic sub-regions, represented as vertices in the similarity graph, are linked through a connection in the similarity graph based on a condition relating to whether the two geographic sub-regions are within a selected number of nearest cities of one another, wherein the geographic sub-regions are cities, wherein the connection is weighted based on a product of a first factor and a second factor, the first factor associated with a distance between the two geographic sub-regions and the second factor associated with check-ins by users in the two geographic sub-regions;

performing a tf-idf technique to determine pages associated with a geographic region as potential local suggestions for a user associated with a geographic sub-region in the geographic region; and

presenting references to at least a portion of the pages as local suggestions to the user.

17. The non-transitory computer-readable storage medium of claim 16 , wherein the geographic sub-regions are cities and the geographic regions are metropolitan areas including the cities.

18. The non-transitory computer-readable storage medium of claim 16 , further comprising:

partitioning the similarity graph by country.

19. The non-transitory computer-readable storage medium of claim 16 , wherein the geographic regions correspond to documents, pages relating to a geographic region correspond to terms in a document, and a number of users who like a page correspond to term frequency in the tf-idf technique.

20. The non-transitory computer-readable storage medium of claim 16 , further comprising:

applying to the pages at least one condition relating to a desired degree of locality of a page in relation to a city to determine the at least a portion of the pages for which the references are presented as local suggestions to the user.