移动社交网络中基于网络中心度的链路预测方法*

移动社交网络中的链路预测是指通过已知的网络节点以及移动社交网络结构等信息预测网络中尚未产生连边的两个节点之间产生链接的可能性。基于网络中心度的思想,提出一种适用于移动社交网络的链路预测算法。在该算法中,根据节点网络中心度和共同邻居数来计算两个节点的相似性指标,两个节点的共同邻居数越多、共同邻居的网络中心度越高,则两个节点的相似度越高。另外,由于移动社交网络的动态性特征,还将考虑时间因素对预测结果的影响。将该方法与其他4种常用的链路预测方法进行比较,实验结果显示所提方法要优于其他方法。     

基于最低度偏置重启随机游走的链路预测方法

链路预测是数据挖掘主题中的一个重要问题。基于随机游走的相似性方法一般设定游走粒子转移到相邻节点的概率是相等的,忽略了节点度值对转移概率的影响。针对此问题,提出一种基于lowest-degree偏置重启随机游走的链路预测方法。首先引入最低度偏置函数,对游走粒子的转移概率进行重新定义,然后将最低度偏置随机游走策略运用到重启随机游走中,探究粒子在游走过程中最低度偏向策略对节点相似度的影响。在九个真实网络数据集上进行链路预测,结果表明,所提方法具有良好的预测精度,且挖掘了更多网络拓扑结构信息,证明该算法在节点相似性的评估上具有一定的优势。     

基于共同邻居惩罚的复杂网络链路预测方法

链接预测是确定用户间关系的基本工具。通过相似性度量进行链路预测是一种常见的方法,提出一种基于相似度的链路预测算法,根据网络结构及拓扑特性来确定相似度,引入优化链路预测度量方法,将聚类系数作为网络结构性质。此外,并考虑共享邻域,得到较其他同类链路预测方法更好的性能。实验结果表明,提出的算法性能优于经典算法。结合在Facebook、Twitter与新浪微博等社交网络环境中的实验结果可知,SLP-CNP法较其他算法具有更优精度与效率。在未来的工作中,还可尝试在所提方法的基础上,提升在加权网络、有向网络和二部网络中的适用性。     

基于相似度的三元社团合并算法*

针对使用相似度测量进行社团划分时可能出现的判断冲突问题,提出了一种基于相似度的三元社团合并算法。首先通过对相似度阈值的选取,筛选网络中不同的三元社团,并将其作为社团合并的基本元素,通过社团相似度将其合并。然后将剩余节点和孤立三元社团分别按照节点从属度和三元社团从属度划分到相应社团。最后通过在人工合成网络和真实世界网络上进行实验测试,结果表明用本文算法可以准确高效的将网络中的节点划分到相应的社团。     

基于网络表示学习与随机游走的链路预测算法

现有的基于随机游走链路预测指标在无权网络上的转移过程存在较强随机性,没有考虑在网络结构上不同邻居节点间的相似性对转移概率的作用。针对此问题,提出一种基于网络表示学习与随机游走的链路预测算法。首先,通过基于深度学习的网络表示学习算法——DeepWalk学习网络节点的潜在结构特征,将网络中的各节点表征到低维向量空间;然后,在重启随机游走（RWR）和局部随机游走（LRW）算法的随机游走过程中融合各邻居节点在向量空间上的相似性,重新定义出邻居节点间的转移概率;最后,在5个真实数据集上进行大量实验验证。实验结果表明：相比8种具有代表性的基于网络结构的链路预测基准算法,所提算法链路预测结果的AUC值均有提升,最高达3.34%。     

基于复杂网络动力学模型的链路预测方法

链路预测是复杂网络中研究缺失连边和未来形成连边的重要组成部分,当前基于网络结构的链路预测方法成果丰富,而基于复杂网络动力学模型的链路预测研究较少。针对无权无向网络,首先构建了复杂网络动力学模型,然后给出了基于复杂网络动力学模型的链路预测节点中心性的量化评价指标,最后通过给出的节点中心性量化指标,提出了由复杂网络动力学模型定义的链路预测方法。通过在真实网络数据集上进行的实验表明,提出的链路预测方法较基准方法有明显的预测精度的提升。     

基于维基百科的领域概念语义知识库的自动构建方法*

