网络在现实生活中无处不在,如在社交领域中用网络对人与人之间的友谊和熟识程度进行建模;在生物领域中,使用网络对实现某一个功能所需要的蛋白质以及蛋白质之间的联系进行建模,从而有效地捕捉生物体内的代谢过程;在商业领域中,使用网络对用户和商品之间的关系进行建模,从而可以对用户进行商品推荐,提高用户购买效率和购买频率;在其他领域中,可以使用网络对不同实体之间的不同关系进行建模。其中,使用节点表示实体,边表示实体之间的关系。复杂网络的一个重要特征是实体趋于聚集在一起形成社区。社区发现算法通过发现网络中的社区来更好地展示复杂网络的结构、行为、动态性和组织性,使我们对网络的特性有更深层次的理解以便于捕捉到将网络作为一个整体来考虑时所不能捕捉到的有意义的特性。社区发现算法具有非常重要的研究意义和研究价值。针对现有的社区发现算法及可视化平台存在的问题,本文主要工作如下:(1)针对传统标签传播算法中由标签赋值过程所造成的标签震荡以及标签更新顺序的随机性造成的算法结果随机性,提出了一种基于随机游走的改进标签传播算法(Improved label propagation algorithm based on random walk,LPASN)。首先,使用随机游走的可能位置的分布来衡量网络中节点的重要性,对每个节点的可能概率分布进行叠加,得到每个节点的重要性。按节点的重要性降序排列作为节点的标签更新顺序;然后遍历节点的更新序列,对每个节点将其与排序在其之前的节点进行相似性的计算,若该节点与排序在其之前的节点是邻居节点且节点之间相似性大于阈值,则将排序在其之前的节点选为种子节点;最后,将种子节点的标签传播给其余的节点,得到社区最终划分结果。LPASN算法有更好的社区划分效果并比原始的LPA算法更稳定。通过与一些经典算法在真实网络数据集上进行实验比较表明LPASN有更好的社区划分效果,在NMI、ARI、模块性等指标上表现良好。(2)设计实现了复杂网络社区发现算法的可视化展示平台Network。现有复杂网络分析平台,用户通常只能对算法的最终实验结果进行展示,而无法跟踪算法的中间过程并对中间结果可视化,进而影响算法改进的精准度。针对此,设计实现了复杂网络社区发现算法的可视化展示平台Network,对不同类型的数据如社交网络、生物网络、技术网络等数据进行整合,提供对运行算法的统一接口;系统可对不同算法的中间聚类结果进行展示,以便用户可以更好地对算法进行改进;此外,系统也允许用户上传算法运行结果并对算法结果进行分析和指标计算。最后,对两种基于遗传策略的重叠社区检测算法(即多目标的粒子群优化算法和基于边的模因算法)进行性能的比较和中间步骤的可视化展示。使得用户可以更好的了解遗传算法的性能,更有针对性地对算法进行改进。
暂无评论