Multi-objective server placement determination

摘要

Methods and apparatus for determining recommended geographic server locations for online social networks by attempting to minimize user-server latency and inter-user communications latency. In an embodiment, geographic and relationship information for a plurality of users is acquired. The plurality of users may belong to one or more networks. The acquired information is transformed into a graph. A first plurality of clusters is generated with a first clustering algorithm. A second plurality of clusters is generated by iteratively examining pairs of the first plurality clusters, and swapping nodes between the examined clusters if it will reduce a total cut weight of the graph and locate each pair of nodes within a defined maximum distance from the centroid of the target cluster. In an embodiment, a method uses a joint analysis approach based upon characteristics of a plurality of existing networks.

主权项

1. A method in a computing device for determining a plurality of server placement locations, the method comprising:
generating, by the computing device, a first plurality of clusters by performing a first clustering algorithm on a graph, wherein the graph includes a plurality of nodes representing a plurality of users and a plurality of edges connecting the plurality of nodes according to known relationships between the plurality of users, wherein each edge of the plurality of edges includes an edge weight, wherein each cluster of the first plurality of clusters includes a centroid and a set of one or more nodes of the plurality of nodes, wherein each node of the set of nodes is included in only one cluster of the first plurality of clusters; generating, by the computing device, a second plurality of clusters by performing a second clustering algorithm comprising,
for each pair of clusters of one or more pairs of clusters of the first plurality of clusters, swapping nodes between the pair of clusters when a swap will:
reduce a total cut weight of the graph, wherein the total cut weight is a sum of edge weights of all edges of the plurality of edges that connect nodes in different clusters, andlocate each node of the pair of nodes, when swapped to the other cluster of the pair of clusters, within a defined maximum distance from the centroid of the other cluster; and causing, by the computing device, information describing geographic locations associated with centroids of the second plurality of clusters to be presented to a user as the plurality of server placement locations.