社区结构是复杂网络中一个常见的特性,它由一组连接紧密的结点组成,同时这些结点与社区外部结点连接稀疏。通过研究社区结构,研究者能够更深刻地理解网络所对应的复杂系统,因为社区结构往往揭示着网络的组织结构。同时,由于社区结构有着广泛的实际用途,所以在复杂网络中发现社区结构有着重要的研究意义。提出了一种衡量结点中心性的方法。基于结点核心值以及局部扩展框架,提出了一种新的重叠社区发现算法。该算法不仅能够发现重叠社区结构,同时还可发现网络中的部分桥接结点。该算法包括四个步骤:首先,根据结点的核心值将它们降序排序,以形成种子优先级列表;其次,列表顶端的结点被选出,以形成一个社区的核心区域;然后,扩展这个核心区域直到一个社区结构或者桥接结点被发现;最后,分配桥接结点到那些它的大多数邻居所在的社区中。其中,交替执行第二、第三步,直至所有社区都被发现,然后再进行第四步。实验结果证明了算法的有效性。针对当前已有的社区发现算法无法有效处理海量级数据的问题,提出了一种基于局部扩展的并行化算法,并且借助Spark框架将其实现。该算法包含四个步骤:首先,挑选出一组互不相关的中心结点并使用中心结点与它们的邻居所形成的局部网络作为种子;其次,通过删除那些本身连接比较稀疏的局部网络来过滤选出的种子;然后,采用一种批量式的扩展策略来扩展种子,即一次向局部社区中添加一批邻居结点或从社区中删除一批结点;最后,融合相似度比较高的社区。实验结果证明了算法的有效性。
