改进朴素贝叶斯模型的复杂网络关系预测

复杂网络包括生物性信息网络、科学家合作网络、社交关系网络等,研究复杂网络的关系预测问题有助于预测蛋白质相互关系,发现科学家合作关系,以及挖掘潜在好友关系等。目前,绝大多数关系预测算法由复杂网络的相似度模型实现,但该类型算法基于显式的网络拓扑特征构建,忽视了影响关系生成的隐含信息。针对这一问题,在朴素贝叶斯链接预测模型(LNB)基础上提出了一种加强(Enhanced)朴素贝叶斯链接预测模型(ELNB),该模型通过定义共邻节点关系概率对共邻节点构成的局部子图特征进行建模,有效缓解了LNB中的独立性假设,实现了共邻节点关系贡献的量化计算。在人工数据集和真实复杂网络数据集上的实验表明,本文提出的模型优于基准算法和其他新近提出的模型。同时,把ELNB的思想有效地拓展到其他基于共邻节点的相似度算法中,为该类模型的研究提供一种新的方案。     

一种集成局部加权聚类系数的链接预测算法

加权复杂网络中的权重主要表示节点与节点之间的相互作用强度。由于权重的存在,传统的基于局部结构的无权链接预测方法并不适用于加权网络。因此一部分工作尝试把传统的基于局部邻接节点结构的算法迁移到加权网络场景,但是该类算法只是利用了一级共邻节点的拓扑属性,无法反映共邻节点的邻居对潜在节点对的贡献以及共邻节点互联密集程度对预测结果的影响。该文从局部结构的密集层面来分析共邻节点对潜在节点对的影响,提出了一种集成加权聚类系数的相似度指标（WCCLP）,该指标能够有效地扩大局部共邻节点结构对预测性能的影响,同时也能轻易拓展到加权局部朴素贝叶斯链接预测模型（WLNB）中。采用无监督学习的实验表明,和现有的相似度算法相比,WCCLP在多个真实数据集取得了更好的预测效果,同时在有监督学习的链接预测场景中,由WCCLP构建的特征比现有的局部相似度算法构成的特征更具判别性,同时拓展到WLNB的实验效果证明加权聚类系数的定义能够有效推广到其他模型当中。     

基于划分社区和差分共邻节点贡献的链路预测

通过改进基于节点相似度的朴素贝叶斯模型, 引入GN和CMN两种经典的划分社区算法挖掘网络社区属性对预测节点对的影响, 赋予共邻节点不同的连接度和社区贡献度并计算其贡献权重, 同时把模型应用于五种相似度算法, 采用ROC和Precision-Recall曲线进行实验评价。人工网络和真实网络中的实验证明, 该模型能够在深入挖掘社会网络结构信息的基础上提高预测的精确度, 同时为该类模型的研究提供一种新的方案。     

差分化节点特征对复杂网络链接预测的分类性能分析

链接预测属于复杂网络分析的研究分支,它根据网络历史结构信息预测未来节点间会产生链接的可能性,从而挖掘网络的传播和演化方式。通过引入差分化节点的贡献权重并结合经典的节点和共邻节点网络拓扑结构特征,分别应用七类有监督学习-分类模型对社交、生物、交通等不同领域的八个真实复杂网络数据集进行实验,并采用Precision和ROC曲线对实验结果进行分析与评价。实验表明,引入基于差分化节点的贡献特征能够在深入挖掘网络结构信息的基础上比其余特征有更优的预测精确度,同时差异化的分类模型和特征选择对链接预测性能有相异的影响。     

非对称信息在链接预测中的应用

针对基于节点相似性的链接关系预测中因未考虑非对称信息导致预测准确度降低的问题,提出一种新的增加非对称信息的节点相似性度量方法。首先,分析了基于共同邻居（CN）的相似性度量算法的缺陷在于仅考虑CN的数量而未考虑各自节点的所有邻居的数量;然后,将节点之间的相似性度量定义为共同节点与所有邻居节点的比值,融合节点间对称相似信息和非对称相似信息,对节点间的相似程度进行深入细致的刻画;最后,将该方法应用到复杂网络中进行链接关系的预测。在真实数据集上的实验结果表明,与目前多种基于共邻的相似性度量方法——CN、AA、资源分配（RA）相比,所提方法提升了节点相似性度量的准确性,并且可以提高复杂网络中链接关系预测的准确度。     

