登陆

章鱼彩票appios-图论与图学习(二):图算法

admin 2019-08-11 186人围观 ,发现0个评论

选自towardsdatascience

作者:Mal Fabien

机器之心编译

参加:熊猫

图(graph)近来正逐渐变成机器学习的一大中心范畴,比方你能够通过猜测潜在的衔接来了解交际网络的结构、检测诈骗、了解轿车租借服务的消费者行为或进行实时引荐。近来,数据科学家 Mal Fabien 在其博客上发布了触及图论、图算法和图学习的系列文章《图论与图学习》。

图(graph)近来正逐渐变成机器学习的一大中心范畴,比方你能够通过猜测潜在的衔接来了解交际网络的结构、检测诈骗、了解轿车租借服务的消费者行为或进行实时引荐。近来,数据科学家 Mal Fabien 在其博客上发布了触及图论、图算法和图学习的系列文章《图论与图学习》。

本文是其间第二篇,介绍了图算法。更多文章和对应代码可拜访:https://github.com/maelfabien/Machine_Learning_Tutorials

本文包含以下主题:

  • 首要的图算法
  • 示意图和用例
  • Python 示例

首要进行一些准备工作,翻开 Jupyter Notebook,导入以下软件包:

importnumpy asnp

importrandom

importnetworkx asnx

fromIPython.display importImage

importmatplotlib.pyplot asplt

后文会运用 networkx 最新的 2.0 版别。networkx 是一个用于杂乱网络的结构、动态和功用的创立、操作和研讨的 Python 软件包。

我会尽量以实用为方针,尽力阐释每个概念。

前一篇文章介绍了图的首要品种以及描绘一个图的根本特性。现在咱们愈加具体地介绍图剖析/算法以及剖析图的不同办法。

为了了解上下文,这儿给出一些图算法的用例:

  • 实时诈骗检测
  • 实时引荐
  • 精简法规遵照性
  • 杂乱网络的办理和监控
  • 身份和拜访办理
  • 交际运用/功用

现在大多数结构(比方 Python 的 networkx 或 Neo4J)支撑的图算法类别首要有三个:

  • Pathfinding(寻路):依据可用性和质量等条件确认最优途径。咱们也将查找算法包含在这一类别中。这可用于确认最快路由或流量路由。
  • Centrality(中心性):确认网络中节点的重要性。这可用于辨认交际网络中有影响力的人或辨认网络中潜在的进犯方针。
  • Community detection(社群检测):评价集体聚类的办法。这可用于区分客户或检测诈骗等。

咱们将在第三篇文章中介绍图中的机器学习和图学习。

networkx 中的一切算法都可在这儿找到:https://networkx.github.io/documentation/stable/reference/algorithms/index.html

咱们只会介绍 networkx 中完成的最常见的根本算法。

一 寻路和图查找算法

  • 寻路算法是通过最小化跳(hop)的数量来寻觅两个节点之间的最短途径。
  • 查找算法不是给出最短途径,而是依据图的相邻状况或深度来探究图。这可用于信息检索。

1. 查找算法

图查找算法首要有两种:

  • 宽度优先查找(BFS):首要探究每个节点的相邻节点,然后探究相邻节点的相邻节点……
  • 深度优先查找(DFS):会测验尽或许地深化一条途径,如有或许便拜访新的相邻节点。

查找算法

2. 寻路算法

a. 最短途径

最短途径核算的是一对节点之间的最短的加权(假如图有加权的话)途径。

最短途径核算的是一对节点之间的最短的加权(假如图有加权的话)途径。

这可用于确认最优的驾驭方向或交际网络上两个人之间的别离程度。

核算图中的最短途径的办法有许多,包含 Dijkstra 算法,这是 networkx 中的默许算法。

