# US 2019/0244402 A1 · Method and game-based system for partitioning of streaming graph

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 2019/0244402 A1
- Document ID: US20190244402A1
- Status: Published application
- Kind: A1
- Application number: 16/237,053
- Filed: 2018-12-31
- Published: 2019-08-08
- Earliest claimed: 2018-02-02
- Assignees: Huazhong University of Science and Technology
- Applicants: Huazhong University of Science and Technology
- Inventors: Qiangsheng HUA; Xuanhua Shi; Hai Jin; Yangyang Li
- Web page: https://patentgrep.com/patent/US20190244402A1

## CPC

- G06T 11/26: Drawing of charts or graphs
- G06F 16/2465: {Query processing support for facilitating data mining operations in structured databases}
- G06F 16/9024: {Graphs; Linked lists (G06F16/9027 takes precedence)}
- G06F 2216/03: Data mining
- G06T: IMAGE DATA PROCESSING OR GENERATION, IN GENERAL
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)

## Abstract

The present invention relates to a game-based method and system for streaming-graph partitioning, the method comprises: 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, the disclosed method and system can partition streaming graph using local information only, without loading the whole streaming graph into the memory, thus have good scalability and support dynamic graph partitioning; the disclosed partitioning method and system can provide better partitioning results.

## Claims

### Claim 1

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.

### Claim 2 (depends on 1)

The method of claim 1, wherein the game process further comprises: if in one round of the game process, none of the edges are moved: determining that the present game process is convergent and partitioning of the sub-graph is completed: and taking the current partitioning result on which the present round of the game process is based as a final partitioning result.

### Claim 3 (depends on 2)

The method of claim 2, wherein the step of 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 comprises: the strategy selection of the current edge depending on partitioning situations of all the edges other than the current edge in the updated current partitioning result.

### Claim 4 (depends on 3)

The method of claim 3, wherein in the factor normalization parameter
β
∈
[

M


E

2
,
k
2


M


E

2
]
,
|M| is the number of vertexes in the sub-graph, and |E| is the number of edges in the sub-graph.

### Claim 5 (depends on 3)

The method of any of claim 3, wherein the first pre-partitioning model successively generates a random number R for the edge of the sub-graph according to a random partitioning rule, and partitions the edge to partition block pR that is numbered corresponding to the random number, wherein R∈[1,k] and is an integer, k is the number of the partition blocks, and k≥2 and is an integer.

### Claim 6 (depends on 5)

The method of claim 5, wherein the one or more processors are further configured to:
acquire a plurality of the sub-graphs and the final partitioning results of these sub-graphs to form a train set; use the train set to train a second pre-partitioning model; and after the training has been conducted for a predetermined number of times, use the second pre-partitioning model instead of the first pre-partitioning model to pre-partition the sub-graph to be partitioned.

### Claim 7 (depends on 3)

The method of any of claim 3, wherein the step of reading the edge streaming having the predetermined number of edges in the unpartitioned area of the streaming graph as the sub-graph is performed according to a stream processing model.

### Claim 8

A game-based system for streaming-graph partitioning, comprising; 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 a 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; and 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, moving 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.

### Claim 9 (depends on 8)

The system of claim 8, wherein the game process further comprises: if in one round of the game process, none of the edges are moved: determining that the present game process is convergent and partitioning of the sub-graph is completed; and taking the current partitioning result on which the present round of the game process is based as a final partitioning result.