基于隐朴素贝叶斯模型的社会关系推荐

基于共邻用户属性的社会关系推荐算法是社会网络分析关系预测领域的热点研究方向。提出了一种基于隐朴素贝叶斯（hidden nave Bayesian,HNB）模型的用户关系推荐算法。该算法通过分析属性之间的依赖性对问题建模,从中度量共邻用户之间关系对推荐用户对之间的贡献和影响,然后对所有候选推荐关系计算其相似度并进行排序,并把模型推广到CN、AA和RA三种关系推荐算法中。在真实网络数据集上的实验结果表明,所提出的算法比目前的基准方法和朴素贝叶斯方法具有更高的AUC值。此外,算法能够发现具备不同拓扑结构属性的网络对推荐精度有着线性的影响。     

融合多元影响力节点识别指标MPR的链接预测

多元网络通常是指节点之间存在多种维度链接关系的图结构.多元网络链接预测算法在构建相似度指标时,多数仅考虑单一维度网络的拓扑结构属性,未挖掘不同维度子网络之间存在的关联,影响链接预测的效果.针对该问题,提出一种基于多元全局节点影响力识别指标MPR的多元网络链接预测算法.通过定义一个多维度节点影响力排序指标MPR,度量多元网络空间中影响力较大的节点,并把影响力排名函数转化为潜在节点对之间的相似度得分,从而应用到多元网络链接预测场景中.在2个真实多元网络数据集上的实验结果表明,该算法的预测效果优于PR、EDC、ANC等对比算法,且具有较好的稳定性.     

基于模体的朴素贝叶斯链路预测方法

在具有模体特征的食物链网络、社交网络中,局部朴素贝叶斯（LNB）的链路预测方法通过准确区分每个共邻节点的贡献以提高链路预测的精确度,但忽略了每个共邻节点对所在路径的贡献不同以及网络模体结构对链接形成的作用。针对LNB链路预测方法存在的局限性问题,结合路径模体特征与朴素贝叶斯理论,提出基于模体的朴素贝叶斯链路预测方法。定义模体密度以量化路径结构上模体的聚集程度。考虑路径结构上模体密度对链接形成的影响,构建每条路径的角色贡献函数,以量化每条路径结构的模体特征对节点相似性的影响。在此基础上,根据朴素贝叶斯理论与角色贡献函数推导节点相似性指标。在Football、USAir、C.elegans、FWMW、FWEW和FWFW 6个真实网络上进行实验,结果表明,该方法能有效提高预测性能且具有较优的鲁棒性,其中在具有显著模体特征的FWMW、FWEW、FWFW网络上,相比现有相似性指标中较优的Katz指标,所提相似性指标的AUC值提升了2%~7%。     

融合网络结构和节点属性的链接预测方法

链接预测旨在推荐网络中潜在的链接,是理解和研究社会网络特征的重要一步。随着社会网络的发展,许多网络中包含了大量的节点属性信息。研究集中在结合网络结构和节点属性信息来进行链接预测。网络中的两个节点既可能因为结构上相邻形成新链接,也可能因为属性相似产生联系,基于此假设提出了一种新的融合网络结构和节点属性的随机游走模型用于链接预测。首先建立了两个不同的网络图以及转移概率矩阵用于新的迭代规则,而后再简化该模型用于计算并提出了一种近似的快速算法。在两个标准数据集上进行的实验表明该方法较同类方法有明显的效果提升,同时进一步分析了随机游走粒子在两个网络图中游走的概率对预测结果的影响,分析结果显示节点属性可有效提高模型的预测能力。     

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

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

SSDBA:the stretch shrink distance based algorithm for link prediction in social networks

In the field of social network analysis,Link Predic-tion is one of the hottest topics which has been attracted attentions in academia and industry.So far,literatures for solving link prediction can be roughly divided into two categories:similarity-based and learning-based methods.The learning-based methods have higher accuracy,but their time complexities are too high for complex networks.However,the similarity-based methods have the advantage of low time consumption,so improving their accuracy becomes a key issue.In this paper,we employ community structures of social networks to improve the prediction accuracy and propose the stretch shrink distance based algorithm(SSDBA),In SSDBA,we first detect communities of a social network and identify active nodes based on community average threshold(CAT)and node average threshold(NAT)in each community.Second,we propose the stretch shrink distance(SSD)model to iteratively calculate the changes of distances between active nodes and their local neighbors.Finally,we make predictions when these links'distances tend to converge.Furthermore,extensive parameters learning have been carried out in experiments.We compare our SSDBA with other popular approaches.Experimental results validate the effectiveness and efficiency of proposed algorithm.     

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

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

