简体中文|English

Introduction

An algorithm of huge graph aggregation based on metis. You can download the paper here.

Developing this algorithm with my partner, who has proposed some effective ideas about finding twins, finding relatives and contraction. The original repository will be opened until the paper is published, therefore she is not a contributor in this repository.

• Algorithm: The python code of algorithm.
• compare: Performance comparison with current libraries.

Environment

• python: 3.6
• graph-tool: 2.33( recommend install it byconda)

The environment of the compared algorithm

• networkx: 2.3
• metis: 0.2a4
• pymetis: 2020.1

Results

Process the graph with tens of thousands of nodes as follows:

Contract to one hundred nodes:

Contract to seven nodes:

Print the radio of load balance and edge cut

After one contract phase, we can print the load balance and edge cut:

Performance

Our algorithm is a lot better than metis and slightly slower than pymetis, here is more details.

Document of how to implement

You can find the document about how to implement this algorithm. We use some data structures and programming skills to decrease time and space complexity such as bucket, hash, queue, list and dictionary.