# graph_diffuse_with_source

**Repository Path**: benechen/graph_diffuse_with_source

## Basic Information

- **Project Name**: graph_diffuse_with_source
- **Description**: 使用带节点标签id的标签传播算法，查找节点关联的关键节点及图的中心节点
- **Primary Language**: Python
- **License**: MIT
- **Default Branch**: main
- **Homepage**: None
- **GVP Project**: No

## Statistics

- **Stars**: 0
- **Forks**: 0
- **Created**: 2025-08-18
- **Last Updated**: 2025-10-01

## Categories & Tags

**Categories**: Uncategorized

**Tags**: label-spreading-with-source-id, graph-node-correlation, graph-central-nodes

## README




          
# 带有传播源头标识的图节点相关性及中心节点计算算法 (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`类是算法的核心实现，包含了图初始化、信息传播、归一化和中心节点计算等功能。

```python
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，便于比较

## 安装与使用

### 安装依赖

```bash
pip install -r requirements.txt
```

### 基本使用示例

```python
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核分解和最大团检测，识别图中的紧密连接社区结构。

## 可视化示例

| 图中心节点 | 节点相关性 |
|----------|----------|
| ![图中心节点](image/central.png) | ![相关节点](image/relate.png) |

## 测试与演示

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

## 许可证

本项目采用MIT许可证。