# Csp-Experiment

**Repository Path**: lee-lg/main

## Basic Information

- **Project Name**: Csp-Experiment
- **Description**: 社区搜索问题的实验部分
- **Primary Language**: Unknown
- **License**: Not specified
- **Default Branch**: master
- **Homepage**: None
- **GVP Project**: No

## Statistics

- **Stars**: 0
- **Forks**: 0
- **Created**: 2026-04-24
- **Last Updated**: 2026-04-24

## Categories & Tags

**Categories**: Uncategorized

**Tags**: None

## README

# CSP (Community Search with Pruning)

这是一个基于图算法的社区搜索项目，实现了多种算法用于处理查询集的社区搜索问题。

## 项目简介

本项目实现了以下算法：

- **GS (Global Search)**: 全局搜索算法
- **K-GS**: K约束的全局搜索算法
- **Grcon**: 基于贪心连接的算法
- **batch-merge**: 批量处理+合并相同Steiner树的优化算法
- **batch-final**: 使用三步优化的批量处理算法

## 项目结构

```
csp-gitee_20/
├── dataset/                    # 数据集目录
│   ├── CA-AstroPh.txt
│   ├── Email-Enron.txt
│   ├── com-amazon.txt
│   ├── com-youtube.ungraph.txt
│   ├── WikiTalk.txt
│   ├── example.txt
│   ├── facebook_combined.txt
│   └── web-NotreDame.txt
├── results/                    # 实验结果目录
│   ├── CA-AstroPh/
│   ├── Email-Enron/
│   ├── com-amazon/
│   ├── com-youtube/
│   ├── WikiTalk/
│   ├── facebook_combined/
│   └── web-NotreDame.txt/
├── main.cpp                    # 主程序文件
├── Graph.h / Graph.cpp         # 图数据结构
├── CoreGroup.h                 # 核心分解算法
├── TreeIndex.h / TreeIndex.cpp  # 树索引结构
├── SharingIndex.h / SharingIndex.cpp  # 共享索引算法
└── VertexScore.h / VertexScore.cpp  # 顶点评分
```

## 数据集说明

| 索引 | 名称 | 文件名 | 节点数 | 边数 |
|------|------|--------|---------|-------|
| 0 | CA-AstroPh | CA-AstroPh.txt | 18,772 | 198,110 |
| 1 | Email-Enron | Email-Enron.txt | 36,692 | 183,831 |
| 2 | com-amazon | com-amazon.txt | 334,863 | 925,872 |
| 3 | com-youtube | com-youtube.ungraph.txt | 1,134,890 | 2,987,624 |
| 4 | WikiTalk | WikiTalk.txt | 2,394,385 | 4,659,570 |
| 5 | example | example.txt | 23 | 57 |
| 6 | facebook_combined | facebook_combined.txt | 4,039 | 88,234 |
| 7 | web-NotreDame | web-NotreDame.txt | 325,729 | 1,090,108 |

## 编译说明

### 手动编译

```bash
# 编译各个源文件
g++ -std=c++17 -O3 -march=native -finline-functions -funroll-loops -c Graph.cpp
g++ -std=c++17 -O3 -march=native -finline-functions -funroll-loops -c TreeIndex.cpp
g++ -std=c++17 -O3 -march=native -finline-functions -funroll-loops -c SharingIndex.cpp
g++ -std=c++17 -O3 -march=native -finline-functions -funroll-loops -c VertexScore.cpp

# 链接生成可执行文件
g++ -std=c++17 -O3 -march=native -finline-functions -funroll-loops -flto \
    main.cpp Graph.o TreeIndex.o SharingIndex.o VertexScore.o -o exp1
```

## 使用说明

### 命令行参数

```
Usage: ./csp <experiment_id> <dataset_id> <parameter>

Parameters:
  experiment_id  Experiment to run (1 or 2)
                1: 实验1 - 相似度对算法性能的影响
                2: 实验2 - 查询大小对算法性能的影响
  dataset_id    Dataset index to use (0-3)
                0: Email-Enron
                1: web-NotreDame
                2: web-Google
                3: com-youtube.ungraph
  parameter      Parameter value
                For experiment 1: similarity threshold (e.g., 2, 4, 6, 8)
                For experiment 2: query size (e.g., 2, 4, 8, 16, 32)
```

### 示例用法

