基于MapReduce的SimRank算法在图聚类中的应用

由Jeh和Widom提出的SimRank算法是一种普适"结构相似度"计算模型。由于SimRank算法采用迭代方式计算图节点间相似性,因此时间复杂度和空间复杂度都非常高。随着数据量的激增,单机运算能力不能满足大规模数据的计算要求。本文提出了基于MapReduce计算模型的分布式SimRank算法,利用该算法对RDF图进行相似度度量,然后利用分布式的AP聚类算法对图节点进行聚类分析。实验结果表明,该方法能够高效的完成图节点的相似度度量,实现图的有效聚类。     

一种基于动态角色标识和张量分解的推荐模型

社交网络推荐中,通常未依据用户兴趣变化进行用户角色动态标注,会造成推荐预测误差,并且用户评分数据稀疏造成评分预测不准确.根据以上问题,本文提出一种基于动态角色标识和张量分解的推荐模型.首先,针对用户角色无差别标识问题,引入信息熵指标度量用户兴趣多样性,对目标用户进行角色定量标识.其次,考虑到用户兴趣漂移现象,提出基于时间窗的动态角色标识方式,解决静态角色标识产生的个体评分数据无偏好差异问题,实现用户评分数据层次化处理.最后,为提高评分预测准确率,通过引入张量分解在数据维度转换和数据压缩的特性,构建基于"用户-项目-角色"张量分解的评分预测模型.同时,在张量分解的过程中,通过对数据缺失值处理,提高评分预测精度,生成目标用户推荐列表.实验表明,该方法缓解了用户无角色差异形成的预测误差问题,并能够有效改善评分数据稀疏情况下传统方法推荐精度不足的问题,提高推荐效率.     

基于霍克斯过程的社交网络用户关系强度模型

社交网络节点之间的关系强度建模是研究信息传播、实现推荐服务等社交网络服务的关键.传统关系强度模型主要研究简单二元关系与静态关系,未考虑用户交互影响及其动态衰减.本文提出一种基于霍克斯过程的社交网络用户关系强度模型,将用户关系强度视为潜在因子,用户相似性与历史交互行为分别视为潜在因子诱因与表象,并使用霍克斯过程刻画历史交互行为与用户关系强度之间的关系,解决了已有模型未考虑用户历史交互影响及其动态衰减的问题.采用微博社交网络数据对模型进行的评估表明,本模型可以提高用户关系强度预测精度以及基于关系强度排序Top-N邻居节点的覆盖率.     

一种环境理解的分布式群体仿真任务划分方法

本文通过引入环境结构因素,提出了一种适用于多层次复杂环境的自适应任务划分算法。自动读取场景模型并通过理解转换为连通邻接区域集,然后对区域进行快速粗粒度划分,有效提高划分性能;自然消除了被障碍隔离的相邻区域个体间的感知计算,大大减少了节点间通信量,使之更适合于大规模群体仿真应用。实验结果表明该算法的划分代价和执行性能均较优。文中设计了一种适合该划分算法的分布式仿真模型,基于该模型的分布式系统对室内多层楼宇或室外场景大规模群体仿真均具有较高仿真性能,相同规模群体的仿真性能与仿真节点数成线性关系表明系统具有良好的可扩展性。     

基于图着色的大规模无人机群三维网络资源分配算法

为了解决大规模无人机集群组网中的网络资源有限、有效分配网络资源难度大的问题,本文针对任意对无人机收发节点构成的通信网络,联合考虑时域、频域、空域,提出了一种基于图着色的三维网络资源分配算法。具体的,本文利用方向回溯阵列天线在传统时频二维网络资源划分的基础上开辟空间维度,得到三维网络资源划分问题。为了解决该三维资源分配问题,本文首先将其建模为图着色问题,然后提出了启发式和贪婪式两种复杂度不同、适应场景也不同的图着色算法,并进一步设计了由着色结果到网络资源分配方案的映射算法。仿真结果验证了所提方法的有效性,相较于传统时分多址接入和时频二维资源分配而言,大大提高了吞吐量和传包成功率。      

