大规模网络可视化关键技术研究

发布时间：2020-08-16 20:01

【摘要】：近年来,复杂网络分析研究表明大量现实网络如社交网络、交通运输网络、引文网络、蛋白质网络、规则关联网络等具有非平凡的拓扑特征。复杂网络分析的主要目标是检测并发现这些结构以有利于人们理解其中蕴含的规律。网络可视化是实现上述目标的重要支撑技术,也是信息可视化的分支研究领域。快速、高效地、多尺度地可视化这些网络拓扑,降低研究复杂性,以供网络分析专家高效浏览并直观发现网络中隐含的规律或趋势,已成为当前重要的研究课题。随着网络规模的快速膨胀,网络结构复杂多样,传统网络可视化方法已经难以满足实际需求。为此,本课题致力于大规模网络的可视化技术研究,将其分解为“网络结构特征检测——网络结构展示”两个阶段,解决如下四个方面的具体问题:(1)大规模网络中重叠社团结构的快速检测;(2)网络拓扑中高阶依赖关系的检测和刻画;(3)大规模网络全局拓扑结构的多尺度展示;(4)局部高密度网络的精确展示。具体研究工作如下:1.针对现有重叠社团挖掘算法易将重叠区域错误地划分为独立的社团且计算复杂的问题,提出了一种基于局部信息度量的快速重叠社团挖掘算法。首先,为节点定义局部信息度量指标——社团连接度和邻居连接度,建模节点与社团的关系,缩小计算范围;然后,每次并行地迭代执行缩减、扩展、去重等操作,并更新局部度量指标,通过松弛每次迭代的终止条件,发现近似最优社团集合而不是最优社团,最终算法复杂度为O(7)m(10)n(8)。基于真实的大规模社交网络数据的试验分析表明:与当前流行的重叠社团挖掘算法相比,本文算法在不损失检测质量的前提下,大幅提升了计算效率。2.针对网络数据中高阶关联特性,设计了一种基于进化博弈理论的网络可视化聚类方法。首先采用超图描述网络内节点间的高阶关联特性,其次,将超图聚类的动态过程建模为进化博弈理论,证明了均衡点与优化问题解的一一对应关系,并推导出用于求解聚类的动力学方程,算法无需设定聚类的数目。人工和真实数据集相结合的试验表明:本文算法能够自动确定分簇数目,具有良好的聚类效果以及较强的鲁棒性。3.针对大规模网络全局结构多尺度展示的问题,提出了一种基于非重要节点拆分融合的网络层次压缩算法。该算法首先在定义节点块及其关系的基础上,给出了针对节点块的拓扑结构重要性度量方法;然后,利用资源分配和分流原理,提出了基于节点拆分的拓扑层次聚合机制;最后,通过将网络中每一层的非重要节点块拆分融合到与其相邻的节点块中,实现网络结构的快速压缩。与现有算法相比,本文算法效率较高,而且可以得到更加连贯的层次结构,从而更好实现多尺度展示。4.针对高密度网络中边的精确展示问题,提出面向强连接网络图的无损压缩算法,借助幂图分析技术,将所有具有相同邻居的节点集合汇聚成单个模块(modules)以大幅压缩网络图,连接到某个模块的一条边表明该边与模块内的所有元素都相连。从而,整个图均可以无损地可视化展示。首先,本文证明了含有单个模块的最优幂图问题为NP难问题,进而扩展一般地最优幂图分解计算为NP难问题;其次,在梳理现有整数线性规划模型和约束规划模型等问题的基础上,本文提出了基于回溯策略的波束搜索算法,以使有限的回溯策略提供启发信息,相较于已知启发式方法更快速地得到更优的结果;最后,通过生成的随机无标度图,验证了本文算法的有效性。
【学位授予单位】：战略支援部队信息工程大学
【学位级别】：博士
【学位授予年份】：2018
【分类号】：O157.5
【图文】：

社团,挖掘算法

社团挖掘是网络结构分析的重要手段，也是网络可视化的重要研究内容。社团挖掘算法通过将网络中连接紧密的节点划分到一起，形成若干个连接紧密的社团，从而可以得到网络的结构组成，效果如图1.1所示[20]。文献[21]便基于模块度提出了一个快速社团挖掘方法，即Louvain算法，极大的提升了社团挖掘的速度；Rosvall等[22]把社团划分问题转化为压缩编码问题，提出了基于随机游走的社团划分方法（Infomap），Infomap算法实用性强、划分效果好，但算法复杂度相对较高。通常网络社团呈现动态性、重叠性等特性导致检测不准确而影响应用性能。文献[25]则以社团的局部统计重要性为优化目标提出了OSLOM社团聚类方法，该方法能满足多目标优化，且克服了Infomap不能应用于重叠社团划分的问题；文献[26]给出了一种动态迭代算法检测社团结构，通过构建一种离散收敛的动态系统，通过动态迭代获取最优解。文献[27]从多尺度的角度分析了社团结构的动态稳定性。文献[28-30]聚焦于重叠社区的检测

技术应用,绑定,网络结构,聚类算法

点提取局部网络，并将标识传播算法应用其中，最终可以发现已有社团之间的联盟检测到重叠社团结构。但是该算法仍不能避免LPA算法的限制。可视化聚类研究主要思想是将聚类结果进行可视化展示，与社团挖掘算法类似网络可视化研究的内容之一。Kwon等[41]针对大量聚类算法及其参数的选择问题，一种帮助用户决策最佳聚类算法的可视化分析工具——Clustervision。文献[42]设计了Clusterix系统，允许用户动态地添加或删除聚类特征。Hongsen Liao等[43]针对基于的数据可视化分析面临的多维扩展问题，提出了基于聚类的可视化抽象方法增强多点图的可视化。Zhiguang Zhou等[44]将可视化聚类方法应用于空气质量分析中，提高析效率。基于网格和密度的聚类方法作为一类重要的聚类技术，与本文算法类似，法不需要将分簇数目作为输入参数，适用于处理大规模数据集且类别可伸缩场景。度的聚类算法通过对象密度计算任意形状的分簇结构，典型的代表为OPTICS算法[划分簇，而是产生一个聚类结构，算法输入参数为领域半径和分簇的最小对象数，度阈值动态划分不同分簇。基于网络的聚类算法，将数据对象组织为矩阵，并使用构划分为矩形块的值空间，通过块信息分布实现聚类，代表性算法为STING算法[46]中，网格聚类通常与基于密度聚类的方法相结合，如GDILC算法[47]。

社团,大规模网络,挖掘算法,较小值

第二章面向大规模网络的快速重叠社团挖掘算法确保在任何社团中的任意节点在社团中至少存在K 个邻居，公 1 , 0ii j i i jjN v K S K N v K 若，其它常大的值，小而稠密的社团将被忽略。另一方面，若K 为非常疏的大型社团和微小的社团，且算法不会受K 取较小值的影响值为 0.6 时（关于社团相似度将在 2.3.3 节（4）步骤中定义）出了本文算法应用于 Amazon 网络[104]时检测的社团的统计变化，稀疏的拓扑将不存在社团结构。除高密度网络拓扑结构之外，。

【参考文献】