Louvain Paritition Demo - 2023.2 English

Vitis Libraries

Release Date
2023-12-20
Version
2023.2 English

To get scalability for graph size and get high-level concurrency for multi compute units on multi boards, we provided louvainPartition API with two partition methods which no communication between subgraphs processing.

  • Linear louvain partition mothed, simply dived vertexes linearly, and save the connection edges between subgraphs to ghost edges. So it is faster in low bandwidth graph but result more ghost edges.
  • BFS louvain partition mothed, dived vertexes by BFS method, and save the connection edges between subgraphs to ghost edges. Its performance of modularity result keeps the same level between high and low bandwidth input graph.

Linear partition achieve on the high bandwidth and low bandwidth graph is shown as the Figure 1. Linear partition is not suitable for High bandwidth graph.

Figure 1 Linear partition achieve on the high bandwidth and low bandwidth graph

In this demo, two methods can be switched by corresponding commands. The comparison of input and output is shown as the table 1.

Table 1 input and output comparison for different partition algorithms
  Linear paritition BFS partition
input graph *.mtx, *.txt … *.mtx, *.txt …
input commend -create_alveo_partitions -create_alveo_BFS_partitions
output project name.par.proj name.par.proj
output header file *.par.src, *.par.parlv *.par.src, *.par.parlv *.bfs.adj
output subgraph name_000.par … name_000.par …