Method and game-based system for partitioning of streaming graph

A game-based method for streaming-graph partitioning, the method comprising:

• partitioning a streaming graph using one or more processors, the one or more processors being configured to:
• read an edge streaming having a predetermined number of edges in an unpartitioned area of the streaming graph as a sub-graph;
• based on a first pre-partitioning model, pre-partition the edges of the sub-graph to at least two partition blocks as an initial state of a game process;
• and
• sequentially select an optimal partition block for each edge of the sub-graph through the game process until the game process becomes convergent;
• wherein the game process comprises:
• considering a set of all the partition blocks as a set of strategy selections, in every round of the game process, calculating for the current edge that is under strategy selection currently its optimal strategy selection in the present round according to partitioning situations of the other edges in a current partitioning result and according to a predetermined cost function, and when the current edge is not in the optimal partition block corresponding to the optimal strategy selection, moving the current edge to its optimal partition block and correspondingly updating the current partitioning result as a basis of strategy selection for the next edge and performing the game process again with the latest current partitioning result after the strategy selections for all the edges of the sub-graph has been done;
• wherein the predetermined cost function is:
• c
• 
• (
• e
• (
• u
• ,
• v
• )
• ,
• p
• i
• )
• =
• α
• 
• 
• β
• 
• 
• l
• 
• (
• p
• i
• )
• +
• (
• 1
• -
• α
• )
• 
• (
• 1
• d
• 
• (
• p
• i
• ,
• u
• )
• +
• 1
• d
• 
• (
• p
• i
• ,
• v
• )
• )
• ;
• and wherein pmin=argmini∈[1,k]c(e(u,v), pi) is the optimal partition block where the value of the cost function is minimal, and when the edge e(u,v) is in a partition block that is not its optimal partition block, move the edge e(u,v) from the partition block it has been in to its optimal partition block;
• wherein e(u,v) denotes the edge connecting vertex u and vertex v, pi denotes the partition block numbered as i, i∈[1,k], k is the number of the partition blocks, wherein k≥2 and is an integer, α denotes relative importance between a load balance factor and a replication factor, wherein α∈(0,1), β denotes a factor normalization parameter, l(pi) denotes the number of edges in partition block pi, d(pi, u) denotes the degree of vertex u in partition block pi, and d(pi, v) denotes the degree of vertex v in partition block pi.