大数据下基于异步累积更新的高效P-Rank计算方法

P-Rank是SimRank的扩展形式,也是一种相似度度量方法,被用来计算网络中任意两个结点的相似性.不同于SimRank只考虑结点的入度信息,P-Rank还加入了结点的出度信息,从而更加客观准确地评价结点间的相似程度.随着大数据时代的到来,P-Rank需要处理的数据日益增大.使用MapReduce等分布式模型实现大规模P-Rank迭代计算的方法,本质上是一种同步迭代方法,不可避免地具有同步迭代方法的缺点:迭代时间(尤其是迭代过程中处理器等待的时间)长,计算速度慢,因此效率低下.为了解决这一问题,采用了一种迭代计算方法——异步累积更新算法.这个算法实现了异步计算,减少了计算过程处理器结点的等待时间,提高了计算速度,节省了时间开销.从异步的角度实现了P-Rank算法,将异步累积更新算法应用在了P-Rank上,并进行了对比实验.实验结果表明该算法有效地提高了计算收敛速度.     

基于链接关系的Web页面相似度搜索

Web页面相似度搜索对于网络新闻推荐、近似查询等研究领域具有重要作用。SimRank是经典的相似度计算模型,但其预计算时间和空间开销非常巨大,不适用大规模Web页面网络。利用SimRank快速收敛的特点,在SimRank基础上提出高效Web页面相似度搜索方法(WSR),预计算1步迭代相似度矩阵,根据预计算的1步迭代相似度矩阵在线计算给定查询页面和其他页面的2步迭代相似度。通过对Web网络进行静态剪枝,进一步提高预计算和在线查询处理的效率。实验结果显示,WSR显著降低了存储开销和预计算时间开销,且具有较高精确度和快速查询响应时间。     

Ad Hoc网络的离散时间马氏链建模及分析

Ad Hoc网络是一种非常有前途的自组无线网，该文通过对Ad Hoc网络作出一些合理假设，建立了Ad Hoc网络的离散时间马氏链模型，给出了模型的平稳分布，并进一步分析了节点相邻的概率、节点的平均邻居数、平均泛洪距离等网络重要参数。最后，给出了转移概率矩阵的一个具体定义方法，并得到了相应结果。     

一种具有等级结构的无标度网络模型

无标度网络的发现,使人类对于复杂网络的认识进入了一个新的天地.为了更好地描述真实网络的主要拓扑特性,主要研究复杂网络的演化机制,提出了一种通过边的迭代方式生成一种等级网络模型的方法.在此模型的基础上对网络的统计特性进行了理论推导,并通过计算机编程仿真了它的统计特性.理论计算和数值仿真结果可知,迭代生成的网络具有等级结构,度分布服从幂律分布,幂指数在2到3之间可调,平均路径长度以网络规模呈对数形式增长和较大的聚类系数.从而有效地论证了具有等级结构的网络模型很好地符合实际网络,说明实际网络的无标度和高聚类是等级网络自组织的结果.     

并行计算水下大尺度弹性壳体的低频声散射

有限元与边界元耦合模型是研究水下弹性壳体目标低频声散射常用的数值方法。应用该模型计算大尺度弹性目标的声散射时需要大量的计算时间与存储空间,采用并行数值的方式可以解决这一问题。首先并行计算生成有限元矩阵和边界元矩阵,然后应用并行化的广义极小残差(GMRES)迭代算法求解大型非对称线性方程组。详细叙述了并行GMRES(m)迭代算法的执行过程,并以球壳的声散射计算为例分析了迭代步数对算法收敛情况的影响。最后计算了Benchmark目标模型的低频散射声场,分析了其收发分置散射目标强度以及表面声场的分布。     

Markov调制服务时间的单服务台排队近似分析