针对为检索服务的语义知识库存在的内容不全面和不准确的问题,提出一种基于维基百科的软件工程领域概念语义知识库的构建方法;首先,以SWEBOK V3概念为标准,从维基百科提取概念的解释文本,并抽取其关键词表示概念的语义;其次,通过概念在维基百科中的层次关系、概念与其它概念解释文本关键词之间的链接关系、不同概念解释文本关键词之间的链接关系构建概念语义知识库;接着, LDA主题模型分别和TF-IDF算法、TextRank算法相结合的两种方法抽取关键词;最后,对构建好的概念语义知识库用随机游走算法计算概念间的语义相似度;将实验结果与人工标注结果对比发现,本方法构建的语义知识库语义相似度准确率能够达到84%以上;充分验证了所提方法的有效性。     

利用集成分类器处理链路预测中的分类不平衡问题*

对于现实的复杂网络而言,有连边的节点对数目通常远小于无连边的节点对数目,在链路预测时,不同类别的样本数量不平衡会导致预测的分类结果与真实情况有较大的偏差。针对此问题,本文提出更优的链路预测算法,先对网络拓扑信息进行特征提取,再设计出一种集成分类器对数据样本进行平衡处理,然后基于网络的拓扑信息改进了分类器的集成规则,最后将训练出的集成分类器同现有的4个针对不平衡分类的链路预测学习算法进行对比研究。通过对4个不同规模的时序网络进行链路预测,结果表明：本文的链路预测学习算法具有更高的召回率,同时也保证了预测结果的准确性,从而更好地解决了链路预测中因类别不平衡导致的误分类问题。     

基于节点亲密度的链路预测算法

链路预测作为复杂网络分析的一个重要分支,在不同领域中有着广泛的应用。现有的链路预测算法通常根据共同邻居节点的结构信息来度量节点对之间的相似性,忽略了节点对与其共同邻居节点之间的连接紧密程度。针对此问题,提出了一种基于节点亲密度的链路预测算法。该算法利用边聚集系数来测量节点对与其共同邻居节点之间的紧密程度,以AUC值作为链路预测的精确度评价指标。在4个真实网络上的实验结果表明,相比于其他相似性算法,所提出的算法提高了链路预测的预测精度。     

基于学习连续时间事件序列的动态网络链路预测

动态网络链路预测是目前复杂网络的热点研究方向,网络表示学习可以有效学习到节点的相似性,从而为链路预测提供基础.现有的动态网络表示学习方法大多先将动态网络进行离散窗口化,然后在静态网络快照图上建模,这样很难有效处理具有细粒度时间特性的动态网络.本文提出了一种可以学习动态网络中复杂的时间特性的链路预测模型,该模型使用连续时间事件序列表示动态网络,对网络中的连续时间信息和结构演化特征进行学习,并提出了基于时间注意力的信息传递机制来模拟网络中信息的扩散与聚合,最后将链路预测转化为分类问题.实验在4个真实动态网络数据集以及模拟网络上进行,并以ap和auc作为评价指标.真实网络实验结果证明该模型能够较好地学习网络演化的连续性,得到更有效的节点表示,从而提升了链路预测效果.模拟网络的实验结果表明链路预测的效果和网络模型相关,但本文模型仍可以获得较好的预测效果.     

基于拓扑连接紧密度的相似性链路预测算法

许多链路预测方法仅仅关注预测的准确度衡量指标,忽略了精确度衡量标准在实际应用中的重要作用,且没有考虑共同邻居与预测节点间紧密度对相似性刻画的影响。针对上述问题,提出了一种基于拓扑连接紧密度的相似性链路预测算法。该方法通过局部拓扑结构定义共同邻居紧密度,并引入参数调节不同网络中紧密程度,最终刻画网络节点间的相似度。6个实际网络测试表明,相比共同邻居（CN）、资源分配（RA）、Adamic-Adar（AA）、局部路径（LP）、Katz等相似性指标,该算法提升了链路预测的预测精度。     

融合聚集系数的链接预测方法

