# 一文综述数据科学家应该了解的5个图算法

## 1. 连通分支

### 代码

```edgelist = [['Mannheim', 'Frankfurt', 85], ['Mannheim', 'Karlsruhe', 80], ['Erfurt', 'Wurzburg', 186], ['Munchen', 'Numberg', 167], ['Munchen', 'Augsburg', 84], ['Munchen', 'Kassel', 502], ['Numberg', 'Stuttgart', 183], ['Numberg', 'Wurzburg', 103], ['Numberg', 'Munchen', 167], ['Stuttgart', 'Numberg', 183], ['Augsburg', 'Munchen', 84], ['Augsburg', 'Karlsruhe', 250], ['Kassel', 'Munchen', 502], ['Kassel', 'Frankfurt', 173], ['Frankfurt', 'Mannheim', 85], ['Frankfurt', 'Wurzburg', 217], ['Frankfurt', 'Kassel', 173], ['Wurzburg', 'Numberg', 103], ['Wurzburg', 'Erfurt', 186], ['Wurzburg', 'Frankfurt', 217], ['Karlsruhe', 'Mannheim', 80], ['Karlsruhe', 'Augsburg', 250],["Mumbai", "Delhi",400],["Delhi", "Kolkata",500],["Kolkata", "Bangalore",600],["TX", "NY",1200],["ALB", "NY",800]]
```

```g = nx.Graph()
for edge in edgelist:
```

```for i, x in enumerate(nx.connected_components(g)):
print("cc"+str(i)+":",x)
------------------------------------------------------------
cc0: {'Frankfurt', 'Kassel', 'Munchen', 'Numberg', 'Erfurt', 'Stuttgart', 'Karlsruhe', 'Wurzburg', 'Mannheim', 'Augsburg'}
cc1: {'Kolkata', 'Bangalore', 'Mumbai', 'Delhi'}
cc2: {'ALB', 'NY', 'TX'}
```

## 2. 最短路径

### 应用

• 在沃尔玛商店中，有不同的过道以及过道之间的距离，您想找到从过道A到过道D的最短途径。

### 代码

```print(nx.shortest_path(g, 'Stuttgart','Frankfurt',weight='weight'))
print(nx.shortest_path_length(g, 'Stuttgart','Frankfurt',weight='weight'))
--------------------------------------------------------
['Stuttgart', 'Numberg', 'Wurzburg', 'Frankfurt']
503
```

```for x in nx.all_pairs_dijkstra_path(g,weight='weight'):
print(x)
--------------------------------------------------------
('Mannheim', {'Mannheim': ['Mannheim'], 'Frankfurt': ['Mannheim', 'Frankfurt'], 'Karlsruhe': ['Mannheim', 'Karlsruhe'], 'Augsburg': ['Mannheim', 'Karlsruhe', 'Augsburg'], 'Kassel': ['Mannheim', 'Frankfurt', 'Kassel'], 'Wurzburg': ['Mannheim', 'Frankfurt', 'Wurzburg'], 'Munchen': ['Mannheim', 'Karlsruhe', 'Augsburg', 'Munchen'], 'Erfurt': ['Mannheim', 'Frankfurt', 'Wurzburg', 'Erfurt'], 'Numberg': ['Mannheim', 'Frankfurt', 'Wurzburg', 'Numberg'], 'Stuttgart': ['Mannheim', 'Frankfurt', 'Wurzburg', 'Numberg', 'Stuttgart']})

('Frankfurt', {'Frankfurt': ['Frankfurt'], 'Mannheim': ['Frankfurt', 'Mannheim'], 'Kassel': ['Frankfurt', 'Kassel'], 'Wurzburg': ['Frankfurt', 'Wurzburg'], 'Karlsruhe': ['Frankfurt', 'Mannheim', 'Karlsruhe'], 'Augsburg': ['Frankfurt', 'Mannheim', 'Karlsruhe', 'Augsburg'], 'Munchen': ['Frankfurt', 'Wurzburg', 'Numberg', 'Munchen'], 'Erfurt': ['Frankfurt', 'Wurzburg', 'Erfurt'], 'Numberg': ['Frankfurt', 'Wurzburg', 'Numberg'], 'Stuttgart': ['Frankfurt', 'Wurzburg', 'Numberg', 'Stuttgart']})
```

## 3. 最小生成树（MST）

### 应用

• MST可应用于网络设计中，包括计算机网络，电信网络，运输网络，供水网络和电网（最初提出目的）。
• MST用于近似旅行商问题。
• 聚类 - 首先构造MST，然后使用群集间距离和群集内距离确定用于破坏MST中某些边的阈值。
• 图像分割 - 以像素为节点，像素之间的距离（基于某种相似性度量，颜色，强度等）的图形上构造一个MST。

### 代码

```# nx.minimum_spanning_tree(g) 返回一个图类型的实例
nx.draw_networkx(nx.minimum_spanning_tree(g))
```

## 4. Pagerank

### 应用

Pagerank可以在想要估计网络中节点重要性的地方使用。

• 它已被用于使用引文查找最具影响力的论文。
• 它可以用来对tweets进行排名，User和Tweets作为节点。如果用户A关注用户B，则在用户之间创建链接；如果用户对某条推文进行推荐，则在用户和推文之间创建链接。
• 推荐引擎