依据维基百科,该算法的伪代码如下:

  • 将图中一切节点符号为未拜访。创立一个一切未拜访节点的调集,称为未拜访集。
  • 为每个节点分配一个暂定的间隔值:将咱们的初始节点的该值设置为零,将其它一切节点的该值设置为无量。将初始开端节点设置为当时节点。
  • 关于当时节点,调查其一切未被拜访过的相邻节点并核算通过当时节点的暂定间隔。比较新核算出的暂定间隔与当时分配的值,配之以其间更小的值。举个比方,假如当时节点 A 符号的间隔为 6,将其与相邻节点 B 衔接的边的长度为 2,则通过 A 抵达 B 的间隔为 6+2=8。假如 B 之前被符号的间隔大于 8,则将其改为 8。不然,坚持其当时的值。
  • 当咱们调查完当时节点的一切未拜访节点时,将当时节点符号为已拜访,并将其移出未拜访集。已拜访节点不会再次进行检查。
  • 假如方针节点已被符号为已拜访(当规划两个特定节点之间的路由时)或未拜访会集节点之间的最小暂定间隔为无量时(当规划一次完好的遍历时;当初始节点与剩下的未拜访节点之间没有衔接时才会呈现这种状况),那么就中止操作。算法完毕。
  • 不然,挑选符号有最小暂定间隔的未拜访节点,将其设置为新的「当时节点」,然后回到进程 3。

更多有关最短途径问题的介绍请参看:https://en.wikipedia.org/wiki/Shortest_path_problem

维基百科上 Dijkstra 算法示意图

该算法的 Python 完成简略直接:

# Returns shortest path between each node

nx.shortest_path(G_karate)

这会回来图中每个节点之间的最小途径的列表:

