论文摘要
现实世界中存在大量复杂系统可以抽象为网络形式,例如,疾病传播网络、科学家合作网络、能源传输网络、细胞代谢网络等。网络由节点和连接节点的边构成,其中节点表示系统中的主体,边表示网络主体间的关系或交互。社团结构作为复杂网络的重要特征,指的是网络中的节点聚集成簇,簇内连接紧密,簇间连接稀疏。社团检测旨在揭示网络中所蕴含的社团结构,有助于对网络结构的分析、对网络功能的推断、对网络拓扑的优化,并指导现实网络结构的识别、构建和预测,因而是理解和探索网络结构与功能的关键问题。高效准确地检测出网络中的社团结构、以及利用检测结果进行分析挖掘是复杂网络理论与实践研究中的重要课题。本文围绕社团检测和社团演化预测相关问题开展研究,主要工作和创新点如下:（1）针对标签扩散社团检测算法（LPA,Label Propogation Algorithm）存在的鲁棒性和稳定性较差等问题,提出一种LPA的改进算法基于角色的标签扩散算法（RLPA,Role-based Label Propogation Algorithm）。在已有社团检测算法中,标签扩散算法具有时间复杂度低、准确率较高、便于并行化等优点,然而,所引入的随机性使得算法具有较差的鲁棒性和稳定性,并且当网络社团结构较弱时,扩散机制可能导致网络中的大部分节点隶属于同一社团,从而得到无意义结果。为此,在深入分析社团角色对标签扩散过程的影响的基础上,基于标签扩散算法,通过引入一种与社团角色相关的度量作为节点偏好,利用局部指标调整节点更新策略,以提高鲁棒性和稳定性,及在社团结构较弱网络中的检测能力。在多个人工网络、实际网络上的实验结果表明,RLPA有效提高了检测的准确性,同时继承了原算法的速度优势。（2）针对基于角色的标签扩散算法在面向动态网络社团检测时,因采用静态检测方式导致结果不具有时序平滑性的问题,提出一种基于角色的标签扩散算法的动态网络扩展算法提出一种基于角色的标签扩散演化社团检测算法（RELPA,Role-based Evolutionary LPA）。由于实际动态网络中社团演化具有连续性的特点,即相邻网络快照中检测出的社团结构不会有过大差异,因此,面向动态网络的社团检测算法需要将社团结构的时序平滑性作为参照。为此,在静态社团检测算法RLPA的基础上,结合前一时刻社团结构信息以提高时序平滑性,并根据时序结构差异性调整前序信息对当前社团结构的贡献权重,以提高结果的准确性。实验结果表明RELPA能够快速准确地检测出动态网络中的演化社团。（3）提出一种基于多元结构特征的社团演化预测方法（MECE,Multi-length Evolution Chains Ensemble）。特征构造是社团演化预测任务中的难点和核心。已有社团演化预测方法所构造的特征难以有效描述多种尺度下（微观、介观、宏观）的社团拓扑结构信息,并且在构造分类器时采用固定长度的演化链数据作为输入,无法利用不同长度演化链中蕴含的时序信息。为此,该算法通过从社团演化数据中提取社团的多尺度结构特征、时序特征、行为特征,并针对多重长度演化链构造集成分类器,以提高预测准确性。实验结果表明了MECE算法能够更加准确地预测动态网络中的社团演化趋势。
论文目录
文章来源
类型: 博士论文
作者: 何伟
导师: 胡学钢
关键词: 复杂网络,社团检测,节点角色,动态网络,社团演化预测
来源: 合肥工业大学
年度: 2019
分类: 基础科学,信息科技
专业: 数学,计算机软件及计算机应用
单位: 合肥工业大学
基金: 国家973计划:社交网络群体影响力及交互作用(2013CB329604),国家自然科学基金:面向多源高维数据流的在线特征选择与分类方法研究(61673152),安徽省科技攻关项目(科技强警专项):毒品犯罪案件信息综合管理分析系统(1001130616)
分类号: O157.5;TP301.6
DOI: 10.27101/d.cnki.ghfgu.2019.000680
总页数: 95
文件大小: 11917k