论文部分内容阅读
随着互联网和无线传感网络的发展,人类社会生活之间的联系越来越密切,由此形成的移动社交网络(Mobile Social Networks,MSNs)受到越来越多研究人员的关注。探索MSNs中的网络性质和社团结构对于理解人类社会的活动规律和揭示复杂网络的共有性质具有重要意义。目前,研究人员就社团划分方法做了大量的研究,但是这些研究的对象大多是静态网络,针对具有时间序列特性的MSNs的社团划分方法较少。因此,本文研究了MSNs中基于时间演化的网络模型和社团划分。具体工作如下:(1)为了解决MSNs的社团划分问题,首先采用多片网络来构建刻画MSNs的网络模型。将MSNs转化成多片网络,即把网络按固定的时间域平均切分成多个时间片。这些时间片上的节点和连边表示当前时间域的网络状态,为了保留网络的时间演化特性,将时间片之间的节点也进行边的重连。然后通过使用多片网络模块度优化算法检测MSNs的社团结构。得到保留了时间序列特性的社团划分结果能够很好地分析MSNs的社团演化现象。此外,还分析了MSNs的匹配系数,发现具有明显社团结构的MSNs在网络演化过程中绝大多数时候匹配系数为负数,说明网络具有异配性。(2)接着以静态网络社团划分问题为出发点。在分析了经典的社团划分的基础上,针对已有的社团划分算法在效率和准确率上有待提高等问题,本文给出了一种基于信息熵减益率的社团发现算法。该算法在传统凝聚算法的基础上通过不断迭代提高网络中所有社团内部的信息熵来得到最优的社团划分。和普通的基于信息熵的社团划分算法相比,该算法在每次合并社团的时候将社团间的熵减益比上整个网络的信息熵值,将比值最大的社团对合并成一个社团。理论分析表明了该算法的可行性。接着,在计算机生成的基准网络、真实的网络数据集上与其他基于信息熵和基于模块度的经典算法相比得到了较高的准确率。最后,再将熵减益率算法推广到MSNs多片网络邻接矩阵中。在真实的MSNs数据集上实验证明,该算法能够较好的反映MSNs网络的社团的演化现象和较高的模块度。