基于簇的无线传感器网络入侵检测系统

基于无线传感器网络的分簇结构,运用Agent技术设计了一个入侵检测系统.在网络中的每个节点部署IDS代理,其中包括本地检测Agent和全局检测Agent两个不同代理,分别完成不同的检测任务.提出采用蓝牙通信技术,引用蓝牙散射网形成算法TPSF构建传感器网络的簇节点层,完成簇的划分,进而对不同的Agent进行任务分配.通过限制节点的角色对算法进行改进,减轻节点的复杂度,从而使IDS代理能有效地工作,提高节点的安全系数.     

面向大规模网络的快速重叠社团挖掘算法

重叠社团在社交网络大数据中普遍存在.针对现有重叠社团挖掘算法易将重叠区域错误地划分为独立的社团且计算复杂的问题,提出了一种基于局部信息度量的快速重叠社团挖掘算法（Local information based Fast Overlapped Communities Detection,Li-FOCD）.首先,为节点定义局部信息度量指标——社团连接度和邻居连接度,建模节点与社团的关系,缩小了计算范围;然后,每次并行地迭代执行缩减、扩展、去重等操作,并更新局部度量指标,通过松弛每次迭代的终止条件,发现近似最优社团集合而不是最优社团,最终算法复杂度为O（m+n）.基于真实的大规模社交网络数据的试验分析表明：与当前流行的重叠社团挖掘算法相比,Li-FOCD在不损失检测质量的前提下,大幅提升了计算效率.     

P2P网络层次化信任模型

大规模文件共享P2P网络中节点之间发生重复交易的可能性较小而难以建立信任关系,从而导致P2P网络容易受到恶意节点攻击。针对该问题本文提出了基于群组的P2P网络层次化信任模型。该信任模型将信任关系划分为群组之间的信任关系,群组与节点之间的信任关系和节点之间的信任关系3个层次。节点利用本地信任信息或所属群组的推荐信任确定给定节点的信任值。仿真分析表明,该信任模型能够有效识别恶意节点,使P2P网络中合作节点具有较高的成功请求率。     

基于双图混合随机游走的社会化推荐模型

近年来,可以有效缓解数据稀疏和冷启动问题的社会化推荐受到了研究者和业界的关注.社会化推荐利用显式或隐式社交关系作为辅助信息,提升了推荐性能.然而,目前的社会化推荐模型通常采用普通图描述社交关系.普通图中的边常描述为成对节点的关系,这种方法适合描述显式关系,但难以描述复杂的隐式关系,如购买过同一商品的多个用户之间的集合关系,因此难以学习到准确的节点表示,影响推荐的性能.针对此问题,本文结合超图和普通图,提出基于双图混合随机游走的推荐（BG-Rec）模型.构建超图描述复杂的隐式关系,同时用普通图描述显式的社交关系,并在两种图上定义混合随机游走策略,生成结合隐式关系和显式关系的游走节点序列,学习更准确的节点嵌入表示.根据用户评分的高低,构建了正反馈超图和负反馈超图,考虑更细粒度的朋友关系,以识别可靠的朋友.融合可靠朋友的偏好和后验概率最大化优化物品个性化排序.三个公开数据集的大量实验表明了BG-Rec在推荐性能上的优越性,冷启动和消融实验表明了其在缓解冷启动问题的有效性和超图建模的合理性.     

融合抗噪机制的图变分自编码器社交网络推荐方法研究

链路预测是根据复杂网络中已有的拓扑信息预测网络中两个不相邻的节点间产生连接的可能性,是社交网络推荐中使用的主要方法之一。随着社交网络近些年来蓬勃发展,数据量的剧烈增加无可避免地导致坏数据的出现（即目标节点特征属性缺失,或是目标节点特征属性错乱）。为了解决有节点属性社交网络中因为节点特征缺失导致的链路预测准确率降低的问题,提出了一种结合噪声对抗机制的图变分自编码器模型（Denoising Graph Variational Autoencoder,DGVAE）来优化链路预测效果。通过建立一种图变分自编码器结构,并设计一个噪声对抗模块,使得图变分自编码器能够有效地抵抗噪声干扰。经过一系列实验的验证,在有节点属性的网络中,采用噪声对抗的图变分自编码器模型能够有效地预测复杂的网络结构,而且在数据有冗余噪声的情况下,这种模型的预测效果有显著的改善。     

