Lets assume there is no upper limit on number of machines.
Here are the goals of partition:
Each node in the graph has a weight. There is an upper limit on total weight stored on a machine. All the nodes are not fitting on one machine, hence we are starting with partition.
When we store an edge on a machine, then the weight of both nodes is being placed on that machine.
All machines are same and have a capacity
Each node should have all its edges on a single machine. If sum of weights of all neighbors of a node is greater than
c, only then its data should be split on more than one machine. In which case, minimize the number of machines to which data is split.
Edge data can be repeated across machines. This relaxation is necessary to satisfy the condition that each node of the graph should have all its neighbors information co-located on a single machine in the network. (unless not possible)
Minimize the total number of machines used.
Corollary: If each node's edges data can be fitted on one machine, then to access any node's edges information we will only have to access one machine on the network.