```bash
# 运行实验1，使用Email-Enron数据集，相似度阈值为0.2
nohup ./csp 1 0 2 > log/exp1/1-0-2.log 2>&1 &

# 运行实验1，使用web-NotreDame数据集，相似度阈值为0.4
nohup ./csp 1 1 4 > log/exp1/1-1-4.log 2>&1 &

# 运行实验1，使用web-Google数据集，相似度阈值为0.6
nohup ./csp 1 2 6 > log/exp1/1-2-6.log 2>&1 &

# 运行实验1，使用com-youtube数据集，相似度阈值为0.8
nohup ./csp 1 3 8 > log/exp1/1-3-8.log 2>&1 &

# 运行实验2，使用Email-Enron数据集，查询大小为2
nohup ./csp 2 0 2 > log/exp2/2-0-2.log 2>&1 &

# 运行实验2，使用web-NotreDame数据集，查询大小为8
nohup ./csp 2 1 8 > log/exp2/2-1-8.log 2>&1 &

# 运行实验2，使用com-youtube数据集，查询大小为16
nohup ./csp 2 3 16 > log/exp2/2-3-16.log 2>&1 &
```

### 后台运行说明

使用 `nohup` 命令可以在后台运行实验，即使关闭终端也不会中断：

```bash
# 创建日志目录
mkdir -p log/exp1 log/exp2

# 查看运行中的日志
tail -f log/exp1/1-1-4.log

# 查看所有实验进程
ps aux | grep csp

# 终止特定实验进程
pkill -f "csp 1 1 4"
```

### 批量运行所有实验

可以编写脚本来批量运行所有实验：

```bash
#!/bin/bash
# 运行实验1的所有数据集和相似度
for data in 0 1 2 3; do
    for param in 2 4 6 8; do
        echo "Running experiment1: data=$data, param=$param"
        nohup ./csp 1 $data $param > log/exp1/1-$data-$param.log 2>&1 &
    done
done

# 运行实验2的所有数据集和查询大小
for data in 0 1 2 3; do
    for param in 2 4 8 16 32; do
        echo "Running experiment2: data=$data, param=$param"
        nohup ./csp 2 $data $param > log/exp2/2-$data-$param.log 2>&1 &
    done
done
```

## 实验计划

### 实验1 (Experiment 1): 相似度对算法性能的影响

#### 研究目标
研究查询之间的相似度对批量处理算法性能的影响。高相似度的查询可以共享更多的计算结果，从而提高批量处理的效率。

#### 实验设计

| 参数 | 取值 | 说明 |
|------|------|------|
| 相似度阈值 | 0.2, 0.4, 0.6, 0.8 | 用于控制查询生成的相似度 |
| 查询数量 | 20 | 每次实验生成的查询组大小 |
| 查询大小 | 10 | 每个查询的节点数量 |
| 数据集 | web-NotreDame.txt | 使用Notre Dame网络数据集 |
| shift_1 | 12 | 核心度下限 |
| shift_2 | 100 | 核心度上限 |

#### 实验流程
1. 加载图数据集 (web-NotreDame.txt)
2. 生成20个具有指定相似度的查询
3. 运行所有算法：
   - GS (Global Search)
   - K-GS (K-constrained Global Search)
   - Grcon
   - batch-merge
   - batch-final
4. 记录每个算法的性能指标

#### 输出格式
```
results/web-NotreDame.txt/{similarity}/experiment1.csv
```

CSV列：
- dataset: 数据集名称
- similarity: 实际计算出的查询相似度
- algorithm: 算法名称
- avg_time: 平均查询时间 (秒)
- avg_size: 平均结果社区大小
- avg_density: 平均社区密度
- avg_qbd: 平均查询偏置密度

#### 预期结果
- **高相似度 (0.6, 0.8)**: batch-final 和 batch-merge 应该显著快于 Grcon 和 GS，因为可以共享更多计算
- **低相似度 (0.2, 0.4)**: 批量算法的优势可能不明显，因为查询之间共享较少
- **质量保证**: 所有算法应该产生相似质量和密度的社区

#### 分析指标
1. **时间效率**: 对比 batch-final / batch-merge 与 Grcon 的时间比
2. **缩放性**: 分析时间比随相似度变化的趋势
3. **质量对比**: 确保批量优化不会显著降低结果质量

---

