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

直观地说，网页排名算法会给有很多朋友的用户打高分，而这些用户又有很多facebook上的朋友。

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(pagerank.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),......] 

以上ID用于最有影响力的用户。

这里可以看到很具影响力用户的子图：

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.中心性度量

中心度量有很多可以用来做机器学习模型的特性。以下将介绍其中的两种。这里可以看到一些其他的测量方法：https://networkx.github.io/documentation/networkx-1.10/reference/algorithms.centrality.html

中介中心性：朋友最多的用户很重要，连接两个地理位置的用户也很重要，因为它让用户可以看到来自不同地理位置的内容。中介中心性量化了一个特定节点在其他两个节点之间最短路径中出现的次数。

度中心性：即节点的连接数。

应用

中心性度量可以用作任何机器学习模型的特性。

编码

以下代码用于查找子图的中介中心性。

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') 

如上可以看到按中介中心性值调整了节点的大小。这些节点可以看作是信息传递者。断开高中介中心性的节点会将图分成许多部分。

总结

本文介绍了一些很具影响力的图算法，它们从各方面改变了人们的生活方式。

随着社会数据的大量涌现，网络分析可以在很大程度上帮助人们改进模型，产生巨大价值，甚至还会增进人类对世界的认识。

现今图算法层出不穷，以上这些是笔者最喜欢的。如果感兴趣，欢迎对这些算法进行深入研究。本文仅对该领域进行了一定的介绍。

这里是本文中提到的所有算法的Kaggle Kernel：https://www.kaggle.com/mlwhiz/top-graph-algorithms

（编辑：ASP站长网）