NetworkX: 图论算法应用

2024-01-08 NetworkX PV:

NetworkX

NetworkX是一款Python的软件包，用于创造、操作复杂网络，以及学习复杂网络的结构、动力学及其功能。有了NetworkX就可以用标准或者不标准的数据格式加载或者存储网络，它可以产生许多种类的随机网络或经典网络，也可以分析网络结构、建立网络模型、设计新的网络算法、绘制网络等

参考文献地址: https://www.osgeo.cn/networkx/reference/index.html

图计算应用方式比较

1.nebula + spark

依赖nebula-spark-connector包、nebula-algorithm包和spark集群的数据读取、图计算方式

2.clickhouse + NetworkX

由于nebula-algorithm依赖spark集群，且nebula-console原生的数据读取能力不佳，在环境受限且计算量有限的情况下优先考虑跳过spark集群和nebula图库，采用clickhouse + NetworkX的图计算方式，其中clickhouse是存储了nebula源数据的列式分布式表，作用类似于方法1中将nebula集群数据通过nebula-spark-connector包导入为spark-DataFrame，仅用做数据读取，再通过将数据转化为NetworkX的图结构进行图计算

应用实例

nebula集群存储以群聊和群成员、好友关系所组成的关系网，clickhouse集群存储节点源数据和对应关系

一、集合运算

交、并、差集

直接使用clickhouse进行查询，适用于两个群组成员或账号所加群的交并差集

输入：

· n个账号（n≥2）

· n个群组（n≥2）

二、路径探寻

直接使用nebula进行查询，适用于搜索图谱中任意两个节点的最短可达路径

输入：

· 任意类型2个节点

三、中心性

输入：

· n个群组（n≥1），分析包括指定n个群组、群组群成员、群成员所加群组成关系网各节点的中心性

· n个账号（n≥1），分析包括指定n个账号、账号所加群、群成员组成关系网各节点的中心性

· 指定关系网，分析各节点中心性

ClickHouse SQL示例（关系图谱）：

1
2
3

SELECT  team_id,account_id FROM mqv3.ly_team_ship lts 
PREWHERE account_id GLOBAL IN 
(SELECT account_id FROM mqv3.ly_team_ship lts PREWHERE team_id='{src_vid}');

1.度中心性

衡量节点中心性的指标

1
2
3

res = nx.degree_centrality(G)
res = dict(sorted(res.items(), key=lambda x: x[1], reverse=True))
print(res)

e.g. 以群（-1151413367、-1541749047）为指定节点，计算三级关系网各节点度中心性（抛弃度<5的节点，突出结构）

2.接近中心性

反映在关系网络中某一节点与其他节点之间的接近程度

1
2
3

res = nx.closeness_centrality(G)
res = dict(sorted(res.items(), key=lambda x: x[1], reverse=True))
print(res)

e.g. 以群（-1151413367、-1541749047）为指定节点，计算三级关系网各节点接近中心性（抛弃度<50的节点，突出结构）

3.中介中心性

以经过某个节点的最短路径数目来刻画节点重要性的指标

1
2
3

res = nx.betweenness_centrality(G, k=1000)
res = dict(sorted(res.items(), key=lambda x: x[1], reverse=True))
print(res)

e.g. 以群（-1151413367、-1541749047）为指定节点，计算三级关系网各节点中介中心性（抛弃度<5的节点，突出结构）

4.特征向量中心性

关系网络中一个节点的重要性既取决于其邻居节点的数量（即该节点的度），也取决于其邻居节点的重要性

1
2
3

res = nx.eigenvector_centrality(G)
res = dict(sorted(res.items(), key=lambda x: x[1], reverse=True))
print(res)

e.g. 以群（-1151413367、-1541749047）为指定节点，计算三级关系网各节点特征向量中心性（抛弃度<5的节点，突出结构）

四、重要性

输入：

· n个群组（n≥1），分析包括指定n个群组、群组群成员、群成员所加群组成关系网各节点的重要程度

· n个账号（n≥1），分析包括指定n个账号、账号所加群、群成员组成关系网各节点的重要程度

