假设我们在水管工程公司或互联网光纤公司工作,我们需要使用最少的电线(或者管道)连接图表中的所有城市。我们如何做到这一点?
无向图和它的最小生成树
代码
# nx.minimum_spanning_tree(g) returns a instance of type graph nx.draw_networkx(nx.minimum_spanning_tree(g))
使用最小生成树算法铺设电线
应用
- 最小生成树在网络设计中有着最直接的应用,包括计算机网络,电信网络,运输网络,供水网络和电网。(最小生成树最初就是为此发明的)
- 最小生成树可用于求解旅行商问题的近似解
- 聚类——首先构造最小生成树,然后使用类间距离和类内距离来设定阈值,从而破坏最小生成树中的某些连边,最终完成聚类的目的
- 图像分割——首先在图形上构建最小生成树,其中像素是节点,像素之间的距离基于某种相似性度量(例如颜色,强度等),然后进行图的分割。
Pagerank 是为谷歌提供长期支持的页面排序算法。根据输入和输出链接的数量和质量,该算法对每个页面进行打分。
代码
在本节中,我们将使用 Facebook 数据。首先,利用 Facebook 用户之间的连接,我们使用以下方法创建图:
# reading the dataset fb = 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()