如何选择图中最具影响力的节点组合-育师

原文：towardsdatascience.com/how-to-select-the-most-influential-combination-of-nodes-in-a-graph-b88b40c77ae7

在寻找图中的影响力节点时，您可以考虑诸如中心性或度这样的图度量，这些度量告诉您单个节点的影响力。然而，要找到图中最具影响力的节点集，您必须考虑哪种节点组合对图具有最高影响力，这是一个具有挑战性的问题。本文探讨了您如何从图中选择最具影响力的节点集的问题。

https://github.com/OpenDocCN/towardsdatascience-blog-zh-2024/raw/master/docs/img/8f31d03444b0242f15a6071291bb39e0.png

通过这篇文章学习如何选择图中最具影响力的节点组合。图片由 ChatGPT 提供。“为“选择图中最具影响力的节点组合”制作图片”提示。ChatGPT，4，OpenAI，2024 年 3 月 10 日。chat.openai.com.

动机

我写这篇文章的动机是我目前正在撰写我的论文，其中涉及半监督聚类。本质上，我必须从图中选择一些我可以知道标签的节点，然后使用这些信息来聚类其他节点。因此，找到可以知道标签的最具影响力的节点集对于我的聚类算法的性能至关重要。在本文的情况下，对图的影响力将视为所选节点集如何帮助聚类算法的程度。然而，这种对图的影响力也可以推广到其他问题。

https://github.com/OpenDocCN/towardsdatascience-blog-zh-2024/raw/master/docs/img/db10f7faea0b992f0a9968b40f71f004.png

本文中您将使用的流程图。首先，您有一个输入图。然后您选择一个节点影响力指标，接着是节点选择策略，输出结果是所选节点集——图片由作者提供。

寻找最有影响力的节点组合的问题很有趣，因为除了使用单个节点的分数作为节点影响力外，还必须考虑节点在图中的位置相对于其他选定的节点。选择最有影响力的节点组合使问题变得更加复杂，因为仅仅选择具有最高单个影响力分数的节点可能不是最优的。这在下图中得到了说明，其中通过度数单独测量的两个最有影响力的节点是节点 4 和 5。然而，选择这两个节点并不一定是影响整个图的最佳选择。在这种情况下，这两个节点是相连的，因此其他节点组合可以对图产生更大的联合影响力，例如，节点 2 和 5，因为这两个节点可以直接到达图中的所有其他节点。

https://github.com/OpenDocCN/towardsdatascience-blog-zh-2024/raw/master/docs/img/0697cb1b15ab6b0256b40fd0cd4cc5d2.png

选择两个最高度数节点的图示例可能对图的影响并不显著。在图中，节点 4 和 5 具有最高的度数，但通过视觉检查，您可以看到选择节点 2 和 5 可能对图有更高的联合影响力——图片由作者提供。

在本文中，我首先将讨论通过使用不同的节点影响力指标来寻找单个节点的影响，并展示如何结合这些指标。随后，我将向您展示在图中选择对图有显著影响的节点组合的启发式方法。然后，我将结合这两种技术，根据每个节点的影响力和节点组合的联合影响力来选择节点组合。这将使您能够在网络中选择具有最高影响力的强大节点组合。

· 动机 · 目录 · 节点影响力指标 · 结合指标 ∘ 归一化和相加 ∘ 为每个指标单独选择节点 · 选择节点集 ∘ 使用社区检测 ∘ 使用节点之间的最小步数 ∘ 结合社区检测和最小步数 · 测试选定节点的影响力 ∘ 测试 1：连接到选定节点的节点数量 ∘ 测试 2：连接到选定节点的社区数量 ∘ 测试 3：下游任务 ∘ 测试 4：视觉检查 · 结论

节点影响力指标

节点影响力是一个泛指，表示节点在图中的重要性。存在许多用于衡量这种节点影响力的指标，其中一些最常见的指标包括：