基于随机游走和多样性图排序的个性化服务推荐方法

针对传统服务推荐算法由于数据稀疏性而导致推荐准确性不高,以及推荐结果缺乏多样性等缺陷,提出基于随机游走和多样性图排序的个性化服务推荐方法（PRWDR）.在分析直接相似关系稀疏性的基础上提出带权重的随机游走模型,通过在用户网络上进行随机游走来挖掘更多的相似关系;基于所有相似用户预测服务的QoS值,并给出服务图模型构建方法,以过滤大量性能过低的候选服务;提出最优节点集合选取策略,利用贪婪算法得到兼具推荐准确性和功能多样性的服务推荐列表.在公开发布的数据集上进行实验,并与多个经典算法进行比较,验证了本算法的有效性.     

基于二分网络的用户聚类电影推荐系统构建

针对已经存在的推荐算法中数据的稀疏性问题,提出一种基于聚类算法的二分图信任网络构造算法,通过聚类技术把项目评分相似的用户聚集起来,形成若干个用户群组,在每个群组内部通过二分图建立连接,利用信任机制在群组内部和群组间建立连接,进而构造出推荐系统.实验是在MovieLens数据集上进行的,采用平均绝对误差(MAE)为评测指标,验证了方法的有效性,从而得出该系统使得数据稀疏性对最终推荐结果的负面影响变小.     

一种基于二分图最优匹配的镜头检索方法

镜头检索是基于内容的视频检索的重要内容.本文首次尝试将二分图的最优匹配用于镜头检索.与现有方法相比,本文提出的方法强调在一一对应的前提下,全面客观地度量两个镜头的相似度.把两个镜头的相似度度量建模为一个带权的二分图:镜头中的每一帧看成二分图的一个结点,两个镜头之间任意帧的相似值作为边的权值.在一一对应的前提下,利用最优匹配的Kuhn-Munkres算法求出该二分图的最大权,以此作为两个镜头的相似度.考虑到检索速度问题,提出了两个改进算法.实验对比结果证实了本文所提方法在镜头检索中的优异表现.     

基于用户节点相似度的局部社团挖掘

随着Web2.0的迅速发展,社交网络规模变得越来越庞大,包含的信息量也越来越多。传统的从全局角度出发进行社团挖掘的算法由于较高的复杂度以及获取全网信息的困难度,不适用于大型复杂网络的社团挖掘。文中提出了一种基于节点相似度和局部中心点的社团挖掘算法,实验结果表明,该算法在保证较高准确度的同时具有线性时间复杂度。     

异质网络中基于节点影响力的相似度度量方法

异质网络相似度学习,即分析两个不同类型对象间的相关程度.不同类型对象在异质网络中的重要程度不同,它们在相似度学习过程中的发挥的作用也不同.针对异质网络,提出了一种基于节点影响力的相似度度量方法NISim,该模型既考虑了网络中的链接结构,也保留了网络中的语义信息,同时区分不同类型节点对异质网络的作用.在异质信息网络环境下,通过启发式规则区分并量化不同类型节点的影响力权值,并结合网络链接结构和节点间语义关系,解决了提高相似度学习准确性的问题.实验结果表明,该方法能够有效地对异质信息网络不同类型节点进行相似度度量,可以应用在网络搜索、推荐系统以及知识图谱构建等不同领域.     

A scalable joint routing and scheduling scheme for large-scale wireless sensor networks

