基于局部谱的种子扩张社团检测算法

摘要

在我们的生活中需要处理分析很多规模很大的数据集，我们将一个大数据集成为网络。社团是网络里面的一种重要的属性，因为它们往往可以代表这个网络，拥有网络的核心价值。而现实网络中的社团结构往往是重叠的，所以那些非重叠社团检测算法就不能很好的处理现实网络，而能够检测出重叠社团的算法才能更好的应用于现实网络。
　　本文提出一个基于局部谱的种子扩张社团检测算法（Spectrum Based Clique Expansion，SCE），SCE算法在找出所有种子集的基础上，对每个种子集进行随机游走，得到可以表示此种子集邻接结构的局部谱空间。在这个局部谱空间中，我们将求解社团问题转化为线性规划来解最小一范数向量，从而近似地求出此种子集所属的局部社团。由于种子集扩张是独立的，所以可以得到重叠社团。
　　实验表明，SCE算法在使用不同种子集以及社团评估函数时，算法都可以保持良好的性能，具体很强的稳定性。在与其他代表性的种子扩张社团检测算法（比如，GCE算法和DEMON算法）相比时，通过实验结果可以明显看出SCE算法的性能优于GCE算法和DEMON算法。经过现实网络数据集的实验证明，SCE算法可以用于现实网络的社团检测。