王一萍

大规模网络中局部层次重叠社区的检测

王一萍

（齐齐哈尔大学 计算机与控制工程学院，黑龙江 齐齐哈尔 161006）

现实世界网络的规模越来越大，使得检测社区的工作变得更具有挑战性．提出了一种可扩展的局部社区检测方法，可有效地发现网络中给定节点的重叠社区．通过考虑图中链接对的相似性及它们在多个环境中的参与程度，确定加入链接对的顺序，形成有意义的分层社区．实验评估时使用了5个大型真实网络的真实社区，结果表明，LDLC算法在准确性和效率方面都显著优于最先进的方法．

复杂网络；等级社区；社区检测；分散

社区结构是现实世界网络的一个重要特性[1]．社区是有共同属性的节点组，如2个人可能在同一所学校、2部电影可能至少有一个共同演员．然而，社区往往是重叠的．如社交网络中某个人可能存在很多社区，如家人、同事、大学同学社区等．很明显社区可能以不同方式重叠，如同事也可能是大学同学．重叠社区可能有一个复杂的联结结构，与不重叠社区相比，识别重叠社区更具挑战性．早期社区检测方法侧重于对网络节点进行分组，或者侧重于删除分离集群的链接[2]764．然而，这些方法没有考虑社区重叠，从而无法准确地表示网络的社区结构．已有很多算法允许节点属于几个重叠社区[3-5]，但不适用于大数据的海量图．需要从全局结构转移到网络的局部观点，在局部上扩展感兴趣社区中的一组目标……