大势所趋！数据科学家必须知道的5种图形算法在构建机器学习模型时，有时也会将这种联系内置到模型中。虽然不可能在关系数据库中使用不同行（用户）之间的这种关系，但在图形数据库中却很容易做到这一点。本文将介绍数据科学家必须知道的一些重要图算法，并解释如何在Python中使用它们。另外，强烈推荐学习图论的基础知识。圣地亚哥大学发布于Coursera上的大数据课程的图分析课：https://www.coursera.org/learn/big-data-graph-analytics?ranMID=40328&ranEAID=lVarvwc5BD0&ranSiteID=lVarvwc5BD0-uD3tAFL0mCUdzcfwDd6FTQ&siteID=lVarvwc5BD0-uD3tAFL0mCUdzcfwDd6FTQ&utm_content=2&utm_medium=partners&utm_source=linkshare&utm_campaign=lVarvwc5BD01。包含3个连通分量的连通分量图每个人都知道聚类算法是如何工作的，对吧？简单的说，把连通分量看成是硬聚类中的簇/岛。举个具体的例子：假设有一个道路数据连接世界上任意两个城市，你需要找到世界上包含的所有大洲和城市。如何实现？动动脑筋。这里使用的连通分支算法是基于BFS/DFS的特例，这里不再赘述。下面解释了如何使用Networkx启动和运行代码。应用从零售的角度来看：假设有许多客户拥有许多帐户，连接分支算法可用于在数据集中查找不同的家庭。基于相同的信用卡用途、相同的地址或相同的电话号码等，可以假定客户ID之间的连接（方式）。拥有这些连接后，您可以在它们上运行连接分支算法以创建单独的集群，然后为这些集群分配一个家族ID。这些家庭ID可用于根据家庭需求提供个性化推荐。它还可用于创建基于家族的分组功能，以不断改进分类算法。从财务角度来看：这些家庭ID也可以用来捕捉欺诈。如果一个帐户是欺诈性的，则关联帐户也可能是欺诈性的。应用的无限可能，尽在您的想象中。编码在这里，我们将使用Python中的Networkx模块来创建和分析图形。让我们首先看一个将要使用的示例地图，其中包含有关城市和城市之间距离的信息。随机距离示意图首先创建一个接触列表和一个距离列表作为接触权重：edgelist=[['Mannheim','Frankfurt',85],['Mannheim','Karlsruhe',80],['Erfurt','维尔茨堡',186],['Munchen','Numberg',167],['Munchen','Augsburg',84],['Munchen','Kassel',502],['Numberg','斯图加特',183],['Numberg','维尔茨堡',103],['Numberg','Munchen',167],['斯图加特','Numberg',183],['奥格斯堡','慕尼黑',84],['奥格斯堡','卡尔斯鲁厄',250],['卡塞尔','慕尼黑',502],['卡塞尔','法兰克福',173],['法兰克福','曼海姆',85],['法兰克福','维尔茨堡',217],['法兰克福','卡塞尔',173],['维尔茨堡','Numberg',103],['维尔茨堡','埃尔福特',186],['维尔茨堡'','法兰克福',217],['卡尔斯鲁厄','曼海姆',80],['卡尔斯鲁厄','奥格斯堡',250],["孟买","德里",400],["德里","加尔各答",500],["加尔各答","班加罗尔",600],["TX","纽约",1200],["ALB","纽约",800]]创建使用Networkx的图形：g=nx.Graph()foredgeinedgelist:g.add_edge(edge[0],edge[1],weight=edge[2])现在我们需要找到不同的大陆及其城市从这张图中。您可以像这样/（如下）使用连接分支算法：fori,xinenumerate(nx.connected_components(g)):print("cc"+str(i)+":",x)---------------------------------------------------------cc0:{'法兰克福','卡塞尔','慕尼黑','Numberg','爱尔福特','斯图加特','卡尔斯鲁厄','维尔茨堡','曼海姆','奥格斯堡'}cc1:{'Kolkata','Bangalore','Mumbai','Delhi'}cc2:{'ALB','NY','TX'}如上所示，仅使用链接和顶点就可以在数据中找到不同的组件。该算法可以在不同的数据上运行以满足上述任何情况。2.在最短路径上，已经获得了德国城市及其距离的地图。接下来，求从法兰克福（起始节点）到慕尼黑的最短距离。解决这个问题的算法称为Dijkstra算法。用Dijkstra自己的话来说：从鹿特丹到格罗宁根最短的路是什么？或者，从任何一个城市到另一个。设计最短路径算法只花了我20分钟。一天早上，我和我年轻的未婚妻在阿姆斯特丹购物。逛累了之后，我们坐在咖啡厅的露台上喝了一杯咖啡。我想这样可以吗，然后我设计了最短路径算法。如前所述，这是一个20分钟的发明。事实上，这本书是在三年后的1959年出版的，今天仍然可以阅读。这是一本好书，因为我当时没有用铅笔和纸进行设计。后来我发现不用铅笔和纸进行设计的好处之一就是你的设计必须要简单。最后没想到这个算法会成为我的成名作之一。-EdsgerDijkstra，对PhilipL.Frana的采访，ACMLetters，2001[3]应用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)----------------------------------------------------------('曼海姆',{'曼海姆':['曼海姆'],'法兰克福':['曼海姆','法兰克福'],'卡尔斯鲁厄':['曼海姆','卡尔斯鲁厄'],'奥格斯堡':['曼海姆','卡尔斯鲁厄','奥格斯堡'],'卡塞尔':['曼海姆','法兰克福','卡塞尔'],'维尔茨堡':['曼海姆','法兰克福','维尔茨堡'],'慕尼黑':['曼海姆','卡尔斯鲁厄','奥格斯堡','慕尼黑'],'爱尔福特':['曼海姆','法兰克福','维尔茨堡','Erfurt'],'Numberg':['Mannheim','Frankfurt','Wurzburg','Numberg'],'Stuttgart':['Mannheim','Frankfurt','Wurzburg','Numberg','Stuttgart']})('法兰克福',{'法兰克福':['法兰克福'],'曼恩eim':['法兰克福','曼海姆'],'卡塞尔':['法兰克福','卡塞尔'],'维尔茨堡':['法兰克福','维尔茨堡'],'卡尔斯鲁厄':['法兰克福','曼海姆','卡尔斯鲁厄'],'奥格斯堡'：['法兰克福'，'曼海姆'，'卡尔斯鲁厄'，'奥格斯堡']，'慕尼黑'：['法兰克福'，'维尔茨堡'，'Numberg'，'慕尼黑']，'埃尔福特'：['法兰克福','Wurzburg','Erfurt'],'Numberg':['Frankfurt','Wurzburg','Numberg'],'Stuttgart':['Frankfurt','Wurzburg','Numberg','Stuttgart']})...3。最小生成树(MST)现在来另一个问题。假设你在一家管道公司或一家互联网光纤公司工作，需要用最少的电线/管道连接图中的所有城市。你怎么做到这一点？?MST在右边的无向图。应用MST直接应用于网络设计。其中包括计算机网络、电信网络、交通网络、供水网络和电网（最初设计目的）MST也用于解决旅行商问题聚类——首先构造MST，然后使用簇间距离和簇内-聚类距离来确定阈值，从而打破MST中的一些关系图像分割-首先在图中构建MST，其中像素是节点，像素之间的距离根据一些相似性度量（颜色、强度等）进行编码#nx。minimum_spanning_tree(g)returnsainstanceoftypegraphnx.draw_networkx(nx.minimum_spanning_tree(g))这个图中的MST如图所示，要铺的线在上图中。4.Pageranking上图是Google的pageranking算法。它根据传入和传出连接的数量和质量为页面分配分数。AppPageRank可用于任何需要估计网络节点重要性的地方。用于使用引文查找最有影响力的论文在谷歌中用于页面排名也用于对推文进行排名-以用户和推文为节点。如果用户A关注用户B，则创建用户之间的连接。如果用户发送或转发一条推文，则会在用户和Twitter之间创建一个连接。推荐引擎编码本练习使用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()FBusermap现在找影响力大的用户。直觉上，PageRank算法会给那些有很多朋友的用户打高分，而这些用户反过来也有很多Facebook朋友。pageranks=nx.pagerank(fb)print(pageranks)-----------------------------------------------------{0:0.006289602618466542,1:0.00023590202311540972,2:0.00020310565091694562,3:0.00022552359869430617,4:0.000238492647012.2.4562,canbesortedlikethisAfterpagerankalgorithmormostinfluentialusers: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),...]TheaboveID是f或最有影响力的用户。在这里可以看到很具影响力用户的子图：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=3connect7)remove(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'ifv==3437else'red'forvinsubgraph_3437]node_size=[1000ifv==3437else34forvinsubgraph37]plt_3.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()MostInfluentialUsers（黄点）5.CentralitymetricsCentralitymetrics有很多属性可以用来制作机器学习模型。其中两个描述如下。其他一些措施可以在这里看到：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*10000forvinbetweennessCentrality.values()]plt.figure(figsize=(20,20))nx.draw_networkx(subgraph_3437,pos=pos,with_labels=False,node_size=node_size)plt.axis('off')如上可以看到根据中介中心性值调整了节点的大小。这些节点可以看作是信息传输器。断开具有高介数中心性的节点会将图分成许多部分。总结本文介绍了一些有影响力的图算法，它们以各种方式改变了人们的生活方式。随着大量社会数据的出现，网络分析可以在很大程度上帮助人们改进模型，产生巨大的价值，甚至增进人类对世界的认识。现在图算法层出不穷，以上就是笔者的最爱。如果你有兴趣，欢迎深入研究这些算法。本文仅对该领域进行简要介绍。这是本文中提到的所有算法的Kaggle内核：https://www.kaggle.com/mlwhiz/top-graph-algorithms
