Determining a location and area of a place based on distances between the first mean and check in locations

1. A method comprising, by one or more computing devices:

accessing a social graph comprising a plurality of nodes and a plurality of edges connecting the nodes, each of the edges between two of the nodes representing a single degree of separation between them, the nodes comprising:

a plurality of user nodes corresponding to a plurality of users of an online social network; and

a plurality of concept nodes corresponding to a plurality of places;

accessing geographic location data for a plurality of check-in locations associated with a place, wherein each of the check-in locations corresponds to an edge of the social graph corresponding to a check-in activity between a user node of a user and a concept node of the place;

calculating a first mean of the plurality of check-in locations;

selecting a subset of the check-in locations based on distances between the first mean and the check-in locations; and

determining a central location and at least a portion of a perimeter of the place based on the subset of the check-in locations.

2. The method of claim 1 , wherein calculating the first mean comprises weighting one or more of the check-in locations based on their recency, accuracy, trustworthiness, or carrier reliability.

3. The method of claim 2 , wherein the weighting of one or more of the check-in locations comprises an exponential decay function.

4. The method of claim 1 , wherein a check-in location comprises a geographic location of a check-in by a user of a social-networking system.

5. The method of claim 1 , wherein the central location is a center or a centroid.

6. The method of claim 1 , wherein calculating the first mean comprises:

projecting two-dimensional geographic coordinates of the check-in locations onto a three-dimensional sphere;

calculating a second mean in each dimension of the three-dimensional sphere; and

calculating the first mean by projecting the one or more of the second means onto a two-dimensional surface.

7. The method of claim 1 , wherein the distances between the first mean and the check-in locations are calculated using great-circle distances.

8. The method of claim 1 , wherein determining the central location and at least the portion of the perimeter comprises:

constructing a cumulative distribution function for the subset of the check-in locations with weighted percentile buckets in distances from the central location; and

determining the perimeter based at least in part on one or more characteristics of the cumulative distribution function.

9. The method of claim 1 , wherein, for each of one or more of the check-in locations, the place associated with the check-in location was selected by a user from a plurality of places presented to the user based on a determined geographic location of the user.

10. One or more computer-readable non-transitory storage media embodying software that is operable when executed to:

access a social graph comprising a plurality of nodes and a plurality of edges connecting the nodes, each of the edges between two of the nodes representing a single degree of separation between them, the nodes comprising:

a plurality of user nodes corresponding to a plurality of users of an online social network; and

a plurality of concept nodes corresponding to a plurality of places;

access geographic location data for a plurality of check-in locations associated with a place, wherein each of the check-in locations corresponds to an edge of the social graph corresponding to a check-in activity between a user node of a user and a concept node of the place;

calculate a first mean of the plurality of check-in locations;

select a subset of the check-in locations based on distances between the first mean and the check-in locations; and

determine a central location and at least a portion of a perimeter of the place based on the subset of the check-in locations.

11. The non-transitory storage media of claim 10 , wherein to calculate the first mean, the software is operable when executed to weight one or more of the check-in locations based on their recency, accuracy, trustworthiness, or carrier reliability.

12. The non-transitory storage media of claim 11 , wherein the weighting of one or more of the check-in locations comprises an exponential decay function.

13. The non-transitory storage media of claim 10 , wherein a check-in location comprises a geographic location of a check-in by a user of a social-networking system.

14. The non-transitory storage media of claim 10 , wherein the central location is a center or a centroid.

15. The non-transitory storage media of claim 10 , wherein to calculate the first mean, the software is operable when executed to:

project two-dimensional geographic coordinates of the check-in locations onto a three-dimensional sphere;

calculate a second mean in each dimension of the three-dimensional sphere; and

calculate the first mean by projecting the one or more of the second means onto a two-dimensional surface.

16. The non-transitory storage media of claim 10 , wherein the distances between the first mean and the check-in locations are calculated using great-circle distances.

17. The non-transitory storage media of claim 10 , wherein to determine the central location and at least the portion of the perimeter, the software is operable when executed to:

construct a cumulative distribution function for the subset of the check-in locations with weighted percentile buckets in distances from the central location; and

determine the perimeter based at least in part on one or more characteristics of the cumulative distribution function.

18. The non-transitory storage media of claim 10 , wherein, for each of one or more of the check-in locations, the place associated with the check-in location was selected by a user from a plurality of places presented to the user based on a determined geographic location of the user.

19. An apparatus comprising:

one or more processors; and

one or more computer-readable non-transitory storage media embodying instructions operable, when executed by the processors, to cause the processors to:

access a social graph comprising a plurality of nodes and a plurality of edges connecting the nodes, each of the edges between two of the nodes representing a single degree of separation between them, the nodes comprising:

a plurality of user nodes corresponding to a plurality of users of an online social network; and

a plurality of concept nodes corresponding to a plurality of places;

access geographic location data for a plurality of check-in locations associated with a place, wherein each of the check-in locations corresponds to an edge of the social graph corresponding to a check-in activity between a user node of a user and a concept node of the place;

calculate a first mean of the plurality of check-in locations;

select a subset of the check-in locations based on distances between the first mean and the check-in locations; and

determine a central location and at least a portion of a perimeter of the place based on the subset of the check-in locations.

20. The apparatus of claim 19 , wherein to calculate the first mean, the instructions are operable, when executed by the processors, to cause the processors to weight one or more of the check-in locations based on their recency, accuracy, trustworthiness, or carrier reliability.

21. The apparatus of claim 19 , wherein the weighting of one or more of the check-in locations comprises an exponential decay function.

22. The apparatus of claim 19 , wherein a check-in location comprises a geographic location of a check-in by a user of a social-networking system.

23. The apparatus of claim 19 , wherein, for each of one or more of the check-in locations, the place associated with the check-in location was selected by a user from a plurality of places presented to the user based on a determined geographic location of the user.