网络社区发现优化：基于随机游走的边权预处理方法

在网络日趋复杂化、巨大化的背景下,仅依靠网络拓扑特征难以提高现有社区发现算法的精确度和性能。该文提出一种优化网络社区发现的边权预处理方法,基于马尔可夫随机游走理论建模社区结构对复杂网络行为的影响,根据多重随机游走对网络连接的遍历情况,重新衡量网络边权。预处理后的边权作为网络拓扑的有效补充信息,能够将网络社区结构去模糊化,从而改善现有算法的社区发现性能。对于一些典型的计算机生成网络和真实网络,经实验验证：该预处理方法能够有效提升现有部分社区发现算法的准确性和效率。     

随机游走技术在网络生物学中的研究进展

网络生物学是近年来受到国际学术界广泛关注的学术前沿领域,在疾病研究和药物预测等领域有重要应用.随机游走（Random Walk）又称随机游动或随机漫步,是一种数学统计模型,在金融、物理和社会网络分析中都有广泛应用.近年来逐渐被应用到网络生物学,并在技术上得到了新的发展.本文以生物网络为基础,介绍了随机游走技术及其基本理论,并详细阐述了随机游走技术在网络生物学中的应用,具体包括蛋白质功能预测、关键蛋白质识别、疾病基因预测、疾病相关非编码RNA预测、药物相关预测等.最后讨论了随机游走技术在网络生物学研究中存在的问题以及未来的研究方向.     

基于加权内容-结构网络和随机游走的社团划分算法

针对传统模块优化社团划分算法仅能利用网络的结构信息,而无法利用同样丰富的内容信息,导致划分精度较低的问题,提出一种结合内容属性并通过给连边加权来全面优化网络拓扑结构的社团划分算法CCSRW（Classification with Content-Structure and Random Walk）.设计利用随机游走理论计算结构节点与内容节点间的相似性关系矩阵,并将结构节点映射到内容属性空间上,最终把社团划分问题转化为多维无监督聚类问题.通过在真实数据集上进行的全面实验分析,展示了相比于传统社团划分算法,本文的算法能更准确的描述网络结构,显著提高划分性能,并有效解决小社团不敏感问题,更适用于大规模复杂信息网络的社团划分.     

基于随机游走和增量相关节点的动态网络社团挖掘算法

动态网络社团结构挖掘有助于获取整体网络特性和发展规律。由于动态网络具有多个时刻,传统静态网络社团挖掘算法不仅容易在相邻时刻产生具有较大差异的社团划分结果,而且导致较高时间复杂度。虽然最近受到广泛关注的动态网络增量算法可以一定程度上降低算法时间复杂度,但普遍存在人工设定参数、可扩展性差等局限性。该文提出一种随机游走与增量相关节点相结合的社团挖掘算法(RWIV)进行动态网络社团挖掘。利用动态网络时间局部性即相邻采样时刻网络变化不大的特点,通过对增量相关节点进行随机游走聚类后社团划分,避免了对整个网络中的节点全部重新划分。实验结果和分析表明：RWIV算法可有效解决IC(Incremental algorithm for Community identification)和IDCM(Increment and Density based Community detection Method)判定参数难以选定、累积误差及网络突变等问题,其社团挖掘效率高于现有IC和IDCM算法。     

基于高阶相似性的属性网络表示学习

现有的网络表示学习方法缺少对网络中隐含的深层次信息进行挖掘和利用。对网络中的潜在信息做进一步挖掘,提出了潜在的模式结构相似性,定义了网络结构间的相似度分数,用以衡量各个结构之间的相似性,使节点可以跨越不相干的顶点,获取全局结构上的高阶相似性。利用深度学习,融合多个信息源共同参与训练,弥补随机游走带来的不足,使得多个信息源信息之间紧密结合、互相补充,以达到最优的效果。实验选取Lap、DeepWalk、TADW、SDNE、CANE作为对比方法,将3个真实世界网络作为数据集来验证模型的有效性,进行节点分类和链路重构的实验。在节点分类中针对不同数据集和训练比例,性能平均提升1.7个百分点;链路重构实验中,仅需一半维度便实现了更好的性能,最后讨论了不同网络深度下模型的性能提升,通过增加模型的深度,节点分类的平均性能增加了1.1个百分点。     

