基于最大熵模型的微博传播网络中的链路预测

微博是基于用户关注关系建立的具有媒体特性的实时信息分享社交平台.微博上的信息扩散具有快速性、爆发性和时效性.理解信息的传播机理,预测信息转发行为,对研究微博上舆论的形成、产品的推广等具有重要意义.本文通过解析微博转发记录来研究影响信息转发的因素或特征,把微博信息转发预测问题抽象为链路预测问题,并提出基于最大熵模型的链路预测算法.实例验证的结果表明:1)基于最大熵模型的算法在运行时间上具有明显的优势;2)在预测结果方面,最大熵模型比同类其他算法表现优异;3)当训练集大小和特征数量变化时,基于最大熵模型的预测结果表现稳定.该方法在预测链路时避免了特征之间相互独立的约束,准确率优于其他同类方法,对解决复杂网络中其他类型的预测问题具有借鉴意义.     

用于混沌时间序列预测的多簇回响状态网络

研究了混沌时间序列预测问题.提出了一种由五元生长因子组调控的类皮层神经网络模型,即多簇回响状态网络模型（MCESN）.研究表明该生长因子组能够有效决定模型的拓扑性质;同时具备小世界和无标度等复杂网络特征的MCESN能够获得较优的预测结果.通过Monte Carlo仿真实验表明,该模型不仅训练算法简单,而且与常规回响状态网络比较,预测结果的精度更高、标准差更小. 关键词： 混沌时间序列预测 回响状态网络 复杂网络 Ω复杂性')" href="#">Ω复杂性     

网络的模块矩阵及其社团结构指标

探讨了复杂网络的模块矩阵的正(负)特征谱与网络的社团结构(反社团结构)的关系,给出了反映网络社团结构性质的相关定义.利用模块矩阵的多个特征值与特征向量,引入反映个体对所处社团的依附程度一种结构中心化指标.利用人工网络与实际网络数据,将这种指标与几种经典的中心化指标进行了比较.结果表明该指标具有较好的分辨率并与度指标具有一定程度的相关性.     

基于最小刚性图代数特性的无线网络拓扑优化算法

对于能量受限的无线传感器网络,拓扑优化能够降低能耗,优化通信链路结构.本文基于最小刚性图原理提出了一种新的拓扑优化算法,算法综合考虑了生成拓扑链路图中通信链路的权值与生成刚性图的代数特性问题,既保证了通信链路较短,有利于延长网络的生命周期,同时使生成的通信链路图结构更加稳定,网络具有较好的鲁棒性.仿真实验表明,与相关算法比较,提出的算法中通信链路较短,具有较好的网络连通性与结构稳定性,同时生成刚性图矩阵的迹较大,具有较好的刚度代数性能.     

基于自规避随机游走的节点排序算法

评估复杂网络系统的节点重要性有助于提升其系统抗毁性和结构稳定性. 目前, 定量节点重要性的排序算法通常基于网络结构的中心性指标如度数、介数、紧密度、特征向量等. 然而, 这些算法需要以知晓网络结构的全局信息为前提, 很难在大规模网络中实际应用. 基于自规避随机游走的思想, 提出一种结合网络结构局域信息和标签扩散的节点排序算法. 该算法综合考虑了节点的直接邻居数量及与其他节点之间的拓扑关系, 能够表征其在复杂网络系统中的结构影响力和重要性. 基于三个典型的实际网络, 通过对极大连通系数、网络谱距离数、节点连边数和脆弱系数等评估指标的实验对比, 结果表明提出的算法显著优于现有的依据局域信息的节点排序算法.     

动态复杂网络中节点影响力的研究进展

节点影响力的识别和预测具有重要的理论意义和应用价值,是复杂网络的热点研究领域.目前大多数研究方法都是针对静态网络或动态网络某一时刻的快照进行的,然而在实际应用场景中,社会、生物、信息、技术等复杂网络都是动态演化的.因此在动态复杂网络中评估节点影响力以及预测节点未来影响力,特别是在网络结构变化之前的预测更具意义.本文系统地总结了动态复杂网络中节点影响力算法面临的三类挑战,即在增长网络中,节点影响力算法的计算复杂性和时间偏见;网络实时动态演化时,节点影响力算法的适应性;网络结构微扰或突变时,节点影响力算法的鲁棒性,以及利用网络结构演变阐释经济复杂性涌现的问题.最后总结了这一研究方向几个待解决的问题并指出未来可能的发展方向.     

