Data Mining / Community Detection
基于代表节点的重叠社区发现算法改进与实验分析
围绕原“代表节点 + 单阈值”重叠社区发现程序在社区表达、相似度选择和阈值稳定性上的问题，重构 Part 1/2/3 实验流水线，引入真实代表节点评分、虚拟几何中心对照、自适应相似度、阈值候选扫描、隶属度过滤、候选质量选择和 Oracle Gap 分析，用 LFR 加权网络对 NMI、Precision、Recall、F-score 与运行时间进行对齐评估。
从原方法入手定位问题：单个真实代表节点对社区整体表达有限，直接边权相似度对稀疏图敏感，单阈值判断缺少稳定性判断。
将程序拆成 Part 1 数据读取与相似度计算、Part 2 阈值扫描与候选生成、Part 3 候选质量评价与最终选择，后续改动可以落到明确环节。
在真实代表节点版本之外加入虚拟几何中心对照，并按图密度切换稀疏图余弦相似度与密图平均边权相似度。
补充 Python 批量评价、NMI 计算、单网络可视化和 Oracle Gap 分析工具，把算法修改、结果评价和问题定位连接成完整实验链路。
Snapshot
对齐结果
14共同 caseoriginal、part_v6、full_v6 和 virtual center 版本共同覆盖的公平对比样本数。
0.865669part_v6 平均 NMI共同 case 口径下，original 平均 NMI 为 0.348747，part_v6 提升 0.516921。
0.915664part_v6 平均 F-score共同 case 口径下，original 平均 F-score 为 0.089776。
972Oracle 候选记录Oracle Gap 表记录 28 个数据集下的阈值候选及 candidate_nmi。
Timeline
推进过程
2026.05梳理原代表节点重叠社区发现程序，确认原方法在代表节点表达、输入数据统一和评价口径上的问题。
2026.05改造 C++ 主程序输入输出，将网络读取、真实社区读取、相似度计算、阈值扫描和结果导出拆分为稳定接口。
2026.05形成 v6 版本：加入自适应相似度、候选扫描、隶属度过滤、密图最大断崖过滤和候选质量选择策略。
2026.06用 original / full_v6 / part_v6 / virtual center 等版本做共同 case 对齐分析，输出版本对比汇总。
2026.06编写 Oracle Gap 候选导出和 Python 评价脚本，用候选集合最优 NMI 定位 Part 3 选择策略是否仍有改进空间。
Methods
方法与工具
C++ / igraphC++ 主程序承载 Part 1/2/3 管线，igraph 用于图结构处理、基础社区划分和社区结果计算。
Python 评估批量运行 C++ 程序，读取预测社区与真实社区，统计 NMI、Recall、Precision、F-score 和运行时间。
LFR Benchmark构造带真实社区标签的加权重叠网络，支撑不同 mu、om 和规模下的对齐实验。
NMI衡量预测社区结构与真实社区结构的一致性，是版本对比中最重要的整体指标。
Oracle Gap导出各阈值候选并逐个计算 NMI，用候选集合最优结果定位最终选择策略的差距。
Mermaid
技术路线
flowchart LR A[原代表节点方法] --> B[问题拆解] B --> C[Part 1 预处理与相似度] C --> D[Part 2 阈值扫描与候选生成] D --> E[Part 3 候选选择] E --> F[Python 批量评价] F --> G[Oracle Gap 分析] G --> H[版本对比与说明文档]
LaTeX
Oracle Gap 定位指标
File Tree
相关文件
Gallery
流程图与实验可视化
Resources