Python 的图形工具：生成第 n 阶的 egonet

Question

似乎graph-tool library中没有内置函数来生成一个子图，该子图包含某个节点的所有邻居，直到n次。这个问题也可以被定义为使用 n 度邻居在节点周围构建一个 egonet。让我们考虑以下玩具示例：

from graph_tool.all import *

edge_list = [
    [('node', 0), ('node', 1), 'xyz'],
    [('node', 1), ('node', 2)],
    [('node', 2), ('node', 3)],
    [('node', 3), ('node', 4), 'abc'],
    [('node', 0), ('node', 4)],
    [('node', 4), ('node', 5)],
    [('node', 5), ('node', 6)],
    [('node', 6), ('node', 7)],
    [('node', 0), ('node', 8)],
    [('node', 7), ('node', 8)],
    [('node', 7), ('node', 9)],
    [('node', 9), ('node', 10)]
]

g = Graph(directed=False)

我添加了一些属性（顶点和边）以检查它们是否传播到子图：

edge_attributes = g.new_edge_property("string")
g.edge_properties['edge_attributes'] = edge_attributes

nodes_id = g.add_edge_list(edge_list, hashed=True, eprops = [edge_attributes] )
g.vertex_properties['nodes_id'] = nodes_id

bool_flg = g.new_vertex_property('int')
bool_flg.set_value(0)
bool_flg[4] = 1
g.vertex_properties['bool_flg'] = bool_flg

因为我从节点的外部名称开始，例如('node', 0)（graph-tool 库对连续的非负整数进行操作）我定义了一个节点 ID 检索函数：

def find_vertex_id(G, node, id_mapping='nodes_id'):
    return int(find_vertex(G, G.vertex_properties[id_mapping], node)[0])

第一步（也是最耗时的）步骤（基于 networkx 解决方案）是生成连接到根节点的 ID（满足 egonet 要求）：

def get_neighbours_n_degree(G, source, cutoff=None):
    seen = set()
    level = 0

    source_id = find_vertex_id(G, source) # translate into int id

    nextlevel={source_id}

    while nextlevel:
        thislevel = nextlevel
        nextlevel = set()
        for v in thislevel:
            if v not in seen:
                seen.update([v]) #set must be updated with an iterable
                nextlevel.update(g.get_all_neighbors(v)) #add neighbours
        if (cutoff is not None and cutoff <= level):
            break
        level = level + 1

    return seen # include the root

子图生成如下：

def generate_subgraph(G, source, cutoff=None):
    subgraph_nodes = get_neighbours_n_degree(G=G, source=source, cutoff=cutoff)

    vfilt = G.new_vertex_property('bool')
    for i in subgraph_nodes:
        vfilt[i] = True

    sub = GraphView(G, vfilt)
    sub = Graph(sub, prune=True) #create independent copy; restart the node index

    return sub

我还定义了一个绘图函数：

def graph_draw_enhanced(graph):
    graph_draw(graph, vertex_text=graph.vertex_index,
              vertex_fill_color = graph.vertex_properties['bool_flg'])

我的自定义函数在提供的示例中运行良好，但在提供 8M 节点的网络时开始变慢 - 计算 4 次 egonet 大约需要 2.5 分钟。在graph-tool中是否有更优化的创建egonet的方法？

解决方案应该return一个包含与原始图相同的顶点和边信息的子图。

subgraph = generate_subgraph(g, ('node', 0), cutoff=2)

# check for edges
for edge in subgraph.edges():
    print(edge, g.edge_properties['edge_attributes'][edge])

# check for nodes
for node in subgraph.vertices():
    print(node, g.vertex_properties['bool_flg'][node])

Answer 1

使用图形工具的过滤功能，这要容易得多。这是一个简单的函数，它生成一个 ego 网络，最高为 n:

def ego_net(g, ego, n): 
    d = shortest_distance(g, ego, max_dist=n) 
    u = GraphView(g, vfilt=d.a < g.num_vertices()) 
    return u

这是对原始图形的 returns 一个 GraphView，因此保留了所有内部属性地图和顶点索引。如果需要独立图，可以通过创建新的修剪图来完成：

u = ego_net(g, ego, n)
u = Graph(u, prune=True)

上述方法应该比问题中提出的方法快得多。

Python 的图形工具：生成第 n 阶的 egonet

Python' s graph-tool: Generate egonet up n-th degree

python

graph

graph-tool