陈俊宇　周　刚　南　煜　曾　琦

(数学工程与先进计算国家重点实验室　郑州　450002)(junychen1107@gmail.com)



一种半监督的局部扩展式重叠社区发现方法

陈俊宇周刚南煜曾琦

(数学工程与先进计算国家重点实验室郑州450002)(junychen1107@gmail.com)

摘要重叠社区发现是近年来复杂网络领域的研究热点之一.提出一种半监督的局部扩展式重叠社区发现方法SLEM(semi-supervised local expansion method).该方法借鉴了带约束的半监督聚类的思想，不仅利用网络的拓扑结构信息，还充分地利用网络节点的属性信息.首先将网络节点的属性信息转化为成对约束，并根据成对约束修正网络的拓扑结构，使网络中的社区结构更加明显；然后基于网络节点的度中心性选取种子节点，得到分散的、局部节点度大的种子作为初始社区；再采用贪心策略将初始社区向邻居节点扩展，得到局部连接紧密的社区；最后检测并合并冗余社区，得到高覆盖率的社区发现结果.在模拟网络数据和真实网络数据上与当前有代表性的基于局部扩展的重叠社区发现算法进行了对比实验，结果表明SLEM方法在稀疏程度不同的网络上均能发现较高质量的重叠社区结构.

关键词复杂网络；重叠社区发现；半监督聚类；局部扩展；SLEM方法

网络是事物之间相互关联的一种模式，现实世界的很多系统都是由相互联系的实体组成的，自然地以网络的形式存在或者可以用网络来表示[1].复杂网络一般指节点众多、连接关系复杂的网络，能够广泛应用于各科学领域对复……