基于随机游走模型的查询日志中命名实体挖掘

提出了一种弱指导的方法从搜索引擎查询日志中挖掘命名实体。该方法中采用人工选择的少量命名实体名称作为种子,使用随机游走模型从查询日志中获得大量的命名实体。其中采用了查询日志中的实体上下文模板,用户点击URL和候选命名实体构建三分图,根据在该图上的随机游走计算候选命名实体属于指定目标实体类别的概率,从而在查询日志中获取该类别的命名实体。在真实的查询日志上对7个实体类别进行的实验,实验结果显示本文方法在各个类别上均获得较好的命名实体挖掘效果。     

物联网中基于相似性计算的传感器搜索

物联网逐渐成为学术界研究的热点领域,无处不在的传感器设备促进了传感器搜索服务的产生。物联网中搜索的强时空性、海量数据的异构性与传感器节点的资源受限性,给物联网搜索引擎高效地查询传感器提出了挑战。该文提出基于传感器定量数值的线性分段拟合相似性(PLSS)搜索算法。PLSS算法通过分段和线性拟合的方法,构建传感器定量数值的相似性计算模型,从而计算传感器的相似度,根据相似度查找最相似的传感器集群。与模糊集(FUZZY)算法和最小二乘法相比,PLSS算法平均查询精度和查询效率较高。与原数据相比,PLSS算法的存储开销至少降低了两个数量级。     

有偏随机游走改进吸收中心性识别关键节点

针对无向网络吸收中心性算法中未考虑信息传递的有偏问题,提出一种基于节点的度信息有偏随机游走,改进吸收中心性识别关键节点的算法.首先在无向网络中利用节点的度信息,构建信息传递的转移概率矩阵并定义吸收节点,通过到达吸收节点的平均首次可达时间,衡量节点的重要性;将该算法向有向网络进行扩展研究,结合有向网络节点的出度、入度信息...     

支持属性撤销的可验证多关键词搜索加密方案

近年来,可搜索加密技术及细粒度访问控制的属性加密在云存储环境下得到广泛应用。考虑到现存的基于属性的可搜索加密方案存在仅支持单关键词搜索而不支持属性撤销的问题,以及单关键词搜索可能造成返回搜索结果部分错误并导致计算和宽带资源浪费的缺陷,该文提出一种支持属性撤销的可验证多关键词搜索加密方案。该方案允许用户检测云服务器搜索结果的正确性,同时在细粒度访问控制结构中支持用户属性的撤销,且在属性撤销过程中不需要更新密钥和重加密密文。该文在随机预言机模型下基于判定性线性假设被证明具有抵抗选择关键词集攻击安全性及关键词隐私性,同时从理论和实验两方面分析验证了该方案具有较高的计算效率与存储效率。

     

Geographic Data Propagation in Location-Unaware Wireless Sensor Networks: A Two-Dimensional Random Walk Analysis

For wireless sensor networks with many locationunaware nodes, which can be modeled as a planar Poisson point process, we investigate a protocol, dubbed BeSpoken, which steers data transmissions along a straight path called a spoke. BeSpoken implements a simple, spatially recursive process, where a basic set of control packets and a data packet are exchanged repeatedly among daisy-chained relays that constitute the spoke. Hence, a data packet originated by the first relay makes a forward progress in the direction of the spoke. Despite the simplicity of the protocol engine, modeling the spoke process is a significant challenge. Bespoken directs data transmissions by randomly selecting relays to retransmit data packets from crescent-shaped areas along the spoke axis. The resulting random walk of the spoke hop sequence may be modeled as a two dimensional Markov process. Based on this model, we propose design rules for protocol parameters that minimize energy consumption while ensuring that spokes propagate far enough and have a limited wobble with respect to the spoke axis. The energy efficiency is demonstrated through simulations of the BeSpoken-based data search, and a comparison with the energy consumption of a search based on directed diffusion.     

移动感知器网络中基于随机游走和协作关系的任务分发算法

