论文部分内容阅读
随着移动互联时代的到来,网络日益得以普及,各种社交网络平台的兴起,人们或多或少通过网络与其他人或物发生着联系,形成复杂的关系网络,产生了海量的网络数据。复杂网络的研究对广告投放、精准营销、内容推荐、用户行为预测等具有极大的价值,而社区发现与社区进化作为复杂网络分析中的研究热点,自提出以来,一直受到学者们的广泛关注,提出了大量的研究成果。对于社区发现,随着网络规模增大,传统社区发现算法已无法有效和高效地处理大规模网络数据,本文结合GraphX图计算框架,提出了新的大规模复杂网络社区并行发现算法。实验表明本文算法能够有效的处理大规模复杂网络数据,百万级以上节点处理时间约为4分钟,是Hadoop平台下并行发现算法运行时间的1/20,社区识别准确率比传统社区发现算法提高了 3%。对于社区进化,随着传统事件框架限制条件越来越宽松,挖掘出的事件虽然增多,但同时也挖掘出了大量冗余事件,而且这些框架没有考虑到事件的重叠性和伴随性。为了克服传统事件框架的问题,本文基于事件框架,提出了弱事件的概念,并对传统事件框架进行了改进,重新定义了各种事件,并给出了新的限制条件,最后提出了适用于弱事件挖掘的框架。实验表明本文社区演化框架发现事件比传统框架多22.9%,事件准确率提高了 4%,解决了弱社区挖掘问题。本文主要工作包括:(1)介绍了复杂网络社区发现及社区进化的研究背景与意义,并介绍了当前社区发现与社区进化方向的国内外研究现状及最新成果。(2)根据模块度思想,结合图论、网络性质及近似优化理论,提出多社区选择模型,并设计了新的模块度增量更新方法,算法首先计算出所有节点间的模块度增量,然后选取网络中所有具有最大模块度增量的社区进行合并,最后利用新的模块度增量更新方法,更新与合并社区相关的模块度增量,再结合GraphX设计了并行处理算法。(3)根据事件框架定义,提出了“弱扩张”、“弱收缩”、“弱分裂”、“弱合并”等新的事件,以解决在一段时间内社区结构同时发生多种事件的情况。为了能够准确的发现这些事件,提出了社区重叠度、社区隶属度、事件发现准确率等新概念。根据以上理论提出了基于弱事件的社区进化分析方法。(4)给出了上述算法的具体实现,并将本文所提的分别在仿真复杂网络和真实复杂网络数据上,同多个算法进行了对比,验证了本文所提算法的准确性和高效性,全面的分析了本文算法及对比算法的优劣之处。