Joins and aggregations on massive graphs using large-scale graph processing

A method comprising:

• retrieving, by at least one hardware processor, a social graph for a social networking service, the social graph including a first plurality of nodes corresponding to members of the social networking service and a first plurality of edges connecting the first plurality of nodes;
• partitioning, by at least one hardware processor, the first plurality of nodes into a first plurality of partitions, the first plurality of partitions being determined according to a source key associated with the first plurality of nodes;
• partitioning, by at least one hardware processor, the first plurality of nodes into a second plurality of partitions, the second plurality of partitions being determined according to a destination key associated with the first plurality of nodes;
• assigning, by at least one hardware processor, each of the first plurality of partitions to a work unit of a first plurality of work units, wherein the first plurality of work units are determined according to a constraint on computing resources;
• assigning, by at least one hardware processor, each of the second plurality of partitions to a work unit of a second plurality of work units;
• and
• determining, by at least one hardware processor, a second plurality of nodes from the social graph using at least one pair of work units constructed from a first work unit selected from the first plurality of work units and a second work unit selected from the second plurality of work units, the second plurality of nodes including at least one node representing a second-degree connection for a member of the social networking service.

A machine-readable medium storing computer-executable instructions that, when executed by at least one hardware processor, causes a system to perform a plurality of operations, the plurality of operations comprising:

• retrieving a social graph for a social networking service, the social graph including a first plurality of nodes corresponding to members of the social networking service and a first plurality of edges connecting the first plurality of nodes;
• partitioning the first plurality of nodes into a first plurality of partitions, the first plurality of partitions being determined according to a source key associated with the first plurality of nodes;
• partitioning the first plurality of nodes into a second plurality of partitions, the second plurality of partitions being determined according to a destination key associated with the first plurality of nodes;
• assigning each of the first plurality of partitions to a work unit of a first plurality of work units, wherein the first plurality of work units are determined according to a constraint on computing resources;
• assigning each of the second plurality of partitions to a work unit of a second plurality of work units;
• and
• determining a second plurality of nodes from the social graph using at least one pair of work units constructed from a first work unit selected from the first plurality of work units and a second work unit selected from the second plurality of work units, the second plurality of nodes including at least one node representing a second-degree connection for a member of the social networking service.