The multihop configuration of a large-scale wireless sensor network enables multiple simultaneous transmissions without interference within the network. Existing time division multiple access (TDMA) scheduling schemes exploit gain based on the assumption that the path is optimally determined by a routing protocol. In contrast, our scheme jointly considers routing and scheduling and introduces several new concepts. We model a large-scale wireless sensor network as a tiered graph relative to its distance from the sink, and introduce the notion of relay graph and relay factor to direct the next-hop candidates toward the sink fairly and efficiently. The sink develops a transmission and reception schedule for the sensor nodes based on the tiered graph search for a set of nodes that can simultaneously transmit and receive. The resulting schedule eventually allows data from each sensor node to be delivered to the sink. We analyze our scheduling algorithm both numerically and by simulation, and we discuss the impact of protocol parameters. Further, we prove that our scheme is scalable to the number of nodes, from the perspectives of mean channel capacity and maximum number of concurrent transmission nodes. Compared with the existing TDMA scheduling schemes, our scheme shows better performance in network throughput, path length, end-to-end delay, and fairness index.     

基于概率图模型的音乐推荐方法

提出了一种基于概率图模型的音乐推荐方法。该方法利用歌曲相似度确定歌曲间的关系,从而建立歌曲网络,在此基础上利用主题模型得到的歌曲主题概率分布,建立包含局部属性（主题概率分布）和全局结构（歌曲网络）的概率图模型,转化为因子图后,再利用推理算法对概率图模型进行计算,最终获得歌曲在不同主题下的推荐列表。实验表明,本方法能够获得较好的推荐效果,是对音乐推荐方法的有益探索。     

Mining user preferences of new locations on location-based social networks: a multidimensional cloud model approach

In recent years, the prevalent of location-based social networks contributes massive data for location recommendation. Although collaborative filtering (CF) algorithm has been widely employed for location recommendation, it suffers the data sparsity and the high time complexity as it estimates the similarity of users by the common locations. In this paper, we extend the two-dimensional cloud model to the multidimensional cloud model and utilize it to the measure the similarity of user preferences and user behaviors. This method not only considers the multiple attributes of users (e.g., the diversity of user preferences), but also alleviates the sparsity of location recommendation based on CF algorithm to some extent. Then we integrate the similarity of user preferences, social ties and user behaviors into CF algorithm, which is expected to mine user preferences of new locations (MUPNL) more precisely. Furthermore, in order to improve the efficiency of the MUPNL algorithm, we parallelize it with Mapreduce framework. Experimental results on Yelp academic dataset demonstrate the good performance of the distributed MUPNL algorithm in accuracy and efficiency.     

Perfect match model‐based link assignment to design topology for satellite constellation system

In satellite constellation network, the satellites visible from one satellite are more than communication terminals (CTs) equipped. Each inter‐satellite link (ISL) would occupy one CT on each of two satellites connected by this ISL. Therefore, a fundamental problem considering link assignment is how to assign limited CTs for each satellite to establish ISLs with its visible satellites. Link assignment scheme based on perfect match model (LAS‐PMM) is proposed to make full use of huge bandwidth provided by CT. In LAS‐PMM, the problem of assigning all the CTs of each satellite to establish ISLs is modeled as a perfect matching problem, where a perfect matching is searched over a mixed complete bipartite graph. Simulation results show that LAS‐PMM is better than the regular and greedy LASs, in terms of CT utilization and average node‐to‐node distance. Copyright © 2015 John Wiley & Sons, Ltd.     

Mapping a class of neural networks on k-ary n-cubes

In this paper we propose a scheme for mapping two important artificial neural network (ANN) models on the popular k-ary n-cube parallel architectures (KNCs). The scheme is based on generalizing the mapping of a bipartite graph onto the KNC architecture and thus can be adapted to any model whose computations can be represented by a bipartite task graph. Our approach is the first to adjust the granularity of parallelism so as to achieve the best possible performance based on properties of the computational model and the target architecture. We first introduce a methodology for optimal implementation of multi-layer feedforward artificial neural networks (FFANNs) trained with the backpropagation algorithm on KNCs. We prove that our mapping methodology is time-optimal and that it provides for maximum processor utilization regardless of the structure of the FFANN. We show that the same methodology can be utilized for efficient mapping of Radial Basis Function neural networks (RBFs) on KNCs. This revised version was published online in June 2006 with corrections to the Cover Date.