研究一种具有马尔科夫调制服务时间的单服务台排队系统。顾客到达服从参数为λ的泊松过程,服务时间为连续时间马尔科夫链调制,若马尔科夫链处于状态i（i=1,2,...N）,则服务时间服从参数为μi的负指数分布。为优化排队系统采用仿真无线通信中信道衰减导致的信道速率变化问题非常有意义。区别于以往的数值计算方法（如矩阵几何分析）,提出了一种离散时间马尔科夫链模型来分析服务台状态的变化过程,导出一组闭合公式来计算排队系统的各性能指标。此外,还开发出一种递推过程来计算队列长度的任意阶矩。数值计算结果显示出近似分析具有良好的精确性。     

自愿计算中重叠网络拓扑对面向结点能力的非集中式调度方法的影响分析

自愿计算在大规模计算模式中正在扮演着越来越重要的角色．目前的自愿计算环境大多是专用和集中控制的,因而存在着某些可用性和可扩展性的问题．最新的研究提出了基于对端重叠网络的自愿计算环境构造方式,通过在各参与结点间建立更灵活的连接形成对端重叠网络来实现计算资源更灵活、有效的共享．面向结点能力的调度方法是为适应这一变化而提出的自愿计算中的一种非集中式资源调度方法,具有简单易行的特点．这一方法的效果在很大程度上取决于底层的重叠网络拓扑结构．文中建立了相应的理论分析模型,计算了该调度方法在具有不同度均值和聚合系数的对端重叠网络中搜索步长和最终所定位结点能力水平的期望．模型计算通过迭代进行,将时间复杂度控制在O（n^3）．利用3种不同的拓扑生成算法所产生的不同特征的重叠拓扑结构进行了仿真验证．模型的理论计算结果与仿真结果吻合良好,表明在具有较小的聚合系数和较大结点度均值的重叠网络中,面向结点能力的资源调度方法具有更好的效果．     

基于复杂网络描述的图像深度卷积分类方法

为了在不增加较多计算量的前提下,提高卷积网络模型用于图像分类的正确率,提出了一种基于复杂网络模型描述的图像深度卷积分类方法。首先,对图像进行复杂网络描述,得到不同阈值下的复杂网络模型度矩阵;然后,在图像度矩阵描述的基础上,通过深度卷积网络得到特征向量;最后,根据得到的特征向量进行K近邻（KNN）分类。在ILSVRC2014数据库上进行了验证实验,实验结果表明,所提出的模型具有较高的正确率和较少的迭代次数。     

2维不相关鉴别矢量集算法

在人脸识别算法中,已有的计算不相关鉴别矢量集的算法均是基于图像向量模型的,因而将遇到所谓的小样本问题,而且由于采用迭代求解方式,算法运算速度缓慢,为此提出了一种新的求取不相关鉴别矢量集的算法,即一种基于图像矩阵模型的2维不相关鉴别矢量集算法。算法由于采用了图像矩阵模型,解决了小样本问题,通过对类内散布矩阵的白化变换,使得推广的2维线性鉴别分析模型具有类似的2维主成分分析模型的形式,从而将两种算法的模型有效地联系起来,进而可以非迭代地求得2维不相关鉴别矢量集,不但求解速度快且数值解稳定。在ORL和Yale人脸库上的实验结果表明,该算法不但减少了计算时间,同时也提高了识别率,为求解不相关鉴别矢量集提供了一个新的思路。     

控制流图上支配关系计算方法的分析与实现

支配关系在数据流分析和静态单赋值等程序分析和优化中应用很广泛.采用位向量表示支配结点集合,描述了采用迭代法计算控制流图上支配结点集合的算法,在支配结点集合的基础上讨论了对直接支配结点、支配边界结点的计算方法,并在NPB和SPEC2000测试集上进行了测试.测试结果表明:控制流图的构建占用了过程内支配关系计算的几乎一半时间;对于不包含goto语句的结构化程序,迭代算法一般只需迭代2次.     

一种基于边数随机增长的BA网络模型

