数据科学家需要知道的5种图算法( 三 ) _图算法

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

文章插图
我们的图的最小生成树
可以看到，上面就是我们需要铺设的电线。
4. Pagerank

文章插图

这就是长期以来支持谷歌的页面排序算法。它根据输入和输出链接的数量和质量为页面分配一个分数。
应用
Pagerank可以用于任何我们想要估计任何网络中节点重要性的地方。

它被用来寻找最具影响力的论文使用引文。
被谷歌用来排列页面
它可以用来把tweets-用户和以及tweets-tweets当成节点进行排序。如果用户A关注了用户B，那么创建用户之间的链接，如果用户tweet/retwets一条tweet，则创建用户和tweet之间的链接。
推荐引擎

代码
在这个练习中，我们将使用Facebook数据。我们有一个facebook用户之间的边/链接文件。我们首先创建FB图，使用：
# 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()

文章插图
FaceBook用户图
现在我们想要找到具有高影响力的用户。
直观地说，Pagerank算法会给有很多朋友的用户打高分，而这些朋友又有很多facebook上的朋友。
pageranks = nx.pagerank(fb)print(pageranks)------------------------------------------------------{0: 0.006289602618466542, 1: 0.00023590202311540972, 2: 0.00020310565091694562, 3: 0.00022552359869430617, 4: 0.00023849264701222462,........}我们可以用PageRank得到最有影响力的用户排序：
import operatorsorted_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),......]以上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. 中心度量
有许多中心度量，你都可以将其用作机器学习模型的特征。我将讨论其中的两个。
内中心：重要的不仅是拥有最多朋友的用户，将一个地理位置与另一个地理位置连接起来的用户也很重要，因为这让用户可以看到来自不同地理位置的内容。内中心度量了一个特定节点在另外两个节点之间的最短路径中出现的次数
度中心：它是节点的连接数。
应用
中心度量可以作为任何机器学习模型的一个特征。
代码
面的代码用于查找子图的内中心。
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')