Determining a location and area of a place

1. A method comprising:

by a computing device, 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;

by the computing device, determining a particular place corresponding to a particular concept node, the particular place having a corresponding associated location and a perimeter;

by the computing device, receiving a set of check-ins associated with the particular place, wherein each of the check-ins corresponds to a geographic location and an edge of the social graph corresponding to a check-in activity between a user node of a user and the particular concept node; and

by the computing device, determining whether to update the associated location and the perimeter of the particular place based on at least a subset of the check-ins, wherein the associated location is a mean of the geographic locations of the check-ins, the mean being calculated at least in part by weighting one or more of check-in locations based on a level of trustworthiness of each user associated with the check-in locations, and wherein the level of trustworthiness of each user is based on current and past actions of the user corresponding to one or more of the check-in locations.

2. The method of claim 1 , wherein the weighting of one or more of the check-in locations is further based on their recency, accuracy, or carrier reliability.

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

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

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

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

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

5. The method of claim 1 , wherein the associated location represents a center or a centroid of a geographic region corresponding to the particular place.

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

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

constructing a cumulative distribution function for a 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.

8. The method of claim 1 , wherein the perimeter of the particular place is based at least in part on a radius around the associated location, wherein a majority of a subset of check-ins corresponds to a geographic location within the radius.

9. The method of claim 1 , wherein the particular place corresponds to an arbitrary-shaped area, and the perimeter is determined at least in part by a minimum convex hull, the minimum convex hull enclosing the check-in geographic locations.

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;

determine a particular place corresponding to a particular concept node, the particular place having a corresponding associated location and a perimeter;

receive a set of check-ins associated with the particular place, wherein each of the check-ins corresponds to a geographic location and an edge of the social graph corresponding to a check-in activity between a user node of a user and the particular concept node; and

determine whether to update the associated location and the perimeter of the particular place based on at least a subset of the check-ins, wherein the associated location is a mean of the geographic locations of the check-ins, the mean being calculated at least in part by weighting one or more of check-in locations based on a level of trustworthiness of each user associated with the check-in locations, and wherein the level of trustworthiness of each user is based on current and past actions of the user corresponding to one or more of the check-in locations.

11. The media of claim 10 , wherein the weighting of one or more of the check-in locations is further based on their recency, accuracy, or carrier reliability.

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

13. The media of claim 10 , wherein calculating the mean comprises:

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

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

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

14. The media of claim 10 , wherein the associated location represents a center or a centroid of a geographic region corresponding to the particular place.

15. The media of claim 10 , wherein the distances between the mean and the check-in locations are calculated using great-circle distances.

16. A system 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;

determine a particular place corresponding to a particular concept node, the particular place having a corresponding associated location and a perimeter;

receive a set of check-ins associated with the particular place, wherein each of the check-ins corresponds to a geographic location and an edge of the social graph corresponding to a check-in activity between a user node of a user and the particular concept node; and

determine whether to update the associated location and the perimeter of the particular place based on at least a subset of the check-ins, wherein the associated location is a mean of the geographic locations of the check-ins, the mean being calculated at least in part by weighting one or more of check-in locations based on a level of trustworthiness of each user associated with the check-in locations, and wherein the level of trustworthiness of each user is based on current and past actions of the user corresponding to one or more of the check-in locations.

17. The system of claim 16 , wherein the weighting of one or more of the check-in locations is further based on their recency, accuracy, or carrier reliability.

18. The system of claim 16 , wherein the weighting of one or more of the check-in locations comprises an exponential decay function.

19. The system of claim 16 , wherein the associated location represents a center or a centroid of a geographic region corresponding to the particular place.

20. The system of claim 16 , wherein the distances between the mean and the check-in locations are calculated using great-circle distances.