论文部分内容阅读
随着复杂网络领域的发展,尤其是在互联网高速发展下的社交网络,涌现了一批新颖并且重要的发现,吸引了各个学科的众多研究者投入其中。社团结构作为它的普遍存在的拓扑特性之一,对于它的探索有助于揭示网络结构与功能之间的关系,因此发现网络中的社团结构具有重要的理论和实际意义。本文主要针对现有社团发现算法进行研究,文中介绍并分析了现有的基于边表示网络的社团发现算法,针对其计算瓶颈的问题,设计了一种基于三角模体和期望极大的社团结构发现(Community structure discovery based on triangular motifs and expectation-maximization,CSDTME)模型的社团发现算法。本文的主要工作如下:(1)针对现有采用边表示网络的社团发现算法的计算瓶颈问题,本文设计了一种基于三角模体的社团发现算法。本文通过三角模体对观测网络进行表示,简化网络结构假设,为设计有效的算法提供基础。通过对三角模体生成过程建模,设计了一个基于三角模体和期望极大的社团结构发现(Community structure discovery based on triangular motifs and expectation-maximization,CSDTME)模型,以此来模拟观测网络,并提出了相应的社团发现算法,在算法中采用全三角模体和两边三角模体作为计算对象,在保证网络真实结构的同时,通过减少计算对象来提高算法的效率,返回节点的社团混合隶属度及社团间的链接概率,并通过实验证明了文中提出算法的可行性和有效性。(2)针对基于CSDTME模型的社团发现算法执行效率问题,本文设计了一种基于CSDTME模型的社团发现算法的改进方法。基于CSDTME模型的社团发现算法在时间效率上已经有了很大的改进,但是通过对该算法的进一步的研究,发现可以在时间和空间上还可以对该算法进行更进一步的改进,可以更快速的发现网络中的社团结构。基于CSDTME模型的社团发现算法在对参数求解的过程中在时间和空间上存在的问题,分别提出了在空间和时间上的应对策略,主要是通过减少迭代次数及中间变量的存储,来提高算法的执行效率。最后通过实验,验证了改进后的基于CSDTME模型的社团发现算法的可行性和有效性。并在此算法的基础上,设计并实现了一个简单的基于CSDTME模型的社团划分系统。