针对基本BA网络模型模拟现实网络的局限性, 采用新节点的度数增加服从泊松分布的随机函数来代替传统BA模型中的常数, 修改了节点度数的增长方式, 提出了一种基于边数随机增长的改进网络模型。从理论分析和实验验证两方面对该模型进行了分析和研究。理论证明过程中, 利用率方程法计算度分布并得到了解析解, 而计算机仿真则验证了度分布解析解的正确性。仿真结果表明改进后的网络模型符合现实网络的一定特性。     

基于节点吸引力的复杂网络演化模型研究

针对BA模型及其推广模型预测节点连接度过大的问题,提出一种基于节点吸引力的复杂网络演化模型。该模型包括吸引因子模型、BA模型的度分布、群集系数以及平均路径长度。采用程序仿真方法模拟吸引因子模型和BA模型,并在同等网络规模下对这2种模型进行比较。实验结果表明,在吸引因子影响下,节点的度分布呈幂律指数形式,近似于BA模型,其群集系数小于BA模型,但平均路径长度大于BA模型。     

社交网络中考虑节点度的演化博弈

在谣言传播过程中,针对度不同的节点具有的辨识能力不同,结合节点度定义一种新的博弈收益,借助博弈论建立一种动态复杂网络演化模型。该模型考虑到谣言传播往往与节点利益相关这一特点,通过引入辨识能力描述不同节点的非一致传播率,研究谣言在该模型上的传播动力学行为,并提出两种谣言抑制策略。随后,利用两种典型网络模型进行仿真实验,并在Facebook真实网络数据中对仿真结果进行验证。研究表明,谣言模糊程度对BA（Barabási-Albert）无标度网络和Facebook网络中谣言传播速率及达到稳定状态所需时间影响较小,随着谣言模糊程度增大,谣言在网络中传播范围变大,相对于WS（Watts-Strogtz）小世界网络,谣言更容易在BA无标度网络和Facebook网络中传播;研究还发现,免疫收益增加值相同时,与BA无标度网络和Facebook网络相比,WS小世界网络中免疫节点的增长幅度更大;此外,通过节点危害程度进行抑制比通过博弈收益进行抑制具有更好的谣言抑制效果。     

网络结点度相关性测度及其稳定性分析

判别网络同配/异配性的Newman相关系数r(g)和网络无标度程度的S(g)是研究网络结点度相关性的两个重要测度,其相关论文被科研人员广泛地引用,两个测度分别被应用到实际网络的同配/异配性和无标度程度的分析.为检验两个测度的稳定性,以BA模型为例,通过大量的计算机模拟和数值统计分析,结果显示:BA-3模型的r(g)与网络规模N的经验公式:r(g)∝-N-0.32,并指出r(g)和S(g)关于网络规模N、网络稠密度ρ都具有波动性.因此,用它们来分析不同规模或不同稠密度的有限的、增长的实际网络,其研究会产生一些误导性结果.     

网络负能量传播动力模型及仿真

针对现有研究没有考虑将网络负能量传播的影响因素细化并构建传播动力学模型进行分析的问题，提出网络负能量传播的弱免疫-强免疫-弱感染-强感染-恶意感染（WSRIE）模型。首先，考虑网络用户对网络负能量免疫能力、传播能力的差异性，将易感染状态划分为弱免疫状态和强免疫状态，将感染状态划分为弱感染状态、强感染状态以及规模保持不变的恶意传播状态；其次，根据网络负能量的感染机制，提出状态转移规律；最后，构建了面向复杂网络的网络负能量传播动力学模型。在NW小世界网络和BA无标度网络上进行仿真对比实验。仿真结果表明，在同样参数的情况下，NW网络的弱免疫节点密度比BA网络低9个百分点，说明具备小世界特征的网络更易受负能量的影响；BA网络中恶意节点度为200时的感染节点密度比其节点度为0时高5个百分点，说明网红意见领袖的节点度越大，受网络负能量影响的网络用户更多。     