一种有效提高无标度网络负载容量的管理策略

现有研究表明明显的社团结构会显著降低网络的传输性能. 本文基于网络邻接矩阵的特征谱定义了链路对网络社团特性的贡献度, 提出一种通过逻辑关闭或删除对网络社团特性贡献度大的链路以提高网络传输性能的拓扑管理策略, 即社团弱化控制策略(CWCS 策略). 在具有社团结构的无标度网络上分别进行了基于全局最短路径路由和局部路由的仿真实验, 并与关闭连接度大的节点之间链路的HDF 策略进行了比较. 仿真实验结果显示, 在全局最短路径路由策略下, CWCS策略能更有效地提高网络负载容量, 并且网络的平均传输时间增加的幅度变小. 在局部路由策略下, 当调控参数0<α<2, 对网络负载容量的提升优于HDF策略. 关键词： 复杂网络 社团特性 负载容量 拓扑管理     

基于相对距离的复杂网络谱粗粒化方法

复杂网络的同步作为一种重要的网络动态特性,在通信、控制、生物等领域起着重要的作用.谱粗粒化方法是一种在保持原始网络的同步能力尽量不变情况下将大规模网络约简为小规模网络的算法.此方法在对约简节点分类时是以每个节点对应特征向量分量间的绝对距离作为判断标准,在实际运算中计算量大,可执行性较差.本文提出了一种以特征向量分量间相对距离作为分类标准的谱粗粒化改进算法,能够使节点的合并更加合理,从而更好地保持原始网络的同步能力.通过经典的三种网络模型(BA无标度网络、ER随机网络、NW小世界网络)和27种不同类型实际网络的数值仿真分析表明,本文提出的算法对比原来的算法能够明显改善网络的粗粒化效果,并发现互联网、生物、社交、合作等具有明显聚类结构的网络在采用谱粗粒化算法约简后保持同步的能力要优于电力、化学等模糊聚类结构的网络.     

WSN中基于对偶线性规划的异常检测和定位算法

文章提出了一种改进的传感器网络异常检测和定位方法;该方法通过两个阶段的探查来收集端到端测量数据实现异常检测和定位;第一阶段探查的目的是选择可以覆盖最大数量异常链路的探点,缩小可疑区域范围,供第2阶段探查,这一阶段的探点选择问题被建模为预算有限条件下的覆盖范围最大化问题,文章提出一种基于对偶线性规划的高效近似方法进行求解;第2阶段的目的是以最小的通信代价,定位出导致观察到的端到端异常现象的具体链路,并根据多环置信度传播算法(LBP)来预测诊断质量;在不同网络设置下展开实验,实验结果表明,文章算法的漏检率和精确求解方法相当但运行速度更快。     

一种基于最大流的网络结构熵

熵是可用来反映网络结构异质性的指标.针对传统熵指标不能很好反映网络全局异构性的不足,本文引入网络流的概念,综合考虑径向测度和中间测度,提出一种新的网络结构熵.特殊网络(如公用数据集Dolphins网络)的分析结果表明,本文提出的熵指标在一定程度上克服了其他网络熵指标的不足,更能够反映网络的真实拓扑结构;对随机网络、最近邻耦合网络、星型网络、无标度网络、Benchmark网络和小世界网络等典型网络的理论分析和仿真实验,进一步证明本文提出的熵指标在刻画一般复杂网络结构特征上的有效性和适用性.     

Link prediction based on a semi-local similarity index

Missing link prediction provides significant instruction for both analysis of network structure and mining of unknown links in incomplete networks. Recently, many algorithms have been proposed based on various node-similarity measures. Among these measures, the common neighbour index, the resource allocation index, and the local path index, stemming from different source, have been proved to have relatively high accuracy and low computational effort. In this paper, we propose a similarity index by combining the resource allocation index and the local path index. Simulation results on six unweighted networks show that the accuracy of the proposed index is higher than that of the local path one. Based on the same idea of the present index, we develop its corresponding weighted version and test it on several weighted networks. It is found that, except for the USAir network, the weighted variant also performs better than both the weighted resource allocation index and the weighted local path index. Due to the improved accuracy and the still low computational complexity, the indices may be useful for link prediction.     

