微博社交网络社区发现方法研究

范超然 ，黄曙光 ，李永成

（1.合肥电子工程学院 研究生管理大队，安徽 合肥 230037；2.合肥电子工程学院 网络工程系，安徽 合肥 230037）

微博作为一种新兴的社交媒体，其用户以及影响力越来越广泛，微博从一开始的社交娱乐工具到现在的重要营销手段，得到了前所未有的关注。微博不同于传统的社交媒体一对多的信息传播模式，它的传播具有迅捷性和裂变性[1]，这种信息传播的模式使得微博在突发事件的传播以及舆论的扩散方面具有更强的作用力。随着复杂网络研究的不断深入，以此为基础理论的社交媒体研究正成为社会网络研究的一大分支。复杂网络中的一个主要特征是社区性[2]，社区的一般定义是同一社区内的节点与节点之间的连接很紧密，而社区与社区之间的连接比较稀疏[3]。社区发现对于挖掘网络中的功能模块以及研究网络的演化是非常重要的。本文提出了一种基于关系分析的社区发现方法。

1 社区发现相关研究

社区发现从算法的角度可以分为两种[4]：（1）基于优化的算法，其中包括著名的谱方法，基本思想是采用二次型优化技术最小化预定义的“截”函数，具有最小“截”的划分被认为是最优的网络划分。（2）Kernighan和Lin在 1970年提出 KL算法[5]，该算法是一种试探优化算法，它将网络分割成两个大小已知的子网络即社区，并且应用了贪婪算法的原理。由于以上两种算法的开销较大，Newman提出了一种快速聚类算法[6]，该算法优化的目标是模块度函数Q，该函数定义为簇内实际连接数目与随机连接情况下簇内期望连接数目之差，用来衡量社区划分的质量，该算法通过合并使ΔQ最大的点的方法形成一个自底向上的聚类过程，该算法在效率上有了很大的提高。……