[NetworkX] Benchmark of memory footprint, IO, and performance

## 1. Systems
| system | single or distributed | multi-threads | performance or flexibility | static or dynamic |
| -------- | -------- | -------- | ------- | ---- |
| NetworkX | single | no | flexibility | dynamic |
| graphscope.nx | distributed | yes | in-between | dynamic |

## 2. Memory Consumption
Use **undirected Erdõs-Rényi random graphs, G(n, m)**, where `n` represents the number of nodes, and `m` represents the number of edges in the graph.

| Graph size | Memory usage [MB] | - |
| -------- | -------- | ------ |
| (Nodes, Edges) | NetworkX | graphscope.nx |
| (1M, 10M) | 3,789 | 4,474 |
| (1M, 100M) | 33,280 | 21,196 |
| (10M, 100M) | 36,864 | |
| (50M, 500M) | 174,080 | 116,326 |

## 3. Graph basic Operations
We measure execution times of basic graph operations for an **Erdõs-Rényi random graph G(n, m)**.

### generation graph execution time(seconds)
| Graph size | NetworkX | graphscope.nx |
| -------- | -------- | -------- |
| (1M, 10M) | 45.8 | 228 |
| (1M, 100M) | 482s | 2920 |

### edge existence operation (seconds)
Edges are random, the number of tests is equal to the number of total edges in the graph.
| Graph size | Execution time [seconds] | - |
| -------- | -------- | ------ |
| (Nodes, Edges) | NetworkX |graphscope.nx |
| (1M, 10M) | 20.027 | 36,541 |

### delete nodes operation (seconds)
Execution times for deleting 10% of nodes and their corresponding edges from **Erdős-Rényi random graph G(1M, 10M).**

| Graph size | NetworkX | graphscope.nx(one by one) | graphscope.nx(batch) |
| -------- | -------- | -------- | ------- |
| (1M, 10M) | 2.79812 | 0.078031 * 100000 | 0.83415 + 3.97145( 0.61 + 3.36) = 4.8056 \n preprocess + op_eval |

#### delete all nodes
- DynamicFragment: 9.36018s = 0.75626(python) + 8.60392(engine)
- DynamicFragment with MutableCSR: 0.85872s = 0.75626 + 0.102458

### adding nodes operation (seconds)
Execution times for adding 10% of random generated nodes to **Erdős-Rényi random graph G(1M, 10M).**

| Graph size | NetworkX | graphscope.nx |
| -------- | -------- | -------- |
| (1M, 10M) | 0.09270 | 0.88083 + 1.61759(0.85 + 0.75) = 2.498424 \n preprocess + op.eval |

- DynamicFragment: 0.1311659s = 0.09925(python) + 0.03191(engine)
- DynamicFragment with MutableCSR: 0.14536s = 0.09925 + 0.046112

### delete edges operation (seconds)
Execution times for deleting 10% of edges from **Erdős-Rényi random graph G(1M, 10M).**

| Graph size | NetworkX | graphscope.nx(one by one) | graphscope.nx(batch) |
| -------- | -------- | -------- | -------- |
| (1M, 10M) | 2.11016 | 0.083911 * 1000000 | 4.2661 + 11.19209(3.44 + 7.75) = 15.45819 \n preprocess + op.eva |

#### Refactor
- DynamicFragment: 2.93367s = 0.89577(python) + 2.0379(engine)
- DynamicFragment with MutableCSR: 2.16236s = 0.89577(python) + 1.26659(engine)
### adding edges operation (seconds)
Execution times for adding 10% of random generated edges to **Erdős-Rényi random graph G(1M, 10M).**

| Graph size | NetworkX | graphscope.nx |
| -------- | -------- | -------- |
| (1M, 10M) | 3.1571 |0.3(append) + 0.35(json.dumps) + 5.7(engine) = 6.35 |
| (1M, 10M) add with data { weight=0.5, type="edge"} | 3.4257 | 0.5243 (append) + 1.235(json dumps) + 6.45（engine) = 8.2153|
| (1M, 10M) add with random edges and new nodes | 10.257 | 0.355(append) + 0.345(json dumps) + 6.524(engine) = 7.224 |
| (50M, 500M) | 212.259021 | 17.7618(append) + 18.1837(json.dumps) + 165.252(engine) = 201.196|

#### profiling of graphscope.nx `add_edge` operation
- op prepare (5.5188) = 3.2486 (edges dumps to json and append to cache) + 1.14379(put edges to proto payload) + 1.12640(attrs to dict)
- op.eval (14.9556) = 3.5524(rpc: client to engine) + 11.4032(op exec in engine)
- op exec in engine(11.4032) = 0.042 (get edges from op params) + 8.1323 (parse from edge json and transform to gid) + 2.97676( insert the edges)

#### optimization 1： dumps the cache to one json str
- **op prepare(0.823)** = 0.292(append to cache time) + 0.3614( dumps to json) + 0.01005(puts to proto payload)
- op.eval(11.48919) = **0.3(rpc: client to engine)** + 11.0829(op execution time in engine)
- op execution in engine(11.0829) = 0.0032(get json string from op params) + 5.19305(parse json to dynamic) + 2.66777(process the edges: oid to gid) + 2.96967 (insert the edges)

#### optimization 2: parse json with nlomann-json
- op execution in engine( 5.70104) = 0.00296(get json string from op params) + **0.438243 (parse json with nlomann-json)** + 1.98785(convert json to dynamic and process the edges) + 3.01865(insert the edges)

#### rapidjson (engine)
- **0.05009 (parse json with rapidjson)** + 1.5485(convert json to dynamic and process the edges) + 3.13879(insert the edges)

#### full rapidjson (engine)
- 0.05009 (parse json with rapidjson) + 0.23190(process the edges) + 2.47478( insert the edges)

#### Refactor (e2e)
- DynamicFragment: 3.97089s = 1.18806(python) + 2.782837(engine)
- DynamicFragment with MutableCSR: 2.30002 = 1.18806(python) + 1.11197(engine)

### json.dumps vs pickle.dumps
| Edge size | json.dumps | pickle.dumps |
| -------- | --------- | ---------- |
| 1M | 0.3614 | 0.47275 |
| 1M with data {weight=0.5, type="edge"} | 1.235 | 0.6837 |
|50M| 18.1837 | 19.79538 |

## 4. Graph Algorithms

### [ego-twitter](https://snap.stanford.edu/data/ego-Twitter.html)
| algorithm | NetworkX | graphscope.nx (built-in) | graphscope.nx (forward) |
| --------- | ----------- | ------------- | ----------- |
| pagerank | 6.03 | 2.25 | 413 |
| sssp length | 1.64 | 4.73s | 206 |
| average clustering coefficient | 85 | 2.98 | |
| closeness_centrality | > 15h | | |
| betweeness centrality | >15h | |

### [LiveJournal](https://snap.stanford.edu/data/soc-LiveJournal1.html)
| algorithm | NetworkX | graphscope.nx (built-in) | graphscope.nx (forward) |
| --------- | ----------- | ------------- | ----------- |
| pagerank | | | |
| sssp length | | | |
| average clustring coefficient | | | |
| closeness_centrality | | | |
| betweeness centrality | | | |