论文部分内容阅读
伴随着突飞猛进的计算机处理能力和海量数据的存储能力,人们能够从客观世界中积累下来的种类繁多的各种实际数据里应用统计学、数据挖掘、机器学习等相关技术来挖掘和揭示隐含在这些数据中的一般性模式和规律。在过去的十年里,研究人员已经发现具有内在网络结构的系统广泛存在于自然界和人类社会中,并逐步揭示出现实世界中的复杂网络所具有的部分独特的统计结构特征,如:“无尺度”特性、“小世界”特性以及高聚集系数等。近年来,由于互联网上基于社会化计算技术的各种在线系统的“爆炸性”广泛普及,使得针对实际网络中的微观社区结构的统计分析迅速成为研究领域中的热点问题。本文对在具有海量数据规模的复杂网络中如何高效地挖掘出具有实际应用意义的社区结构,揭示这些潜在的社区结构会具有怎样的静态统计结构特征和动态演化机制,以及如何将这些模式特征进一步应用到电信领域等问题进行了深入研究,并取得了如下成果:1.提出了适用于在具有大规模海量结点数和边数的实际网络中高效地挖掘出所有极大团结构的Peamc并行算法,从而有效地解决实际工程问题中所面临的挑战。经过多种不同类型实际网络的测试,Peamc在执行效率上要优于现有已知典型算法。2.提出了基于极大团的不可重叠社区结构发现算法ComTector。在社区结构事先已知的实际网络中,ComTector算法可以给出准确的社区划分结果。在社区结构事先未知且很难进行手工分析的具有海量规模的真实网络中,ComTector算法不但可以挖掘出具有实际意义的社区结构,而且在执行效率上要好于已有算法。在所挖掘得到的社区结构的基础上,我们进一步提出了结合社区内部拓扑结构和结点自然属性的社区描述和命名算法ComResume。通过对北邮科研合作者网络和电信呼叫网络等实际应用案例的分析,ComResume在一定程度上可以帮助人们了解实际网络的组织结构、深入分析不同社区形成的原因,并最终以直观的形式展示出来。与此同时,我们还提出了基于社区的网络骨干抽取算法Sketcher,将给定大规模复杂网络的核心骨干进行可视化展示,从而以一种直观的方式帮助人们更好地理解网络的整体结构及内在组成。3.提出了适用于实际大规模复杂网络的可重叠社区结构发现算法COCD。对比已有算法,COCD不需要用户事先输入任何的额外信息,完全根据网络的拓扑结构就可以在具有上百万规模结点数和边数的实际网络中高效地挖掘出相应的可重叠社区结构划分。与此同时,我们进一步提出了在一组随时间演化的网络序列中,基于社区核心成员的社区演化描述算法ComTracer,揭示了在不同类型的网络中,社区结构所具有的不同演化模式特征。最后,通过将COCD算法扩展到二分图中,我们还提出了针对二分图的可重叠社区结构发现算法BiTector,实验结果表明该算法在二分图上可以取得良好的社区划分效果。4.首次在大规模个人移动通信网络中揭示了关于极大团结构的三种新发现的统计结构特征,并进一步提出了“收益”驱动的网络生成模型PaC,与现有模型相比较,PaC模型以一种更自然的收益函数来模拟人们的决策过程,而不是简单地依靠事先假设的某一种随机分布来指引结点的行为。仅通过定义结点之间交互的局部规则,PaC模型便可以使得整个网络结构自然地涌现出来,且该网络可以同时满足在实际网络中人们已知的,以及在本文中所新发现的相关网络统计结构特征。