图是表示不同实体之间关系的有用数据结构。它们经常用于各种学科，包括计算机科学、数学、物理学和社会科学。在许多情况下，识别图中最重要的节点至关重要，因为它对社交网络分析、推荐系统等一系列应用程序都有好处。在这篇博客文章中，我们将查看许多指标来确定图中节点的重要性。
入度和出度
入度和出度是确定图中节点重要性的两个最基本指标。进入节点的边数表示为入度，而离开节点的边数表示为出度。这些指标经常用于具有方向边的有向图中。
入度和出度对于检测有向图（如社交网络、引文网络和网络图）中的关键节点很有用。例如在社交网络中，入度高的节点可能被视为影响者或领导者，而出度高的节点可能被视为经常与他人互动的活跃用户。入度高的节点可能被认为是引文网络中被许多其他出版物提及的重要论文，而出度高的节点可能被认为是撰写了大量论文的多产研究人员。
importnetworkxasnx#CateasimpleDigraphG=nx.DiGraph()G.add_edges_from([(1,2),(1,3),(2,3),(3,4),(4,5)])nx.draw(G,with_labels=True,node_color=#00b4d9)#Calculatein-degeandout-degeforeachnodefornodeinG.nodes():print("Node",node,"In-dege:",G.in_dege(node),"Out-dege:",G.out_dege(node))
中心性
中心性是一个更通用的指标，可用于确定图中节点的重要性。有多种类型的中心性，包括度中心性、邻近中心性和中介中心性。这些指标中的每一个都提供了关于图中节点重要性的独特观点，并且每个指标都适用于各种应用程序。
度中心性是一个节点与图中其他节点的连接数。该指标对于检测图中连接良好的节点非常有用，例如社交网络中具有大量邻居的节点。
连接到一个节点的边的数量称为它的度中心性。要计算标准化分数，每个分数除以n-1，其中n是节点数。
介数中心性计算一个节点作为图中其他节点之间的链接的次数。该指标对于识别在连接图中不同区域中起重要作用的节点非常有用，例如在社交网络中充当重要中介的节点。
节点v的介数中心性是通过v的所有对最短路径的分数之和。
Closenesscentrality计算图中节点与所有其他节点之间的平均距离。此指标对于检测与图的其余部分有很强联系的节点很有用，例如社交网络中的节点。
节点u的接近中心性是到u总体n-1个可达节点的平均最短路径距离的倒数。
importnetworkxasnx#CateasimplegraphG=nx.Graph()G.add_edges_from([(1,2),(1,3),(2,3),(3,4),(4,5)])#Calculatedegecentralitydege_centrality=nx.dege_centrality(G)print("Degecentrality:",dege_centrality)#Calculateclosenesscentralitycloseness_centrality=nx.closeness_centrality(G)print("Closenesscentrality:",closeness_centrality)#Calculatebetweennesscentralitybetweenness_centrality=nx.betweenness_centrality(G)print("Betweennesscentrality:",betweenness_centrality)
随机游走
随机游走可用于识别图中节点的重要性。随机游走背后的主要思想是在图上复制随机游走者的运动，游走者从某个节点开始，每一步都行进到其相邻节点之一。前往特定相邻节点的可能性由节点之间的边权重或转移概率决定。被更频繁访问的节点被认为是更重要的。
随机游走可用于以多种方式衡量图中节点的重要性。一种方法是使用随机游走的平稳分布，这是步行者在经过大量步数后到达特定节点的机会。平稳分布显示了随机游走的长期行为，可用于确定图中最重要的节点。
另一种方法是使用随机游走的返回时间或命中时间，这是游走者返回到特定节点所需的预期时间。节点的返回时间表示其可访问性，可用于识别图中最中心的节点。
随机游走分为两种类型：未加权随机游走和加权随机游走。加权随机游走考虑每条边的权重，而未加权随机游走将所有边视为具有相同的权重。
importnetworkxasnximportnumpyasnp#CateasimplegraphG=nx.DiGraph()G.add_edges_from([(1,2),(1,3),(2,3),(3,4),(4,5),(5,1)])#Performunweightedrandomwalkdefunweighted_random_walk_importance(G,num_walks,walk_length):"""Calculatestheimportanceofeachnodeinagraphusingrandomwalks.:paramG:NetworkXgraph.:paramnum_walks:Numberofrandomwalkstoperform.:paramwalk_length:Lengthofeachrandomwalk.:turn:Adictionaryofimportancescosforeachnode."""importance_scos={node:0fornodeinG.nodes()}for_inrange(num_walks):curnt_node=np.random.choice(list(G.nodes()))for_inrange(walk_length):next_node=np.random.choice(list(G.neighbors(curnt_node)))importance_scos[next_node]+=1curnt_node=next_nodefornodeinimportance_scos:importance_scos[node]/=num_walks*walk_lengthturnimportance_scosprint("RandomWalkImportance:",unweighted_random_walk_importance(G,10,5))nx.draw(G,with_labels=True,node_color=#00b4d9,pos=pos)
网页排名
PageRank是Google建立的用于对网页进行排名的指标。它建立在一个节点重要的前提下，如果它与其他重要节点相关。特别是PageRank算法为图中的每个节点分配一个分数，其中分数表示随机冲浪者（即随机游走者）将登陆该节点的可能性。登陆节点的可能性由到该节点的入站链接的数量以及链接到它的节点的相关性控制。
importnetworkxasnx#CateasimplegraphG=nx.DiGraph()G.add_edges_from([(1,2),(1,3),(2,3),(3,4),(4,5),(5,1)])#CalculatePageRankpagerank=nx.pagerank(G)pagerank={k:round(v,3)fork,vinpagerank.items()}print("PageRank:",pagerank)nx.draw(G,with_labels=True,node_color=#00b4d9,pos=pos)
其他指标
特征向量中心性根据节点所连接的节点的重要性计算节点的重要性。此指标对于在图中查找与其他相关节点相关的节点很有用，例如社交网络中与有影响力的节点连接良好的节点。
Katz中心性是概括特征向量中心性的中心性度量。它不仅考虑节点的直接邻居，还考虑邻居的邻居，等等。测度定义为方程Ax=λx的解，其中A是图的邻接矩阵，x表示特征向量，λ是特征值。
HITS（超链接诱导主题搜索）是衡量网站在超链接网络中重要性的指标。该算法由两部分组成：权威和中心。一个网页的权限是通过将所有链接到它的页面的中心分数相加来计算的，而一个网页的中心是通过将所有链接到它的页面的权限分数相加来确定的。
结论
识别图中节点的重要性是一项具有广泛应用的关键任务。可用于此目的的各种指标包括入度、出度、中心性、随机游走、PageRank等。每种方法都有自己的优缺点，方法的选择取决于具体的任务和数据。例如，入度和出度很简单，但只考虑边数，而像中间度和接近度这样的中心性度量考虑了网络位置，但可能代价高昂。Randomwalks和PageRank考虑网络结构但需要大量数据和资源。因此，在选择一种方法来识别图中节点的重要性时，必须考虑问题的约束和可用资源。