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
├── results/                    # 实验结果目录
│   ├── CA-AstroPh/
│   │   ├── experiment1.csv
│   │   ├── experiment2.csv
│   │   ├── experiment3.csv
│   │   ├── experiment4.csv
│   │   ├── nohup.out
│   │   └── pid
│   ├── Email/
│   ├── Amazon/
│   ├── Youtube/
│   └── WikiTalk/
├── src/                        # 源代码
│   ├── main.cpp
│   ├── Graph.h
│   ├── Graph.cpp
│   ├── CoreGroup.h
│   ├── CoreGroup.cpp
│   ├── TreeIndex.h
│   ├── TreeIndex.cpp
│   ├── SharingIndex.h
│   └── SharingIndex.cpp
├── run_all_experiments.sh       # Linux/Mac 批量运行脚本
├── run_all_experiments.bat      # Windows 批量运行脚本
└── README.md

数据集说明

索引	名称	文件名
0	CA-AstroPh	CA-AStroPh.txt
1	Email-Enron	Email-Enron.txt
2	com-amazon	com-amazon.txt
3	com-youtube	com-youtube.ungraph.txt
4	WikiTalk	WikiTalk.txt
5	example	example.txt
6	facebook_combined	facebook_combined.txt

编译说明

使用 Makefile（推荐）

make

使用 g++ 手动编译

g++ -std=c++17 -O3 -o csp *.cpp

编译清理

make clean

使用说明

命令行参数

Usage: ./csp [options]

Options:
  -d <index>    Dataset index to use (0-6)
  -e <number>   Experiment to run (1=all, 2=exp1, 3=exp2, 4=exp3, 5=exp4, 6=exp5)
  -s1 <value>   shift_1 value (default: 12)
  -s2 <value>   shift_2 value (default: 100)
  -h            Show this help message

示例用法

# 使用默认数据集 (Email-Enron) 运行所有实验
./csp

# 使用 Amazon 数据集运行所有实验
./csp -d 2

# 使用 Youtube 数据集仅运行实验1
./csp -d 3 -e 2

# 自定义 shift 参数
./csp -d 0 -s1 15 -s2 80

# 查看帮助
./csp -h

脚本使用

Linux/Mac 批量运行脚本

使用 run_all_experiments.sh 脚本可以自动并行运行所有数据集的实验。

# 赋予执行权限
chmod +x run_all_experiments.sh

# 运行脚本（自动编译并执行所有数据集）
./run_all_experiments.sh

# 查看特定数据集的日志
cat results/Email/nohup.out

# 查看所有运行中的进程
ps aux | grep csp

# 终止所有实验进程
pkill csp

Windows 批量运行脚本

使用 run_all_experiments.bat 脚本在 Windows 系统上批量运行。

REM 编译程序
g++ -std=c++17 -O3 -o csp.exe *.cpp

REM 运行批量实验脚本
run_all_experiments.bat csp.exe

REM 查看进程
tasklist | findstr csp

REM 查看日志
type results\Email\nohup.out

实验说明

实验1 (experiment1)

测试不同查询相似度对算法性能的影响。

• 参数：查询相似度 {0.2, 0.4, 0.6, 0.8}
• 输出：results/{dataset}/experiment1.csv
• 列：dataset, similarity, algorithm, avg_time, avg_size, avg_density, avg_qbd

实验2 (experiment2)

测试不同查询大小对算法性能的影响。

• 参数：查询大小 {2, 4, 8, 16, 32}
• 输出：results/{dataset}/experiment2.csv
• 列：dataset, |Q|, algorithm, avg_time, avg_size, avg_density, avg_qbd

实验3 (experiment3)

分析 batch-final 算法各阶段的时间消耗。

• 输出：results/{dataset}/experiment3.csv
• 列：dataset, |Q|, clustering_time, greedy_time, steiner_time, simple_time

实验4 (experiment4)

测试不同聚类阈值（γ）对算法性能的影响。

• 参数：γ {0.0, 0.2, 0.4, 0.6, 0.8, 1.0}
• 输出：results/{dataset}/experiment4.csv
• 列：dataset, γ, avg_time

实验5 (experiment5)

在所有数据集上比较不同算法的性能。

• 输出：results/experiment5.csv
• 列：dataset, n, m, algorithm, avg_time

算法参数说明

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

结果文件说明

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

# Python 读取示例
import pandas as pd

df_exp1 = pd.read_csv('results/Email/experiment1.csv')
print(df_exp1.head())

系统要求

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

故障排除

编译错误

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

1. 已安装 C++17 支持的编译器
2. 所有源文件（.cpp 和 .h）都在同一目录下
3. 尝试使用 Makefile 编译：make clean && make

运行时错误

1. 找不到数据集文件：确保 dataset/ 目录下有对应的数据集文件
2. 内存不足：尝试减小 shift_1 值或使用较小的数据集
3. 输出目录错误：确保程序有创建 results/ 目录的权限

许可证

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

联系方式

如有问题或建议，请提交 Issue 或 Pull Request。