基于共享近邻加权图的Chameleon算法改进（2012年）

简介：
本文提出了一种改进版的Chameleon社区发现算法，通过引入共享近邻加权图的概念，优化了原有算法中模块相似性度量和分裂准则，从而提升了复杂网络结构中的社区识别精确性和稳定性。 针对Chameleon算法中存在的问题，如使用距离函数度量数据点间的相似性可能导致距离相近的两个点仅有少量共同特征、最小二分操作的实际困难以及合并过程中需要人工指定阈值且一旦完成不可撤销等问题，我们提出了一种改进方案——引入共享近邻加权图（WSnnG）的Chameleon算法。该方法通过计算数据对象间的共享近邻数量来衡量相似度，并基于此构造了WSnnG。随后利用网络模块性评价函数指导最小二分过程，在合并时采用结构等价相似度作为依据，最后引入内聚度度量函数解决了合并后不可撤销的问题。 为了验证改进算法的有效性和实用性，我们在UCI数据集和四个二维人造数据上进行了实验测试。