度
介数中心性
亲近中心性
特征向量中心性
感染传播速度，灵感来源于SIR 模型

最容易理解的指标是度指标，它衡量了进入和离开一个节点的边的数量。连接到一个节点的边越多，该节点的影响力就越大。在社会网络中，你通常会看到一个遵循幂律的图，这意味着少数节点连接到许多节点，而大多数节点只连接到少数节点。这意味着高度节点往往连接到低度节点。你可以在下面的图像中看到这一点，其中蓝色直方图显示少数具有高度节点的节点和更多具有较低度数的节点。另一方面，你有更平衡的图，具有相同度数的节点相互连接。这可以在黄色直方图图中看到，它遵循正态分布。

https://github.com/OpenDocCN/towardsdatascience-blog-zh-2024/raw/master/docs/img/361f321c3988189488265d35779eebc7.png

绘制不同类型图中具有加权边的节点度数。蓝色直方图遵循幂律分布，这是社交网络图的特征，而黄色直方图遵循正态分布，这在现实世界的图中较少见。图片由作者提供。

介数中心性是另一个你可以使用的常见指标。介数中心性找到所有节点对之间的最短路径，并计算有多少最短路径通过每个节点。如果一个节点通过许多最短路径，那么该节点被认为具有更高的影响力。亲近中心性是以类似的方式测量的，但它更多地衡量每个节点在网络中与其他节点的接近程度。我还提到了特征向量中心性，简而言之，它衡量一个节点与其他连接良好的节点连接得有多好。

