论文部分内容阅读
近年来,社团发现一直是复杂网络研究中的热点问题。所谓社团就是同一网络中连接比较紧密的顶点构成的集合,并且不同社团之间的连接比较稀疏。目前已经有多种社团发现算法相继被提出,不过其中的静态社团发现往往会忽略网络结构的变化,也无法检测到网络中社团结构的演化过程。同时在数据量迅猛增长的情况下,单机算法的效率较低,难以支撑大规模网络中社团结构的挖掘与分析。因此,进行动态社团发现及演化分析并行算法的研究在实际应用中具有重要的意义。本论文基于Spark并行计算框架设计实现动态社团的结构划分和演化分析时,主要有如下几部分工作:本论文首先提出了一种基于Spark的并行增量动态社团发现算法PIDCDS,为了在GraphX并行图计算平台上通过最大化持久力发现社团,该算法对节点的持久力计算公式进行了有效修正。PIDCDS计算每个时间片中增量节点的持久力指标,更新其社团归属,在保证一定的社团划分准确性的基础上减少计算量。通过与FacetNet动态社团发现算法做比较,验证了本算法能够获得更好的稳定性,同时能发现更真实的社团划分。对不同规模网络在PIDCDS上的运行时间进行对比,发现该算法在网络节点和连边增加的情况下,运行时间缓慢增长,性能较高,并且增加内核数将在一定程度上加速算法的执行。在通过PIDCDS算法发现动态网络中社团结构的同时,本论文提出了一种动态社团演化并行算法,设计社团的骨骼结构并获取关键节点集合,构造以社团为节点的二分图,根据关键节点的分布最终确定社团的演化过程。之后将文本数据处理为动态网络的形式输入算法,得到效果不错的事件演化分析结果。最后,本课题基于Spark和OSGI构建得到一个并行图数据挖掘系统,通过组件化技术将多种算法集成到系统中,用户只需简单地拖拽组件连成工作流即可完成大规模的社会网络分析。