### 代码

```# 读取数据集
```

```pos = nx.spring_layout(fb)
import warnings
warnings.filterwarnings('ignore')
plt.style.use('fivethirtyeight')
plt.rcParams['figure.figsize'] = (20, 15)
plt.axis('off')
nx.draw_networkx(fb, pos, with_labels = False, node_size = 35)
plt.show()
```

FB用户图

```pageranks = nx.pagerank(fb)
print(pageranks)
------------------------------------------------------
{0: 0.006289602618466542,
1: 0.00023590202311540972,
2: 0.00020310565091694562,
3: 0.00022552359869430617,
4: 0.00023849264701222462,
........}
```

```import operator
sorted_pagerank = sorted(pageranks.items(), key=operator.itemgetter(1),reverse = True)
print(sorted_pagerank)
------------------------------------------------------
[(3437, 0.007614586844749603), (107, 0.006936420955866114), (1684, 0.0063671621383068295), (0, 0.006289602618466542), (1912, 0.0038769716008844974), (348, 0.0023480969727805783), (686, 0.0022193592598000193), (3980, 0.002170323579009993), (414, 0.0018002990470702262), (698, 0.0013171153138368807), (483, 0.0012974283300616082), (3830, 0.0011844348977671688), (376, 0.0009014073664792464), (2047, 0.000841029154597401), (56, 0.0008039024292749443), (25, 0.000800412660519768), (828, 0.0007886905420662135), (322, 0.0007867992190291396),......]
```

```first_degree_connected_nodes = list(fb.neighbors(3437))
second_degree_connected_nodes = []
for x in first_degree_connected_nodes:
second_degree_connected_nodes+=list(fb.neighbors(x))
second_degree_connected_nodes.remove(3437)
second_degree_connected_nodes = list(set(second_degree_connected_nodes))
subgraph_3437 = nx.subgraph(fb,first_degree_connected_nodes+second_degree_connected_nodes)
pos = nx.spring_layout(subgraph_3437)
node_color = ['yellow' if v == 3437 else 'red' for v in subgraph_3437]
node_size =  [1000 if v == 3437 else 35 for v in subgraph_3437]
plt.style.use('fivethirtyeight')
plt.rcParams['figure.figsize'] = (20, 15)
plt.axis('off')
nx.draw_networkx(subgraph_3437, pos, with_labels = False, node_color=node_color,node_size=node_size )
plt.show()
```

### 5. Centrality Measures

Betweenness Centrality:：不仅有很多朋友的用户很重要，而且将一个地理位置连接到另一个地理位置的用户也很重要，因为这使用户可以查看来自不同地理位置的内容。Betweenness Centrality可量化特定节点进入其他两个节点之间最短选择路径的次数。

Degree Centrality：一个节点的连接数量。

### 应用

Centrality measures可用作任何机器学习模型的特征。

### 代码

```pos = nx.spring_layout(subgraph_3437)
betweennessCentrality = nx.betweenness_centrality(subgraph_3437,normalized=True, endpoints=True)
node_size =  [v * 10000 for v in betweennessCentrality.values()]
plt.figure(figsize=(20,20))
nx.draw_networkx(subgraph_3437, pos=pos, with_labels=False,
node_size=node_size )
plt.axis('off')
```

## 总结

0 条评论

• ### 使用特定领域的文档构建知识图谱 | 教程

来源 | github 【磐创AI导读】：本系列文章为大家介绍了如何使用特定领域的文档构建知识图谱。想要获取更多的机器学习、深度学习资源，欢迎大家点击上方蓝字...

• ### 目标检测算法上手实战

从广义上说，计算机视觉就是“赋予机器自然视觉能力”的学科。计算机视觉与人工智能有密切联系，但也有本质的不同。人工智能更强调推理和决策，但至少计算机视觉目前还主要...

• ### PageRank、最小生成树：ML开发者应该了解的五种图算法

在互联世界中，用户不能被视为独立的实体。他们之间存在一定的关系，我们有时希望在构建机器学习模型时考虑到这些关系。

• ### 5大必知的图算法，附Python代码实现

作为数据科学家，我们已经对 Pandas 或 SQL 等其他关系数据库非常熟悉了。我们习惯于将行中的用户视为列。但现实世界的表现真的如此吗？

• ### 盘点那些奇形怪状的编程语言

有的语言是多面手，在很多不同的领域都能派上用场。这类编程语言叫 general-purpose language，简称 GPL。大家学过的编程语言很多都属于这一...

• ### 换头术

他的一个观点，令我印象深刻。他说，医学的进步改变了人们对于死亡的看法。人们不再把死亡当作不可避免的自然结果，而是归因于某种技术失败。某个治疗步骤出错了，或者技术...

• ### 【Flutter 专题】58 图解 Flutter 嵌入原生 AndroidView 小尝试

和尚前段时间学习了一下 Flutter 与原生 Android 之间的交互；是以 Android 为主工程，Flutter 作为 Module 方式...

• ### vue cli安装步骤 原

1、全局安装 vue-cli      npm install --global vue-cli 2、创建一个基于 webpack 模板的新项目     ...