基于双向长短期记忆网络的太赫兹光谱识别

特征提取是太赫兹光谱识别的关键处理步骤,通常利用降维方法作为特征提取手段。然而,当一些化合物的太赫兹光谱曲线整体差异度较小时,降维方法往往会缺失样本差异的重要特征信息,从而导致分类错误。如果不采用降维方法提取特征,传统机器学习分类算法对维数较高的原始太赫兹光谱数据又不能很好的分类。针对此问题,提出了一种基于双向长短期记忆网络（BLSTM-RNN）自动提取太赫兹光谱特征的识别方法。BLSTM-RNN作为一种特殊的循环神经网络,利用其LSTM单元可以有效解决原始太赫兹光谱数据维数较高使得模型难以训练问题。再结合模型的双向频谱信息利用架构模式,可以增强模型对复杂光谱数据自动提取有效特征信息的能力。采用三类、15种化合物太赫兹透射光谱作为测试对象,首先利用S-G滤波和三次样条插值对Anthraquinone,Benomyl和Carbazole等十五种化合物在0.9～6 THz内的太赫兹透射光谱数据进行归一化处理,然后通过构建一个具有双向长短期记忆的循环神经网络对太赫兹光谱的全频谱信息进行自动特征提取并利用Softmax分类器进行分类。通过试验优化网络结构和各项参数,最终获得了针对复杂太赫兹透射光谱数据的预测模型,并与传统机器学习算法SVM,KNN及神经网络算法MLP,CNN进行对比实验。结果表明,dataset-1和dataset-2分别作为差异度较大和无明显峰值特征的五种化合物太赫兹透射光谱数据集,其平均识别率分别为100%和98.51%,与其他方法相比识别率有所提高;最重要的是,dataset-3作为5种化合物谱线极为相似的太赫兹透射光谱数据集,其平均识别率为96.56%,与其他方法相比识别率提高显著;dataset-4作为dataset-1,dataset-2和dataset-3的透射光谱数据集集合,其平均识别率为98.87%。从而验证了BLSTM-RNN模型能自动提取有效的太赫兹光谱特征,同时又能保证复杂太赫兹光谱的预测精度。在选择模型训练优化算法方面,使用Adam优化算法要好于RMSProp,SGD和AdaGrad,其模型的目标函数损失值收敛速度最快。同时随着模型训练迭代次数增加,相似太赫兹透射光谱数据集的预测准确率也不断提升。可为复杂太赫兹光谱数据库的光谱识别检索提供一种新的识别方法。     

Link prediction in complex networks: A survey

Link prediction in complex networks has attracted increasing attention from both physical and computer science communities. The algorithms can be used to extract missing information, identify spurious interactions, evaluate network evolving mechanisms, and so on. This article summaries recent progress about link prediction algorithms, emphasizing on the contributions from physical perspectives and approaches, such as the random-walk-based methods and the maximum likelihood methods. We also introduce three typical applications: reconstruction of networks, evaluation of network evolving mechanism and classification of partially labeled networks. Finally, we introduce some applications and outline future challenges of link prediction algorithms.     

Link prediction in complex networks via modularity-based belief propagation

Link prediction aims at detecting missing, spurious or evolving links in a network, based on the topological information and/or nodes' attributes of the network. Under the assumption that the likelihood of the existence of a link between two nodes can be captured by nodes' similarity, several methods have been proposed to compute similarity directly or indirectly, with information on node degree. However, correctly predicting links is also crucial in revealing the link formation mechanisms and thus in providing more accurate modeling for networks. We here propose a novel method to predict links by incorporating stochastic-block-model link generating mechanisms with node degree. The proposed method first recovers the underlying block structure of a network by modularity-based belief propagation, and based on the recovered block structural information it models the link likelihood between two nodes to match the degree sequence of the network. Experiments on a set of real-world networks and synthetic networks generated by stochastic block model show that our proposed method is effective in detecting missing, spurious or evolving links of networks that can be well modeled by a stochastic block model. This approach efficiently complements the toolbox for complex network analysis, offering a novel tool to model links in stochastic block model networks that are fundamental in the modeling of real world complex networks.     

