Graph Analytics with Python -Graph Generation-
Tags: python, datascience, graph, networkx
Published: 2021-01-18 05:58:28

<!--この記事では，複雑ネットワークのような様々なグラフの生成について説明を行い，生成したグラフをメトリクスを用いて評価する．なおグラフ生成の前に必要なライブラリのロードと密度およびクラスタ係数を評価する関数を定義する．-->
In this article, we explain how to generate various types of graphs such as complex networks, and evaluate the generated graphs using metrics. Before generating the graphs, we load the necessary libraries and define functions to evaluate the density and cluster coefficients.

```Python
# Load Module
import networkx as nx
import matplotlib.pyplot as plt

# Define function to quantify Cluster Coefficient 
def draw_metrics(G, pos):
  nodes = nx.draw_networkx_nodes(G, pos, node_size=200,node_color="#00C98D")
  labels = nx.draw_networkx_labels(G, pos)
  edges = nx.draw_networkx_edges(G, pos)
  plt.title(["density:{:.5}".format(nx.density(G)), "clustering coefficient:{:.5}".format(nx.average_clustering(G))])
  plt.axis("off")
  plt.show()
```

# Watts Strogatz Graph

<!--ワッツストロガッツグラフとは，全ての頂点を近隣のx個の頂点と格子状に辺で繋ぎ，それらの辺を一定の確率に基づいてランダムに張り替えることで生成されるグラフのことを指す．この確率を0にすると格子，1にするとランダムグラフとなり，0.1前後にすると格子とランダムグラフを併せ持つグラフの生成が可能となる．ワッツストロガッツグラフではショートカットが形成されることで平均最短距離は概ねスモールワールド性を満足する．-->
A Watts-Strogatz graph is a graph generated by connecting all vertices to x neighboring vertices in a lattice with edges, and randomly replacing these edges based on a certain probability. 
When the probability is set to 0, the graph is a lattice, when it is set to 1, it is a random graph, and when it is set to around 0.1, it is possible to generate a graph that is both a lattice and a random graph. 
In Watts-Strogatz graphs, shortcuts are formed, and the average shortest distance generally satisfies the small-world property.

```Python
ws = nx.watts_strogatz_graph(10,5,0.05)
pos = nx.spring_layout(ws)
draw_metrics(ws, pos)
```

![Alt Text](https://dev-to-uploads.s3.amazonaws.com/i/2ccn23f11eld6ol4ricx.png)

# Barabasi Albert Graph

<!--バラバーシアルベルトグラフとは，スケールフリー性をもつグラフであり，既存の次数の大きな頂点に対して新しい辺が高い確率で加わることで頂点がハブへと成長するグラフのことを指す．バラバーシアルバートグラフの生成アルゴリズムは，まずm個の頂点からなる完全グラフKmを用意する．ここに新しい頂点を一個追加し，その頂点からすでに存在するm個の頂点に対して辺を張ることで生成される．-->
A Barabási-Albert graph is a scale-free graph in which vertices grow into hubs by adding new edges with high probability to existing vertices with a large degree. The algorithm for generating a Barabási-Albert graph begins with a complete graph Km consisting of m vertices. A new vertex is added to the complete graph, and an edge is added from that vertex to each of them vertices that already exist.

```Python
ba = nx.barabasi_albert_graph(10,2)
pos = nx.spring_layout(ba)
draw_metrics(ba, pos)
```

![Alt Text](https://dev-to-uploads.s3.amazonaws.com/i/bagek6geyugagjwsj4ro.png)

# Conclusion
<!--本記事では，ワッツストロガッツグラフとバラバーシアルベルトグラフを生成して，密度とクラスタ係数を測定した．この他にも様々な複雑ネットワークの生成が可能なため，下記リンクを参考に生成してみるとグラフの特性を理解しやすい．-->
In this article, we generated Watts-Strogatz and Barabási-Albert graphs to measure the density and cluster coefficients. Since it is possible to generate various other complex networks, it is easy to understand the characteristics of the graphs by referring to the links below.

# Link
[Networkx: Graph generators](https://networkx.org/documentation/stable//reference/generators.html)