{0: {0: [0],

1: [0, 1],

2: [0, 2],

...

b. 单源最短途径

单源最短途径(Single Source Shortest Path/SSSP)是找到给定节点与图中其它一切节点之间的最短途径。

单源最短途径(Single Source Shortest Path/SSSP)是找到给定节点与图中其它一切节点之间的最短途径。

这常用于 IP 网络的路由协议。

c. 一切配对最短途径

一切配对最短途径(All Pairs Shortest Path / APSP)算法是找到一切节点对之间的最短途径。

一切配对最短途径(All Pairs Shortest Path / APSP)算法是找到一切节点对之间的最短途径。

虽然能够供给附近的成果,但这比为每个节点对调用单源最短途径算法更快。该算法一般可用于确认交通网格的不同分区的流量负载。

# Returns shortest path length between each node

list(nx.all_pairs_shortest_path_length(G_karate))

这会回来:

[( 0,

{ 0: 0,

1: 1,

2: 1,

3: 1,

4: 1,

...

d. 最小权重生成树

最小权重生成树(minimum spanning tree)是图(一个树)的一个子图,其用权重和最小的边衔接了图中的一切节点。

最小权重生成树(minimum spanning tree)是图(一个树)的一个子图,其用权重和最小的边衔接了图中的一切节点。

最小生成树应该用于无向图。

from networkx.algorithms import tree

mst = tree.minimum_spanning_e章鱼彩票appios-图论与图学习(二):图算法dges(G_karate, algorithm='prim', data=False)

edgelist = list(mst)

sorted(edgelist)

这会回来:

[( 0, 1),

( 0, 2),

( 0, 3),

( 0, 4),

( 0, 5),

( 0, 6),

...

二 社群检测

社群检测是依据给定的质量目标将节点区分为多个分组。

社群检测是依据给定的质量目标将节点区分为多个分组。

这一般可用于辨认交际社群、客户行为或网页主题。

社区是指一组相连节点的调集。可是,现在关于社群还没有广泛公认的界说,仅仅社群内的节点应该要密布地相连。

社群

Girvan Newman 算法是一个用于发现社群的常用算法。其通过逐渐移除网络内的边来界说社区。咱们将居间性称为「边居间性(edge betweenness)」。这是一个正比于穿过该边的节点对之间最短途径的数量的值。

该算法的进程如下:

  • 核算网络中一切已有边的居间性。
  • 移除居间性最高的边。
  • 移除该边后,从头核算一切边的居间性。
  • 重复进程 2 和 3,直到不再剩下边。

你能够通过 Python 运用以下代码完成它:

fromnetworkx.algorithms importcommunityk = 1

comp = community.girvan_newman(G_karate) forcommunities initertools.islice(comp, k):

print(tuple(sorted(c) forc incommunities))

这会得到一个归于每个社群的节点的列表(k=1 的意思是咱们希望得到 2 个社群):

( [0, 1, 3, 4, 5, 6, 7, 10, 11, 12, 13, 16, 17, 19, 21], [2, 8, 9, 14, 15, 18, 20, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33])

如上给出的那样,这个办法真实无法扩展。由于这个原因,Louvain 等办法已被开发出来。可是,假如要运转大规划的图,这些办法需求很长的时刻。

3. Louvain 模块性

在界说 Louvain 办法之前,需求介绍一下模块性(modularity)的概念。模块性是一个衡量,衡量的是分组被区分为聚类的程度:

模块性

Louvain 办法的伪代码如下:

  • 首要为每个节点分配一个社群
  • 替换履行接下来的两个进程,直到收敛
  • 创立一个带有相邻节点的新社群,以最大化模块性
  • 创立一个新的加权的图。之前进程的社群变成图的节点。

这个现在或许看起来有些让人利诱。事实上,咱们现在仅有做的工作是将最近的节点区分为分组,以便咱们优化模块性目标。

Louvain 办法

留意,Louvain 办法没有理论上的确保,但实践作用很好。Louvain 办法是 networkx 的一个子项目,参看:https://python-louvain.readthedocs.io/en/latest/

首要,装置软件包:

pipinstall python-louvain

然后,核算最佳的区分办法(依据 Louvain 办法):

import community

partition = community.best_partition(G_karate) pos= nx.spring_layout(G_karate)

plt.figure(figsize=( 8, 8))

plt.axis( 'off')

nx.draw_networkx_nodes(G_karate, pos, node_size= 600, cmap=plt.cm.RdYlBu, node_color=list(partition.values))

nx.draw_networkx_edges(G_karate, pos, alpha= 0. 3)

plt.show(G_karate)

运用 Louvain 对空手道图履行的最佳区分

4. 强互连的组分

强互连的组分(Strongly Connected Components /SCC)算法能找到有向图中的互连节点的分组。留意,在同一个分组中,每个节点都必须从恣意其它节点从两个方向都抵达。

强互连的组分(Strongly Connected Components /SCC)算法能找到有向图中的互连节点的分组。留意,在同一个分组中,每个节点都必须从恣意其它节点从两个方向都抵达。

这一般用在图剖析进程的前期阶段,能让咱们了解图构建的办法。举个比方,这能让咱们探究财务报表数据,了解谁具有什么公司的股份。

5. 弱互连的组分(并查集)

弱互连的组分(Weakly C章鱼彩票appios-图论与图学习(二):图算法onnected Components),也称为并查集(Union Find)算法,能找到有向图中的互连节点的调集,在同一个章鱼彩票appios-图论与图学习(二):图算法调会集,每个节点都可从恣意其它节点抵达。

弱互连的组分(Weakly Connected Components),也称为并查集(Union Find)算法,能找到有向图中的互连节点的调集,在同一个调会集,每个节点都可从恣意其它节点抵达。

这只需求节点对之间在一个方向上存在一条途径即可,而 SCC 则需求两个方向都存在途径。和 SCC 相同,并查集一般用在剖析的前期阶段,以了解图的结构。

并查集是一个预处理进程,为了了解图的结构,在任何算法之前都是必需的。

咱们能够运用下面的办法测验相连的有向图:

nx.is_weakly_connected( G)

nx.is_strongly_connected( G)

或运用下面的办法测验无向图:

nx.is_connected( G_karate)

这会回来一个布尔值。

一定要看看 networkx 文档中有关衔接性完成的问题:https://networkx.github.io/documentation/stable/reference/algorithms/component.html

6. 分层聚类

在分层聚类(hierarchical clustering)中,咱们构建聚类的层次结构。咱们用树状图的办法表明聚类。

在分层聚类(hierarchical clustering)中,咱们构建聚类的层次结构。咱们用树状图的办法表明聚类。

树状图

其思维是以不同的规划剖析社群结构。咱们一般自下而上构建树状图。咱们从每个节点一个聚类开端,然后兼并两个「最近」的节点。

但咱们怎么衡量聚类是否附近呢?咱们运用相似度间隔。令 d(i,j) 为 i 和 j 之间的最短途径的长度。

相似度间隔

要得到最大衔接,在每个进程,被最短间隔分隔的两个聚类被组合到一同。相似度间隔可用以下示意图阐释:

衔接办法

回到咱们的空手道示例。在运用分层聚类之前,咱们需求界说每个节点之间的间隔矩阵。

pcc _longueurs=list(nx.all_pairs _shortest_path _length(G_karate))

distances=np.zeros((n,n))# distances[i, j] is the length of the shortest path between i and j

for i in range(n):

for j in range(n):

distances[ i, j] = pcc_longueurs[ i][ 1][ j]

现在,咱们将运用 sklearn 的 AgglomerativeClustering 函数来确认分层聚类。

fromsklearn.cluster importAgglomerativeClusteringclustering = AgglomerativeClustering(n_clusters= 2,linkage= 'average',affinity= 'precomputed').fit_predict(distances)

最终,依据聚类成果,用不同色彩绘出所得到的图:

nx.draw(G_karate, node_color = clustering)

分层聚类

7. 聚类系数

聚类系数衡量的是两个节点倾向于聚类到一同的程度。

聚类系数衡量的是两个节点倾向于聚类到一同的程度。

部分聚类系数是以节点 i 为中心的三角形的数量与以节点 i 为中心的三节点的数量的比。某种程度而言,这衡量的是节点 i 与其相邻节点挨近齐备图(complete graph)的程度。

聚类系数

我通过以下图演示了聚类系数的核算:

聚类系数

大局聚类系数衡量的是图中三角形(部分聚类)的密度:

大局聚类系数

上面的图的大局聚类系数为:

关于 Erdos-Rnyi 随机父亲的草原母亲的河图,E[Clustering Coefficient]=E[Ci]=p,其间 p 是前一篇文章中界说的概率。

关于 Barbasi-Albert 随机图,大局聚类系数依据节点的数量遵从幂律。度为 k 的节点的均匀聚类系数正比于 k 的倒数:

度较低的节点衔接的是它们社群中的其它节点。度较高的节点衔接的是其它社群的节点。

关于一个给定的图,在 networkx 中,聚类系数很简单算出。首要,咱们来核算部分聚类系数:

# Listoflocalclusteringcoefficients

list( nx.clustering( G_barabasi) .valu章鱼彩票appios-图论与图学习(二):图算法es)

这会得到相似下面的成果:

0 .13636363636363635,

0 .2,

0 .07602339181286549,

0 .04843304843304843,

0 .09,

0 .055384615384615386,

0 .07017543859649122,

...

然后均匀这些成果,得到该图的大局聚类稀少:

# Globalclusteringcoefficient

np.mean( list( nx.clustering( G_barabasi) .values))

这会得到:

0 .0965577637155059

三 中心度算法

中心度(Centrality)衡量的是节点的重要程度。这并非一个清楚的界说,但假如咱们想要确认重要的网页、交通网络中的瓶颈……,那这就会很有用。

中心度(Centrality)衡量的是节点的重要程度。这并非一个清楚的界说,但假如咱们想要确认重要的网页、交通网络中的瓶颈……,那这就会很有用。

游走(walk)是能够屡次通过同一个节点的途径。依据所考虑的游走类型和核算它们的办法,中心度衡量也会各有不同。

1. PageRank 算法

PageRank 是依据所衔接的相邻节点,然后再依据它们各自的相邻节点估量当时节点的重要性。

虽然是谷歌让这种算法流行起来的,但这种办法能够用于检测任何网络中的高影响力节点。比方可用在交际网络上进行引荐。

PageRank 要么是通过在相邻节点上迭代地分配节点的秩(原本是依据度)来核算,要么是通过随机遍历图并核算每次游走期间抵达每个节点的频率来核算。

Neo4J 对 PageRank 算法的总结

PageRank 一般是在有向图上核算,但也可通过将有向图中的每条边转换成两条边而在无向图上履行。

举个比方,空手道图的 PageRank 能够这样取得:

nx.pagerank(G_karate, alpha=0.9)

其间 alpha 是阻尼参数(默许为 0.85)。这应该能回来一个排名列表:

{0: 0.09923208031303203,

1: 0.0543403155825792,

2: 0.05919704684187155,

3: 0.036612460562853694,

...

2. 度中心度

度中心度(Degree Centrality)核算的是终止于节点 i 的长度为 1 的游走的数量。

度中心度(Degree Centrality)核算的是终止于节点 i 的长度为 1 的游走的数量。

这能够衡量传入和传出联系。这能通过 C(Xi)=di 给出。度中心度可用于辨认交际网络中最有影响力的人。

c_degree= nx.degree_centrality(G_karate)

c_degree= list(c_degree.values)

3. 特征向量中心度

特征向量中心度(Eigenvector Centrality)是终止于节点 i 的长度为无量的游走的数量。

特征向量中心度(Eigenvector Centrality)是终止于节点 i 的长度为无量的游走的数量。

这能让有很好衔接相邻节点的节点有更高的重要度。

特征向量中心度

c_eigenvector= nx.eigenvector_centrality(G_karate)

c_eigenvector= list(c_eigenvector.values)

4. 挨近度中心度

挨近度中心度(Closeness Centrality)检测的是能够在图中有用传达信息的节点。

挨近度中心度(Closeness Centrality)检测的是能够在图中有用传达信息的节点。

这可用于辨认假新闻账户或恐怖分子,以便阻隔能向图中其它部分传达信息的个别。

挨近度中心度反比于到其它节点的最短途径长度的总和。

c_closeness= nx.closeness_centrality(G_karate)

c_closeness= list(c_closeness.values)

5. 居间性中心度

居间性中心度(Betweenness Centrality)检测的是节点在图中的信息流上所具有的影响量。

居间性中心度(Betweenness Centrality)检测的是节点在图中的信息流上所具有的影响量。

这一般可用于发现用作从图的一部分到另一部分的桥的节点,比方用在电信网络的数据包传递处理器或假新闻传达剖析中。

其间:

  • _jk 是 j 和 k 之间的最短途径的数量
  • _jk(i) 是 j 和 k 之间的通过 i 的最短途径的数量

居间性中心度衡量的是一个节点用作两个节点之间的桥的次数,比方:

中心度衡量

c_betweenness= nx.betweenness_centrality(G_karate)

c_betweenness= list(c_betweenness.values)

Python 中完成依赖于 networkx 的内置函数:

# Plot the centrality of the nodes

plt.figure(figsize=( 18, 12)) # Degree Centrality

f, axarr = plt.subplots( 2, 2, num= 1)

plt.sca(axarr[ 0, 0])

nx.draw(G_karate, cmap = plt.get_cmap( 'inferno'), node_color = c_degree, node_size= 300, pos= pos, with_labels=True)

axarr[ 0, 0].set_title( 'Degree Centrality', size= 16) # Eigenvalue Centrality

plt.sca(axarr[ 0, 1])

nx.draw(G_karate, cmap = plt.get_cmap( 'inferno'), node_color = c_eigenvector, node_size= 300, pos= pos, with_labels=True)

axarr[ 0, 1].set_title( 'Eigenvalue Centrality', size= 16) # Proximity Centrality

plt.sca(axarr[ 1, 0])

nx.draw(G_karate, cmap = plt.get_cmap( 'inferno'), node_color = c_closeness, node_size= 300, pos= pos, with_labels=True)

axarr[ 1, 0].set_title( 'Proximity Centrality', size= 16) # Betweenness Centrality

plt.sca(axarr[ 1, 1])

nx.draw(G_karate, cmap = plt.get_cmap( 'inferno'), node_color = c_betweenness, node_size= 300, pos= pos, with_labels=True)

axarr[ 1, 1].set_title( 'Betweenness Centrality', size= 16)

不同的中心度衡量

能够观察到,不同的中心度衡量重视的节点也不同。比方,居间性中心度得到的成果与其它办法的成果十分不同,由于它们衡量的不是同一个目标。

四 总结

现在咱们现已介绍了图的基础知识、图的首要类型、不同的图算法和它们运用 networkx 的 Python 完成。

下一篇文章咱们将介绍图学习,这能供给猜测图中节点和边的办法,然后处理缺失值或猜测新的联系。

扩展阅览:

  • Neo4j 的图算法全面攻略,Mark Needham & Amy E. Hodler:https://go.neo4j.com/rs/710-RRC-335/images/Comprehensive-Guide-to-Graph-Algorithms-in-Neo4j-ebook-EN-US.pdf
  • Networkx 文档:https://networkx.github.io/documentation/stable/

原文链接:https://towardsdatascience.com/graph-algorithms-part-2-dce0b2734a1d

最近发表
  • 章鱼彩票appios-监管全面清查财险产品问题:20家组织被处分
  • 追债触及一家银行、信任、担保和证券公司 甘孜州农信联社近2亿出资踩雷供应链金融
  • 请关注微信公众号
    微信二维码
    不容错过
    Powered By Z-BlogPHP