Revealing how network structure affects accuracy of link prediction

Link prediction plays an important role in network reconstruction and network evolution. The network structure affects the accuracy of link prediction, which is an interesting problem. In this paper we use common neighbors and the Gini coefficient to reveal the relation between them, which can provide a good reference for the choice of a suitable link prediction algorithm according to the network structure. Moreover, the statistical analysis reveals correlation between the common neighbors index, Gini coefficient index and other indices to describe the network structure, such as Laplacian eigenvalues, clustering coefficient, degree heterogeneity, and assortativity of network. Furthermore, a new method to predict missing links is proposed. The experimental results show that the proposed algorithm yields better prediction accuracy and robustness to the network structure than existing currently used methods for a variety of real-world networks.     

A decentralised topology control to regulate global properties of complex networks

In the last decade much research effort has been devoted to the investigation of the interplay between properties (i.e. synchronization, clustering, resilience to node fault) and topology of complex networks. Many algorithms have been proposed to construct a network topology with a given properties or to optimize them. These algorithms are static, off-line implemented and may require global network knowledge. In this paper we propose a simple decentralized topology control algorithm that by local actions carried out at the node allows to regulate network global properties. Additionally the algorithm is dynamic coping with both node and link faults and can be on-line implemented.     

A novel similarity measure for mining missing links in long-path networks

Network information mining is the study of the network topology, which may answer a large number of application-based questions towards the structural evolution and the function of a real system. The question can be related to how the real system evolves or how individuals interact with each other in social networks. Although the evolution of the real system may seem to be found regularly, capturing patterns on the whole process of evolution is not trivial. Link prediction is one of the most important technologies in network information mining, which can help us understand the evolution mechanism of real-life network. Link prediction aims to uncover missing links or quantify the likelihood of the emergence of nonexistent links from known network structures. Currently, widely existing methods of link prediction almost focus on short-path networks that usually have a myriad of close triangular structures. However, these algorithms on highly sparse or long-path networks have poor performance. Here, we propose a new index that is associated with the principles of structural equivalence and shortest path length (SESPL) to estimate the likelihood of link existence in long-path networks. Through a test of 548 real networks, we find that SESPL is more effective and efficient than other similarity-based predictors in long-path networks. Meanwhile, we also exploit the performance of SESPL predictor and of embedding-based approaches via machine learning techniques. The results show that the performance of SESPL can achieve a gain of 44.09% over GraphWave and 7.93% over Node2vec. Finally, according to the matrix of maximal information coefficient (MIC) between all the similarity-based predictors, SESPL is a new independent feature in the space of traditional similarity features.     

Entropy-based link prediction in weighted networks

Information entropy has been proved to be an effective tool to quantify the structural importance of complex networks.In a previous work [Xu et al. Physica A, 456 294(2016)], we measure the contribution of a path in link prediction with information entropy. In this paper, we further quantify the contribution of a path with both path entropy and path weight,and propose a weighted prediction index based on the contributions of paths, namely weighted path entropy(WPE), to improve the prediction accuracy in weighted networks. Empirical experiments on six weighted real-world networks show that WPE achieves higher prediction accuracy than three other typical weighted indices.     

基于BP神经网络提高伪装目标识别概率的研究

采用静态迈克尔逊干涉仪对待测目标进行光谱识别,在空间干涉长度不变的条件下,应用BP神经网络算法对混合光谱分离过程进行优化,从而达到提高伪装目标识别概率的目的。由干涉仪及线阵CCD记录视场内所有位置上的光谱信息,构成混合光谱数据集合,以已知材料的标准吸收光谱作为隐含层的规则依据,将BP神经网络应用于混合光谱的分离。实验采用不同距离、不同背景组合的混合光谱作为初始数据,以1.5 m×1.5 m钢板做成四种待测目标,由静态迈克尔逊干涉仪得到混合光谱,BP神经网络算法与传统光谱吸收算法对无伪装目标的识别率都在90%以上,对具有伪装效果的待测目标识别概率分别为75.5%和31.7%,所以采用BP神经网络可有效地提高伪装目标的识别概率。