在互联世界中，用户不能被视为独立实体。在构建机器学习模型时，我们有时需要考虑它们之间的某些关系。在关系数据库中，我们无法利用不同行（用户）之间的这种关系，但在图形数据库中，这样做非常容易。在这篇文章中，我们将讨论数据科学家应该了解的一些非常重要的图形算法，以及如何使用Python实现它们。连通分量我们都知道聚类是如何工作的，您可以将连通分量视为一种硬聚类算法，用于在关联/连通数据中查找聚类/个体。下面是一个示例：假设您有连接世界上任意两个城市之间道路的数据。现在你需要找到世界上所有的大陆和它们包含的城市。你将如何实现这个目标？我们使用的连通分量算法是基于广度优先搜索（BFS）/深度优先搜索（DFS）的特例。在这里不深入讨论工作原理，让我们看看如何使用Networkx启动和运行此代码。应用程序从零售的角度来看：假设我们有很多客户使用大量帐户。使用连通分量算法的一种方法是在此数据集中查找不同的族。我们可以根据相同的信用卡用途、相同的地址、相同的手机号码在某些客户ID之间建立联系。一旦我们有了这些连接，我们就可以运行连接组件算法来为连接的客户创建一个集群，然后为他们分配一个家庭ID。然后，我们可以使用这些家庭ID，根据家庭需求提供个性化推荐。我们还可以利用家族ID通过创建基于家族的分组特征来推进分类算法。从财务角度来看：另一个用例是使用这些家庭ID来抓骗子。如果一个账户过去被骗过，关联的账户很容易再次被骗。实施的可能性仅受个人想象力的限制。（越有想象力，算法的应用就越广泛。）代码我们将使用Python中的Networkx模块来创建和分析图形。我们以包含城市和城市间距离信息的图表为例来实现我们的目标。具有随机距离的图首先创建一个包含城市名称（边）和距离信息的列表，其中距离表示边的权重。edgelist=[['曼海姆','法兰克福',85],['曼海姆','卡尔斯鲁厄',80],['爱尔福特','维尔茨堡',186],['慕尼黑','Numberg',167],['慕尼黑','奥格斯堡',84],['慕尼黑','卡塞尔',502],['纽贝格','斯图加特',183],['纽贝格','维尔茨堡',103],['Numberg','Munchen',167],['Stuttgart','Numberg',183],['Augsburg','Munchen',84],['Augsburg','Karlsruhe',250],['Kassel','慕尼黑',502],['卡塞尔','法兰克福',173],['法兰克福','曼海姆',85],['法兰克福','维尔茨堡',217],['法兰克福','卡塞尔',173],['维尔茨堡','Numberg',103],['维尔茨堡','爱尔福特',186],['维尔茨堡','法兰克福',217],['卡尔斯鲁厄','曼海姆',80],['卡尔斯鲁厄','奥格斯堡',250],["孟买","德里",400],["德里","加尔各答",500],["加尔各答","班加罗尔",600],["TX","NY",1200],["ALB","NY",800]]让我们使用Networkx创建一个图：g=nx.Graph()foredgeinedgelist:g.add_edge(edge[0],edge[1],weight=edge[2])现在我们想从这个图中找到不同的大陆和它们的城市，可以使用连通分量算法来实现：fori,xinenume速率(nx.connected_components(g)):print("cc"+str(i)+":",x)--------------------------------------------------------------cc0:{'法兰克福','卡塞尔','Munchen','Numberg','Erfurt','Stuttgart','Karlsruhe','Wurzburg','Mannheim','Augsburg'}cc1:{'Kolkata','Bangalore','Mumbai','Delhi'}cc2:{'ALB','NY','TX'}如您所见，仅使用顶点和边，我们就可以找到数据中的不同成分。该算法可以在不同的数据上运行以满足上述各种用例的要求。最短路径继续上面的例子，我们现在有一张德国城市和它们之间的距离的图表。如何找到从法兰克福（起始节点）到慕尼黑的最短距离？我们用来解决这个问题的算法叫做Dijkstra。用Dijkstra自己的话来说：从鹿特丹到格罗宁根的最短路线是什么？这是最短路径算法，我设计了大概20分钟。一天早上，我和我的未婚妻在阿姆斯特丹逛街，累了，我们坐在咖啡馆的露台上喝咖啡，我就想我能不能实现最短路径算法，我成功了。正如我所说，这是一个二十分钟的发明。事实上，它是1959年出版的，即使到现在也非常可读。它如此美丽的原因之一是我设计它时没有使用笔和纸。后来我了解到，不用笔和纸进行设计的好处之一就是你必须避免所有可以避免的并发症。最终，令我惊讶的是，这个算法成为了我著名的成果之一。应用Dijkstra算法的变体广泛用于Google地图中以查找最短路线。假设您有关于沃尔玛商店中各个过道位置和过道之间距离的数据。您想要为客户提供从A到D的最短路径。您已经了解了LinkedIn显示主要和次要连接的方式。这背后的机制是什么？代码print(nx.shortest_path(g,'Stuttgart','Frankfurt',weight='weight'))print(nx.shortest_path_length(g,'Stuttgart','Frankfurt',weight='weight'))----------------------------------------------------['Stuttgart','Numberg','Wurzburg','Frankfurt']503你还可以找到所有对之间的最短路径：forxinnx.all_pairs_dijkstra_path(g,weight='weight'):print(x)-----------------------------------------------------('曼海姆',{'曼海姆':['曼海姆'],'法兰克福':['曼海姆','法兰克福'],'卡尔斯鲁厄':['曼海姆','卡尔斯鲁厄'],'奥格斯堡':['曼海姆','卡尔斯鲁厄','奥格斯堡'],'卡塞尔':['曼海姆','法兰克福','卡塞尔'],'维尔茨堡':['曼海姆','法兰克福','维尔茨堡'],'慕尼黑':['曼海姆','卡尔斯鲁厄','奥格斯堡','慕尼黑'],'爱尔福特':['曼海姆','法兰克福','维尔茨堡','爱尔福特'],'纽堡':['曼海姆','法兰克福','维尔茨堡','Numberg'],'斯图加特':['曼海姆','法兰克福','维尔茨堡','Numberg','斯图加特']})('法兰克福',{'法兰克福':['法兰克福'],'曼海姆':['法兰克福','曼海姆'],'卡塞尔':['法兰克福','卡塞尔'],'维尔茨堡':['法兰克福','维尔茨堡'],'卡尔斯鲁厄':['法兰克福','曼海姆','卡尔斯鲁厄'],'奥格斯堡':['法兰克福'','曼海姆','卡尔斯鲁厄','奥格斯堡'],'慕尼黑':['法兰克福','维尔茨堡','Numberg','慕尼黑'],'爱尔福特':['法兰克福','维尔茨堡','Erfurt'],'Numberg':['Frankfurt','Wurzburg','Numberg'],'Stuttgart':['Frankfurt','Wurzburg','Numberg','Stuttgart']})....MinimumSpanningTree(MST)现在我们面临另一个问题假设我们为管道公司或布线公司工作。我们需要使用最少的电线/管道来连接图中的所有城市。我们如何做到这一点？左：无向图；右图：对应的MST应用最小生成树在网络设计中有直接应用，包括计算机网络、电信网络、交通网络、供水网络和电网（它们最初是为这些网络而发明的）。MST用于近似旅行商问题。聚类：首先构建MST，然后利用类间距离和类内距离来确定MST中打破某些边的阈值。图像分割：首先在图上构建MST，其中像素是节点，像素之间的距离基于某种相似性度量（颜色、强度等）g))左：无向图；右：对应MST.Pagerank上图是Google长期提供的页面排序算法（pagesortingalgorithm）。它根据传入和传出链接的数量和质量对页面进行评分。ApplyingPagerank可以用在任何我们想估计网络节点重要性的地方。它已被用来寻找最有影响力的论文；它已被谷歌用于对页面进行排名；它可用于对推文进行排序-用户和推文作为节点。如果用户A关注了用户B，则创建用户之间的链接；如果用户发推文/转推文，则在用户和推文之间创建链接；推荐引擎。代码在本练习中，我们将使用Facebook数据。我们有一个facebook用户之间的边缘/链接文件。首先通过以下方式创建Facebook图：#readingthedatasetfb=nx.read_edgelist('../input/facebook-combined.txt',create_using=nx.Graph(),nodetype=int)它是这样的：pos=nx.spring_layout(fb)importwarningswarnings.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()FacebookUserGraph现在我们想找出具有高影响力的用户。直觉上，Pagerank算法会给那些有很多朋友的用户打高分，而这些用户又会在Facebook上有很多朋友。pageranks=nx.pagerank(fb)print(pageranks)-----------------------------------------------------{0:0.006289602618466542,1:0.00023590202311540972,2:0.00020310565091694562,3:0.00022552359869430617,4:0.000238492647012...ThefollowingcodecanbeusedGetsortedPageRankormostinfluential用户：importoperatorsorted_pa??gerank=sorted(pagerank.items(),key=operator.itemgetter(1),reverse=True)print(sorted_pa??gerank)--------------------------------------------------------[(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),...]The以上ID是最有影响力的用户。最具影响力用户的子图如下所示：first_degree_connected_nodes=list(fb.neighbors(3437))second_degree_connected_nodes=[]forxinfirst_degree_connected_nodes:second_degree_connected_nodes+=list(fb.neighbors(x))second_degree_connected_nodes.remove_second(34connected_second(34connected_nodes)设置（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'ifv==3437else'forvinsubgraph_3437]node_size=[1000ifv==3437else35forvinsubgraph_34]plt_34style.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()黄色是最有影响力的用户中心性度量您可以使用许多中心性度量作为机器学习模型的特征，这里仅提及其中两个。其他指标链接：https://networkx.github.io/documentation/networkx-1.10/reference/algorithms.centrality.html#current-flow-closeness。介数中心性：不仅拥有很多朋友的用户很重要，而且从一个地理位置连接到另一个地理位置的用户也很重要，因为这允许用户看到来自不同位置的内容。中介中心性量化特定节点出现在两个其他节点之间的最短路径中的次数。度中心性：简单来说就是节点的连接数。下面的代码是求子图介数中心性的代码：pos=nx.spring_layout(subgraph_3437)betweennessCentrality=nx.betweenness_centrality(subgraph_3437,normalized=True,endpoints=True)node_size=[v*10000forvinbetweennessCentrality.values()]铂。figure(figsize=(20,20))nx.draw_networkx(subgraph_3437,pos=pos,with_labels=False,node_size=node_size)plt.axis('off')您可以在此处通过节点的中介中心值查看大小。他们可以被认为是信使。打破具有高介数中心性的任何节点会将图分成许多部分。
