大势所趋！数据科学家必知的5种图算法(2)

应用

• Dijkstra算法的演变版本被广泛应用于谷歌地图中用来寻找最短路径
• 假设你在沃尔玛工作，已知不同的通道和所有通道之间的距离，求出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中的一些联系
• 图像分割——首先在图中构建MST，其中像素是节点，像素之间的距离基于一些相似性度量(颜色、强度等)

编码

# nx.minimum_spanning_tree(g) returns a instance of type graph 
nx.draw_networkx(nx.minimum_spanning_tree(g)) 

本图中的MST

如图所示，上图中便是要铺设的电线。

4. 网页排名

上图便是谷歌一直以来的网页排名算法。它根据输入和输出连接的数量和质量为页面分配分数。

应用

网页排名可用于需要估算网络节点重要性的任何地方。

• 用于使用引文找到最有影响力的论文
• 在谷歌中用于网页排名
• 还可用来给推特排序——以用户和推特作为节点。如果用户A关注了用户B，就创建用户间的连接。如果用户发送或转发一条推特，则创建用户和推特之间的连接。
• 推荐引擎

编码

此练习会使用Facebook数据。这里有facebook用户之间的连接/链接文件。首先这样创建Facebook图形：

# reading the datasetfb = nx.read_edgelist('../input/facebook-combined.txt', create_using = nx.Graph(), nodetype = int) 

它是这样运作的：

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用户图

现在要找到影响力高的用户。

（编辑：ASP站长网）