This page is documentation for a DEVELOPMENT / PRE-RELEASE version. Switch to stable version
logo
  • 安装
  • 教程
  • 参考文献
  • 释放
  • 开发商
  • 绘图示例
  • Guides
    • devel (latest)
    • current (stable)
  • 属性
  • 读写图表。
  • 简单图
  • 国际象棋大师
  • 自定义节点图标
  • 学位分析
  • 有向图
  • 边色图
  • 自我图
  • 本征值
  • 四网格
  • 有颜色的房子
  • 克努斯英里
  • 标签和颜色
  • 多部分布局
  • 节点色图
  • 彩虹上色
  • 随机几何图形
  • 桑普森
  • 自环
  • 简单路径
  • 谱嵌入
  • 旅行商问题
  • UNIX电子邮件
  • 赋权图
  • 梅亚维2
  • 基本Matplotlib
  • 阿特拉斯
  • 圆树
  • 分解
  • 巨型构件
  • Lanl路线
  • 属性
  • 转换
  • 二维网格
  • 阿特拉斯
  • 度序列
  • 鄂尔多斯仁义
  • 期望度序列
  • 足球
  • 空手道
  • 拿破仑俄国战役
  • 罗格特
  • 文字/阶梯图
  • 波束搜索
  • 中间性中心性
  • 块模型
  • 电路
  • 戴维斯俱乐部
  • 脱敏
  • 迭代动力系统
  • 克拉克哈特中心性
  • 平行中间值
  • 反向Cuthill--McKee
  • 捕捉图摘要
  • 子图
  • JavaScript
  • 字形
  • 基于地理点的Delaunay图
  • 来自一组线的图形
  • 使用OSMnx的OpenStreetMap
  • 来自地理点的图表
  • 来自多边形的图表
  • 反图
  • 打印图
On this page
  • 寻找具有高中心度的节点。

备注

点击 here 下载完整的示例代码

波束搜索#

动态波束宽度的波束搜索。

渐进式加宽波束搜索反复执行波束搜索,不断增加波束宽度,直到找到目标节点。

import math

import matplotlib.pyplot as plt
import networkx as nx


def progressive_widening_search(G, source, value, condition, initial_width=1):
    """Progressive widening beam search to find a node.

    The progressive widening beam search involves a repeated beam
    search, starting with a small beam width then extending to
    progressively larger beam widths if the target node is not
    found. This implementation simply returns the first node found that
    matches the termination condition.

    `G` is a NetworkX graph.

    `source` is a node in the graph. The search for the node of interest
    begins here and extends only to those nodes in the (weakly)
    connected component of this node.

    `value` is a function that returns a real number indicating how good
    a potential neighbor node is when deciding which neighbor nodes to
    enqueue in the breadth-first search. Only the best nodes within the
    current beam width will be enqueued at each step.

    `condition` is the termination condition for the search. This is a
    function that takes a node as input and return a Boolean indicating
    whether the node is the target. If no node matches the termination
    condition, this function raises :exc:`NodeNotFound`.

    `initial_width` is the starting beam width for the beam search (the
    default is one). If no node matching the `condition` is found with
    this beam width, the beam search is restarted from the `source` node
    with a beam width that is twice as large (so the beam width
    increases exponentially). The search terminates after the beam width
    exceeds the number of nodes in the graph.

    """
    # Check for the special case in which the source node satisfies the
    # termination condition.
    if condition(source):
        return source
    # The largest possible value of `i` in this range yields a width at
    # least the number of nodes in the graph, so the final invocation of
    # `bfs_beam_edges` is equivalent to a plain old breadth-first
    # search. Therefore, all nodes will eventually be visited.
    log_m = math.ceil(math.log2(len(G)))
    for i in range(log_m):
        width = initial_width * pow(2, i)
        # Since we are always starting from the same source node, this
        # search may visit the same nodes many times (depending on the
        # implementation of the `value` function).
        for u, v in nx.bfs_beam_edges(G, source, value, width):
            if condition(v):
                return v
    # At this point, since all nodes have been visited, we know that
    # none of the nodes satisfied the termination condition.
    raise nx.NodeNotFound("no node satisfied the termination condition")

寻找具有高中心度的节点。#

我们生成一个随机图,计算每个节点的中心度,然后进行逐步加宽搜索,以找到一个高中心度的节点。

# Set a seed for random number generation so the example is reproducible
seed = 89

G = nx.gnp_random_graph(100, 0.5, seed=seed)
centrality = nx.eigenvector_centrality(G)
avg_centrality = sum(centrality.values()) / len(G)


def has_high_centrality(v):
    return centrality[v] >= avg_centrality


source = 0
value = centrality.get
condition = has_high_centrality

found_node = progressive_widening_search(G, source, value, condition)
c = centrality[found_node]
print(f"found node {found_node} with centrality {c}")


# Draw graph
pos = nx.spring_layout(G, seed=seed)
options = {
    "node_color": "blue",
    "node_size": 20,
    "edge_color": "grey",
    "linewidths": 0,
    "width": 0.1,
}
nx.draw(G, pos, **options)
# Draw node with high centrality as large and red
nx.draw_networkx_nodes(G, pos, nodelist=[found_node], node_size=100, node_color="r")
plt.show()
plot beam search

出:

found node 73 with centrality 0.12598283530728402

脚本的总运行时间: (0分0.191秒)

Download Python source code: plot_beam_search.py

Download Jupyter notebook: plot_beam_search.ipynb

Gallery generated by Sphinx-Gallery

© Copyright 2004-2022, NetworkX Developers.

Created using Sphinx 4.5.0.