带有传播源头标识的图节点相关性及中心节点计算算法 (Graph Diffusion with Source, GDS)

项目简介

本项目实现了一种基于图传播的节点相关性分析算法，该算法通过带有源头标识的信息传播机制，计算图中节点间的相关性，并识别图的中心节点。此算法适用于社交网络分析、欺诈检测、推荐系统等场景，可有效识别图中的关键节点和社区结构。

核心功能

1. 带有源头标识的图传播算法 - 追踪信息传播路径，保留源节点标识
2. 节点相关性计算 - 基于传播模型计算节点间的相关性
3. 中心节点识别 - 识别图中的重要节点
4. 边介数近似计算 - 快速估算边的介数中心性
5. K核社区发现 - 基于K核分析发现紧密连接的社区结构

目录结构

graph_diffuse_with_source/
├── doc/                    # 文档目录
│   ├── explain.md          # 算法详细说明
│   ├── explain_en.md       # 算法英文说明
│   ├── gds_mathematical_analysis.md   # 算法数学分析
│   └── images/             # 文档图片
├── image/                  # 示例图片
├── src/                    # 源代码目录
│   ├── graph_diffuse_with_source/     # 核心模块
│   │   ├── __init__.py     # 包初始化文件
│   │   ├── gds.py          # 核心算法实现
│   │   ├── gds_edge_betweenness.py    # 边介数计算
│   │   └── gds_k_core_clique.py       # K核社区发现
│   ├── gds_community.ipynb # 社区分析演示
│   ├── gds_features.ipynb  # 特征分析演示
│   └── tests/              # 测试目录
├── tests/                  # 测试脚本
└── requirements.txt        # 项目依赖

核心类与数据结构

Gds类

Gds类是算法的核心实现，包含了图初始化、信息传播、归一化和中心节点计算等功能。

class Gds():
    def __init__(self, G):
        # 图初始化代码

主要数据结构

• r_msg: 存储节点的关联消息，以JSON格式存储的字典，键为源节点ID，值为关联度
• buffer: 存储邻居节点传播来的消息缓冲区，实现并行化传输
• id_nodeid_dict: 顶点vertex ID到节点node_id的映射
• nodeid_id_dict: 节点node_id到顶点vertex ID的映射

传播算法原理

1. 初始化

初始化图结构，设置传播参数，创建ID映射和消息存储结构。

2. 添加源节点

为源节点设置初始消息，权重为1。

3. 消息传播机制

• 从指定节点传播：设置源节点的初始消息
• 全局传播到缓冲区：每个节点的消息传播到其邻居节点的缓冲区

4. 消息合并与归一化

合并来自邻居节点的消息，并进行归一化处理，确保节点消息总和为1。

5. 中心节点计算

基于节点接收到的消息强度，计算每个节点的中心性得分。

算法参数

• FADE: 消息传播衰减系数，默认值为0.3
• LIMIT: 关联度过滤阈值，默认值为3*(1/节点数)
• MIN_SIZE/MAX_SIZE/DEFAULT_SIZE: 节点可视化大小参数

算法特点

1. 源头标识: 消息中保留了源节点的标识，可追踪信息传播路径
2. 衰减机制: 消息在传播过程中会衰减，避免远距离节点影响过大
3. 动态阈值: 根据节点数量动态调整关联度过滤阈值
4. 可视化: 提供节点重要性可视化功能
5. 归一化: 确保节点消息总和为1，便于比较

安装与使用

安装依赖

pip install -r requirements.txt

基本使用示例

from graph_diffuse_with_source.gds import Gds
import igraph as ig

# 创建图
g = ig.Graph()
g.add_vertices(5)
g.add_edges([(0, 1), (1, 2), (2, 3), (3, 4)])
g.vs['node_id'] = [str(i) for i in range(5)]

# 初始化GDS对象
gds = Gds(g)

# 添加源节点
gds.add_one_node_ids(['0'])

# 执行消息传播
gds.emit_to_buffer(['0'])
gds.merge_from_buffer()

# 计算并显示中心节点
central_nodes = gds.show_central()
print(central_nodes)

功能模块

1. 边介数近似计算 (gds_edge_betweenness.py)

利用GDS传播算法快速近似计算图中边的介数中心性，适用于大规模网络分析。

2. K核社区发现 (gds_k_core_clique.py)

基于K核分解和最大团检测，识别图中的紧密连接社区结构。

可视化示例

图中心节点	节点相关性

测试与演示

详细测试和演示示例请参考src/tests/目录下的脚本。

许可证

本项目采用MIT许可证。