最后，我提到的第四个指标是感染传播模型，该模型灵感来源于SIR 模型。这个模型有效地衡量了疾病从每个节点开始传播的情况。如果疾病从一个节点快速传播，这表明该节点的影响力更大。你可以在[我的关于高级图分析的文章中]了解更多关于感染传播模型的信息。(https://blog.devgenius.io/analyzing-graph-networks-part-2-utilizing-advanced-methods-604ade49f9b8)

https://github.com/OpenDocCN/towardsdatascience-blog-zh-2024/raw/master/docs/img/26d32f5a3617b5194a38e12d773a1247.png

这是一张图像，显示了通过图表按时间戳传播的感染情况，显示了多次运行的结果。蓝色线是平均值，红色部分是标准差。你可以注意到，感染在开始时迅速传播，然后在每个时间戳感染节点较少时趋于停滞。图像由作者提供。

你应该使用哪种度量标准将取决于你正在解决的问题和你的图表类型。通常很难事先知道哪种度量标准最能代表你的图表，因此在对下游任务测试不同的度量标准通常是可行的。此外，正如我将在下一节中解释的，你还可以将不同的度量标准结合起来，形成一个更强大的度量标准，以表示节点的影响。

度量标准的组合

除了计算节点影响力的单个度量标准之外，你还可以将度量标准结合起来。我将向你展示在图中结合度量标准的两种主要方法。我还会可视化所选的图中的节点，你可以使用以下函数来完成：

defhighlight_frozen_nodes(G,freezed_nodes):"""given adjacency matrix and a list of frozen nodes. Visualize a graph were the frozen nodes are highlighted. Graph is also drawn deterministically, so layout does not change everyti,e"""colors=['yellow'ifnodeinfreezed_nodeselse'lightblue'fornodeinG.nodes()]pos=nx.spring_layout(G,seed=28)# Fixed seed for reproducibilitynx.draw(G,pos,with_labels=True,node_color=colors)plt.show()

归一化并添加

首先，你可以简单地将两个不同的度量标准相加，以形成一个组合度量标准。然而，在这样做的时候，你必须记住首先将每个度量标准归一化到 0 到 1 之间，以便度量标准的尺度相等。这个理由可以通过查看两个度量标准，即度影响力与介数中心性影响力来理解。一个节点的度通常范围从 0 到一个很大的整数，而介数中心性将在 0 和 1 之间。如果你将来自不同尺度的两个数字结合起来，较大的数字（在这个例子中是度），将产生更大的影响。因此，你必须记住在将它们相加之前归一化度量标准。你可以在下面的代码中看到如何对两个节点影响力度量标准度与介数中心性进行归一化。

degrees=np.array(list(degreefor_,degreeinlist(G.degree())))centralities=np.array(list(nx.betweenness_centrality(G).values()))# # normalize degree and centralities to be between 0 and 1degrees=(degrees-np.min(degrees))/(np.max(degrees)-np.min(degrees))centralities=(centralities-np.min(centralities))/(np.max(centralities)-np.min(centralities))combined_scores=degrees+centralities combined_scores

自然地，这不仅仅限于两个度量标准，你可以结合你喜欢的任意多个，只要每个度量标准都是归一化的。此外，你还可以为每个度量标准添加权重，这本质上意味着某些度量标准比其他度量标准更重要。例如，如果你认为节点的度对于该节点的影响更为重要，你可以为度度量标准添加权重，使其对节点的影响更为重要。你可以在下面的代码中看到我是如何使度比介数中心性在代码中重要两倍的。

weighting=np.array([2/3,1/3]).reshape(1,-1)#normalize weighting to sum to 1:weighting=weighting/np.sum(weighting)degrees=np.array(list(degreefor_,degreeinlist(G.degree())))centralities=np.array(list(nx.betweenness_centrality(G).values()))# # normalize degree and centralities to be between 0 and 1degrees=(degrees-np.min(degrees))/(np.max(degrees)-np.min(degrees))centralities=(centralities-np.min(centralities))/(np.max(centralities)-np.min(centralities))combined_scores=np.column_stack((degrees,centralities))# multiply by weightsweighted_combined_scores=combined_scores*weighting# sum the weighted scoressummed_scores=np.sum(weighted_combined_scores,axis=1)

分别为每个度量标准选择节点

您也可以选择为每个指标单独选择节点。比如说，您，例如，想要从图中选择 N 个最有影响力的节点；您可以先从度指标中选择 N/2 个节点，然后从介数中心性指标中选择 N/2 个节点。这种替代方案让您可以只关注度，有时甚至只关注介数中心性，如果您更重视个体而不是两个指标的组合，这可能是一个优势。例如，您可能想要选择一个度数非常高的节点，但如果该节点的介数中心性较低，它将不会被选中。然而，为每个指标单独选择节点将解决这个问题，并允许您选择在单个指标上表现良好的节点。

选择节点集

在您为每个节点单独计算节点影响力指标之后，是时候选择一个节点选择策略了。这里我指的是选择最能代表图的节点集。这是一个更难解决的问题，因为您可以选择的节点组合有无数种。因此，您需要一个启发式方法来告诉您如何决定包含和排除在所选节点中的节点。下面，我将向您展示两种选择一组最能代表图的节点的主要方法，同时考虑之前计算的节点影响力指标。

使用社区检测

您可以使用的第一种方法是社区检测来找出每个节点属于哪个社区。可以使用多种社区检测方法，如 Louvain、Girvan-Newman 或谱聚类。您应该使用哪种方法将取决于您正在解决的问题。例如，如果您正在处理加权边，我建议使用考虑边的社区检测算法，如 Louvain。同样，如果您正在处理具有固定社区数量的问题，我也建议选择可以使用固定数量社区的算法，如谱聚类。

我还想补充一点，我自己正在研究一个半监督聚类问题，但我仍然认为选择节点组合的社区检测方法可能有效。理由是您不需要使用的社区检测算法完美工作。使用社区检测的目的在于找到图中不同社区中的节点，这反过来会增加所选节点组合的代表性。

https://github.com/OpenDocCN/towardsdatascience-blog-zh-2024/raw/master/docs/img/0ec937d283e42561a05b4f678e5b881d.png

在图像中显示的图中应用了 Louvain 社区检测算法。该算法将图分为两个合理的社区。图片由作者提供。

要选择最具影响力的节点集，我首先会计算每个节点的相关节点影响力指标。然后，我会遍历社区检测算法找到的每个社区，并选择该社区中节点影响力分数最高的节点。此外，您必须确保您选择的是之前未选择的节点。从社区中选择一个节点后，您就可以继续到下一个社区，并从该社区中选择最具影响力的节点，依此类推，直到您从每个社区中选择了节点。然后，您可以从第一个社区重新开始循环，并从该社区中选择第二个最具影响力的节点。当您选择了所需的节点数量后，您就可以退出循环。

此方法确保您根据自己的指标选择高影响力节点，并从不同社区中选择多样化的节点样本。这将比只关注最高影响力节点并忽略所有社区更好地代表图。

要在 Python 中实现此操作，您需要 Python Louvain 包：

pip install python-louvain

然后，您可以使用以下代码根据每个节点的度分数从每个社区中选择节点：

importcommunityascommunity_louvain# select one node per partitiondefselect_nodes_based_on_communities(G,partition,scores,n=2):"""given a node influence score per node, select n nodes based on communities"""sorted_node_indices=np.argsort(scores)[::-1]# highest to lowest degree node indiceschosen_nodes=set()for_inrange(n):forcommunityinset(partition.values()):fornode_idxinsorted_node_indices:node_idx+=1# node indices are 1-basedifnode_idxnotinchosen_nodesandpartition[node_idx]==community:chosen_nodes.add(node_idx)if(len(chosen_nodes)>=n):returnchosen_nodesbreakraiseException("Not enough nodes to select")#if you got here, you did not select enough nodesnum_nodes_to_select=2partition=community_louvain.best_partition(G)selected_nodes=select_nodes_based_on_communities(G,partition,degrees,num_nodes_to_select)

使用上述代码将选择图中的节点 4 和 5，如图所示：

https://github.com/OpenDocCN/towardsdatascience-blog-zh-2024/raw/master/docs/img/2e758b9a88188f57b8c8144f4db089bd.png

节点 4 和 5 被选为基于度影响力分数和基于社区选择的最具影响力的 2 节点组合，图像由作者提供。

上图突出显示了一个问题：尽管节点来自不同的社区，但它们在图中通常直接相连。在下一节中，我将向您展示一种避免此问题的方法。

使用节点之间的最小步数

另一种您可以采用的方法是确保节点之间的最小步数。最简单的方法是将最小步数设置为 2，这确保所选节点不是邻居。

要选择最具影响力的节点集，您首先找到每个节点的所有相关节点影响力指标。然后，根据您的指标选择最具影响力的节点。接下来，转到第二个最具影响力的节点。如果该节点与已选择的节点（在这种情况下，如果第二个最具影响力的节点与最具影响力的节点相邻）的最小步数不足，则忽略该节点并转到第三个最具影响力的节点。如果第三个最具影响力的节点与已选择的节点超过 2 步的距离，则选择该节点。

你然后继续这样做，始终确保最新的所选节点与其他所有已选节点保持最小步数。这确保了你的节点选择是从图中抽取的多样化样本。

要用代码实现这一点，你可以使用下面的 Python 代码：

importcommunityascommunity_louvain# select one node per partitiondefselect_nodes_based_on_min_steps(G,scores,n=2,min_steps=2):"""given a node influence score per node, select n nodes based on communities"""sorted_node_indices=np.argsort(scores)[::-1]# highest to lowest degree node indiceschosen_nodes=set()for_inrange(num_nodes_to_select):# run max num_nodes_to_select times. Use this loop to ensure we select from each communityforninrange(n,0,-1):# if we do not get all nodes to select in n steps, we will decrease n by 1 and try againfornode_idxinsorted_node_indices:# iterate over nodes in order of scorenode_idx+=1#since my nodes start at index 1if(node_idxnotinchosen_nodes):#check if node is at least n steps away from any frozen nodeifall([nx.shortest_path_length(G,node_idx,chosen_node)>=nforchosen_nodeinchosen_nodes]):chosen_nodes.add(node_idx)iflen(chosen_nodes)>=num_nodes_to_select:returnchosen_nodes num_nodes_to_select=2min_steps=2selected_nodes=select_nodes_based_on_min_steps(G,degrees,num_nodes_to_select,min_steps)

这将导致选择节点 4 和 7，正如你在下面的图像中看到的那样：

https://github.com/OpenDocCN/towardsdatascience-blog-zh-2024/raw/master/docs/img/3d2bd41a9657d1dee84d53647f6264d8.png

在这张图像中，节点 4 和 7 是基于节点度和所选节点之间至少两步的距离被选中的。图由作者提供。

结合社区检测和最小步数

选择节点组合的第三种方法是结合我之前提到的两种方法。首先，你找到图中的不同社区。然后，你可以在附加条件下从每个社区中选择最有影响力的节点，即所选节点也必须与已选择的节点保持最小步数。

在我看来，这种方法是选择节点组合的最佳方式。它确保图中的每个社区都由一个所选节点代表，并进一步确保所选节点之间没有连接，这增加了它们的代表性。

然而，重要的是要注意，不同的方法在不同的图上可能效果更好或更差。哪种方法最适合你将取决于你使用的图，因此我建议尝试不同的方法，看看哪一种最适合你。

你可以通过以下方式根据社区检测和最小步数选择一组节点：

defselect_nodes_based_on_communities_and_min_number_steps(G,partition,scores,n=2,min_steps=2):"""given a node influence score per node, select n nodes based on communities"""sorted_node_indices=np.argsort(scores)[::-1]# highest to lowest degree node indiceschosen_nodes=set()for_inrange(n):forcommunityinset(partition.values()):fornode_idxinsorted_node_indices:node_idx+=1ifnode_idx+1notinchosen_nodesandpartition[node_idx]==communityandall([nx.shortest_path_length(G,node_idx,chosen_node)>=nforchosen_nodeinchosen_nodes]):chosen_nodes.add(node_idx)if(len(chosen_nodes)>=n):returnchosen_nodesbreaknum_nodes_to_select=2min_steps=2partition=community_louvain.best_partition(G)selected_nodes=select_nodes_based_on_communities_and_min_number_steps(G,partition,degrees,num_nodes_to_select,min_steps)

这实际上与社区选择代码相同，但在 if 语句中有一个额外的条件，即节点之间至少要有 n 步的距离。

如果你使用上面的代码，你应该选择节点 2 和 5，这将给出以下结果：

https://github.com/OpenDocCN/towardsdatascience-blog-zh-2024/raw/master/docs/img/c8c98791b1020810d0e8decd884f7def.png

图像显示了使用度作为节点影响力分数，并根据社区和它们之间的最小步数选择节点集的结果。图由作者提供。

测试所选节点的影响力

在你根据节点影响力指标和社区检测或最小步数方法选择了节点之后，你也应该测试它们。在这种情况下的问题是，没有可以告诉你是否选择了最优节点集的基准真理。尽管如此，我仍将向你展示你可以用来评估所选节点集质量的三个测试。

测试 1：连接到所选节点的节点数量

第一次测试计算的是与您选择的节点相连的节点数量。这个测试代表了您的节点在图中的连接程度，并且可以告诉您您选择的节点组合是否能够代表整个图。这个测试的分数越高，意味着您选择的节点集更好。

然而，您应该意识到，如果您优先选择高度节点，这个测试将表现得更好，因为它们通常连接到更多的节点。尽管如此，这是一个很好的测试，可以衡量使用社区检测或最小步数是否是选择图节点集的最佳方式。此外，您应该将此测试作为一个相对度量来使用，仅将其与其他图在同一测试中的结果进行比较，以查看图是否更好或更差。

如果您使用度影响分数进行此测试，并选择基于社区检测和最小步数的节点组合，您将选择图中的 8/8 个节点，您可以可视化如下：

https://github.com/OpenDocCN/towardsdatascience-blog-zh-2024/raw/master/docs/img/86705c2ca405bc69b60636677aaaf1e8.png

这张图像可视化了由选择节点到达的节点。在这种情况下，选择了节点 2 和 5，您可以看到这两个节点合并并连接到图中的所有其他节点。图由作者提供。

如果您只根据它们的社区选择节点，您将连接到图中的 7/8 个节点，错过索引为 1 的节点，如下面的图像所示：

https://github.com/OpenDocCN/towardsdatascience-blog-zh-2024/raw/master/docs/img/78e8f7f193c369a83d80387059d54b12.png

这张图像可视化了选择节点 4 和 5 的情况，您可以看到它们连接到所有节点，除了 1 个，突出了这种方法的问题。图由作者提供。

测试 2：与选择节点相连的社区数量

您还可以使用另一个测试，即您的选择节点集影响的社区数量。这个测试可以表示您选择的节点集如何影响图中的不同社区，这对于连接图中的所有节点非常重要。然而，您应该注意，这个测试自然会偏向于基于社区选择节点集。这个测试也应该作为一个相对度量，类似于我之前解释的最后一个测试。

测试 3：下游任务

您还可以使用的一个可靠的测试是测试选择节点在下游任务中的表现。例如，我正在使用选择节点集进行半监督聚类下游任务。因此，我可以测试不同的节点选择方法。

然而，重要的是要记住，在测试下游任务时，还有其他几个因素可能会发挥作用，比如聚类的随机性或其他决策，如超参数。尽管如此，下游任务上获得的分数可以表明所选节点的质量。

https://github.com/OpenDocCN/towardsdatascience-blog-zh-2024/raw/master/docs/img/8014464106743f9f3b7034f78428d424.png

这是一张表示将社区检测应用于图的图像，预测的社区由圆圈表示，真实的社区由节点的颜色表示。你可以看到在这个案例中，社区检测做得很好，这表明你选择了一组好的节点。图片由作者提供。

测试 4：视觉检查

第四次也是最后一次测试是视觉检查，这是我总是推荐在进行机器学习项目时进行的测试。进行视觉检查将帮助你进一步了解你正在处理的问题。在这种情况下，对所选节点的视觉检查让你能够看到所选节点对你的图的影响，尤其是在较小的图中；你可以理解所选节点集是好是坏。例如，如果你在视觉检查中注意到选择了大量异常节点，这表明你的节点选择中存在错误，你需要修复它。此外，视觉检查还允许你发现你在选择节点集时的潜在改进。

当对节点进行视觉检查时，我使用了大量的 NetworkX 来处理较小的图，这让我可以直接在我的 Jupyter Notebook 中可视化图。然而，对于较大的图来说，这并不太有效，在这种情况下，我建议使用像 Cytoscape 这样的图形可视化工具，它提供了大量可视化你的图和查看图有趣方面的选项，这可以帮助你进一步理解你的图。如果你想了解更多关于理解图质量的信息，你可以阅读我下面的文章：

如何测试图质量以提高图机器学习性能

结论

在这篇文章中，我讨论了你可以使用不同的方法来选择图中最具影响力的节点组合。首先，你使用诸如度或介数中心性等指标单独计算每个节点的影响力。然后，你可以使用不同的方法来选择节点组合，例如使用像 Louvain 这样的社区检测算法从不同的社区中选择节点。你也可以选择它们之间至少有最小步数的节点，或者使用最小步数和社区检测的组合。最后，我还提到了你可以用来测试所选节点质量的不同测试，包括以下测试：