· 指定关系网，分析各节点的重要程度

1.k核

用于在图中寻找符合一定紧密关系条件（K）的子图结构的算法，要求每个顶点至少与该子图的其他K个顶点关联

res1 = nx.core_number(G)
res2 = nx.k_core(G, 6)
res1 = dict(sorted(res1.items(), key=lambda x: x[1], reverse=True))
print(res1)
print(list(res2))

e.g. 以群（-1151413367、-1541749047）为指定节点，计算三级关系网各节点k-core值，结合louvain社区上色（全图）

2.PageRank

衡量图中节点重要性的指标，值越高，图中访问该节点的概率越高

1
2
3

res = nx.pagerank(G, alpha=0.85)
res = dict(sorted(res.items(), key=lambda x: x[1], reverse=True))
print(res)

e.g.1. 以群（-1151413367、-1541749047）为指定节点，计算三级关系网各节点pagerank值（抛弃度<5的节点，突出结构）

e.g.2. 以群（-1151413367、-1541749047）为指定节点，计算三级关系网各节点pagerank值，结合louvain社区（全图）

五、聚类算法

输入（社区发现）：

· n个群组（n≥1），划分包括指定n个群组、群组群成员、群成员所加群组成关系网的各个社区

· n个账号（n≥1），划分包括指定n个账号、账号所加群、群成员组成关系网的各个社区

· 划分指定关系网各节点的社区

输入（三角形计数）：

· n个群组（n≥1），计算包括指定n个群组、群组群成员、群成员好友、群成员所加群组、群成员所加群组成关系网的三角形数量，挖掘团体关系

· 计算指定关系网各节点的三角形数量，挖掘团体关系

用于计算图谱中三角关系数量，挖掘关系团体

ClickHouse SQL示例（三角形计数）：

WITH T AS(-- 指定群群成员
SELECT DISTINCT team_id,account_id FROM mqv3.ly_team_ship PREWHERE team_id = '{src_vid}'
),T1 AS(-- 指定群群成员的好友
SELECT DISTINCT account_id,fri_account_id FROM mqv3.ly_account_ship PREWHERE account_id GLOBAL IN (SELECT account_id FROM T) 
UNION DISTINCT 
SELECT DISTINCT fri_account_id,account_id FROM mqv3.ly_account_ship PREWHERE fri_account_id GLOBAL IN (SELECT account_id FROM T)
),T2 AS(-- 群成员所加群
SELECT DISTINCT team_id,account_id FROM mqv3.ly_team_ship PREWHERE account_id GLOBAL IN (SELECT account_id FROM T)
),T3 AS(-- 群成员所加群和群成员和群成员的好友
SELECT DISTINCT team_id,account_id,fri_account_id FROM T2 RIGHT JOIN T1 ON T2.account_id = T1.account_id
),T4 AS(-- 群成员好友所加群
SELECT DISTINCT team_id,account_id AS fri_account_id FROM mqv3.ly_team_ship lts PREWHERE lts.account_id GLOBAL IN (SELECT fri_account_id FROM T1)
),T5 AS(-- 共同所加群
SELECT DISTINCT team_id,account_id,fri_account_id FROM T3 JOIN T4 ON (T3.team_id = T4.team_id AND T3.fri_account_id = T4.fri_account_id)
)
select DISTINCT team_id,account_id,fri_account_id from T5

1.标签传播（LPA社区发现）

基于lpa的社区划分

1 2	res = nx.algorithms.community.label_propagation_communities(G) print(list(res))

e.g.以群（-1151413367、-1541749047）为指定节点，划分lpa标签传播社区（抛弃度<5的节点，突出结构）

2.鲁汶（Louvain社区发现）

基于louvain的社区划分

1 2	res = nx.algorithms.community.louvain_communities(G, resolution=0.5) print(res)

e.g.1.以群（-1151413367、-1541749047）为指定节点，划分louvain鲁汶社区（resolution=1，抛弃度<5的节点，突出结构）

