融合社区结构信息和节点信息的链路预测研究
发布时间：2021-08-18 22:51
随着互联网技术的发展,链路预测作为研究复杂网络的重要手段之一,具有重要的理论和现实意义。近年来,该方向的研究成果层出不穷,然而现有算法在充分提取网络信息方面仍存在不足,不能准确且高效地预测缺失链路。为了解决以上问题,本文首先利用社区发现算法提取复杂网络中的结构信息,再与节点信息进行融合,充分利用复杂网络中的信息,提出一种融合社区结构信息和节点信息的链路预测算法。内容概述如下:一、针对模块度分辨率受限和传统差分进化准确性与收敛速度方面的问题,提出结合改进差分进化和模块密度的社区发现算法（Improved Differential Evolution and Modularity Density Community Detection,IMDECD）。首先调整差分进化的变异策略和参数,再将模块密度作为适应度函数以克服模块度分辨率限制;最后根据社区结构进行修正操作,以提高种群中的个体质量,加快全局收敛速度。二、针对现有的链路预测算法在大规模网络耗时较长或者预测结果不准确的问题,利用社区结构中的结构信息,融合节点相似性,提出融合社区结构信息和节点信息的链路预测算法（Link Predictio...
【文章来源】：辽宁大学辽宁省 211工程院校
【文章页数】：63 页
【学位级别】：硕士
【部分图文】：
空手道俱乐部网络图
第1章绪论5链路预测早期主要基于马尔科夫链和机器学习来进行研究，Sarukkai[21]于2000年首次在万维网中应用马尔科夫链进行链路预测和路径分析。之后Liben和Kleinberg[22]于2003年首次研究了社会合作网络中的链路预测。链路预测可以通过网络中的已知信息来预测尚未产生连接的概率，也可以被用于识别和删除网络中的虚假连接，具体预测任务见图1-2。图1-2链路预测的预测任务根据研究方式的不同，链路预测可以大致分为基于结构相似性的算法、基于似然分析的算法以及基于机器学习的算法，其中基于结构相似性的算法又分为基于局部信息的相似性指标、基于路径的相似性指标、基于随机游走的相似性指标以及其他相似算法。基于似然分析的算法，有层次结构模型（HierachicalStructureModel，HSM）、随机分块模型（StochasticBlockModel，SBM）以及闭路模型等。Clauset[23]等人提出层次结构模型，利用分层的网络结构信息进行链路预测；Dorelan[24]等人提出随机分块模型，在多个网络上进行实验，提高了预测准确度；潘黎明[25]等人提出闭路模型，使得预测准确度更高。以上算法虽然预测准确度较高，但是当网络规模过大时，其计算量会大幅增加，导致无法在大规模网络上使用。机器学习分为有监督、无监督以及半监督学习，其中基于结构相似性和似然分析的链路预测算法都是利用结构信息，它们都属于无监督学习的范围。陈可佳[26]等人在链路预测中引入半监督学习，利用网络中未连接节点对的潜在信息去进行预测，最后在不同规模数据集上进行实验验证。基于有监督学习的算
第1章绪论7图1-3本文算法的整体流程图（1）学习有关技术、收集相关文献，了解差分进化、模块度、模块密度、社区结构信息和节点相似性等相关概念，对社区发现算法、链路预测算法及其应用进行了详细的研究，总结国内外的相关研究情况，对现有算法的贡献与不足进行总结。（2）针对模块度分辨率受限和传统差分进化准确性与收敛速度方面的问题，将差分进化和模块密度思想引入社区发现中，提出结合改进差分进化和模块密度的社区发现算法(ImprovedDifferentialEvolutionandModularityDensityCommunityDetection，IMDECD)。首先对差分进化进行变异策略改进和动态自适应参数调整，提出改进的差分进化策略(ImprovedDifferentialEvolution，IMDE)，再将模块密度作为适应度函数以克服模块度分辨率限制；然后在改进差分进化结合社区发现的过程中，进行基于社区结构的修改，以提高种群中的个体质量，加快全局收敛速度；最后，在计算机生成网络数据集及5个具有代表性的真实世界网络数据集上，与多个应用较为广泛的社区发现算法进行对比实验。实验结果表明本文所提算法具有更高的准确性和更优的收敛性能。（3）针对现有的链路预测算法在大规模网络耗时较长或者预测结果不准确的问题，利用社区划分后社区结果中的结构信息，融合节点相似性，提出融合社区结构信息和节点信息的链路预测算法（LinkPredictionAlgorithmIntegratedwithCommunityStructureInformationandNodeInformation，LPCN）。首先基于模块密度以及划分后的社区结构，定义一种在不同分辨率下的社区相似性指标；然后考虑网络中的节点信息，将RA指标进行改进，基于考虑增强大度节点的重要性的RAm指标计算节点相似性指标，再将二者融合得到融合相似性指标；最后在多个真实世界网络数据集上，与现有
本文编号：3350775
【文章来源】：辽宁大学辽宁省 211工程院校
【文章页数】：63 页
【学位级别】：硕士
【部分图文】：
空手道俱乐部网络图
第1章绪论5链路预测早期主要基于马尔科夫链和机器学习来进行研究，Sarukkai[21]于2000年首次在万维网中应用马尔科夫链进行链路预测和路径分析。之后Liben和Kleinberg[22]于2003年首次研究了社会合作网络中的链路预测。链路预测可以通过网络中的已知信息来预测尚未产生连接的概率，也可以被用于识别和删除网络中的虚假连接，具体预测任务见图1-2。图1-2链路预测的预测任务根据研究方式的不同，链路预测可以大致分为基于结构相似性的算法、基于似然分析的算法以及基于机器学习的算法，其中基于结构相似性的算法又分为基于局部信息的相似性指标、基于路径的相似性指标、基于随机游走的相似性指标以及其他相似算法。基于似然分析的算法，有层次结构模型（HierachicalStructureModel，HSM）、随机分块模型（StochasticBlockModel，SBM）以及闭路模型等。Clauset[23]等人提出层次结构模型，利用分层的网络结构信息进行链路预测；Dorelan[24]等人提出随机分块模型，在多个网络上进行实验，提高了预测准确度；潘黎明[25]等人提出闭路模型，使得预测准确度更高。以上算法虽然预测准确度较高，但是当网络规模过大时，其计算量会大幅增加，导致无法在大规模网络上使用。机器学习分为有监督、无监督以及半监督学习，其中基于结构相似性和似然分析的链路预测算法都是利用结构信息，它们都属于无监督学习的范围。陈可佳[26]等人在链路预测中引入半监督学习，利用网络中未连接节点对的潜在信息去进行预测，最后在不同规模数据集上进行实验验证。基于有监督学习的算
第1章绪论7图1-3本文算法的整体流程图（1）学习有关技术、收集相关文献，了解差分进化、模块度、模块密度、社区结构信息和节点相似性等相关概念，对社区发现算法、链路预测算法及其应用进行了详细的研究，总结国内外的相关研究情况，对现有算法的贡献与不足进行总结。（2）针对模块度分辨率受限和传统差分进化准确性与收敛速度方面的问题，将差分进化和模块密度思想引入社区发现中，提出结合改进差分进化和模块密度的社区发现算法(ImprovedDifferentialEvolutionandModularityDensityCommunityDetection，IMDECD)。首先对差分进化进行变异策略改进和动态自适应参数调整，提出改进的差分进化策略(ImprovedDifferentialEvolution，IMDE)，再将模块密度作为适应度函数以克服模块度分辨率限制；然后在改进差分进化结合社区发现的过程中，进行基于社区结构的修改，以提高种群中的个体质量，加快全局收敛速度；最后，在计算机生成网络数据集及5个具有代表性的真实世界网络数据集上，与多个应用较为广泛的社区发现算法进行对比实验。实验结果表明本文所提算法具有更高的准确性和更优的收敛性能。（3）针对现有的链路预测算法在大规模网络耗时较长或者预测结果不准确的问题，利用社区划分后社区结果中的结构信息，融合节点相似性，提出融合社区结构信息和节点信息的链路预测算法（LinkPredictionAlgorithmIntegratedwithCommunityStructureInformationandNodeInformation，LPCN）。首先基于模块密度以及划分后的社区结构，定义一种在不同分辨率下的社区相似性指标；然后考虑网络中的节点信息，将RA指标进行改进，基于考虑增强大度节点的重要性的RAm指标计算节点相似性指标，再将二者融合得到融合相似性指标；最后在多个真实世界网络数据集上，与现有
本文编号：3350775
本文链接：https://www.wllwen.com/kejilunwen/zidonghuakongzhilunwen/3350775.html
