复杂网络社区发现及布局算法研究

发布时间：2020-09-28 16:35

　　人类社会早已被网络化,万维网、社交网络和交通网络等复杂网络普遍存在于人们的生活当中。复杂网络的拓扑结构是理解和解释网络动态行为或过程的有效手段。对于计算机病毒在计算机网络上的传播、信息或者谣言在社会网络中的扩散等一些应用性很强的网络行为,都需要依靠网络拓扑结构进行分析研究。通过社区发现算法发现复杂网络中的社区结构,同时利用可视化布局方法展示复杂网络的社区结构,能够帮助研究者发掘网络中有用信息。针对现有的社区发现算法存在社区质量低,算法执行效率不高的问题,以及FR算法社区结构不明显,算法不适用于复杂网络的问题。本文提出了一种基于Louvain算法的改进社区发现算法和一种基于FR算法的改进社区布局算法。首先,在Louvain算法的基础上研究一种面向复杂网络的社区发现算法。复杂网络的特征包括小世界及无尺度,节点度数表现为幂率分布规律,以及大部分节点度数较低而少部分节点度数偏高。其中复杂网络中度数高的节点和相邻度数低的节点容易构成一个社区。为了解决Louvain算法效率不高、社区划分不合理的问题,通过在重要节点中选取重要程度高的节点,控制大社区过度归并的趋势,减少算法的迭代周期,在迭代过程中迅速地归并小社区,提高算法运行效率,同时提高社区划分质量。实验结果表明,通过优化改进后的Louvain算法在社区划分质量和算法效率上都有所提高。其次,在FR算法的基础上研究一种社区布局算法,该算法能展示网络社区结构,对社区引力和斥力模型进行了优化,引力的计算考虑了节点的亲密度信息,斥力的计算考虑了节点的重要程度信息,使得引力和斥力的计算步骤更加高效。结合社区发现算法执行结果,对社区结构进行布局。实验结果表明,改进的算法有效地提高了算法执行效率,使得社区结构布局更加清晰。
【学位单位】：重庆邮电大学
【学位级别】：硕士
【学位年份】：2018
【中图分类】：TP301.6;O157.5
【部分图文】：

复杂网络

意义物联网技术的飞速发展，各种终端、传感器、类型的数据，这些数据源源不断地进入信息系复杂的数据中获得有价值的信息是一项虽然繁，把实体当作节点，把实体之间的关系作为边连接的网络，这种网络被称为复杂网络[1]，如络，小聚居”的特征。该网络具有自组织，自，复杂网络具有部分或全部网络特征。其中，无标度。小世界特征意味着网络有一个小的平标度特征意味着网络连通性的分布具有幂律形

简单网络,聚类系数,社区

iiG聚类系数iC 的平均值就是整个网络的聚类系数之间。网络中，局部聚类系数iC 随着节点 i 的减小而，如果网络规模比较大，聚类系数接近于零。远大于零，即具有明显的聚类特征。节点可划分为几个组，是许多现实网络的共同组之间的节点连接稀疏，图 2.1 显示了一个拥

社区,复杂网络

于解释网络的均度，聚类系数和最短路径等特性具有重要作用。由于发现网络中连接的发现需要耗费高昂的费用，导致许多真实网络不完预测网络中丢失的连接意义重大。Clauset 在已有建立模型基础上，提出了连接的预测器，与传统的算法相比，优点是能够适用于更广泛类型的网络结2 社区发现算法复杂网络可以表示为图 G (V ,E)，其中V 是网络中所有节点的集合，E是的边集，而复杂网络的社区发现实质上是对图的划分。综合当前社区发现究现状，王永程[61]将社区划分方法分为传统的社区划分算法与新型社区划从划分思想的角度，传统方法主要基于图分割理论、标签、层次聚类、随新型方法主要基于统计推断、重叠社区、密度、动态距离，整体框架如图。

【参考文献】