### 实验2 (Experiment 2): 查询大小对算法性能的影响

#### 研究目标
研究查询大小（查询节点数量）对算法性能的影响。较大的查询通常需要更多的计算资源，但也可能产生更大的社区。

#### 实验设计

| 参数 | 取值 | 说明 |
|------|------|------|
| 查询大小 | 2, 4, 8, 16, 32 | 不同规模的查询 |
| 查询数量 | 100 | 每次实验生成的查询组大小 |
| 相似度阈值 | 0.5 | 固定中等相似度 |
| 数据集 | web-NotreDame.txt | 使用Notre Dame网络数据集 |
| shift_1 | 12 | 核心度下限 |
| shift_2 | 100 | 核心度上限 |

#### 实验流程
1. 加载图数据集 (web-NotreDame.txt)
2. 对于每个查询大小：
   - 生成100个具有相似度0.5的查询
   - 运行所有算法
   - 记录性能指标
3. 比较不同查询大小下的算法性能

#### 输出格式
```
results/web-NotreDame.txt/experiment2.csv
```

CSV列：
- dataset: 数据集名称
- |Q|: 查询大小
- algorithm: 算法名称
- avg_time: 平均查询时间 (秒)
- avg_size: 平均结果社区大小
- avg_density: 平均社区密度
- avg_qbd: 平均查询偏置密度

#### 预期结果
- **时间复杂度**: 
 2. **社区大小**: 随着查询大小增大，结果社区应该也增大
- **算法比较**:
  - GS 的性能可能随查询大小呈指数增长
  - Grcon 应该有较好的缩放性
  - batch-final 在大查询时优势最明显
- **查询大小 2, 4**: 所有算法都应该快速完成
- **查询大小 16, 32**: GS 可能非常慢，批量算法的优势显著

#### 分析指标
1. **增长率**: 分析时间随查询大小的增长曲线
2. **算法选择**: 找出每个查询规模的最优算法
3. **质量-时间权衡**: 比较不同算法在时间和质量之间的权衡

---

## 算法参数说明

- **shift_1**: 核心度下限，用于筛选初始节点（默认：12）
- **shift_2**: 核心度上限，用于筛选初始节点（默认：100）
- **simi**: 相似度阈值，用于查询聚类（默认：0.5）

## 结果文件说明

所有实验结果以 CSV 格式保存，可以直接用 Excel、Python pandas 或 R 读取分析。

```python
# Python 读取示例
import pandas as pd
import matplotlib.pyplot as plt

# 读取实验1结果
df_exp1 = pd.read_csv('results/web-NotreDame.txt/0.5/experiment1.csv')
print(df_exp1.head())

# 读取实验2结果
df_exp2 = pd.read_csv('results/web-NotreDame.txt/experiment2.csv')
print(df_exp2.head())

# 绘制图表
df_exp1.pivot(index='similarity', columns='algorithm', values='avg_time').plot(kind='bar')
plt.title('实验1: 相似度对算法性能的影响')
plt.ylabel('平均时间 (秒)')
plt.savefig('exp1_results.png')
```

## 系统要求

- C++17 或更高版本
- g++ 或支持 C++17 的编译器
- Linux/Mac/Windows 操作系统
- 至少 8GB 内存（web-NotreDame数据集推荐 16GB+）

## 故障排除

### 编译错误

如果遇到编译错误，请确保：

1. 已安装 C++17 支持的编译器
2. 所有源文件（.cpp 和 .h）都在同一目录下
3. 检查编译器版本：`g++ --version`

### 运行时错误

1. **找不到数据集文件**：确保 `dataset/` 目录下有对应的数据集文件
2. **内存不足**：尝试减小 `shift_1` 值或使用较小的数据集
3. **输出目录错误**：确保程序有创建 `results/` 目录的权限
4. **段错误**：检查数据集格式是否正确，节点ID应该是非负整数

## 贡献指南

欢迎提交 Issue 和 Pull Request！

1. Fork 本项目
2. 创建特性分支 (`git checkout -b feature/AmazingFeature`)
3. 提交更改 (`git commit -m 'Add some AmazingFeature'`)
4. 推送到分支 (`git push origin feature/AmazingFeature`)
5. 开启 Pull Request

## 许可证

本项目仅用于学术研究目的。

## 参考文献

如果您使用本项目，请引用相关论文。