许多基于网络结构信息的链接预测算法利用节点的聚集程度评估节点间的相似性,进而执行链接预测;然而,该类算法只注重网络中节点的聚集系数,没有考虑预测节点与共同邻居节点之间的链接聚集系数对节点间相似性的影响。针对上述问题,提出了一种融合节点聚集系数和非对称链接聚集系数的链接预测算法。首先,计算共同邻居节点的聚集系数,并利用共同邻居节点对应的两个非对称链接聚集系数计算该预测节点的平均链接聚集系数;然后,基于Dempster-Shafer证据理论将两种聚集系数进行融合生成一个综合性度量指标,并将该指标应用于中间概率模型（IMP）,得到一个新的节点相似性指标（IMP_DS）。在9个网络数据上的实验结果表明,该算法的受试者工作特征（ROC）的曲线下方面积（AUC）与精度值（Precision）优于共同邻居（CN）、Adamic-Adar（AA）、资源分配（RA）指标和基于共同邻居的中间概率模型（IMP_CN）。     

两阶段量子行走算法在社区检测中的应用

已有基于量子行走的社区检测算法存在计算开销过大或对时间参数过于敏感的问题。针对此问题,提出两阶段量子行走（two-stage quantum walk,TSQW）算法。TSQW算法第一阶段为无测量量子行走,此阶段融合节点的邻域拓扑信息将节点表达为向量,第二阶段利用K-means方法聚类上一阶段得到的节点向量以划分网络社区。通过仿真网络和空手道俱乐部网络的验证,该算法能够准确地检测网络社区结构。进一步,提出TSQW的扩展（TSQW-E）算法,该算法依据节点的社区信息增加或删除原始网络的连边并实现社区隐藏。根据互信息指标和调整兰德系数下的实验表现,TSQW-E算法使已有社区检测算法的平均识别精度分别下降0.491和0.58,对网络社区结构的破坏效果最好。     

基于高阶自包含协同过滤的有向网络链路预测

针对大部分现存有向网络链路预测方法仅关注有向局部结构及互惠链接信息而忽略有向全局结构的问题,提出高阶自包含协同过滤(HSCF)链路预测框架。首先,利用随机游走方法计算高阶相似度矩阵去保持有向网络的高阶路径信息;其次,将高阶相似度矩阵与协同过滤方法相融合构建HSCF框架;最后,把所提框架分别与有向共同邻居(DCN)、有向Adamic-Adar(DAA)、有向资源分配(DRA)和势能理论Bifan 4个典型有向结构相似度相融合,并由此提出HSCF-DCN、HSCF-DAA、HSCF-DRA和HSCF-Bifan 4个有向网络预测指标。在10个真实有向网络上的实验结果表明,与基准指标相比,HSCF-DCN、HSCF-DAA、HSCF-DRA和HSCF-Bifan的受试者工作特征（ROC）曲线下方面积（AUC）值分别平均提高了8.16%、8.85%、9.64%和10.33%,且F分数值分别平均提高了66.62%、68.32%、68.95%和76.18%。     

基于复杂网络节点重要性的链路预测算法

提升链路预测精度是复杂网络研究的基础问题之一,现有的基于节点相似的链路预测指标没有充分利用网络节点的重要性,即节点在网络中的影响力。针对以上问题提出基于节点重要性的链路预测算法。该算法在基于局部相似性链路预测算法的共同邻居（CN）、Adamic-Adar（AA）、Resource Allocation（RA）相似性指标的基础上,充分利用了节点度中心性、接近中心性及介数中心性的信息,提出考虑节点重要性的CN、AA、RA链路预测相似性指标。在4个真实数据集上进行仿真实验,以AUC值作为链路预测精度评价指标,实验结果表明,改进的算法在4个数据集上的链路预测精度均高于共同邻居等对比算法,能够对复杂网络结构产生更精确的分析预测。     

半监督学习在链接预测问题中的应用

链接预测是社会网络分析领域的关键问题,研究如何从已知网络中预测可能存在的新链接。现实网络中存在了大量未连接的节点对,从中挖掘潜在信息可以帮助实现链接预测任务。将链接预测视为二类分类问题,使用半监督学习技术,利用网络中的未标记数据帮助学习。使用了两种半监督范式:自我训练和协同训练。在现实数据集Enron和DBLP中的实验结果表明,链接预测任务中采用未标记数据能够有效提高预测的准确率。     

链路预测的方法与发展综述

链路预测对网络结构特征的演化趋势进行挖掘有着不可磨灭的促进作用。为了对网络的未来结构变化进行预测，学者们提出了许多算法。综述了4类较为常见的链路预测方法，分别是基于节点属性、基于网络拓扑结构、基于机器学习以及基于最大似然的方法，比较了4类预测方法的优劣，并概述了几种常见的衡量链路预测算法精确度标准。最后总结并展望了链路预测的未来研究方向和发展前景。