e.g.2.以群（-1151413367、-1541749047）为指定节点，划分louvain鲁汶社区（resolution=0.3，抛弃度<5的节点，突出结构）

3.三角形计数

1
2
3

res = nx.triangles(G)
res = dict(sorted(res.items(), key=lambda x: x[1], reverse=True))
print(res)

e.g.以群（-1151413367、-1541749047）为指定节点，计算关系网中各个节点三角形数量（抛弃度<5的节点，突出结构）

六、连通性

输入：

· 指定n个群组（n≥2），判断群组、群成员、群成员所加群所组关系网是否为连通图

· 指定n个账号（n≥2），判断账号、账号所加群、群成员所组关系网是否为连通图

· 指定关系网

1.连通性检测

判断目标图谱是否为连通图

1 2	res1 = nx.is_connected(G) print(res1)

e.g.1.连通图

e.g.2.非连通图

2.联通组件数

判断目标图谱中联通组件的数量（n）

1 2	res2 = nx.number_connected_components(G) print(res2)

3.联通组件

显示目标图谱中的全部联通组件

1 2	res3 = nx.connected_components(G) print(res3)

4.指定节点联通组件

显示目标图谱中指定节点所在的联通组件

1 2	res4 = nx.node_connected_component(G, "sample_node") print(res4)

七、几何

输入：

· 指定n个群组（n≥2），计算群组、群成员、群成员所加群所组关系网的中心、重心

· 指定n个账号（n≥2），计算账号、账号所加群、群成员所组关系网的中心、重心

· 计算指定关系网几何中心、重心

1.几何重心

图的重心节点

1 2	res1 = nx.barycenter(G) print(res1)

2.几何中心

图的中心节点

1 2	res2 = nx.center(G) print(res2)

绘图

e.g. 中心中心性 + LPA标签传播算法聚类

数据源：https://www.inetbio.org/wormnet/downloadnetwork.php

· WormNet v.3-GS (https://www.inetbio.org/wormnet/download.php?type=2)

完整代码：

from random import sample
import networkx as nx
import matplotlib.pyplot as plt

# Gold standard data of positive gene functional associations
# from https://www.inetbio.org/wormnet/downloadnetwork.php
G = nx.read_edgelist("WormNet.v3.benchmark.txt")

# remove randomly selected nodes (to make example fast)
num_to_remove = int(len(G) / 1.5)
nodes = sample(list(G.nodes), num_to_remove)
G.remove_nodes_from(nodes)

# remove low-degree nodes
low_degree = [n for n, d in G.degree() if d < 10]
G.remove_nodes_from(low_degree)

# largest connected component
components = nx.connected_components(G)
largest_component = max(components, key=len)
H = G.subgraph(largest_component)

# compute centrality
centrality = nx.betweenness_centrality(H, k=10, endpoints=True)

# compute community structure
lpc = nx.community.label_propagation_communities(H)
community_index = {n: i for i, com in enumerate(lpc) for n in com}

#### draw graph ####
fig, ax = plt.subplots(figsize=(20, 15))
pos = nx.spring_layout(H, k=0.15, seed=4572321)
node_color = [community_index[n] for n in H]
node_size = [v * 20000 for v in centrality.values()]
nx.draw_networkx(
    H,
    pos=pos,
    with_labels=False,
    node_color=node_color,
    node_size=node_size,
    edge_color="gainsboro",
    alpha=0.4,
)

# Title/legend
font = {"color": "k", "fontweight": "bold", "fontsize": 20}
ax.set_title("Gene functional association network (C. elegans)", font)
# Change font color for legend
font["color"] = "r"

ax.text(
    0.80,
    0.10,
    "node color = community structure",
    horizontalalignment="center",
    transform=ax.transAxes,
    fontdict=font,
)
ax.text(
    0.80,
    0.06,
    "node size = betweeness centrality",
    horizontalalignment="center",
    transform=ax.transAxes,
    fontdict=font,
)

# Resize figure for label readibility
ax.margins(0.1, 0.05)
fig.tight_layout()
plt.axis("off")
plt.show()