关于移动感知器网络中感知任务的分发问题,目前学术界已经有了诸多相关研究.然而,这些研究很少涉及到多个智能体协作完成复杂感知任务问题.针对这种情况,首先,通过分析移动感知器网络的结构特征、智能体相互之间、以及智能体和感知任务之间的关系,本文提出了智能体之间协作关系强度和智能体对感知任务适应度两个概念,并讨论了二者对于移动感知器网络中感知任务动态分发的作用.其次,在上述概念的基础上,将二者融合为偏好因子,提出了基于随机游走和协作关系的任务分发算法（TDCR,Task Distribution With Cooperative Relationship）,通过该算法达到提高任务分发效率的目的.最后,将TDCR与Personal Rank算法（PR）、HITS算法对比分析,表明所提出的算法TDCR在任务分发效率和准确度等性能指标上有较好的提升.     

中继蜂窝网络中增强型随机接入算法

提出一种适用于蜂窝中继网络的增强型随机接入算法。为了保证不同用户的QoS需求,实时业务通过提前预约随机接入信道(Random Access Channel,RACH)实现无冲突的接入,而非实时业务则利用中继节点通过共享剩余的随机接入信道实现两跳接入。为了解决非实时业务在时域接入发生碰撞的问题,中继节点根据当前的非实时业务到达状况和剩余的RACH信道数目,综合地确定所采取的退避策略以及最佳频域退避窗口大小。理论分析和实验仿真表明,该算法能更好地保证非实时业务的接入过程,进一步提高了接入资源的利用率。     

Estimation of the Average Search Length of Random Walks in Power-Law Networks

In this paper we introduce a model to study random walks in power-law networks with one-hop replication. Basically, this model gives a set of expressions that captures how the knowledge about the network evolves as the random walk traverses the network: how many nodes have been known, either because they or their neighbors have been visited by the random walk. With this, we obtain an expression that gives a good estimation of the average number of hops needed to find some random peer from any other random peer. We denote this metric the average search length, and we deem it can be very useful to evaluate random walk based resource location solutions in P2P networks.     

Channel Assinment Using Tabu Search in Wireless Mesh Networks

Wireless Personal Communications - Wireless networks pave a way for faster and quicker transmission. The most important terminology in mesh networking is assigning proper channel for faster...     

Design and Performance of Wireless Data Gathering Networks Based on Unicast Random Walk Routing

Wireless environment monitoring applications with significantly relaxed quality-of-service constraints are emerging. Hence, the possibility to use rough low knowledge routing in sensor networks to reduce hardware resource and software complexity is questionable. Moreover, low knowledge handling allows better genericity, which is of interest, for instance, for basic operation enabling system set-up. In this framework, this paper revisits stateless unicast random walk routing in wireless sensor networks. Based on random walk theory, original closed-form expressions of the delay, the power consumption and related spatial behaviors are provided according to the scale of the system. Basic properties of such a random routing are discussed. Exploiting its properties, data gathering schemes that fulfill the requirements of the application with rather good energy efficiency are then identified.      

Parameter Estimation Using Microprocessors and Adaptive Random Search Optimization

An optimization procedure is presented which can be used for off-line system parameter estimation. The technique utilizes a model reference adaptive control configuration and an adaptive random search to identify the parameter values for an arc voltage control system of an automatic welding process. An 8-bit microprocessor is used to acquire data from the system, and a microprocessor development system performs the optimization routine.     

一种基于随机游动的聚类算法

该文提出一种改进的随机游动模型,并在此模型的基础上,发展了一种数据聚类算法。在此算法中,数据集中的样本点根据改进的随机游动模型,生成有权无向图G(V,E,d),其中每个样本点对应图G的一个顶点,并且假设每个顶点为可以在空间中移动的Agent。随后计算每个顶点向其邻集中顶点转移的概率,在随机选定邻集中的一个顶点作为转移方向后,移动一个单位距离。在所有样本点不断随机游动的过程中,同类的样本点就会逐渐的聚集到一起,而不同类的样本点相互远离,最后使得聚类自动形成。实验结果表明,基于随机游动的聚类算法能使样本点合理有效地被聚类,同时,与其他算法对比也说明了此算法的有效性。