Graph kernel based link prediction for signed social networks

By revealing potential relationships between users, link prediction has long been considered as a fundamental research issue in singed social networks. The key of link prediction is to measure the similarity between users. Existing works use connections between target users or their common neighbors to measure user similarity. Rich information available for link prediction is missing since use similarity is widely influenced by many users via social connections. We therefore propose a novel graph kernel based link prediction method, which predicts links by comparing user similarity via signed social network’s structural information: we first generate a set of subgraphs with different strength of social relations for each user, then calculate the graph kernel similarities between subgraphs, in which Bhattacharyya kernel is used to measure the similarity of the k-dimensional Gaussian distributions related to each k-order Krylov subspace generated for each subgraph, and finally train SVM classifier with user similarity information to predict links. Experiments held on real application datasets show that our proposed method has good link prediction performances on both positive and negative link prediction. Our method has significantly higher link prediction accuracy and F1-score than existing works.     

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

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

Proximity measures for link prediction based on temporal events

Link prediction is a well-known task from the Social Network Analysis field that deals with the occurrence of connections in a network. It consists of using the network structure up to a given time in order to predict the appearance of links in a close future. The majority of previous work in link prediction is focused on the application of proximity measures (e.g., path distance, common neighbors) to non-connected pairs of nodes at present time in order to predict new connections in the future. New links can be predicted for instance by ordering the pairs of nodes according to their proximity scores. A limitation usually observed in previous work is that only the current state of the network is used to compute the proximity scores, without taking any temporal information into account (i.e., a static graph representation is adopted). In this work, we propose a new proximity measure for link prediction based on the concept of temporal events. In our work, we defined a temporal event related to a pair of nodes according to the creation, maintenance or interruption of the relationship between the nodes in consecutive periods of time. We proposed an event-based score which is updated along time by rewarding the temporal events observed between the pair of nodes under analysis and their neighborhood. The assigned rewards depend on the type of temporal event observed (e.g., if a link is conserved along time, a positive reward is assigned). Hence, the dynamics of links as the network evolves is used to update representative scores to pairs of nodes, rewarding pairs which formed or preserved a link and penalizing the ones that are no longer connected. In the performed experiments, we evaluated the proposed event-based measure in different scenarios for link prediction using co-authorship networks. Promising results were observed when the proposed measure was compared to both static proximity measures and a time series approach (a more competitive method) that also deploys temporal information for link prediction.     

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

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

基于共同邻居邻域拓扑稠密性加权的链路预测方法

链路预测旨在利用已知的网络节点和拓扑结构信息,预测网络中未连接的两个节点之间存在连边的可能性。基于网络拓扑相似性的链路预测方法计算复杂度低且预测效果好,但现有的相似性指标对共同邻居的邻域拓扑信息考虑较少。针对此问题,提出一种基于共同邻居邻域拓扑稠密性加权的链路预测方法。首先,基于邻域拓扑相对稠密指数量化节点的邻域拓扑结构;然后,利用共同邻居的节点度和邻域拓扑相对稠密指数刻画共同邻居及其邻域拓扑的相似性贡献;最后,提出基于共同邻居邻域拓扑稠密性加权的节点相似性指标。在多个实际网络数据上的实验结果表明,与现有相似性指标相比,该方法能够取得更高的预测精度。     

融合节点中心性和度相关聚类的有向网络链路预测

现存大部分有向网络的链路预测方法仅关注链接方向信息和互惠链接信息而忽略节点重要性及度相关聚类的贡献,导致预测精度下降。针对以上不足,提出基于节点中心性和度相关聚类的有向网络链路预测指标。首先,利用节点中心性统计任意节点邻居数量去衡量节点的影响力;其次,将节点度相关聚类系数方法扩展到有向网络去评估节点聚类能力,并与网络同配系数相融合获得节点对高聚类能力;最后,融合以上2类信息提出一个带参的有向网络链路预测指标。在6个真实世界有向网络上与最近代表性预测指标比较,所提指标AUPR和AUC分别提高了33%和1.6%。