Scale-free topology evolution for wireless sensor networks with reconstruction mechanism

How to improve survivability of wireless sensor networks (WSNs) is an important issue which has attracted much attention over recent years. In this paper, by resorting to complex network theories, we propose two models, namely, a linear growth evolution model (LGEM) and an accelerated growth evolution model (AGEM). In the model evolution processes, the following factors: node addition, node deletion, and link reconstruction that naturally arise from practical WSNs applications are considered. In addition, accelerated growth is introduced into the evolving processes of AGEM. Theoretical analysis shows that AGEM is an extension of the LGEM model, and AGEM is generally more flexible and accommodating in practice. Simulation results show that the degree distributions of two models have scale-free characteristics and the topologies generated by the two models show a good survivability under random and deliberate attacks.     

无线传感器网络能量均衡拓扑模型研究

针对BA模型仅考虑节点寿命对网络拓扑结构影响的现状,考虑到拓扑能量利用率不高会缩短网络生命周期,在分析网络平均剩余能量和通信半径对网络生命周期影响的基础上,提出一种无线传感器网络能量均衡拓扑模型.该模型在拓扑演化过程中,综合考虑节点剩余能量、通信半径和节点度,并引入剩余能量调节参数、通信半径调节参数和节点度调节参数,最终使剩余能量大的节点连接概率更高.理论分析和仿真实验结果表明,该模型不仅具有无标度网络的幂律特性,具有较好的稳定性,且能够均衡节点和网络能耗,延长网络的生命周期.     

非广延熵:一种新的Internet拓扑度量

随着Internet规模的不断扩大,Internet拓扑模型已成为网络领域的研究热点。从最初的Waxman随机模型到基于幂律[1]特征提出的BA模型、GLP模型、PFP模型,都试图去发现和解析Internet拓扑演化的规律。节点度、聚簇系数、介数等拓扑度量分别被提出,用于刻画拓扑特征。引入统计物理学上非广延熵[2]作为一个新的拓扑度量,从概率分布的均匀程度上刻画拓扑模型的节点度分布的特征。为了定量地分析非广延熵在不同模型上的差异,通过从CAIDA获得最新的真实拓扑数据,比较BA模型和Waxman模型与真实拓扑数据在非广延熵上是否具有一致性,来验证非广延熵作为拓扑度量的合理性。最后指出BA模型的非广延熵接近真实的Internet拓扑,从而也说明非广延熵作为一种新的拓扑度量的可行性。     

基于改进PageRank的BA演化模型

针对原始BA模型择优连接概率决定因素的缺陷,即只从节点的度来衡量节点的重要性,提出了使用改进的节点的PageRank值来替代节点的度来衡量节点重要性的方法,建立了采用改进的节点PageRank值作为择优连接概率决定因素的扩展的BA演化模型.该演化模型的度分布呈现幂律分布,与原始的BA模型进行比较得出更优的统计特性,仿真实验结果表明了此模型的正确性与可行性.     

考虑节点亲密度的社交网络谣言传播研究

考虑到真实社交网络中节点间亲密程度对谣言传播的影响,提出一种新的SI2R传播模型,建立谣言传播动力学方程组,研究谣言在无标度网络上的传播特性。该模型中不同节点间谣言传播率的非一致性同时取决于节点度与节点间亲密度,理论分析得到了无标度网络上谣言传播阈值表达式。随后,在BA（Barabási-Albert）无标度网络中就节点亲密度对谣言传播过程的影响进行了仿真实验,并利用Twitter和Live Journal两种真实网络数据集对仿真结果进行验证。研究表明,无标度网络中节点间平均亲密度随网络聚类系数的增大而减小,随着网络中节点间平均亲密度增大,谣言传播最终范围变大。研究还发现,节点间亲密度的存在使无标度网络中存在传播阈值,传播阈值随着节点间平均亲密度增大而减小。