基于传染病模型的LPA特征阀值社团划分方法

社团结构划分对于分析复杂网络的统计特性非常重要.在非均匀社交网络的信息传播中,社团结构划分更是一个广泛关注的研究热点,相关研究往往侧重于研究紧密连接的社团结构对于信息传播所产生的关键影响.传统社团划分方法大多基于点和边的相关特性进行构建,如标签传播算法LPA（Label Propagation Algorithm）通过半监督机器学习方法,基于网络节点标签的智能交换和社团融合过程进行社团划分,但运行效率较低.为提高LPA类算法的运行速度,使其快速收敛,并提高社团划分精度,特别是重叠社团划分精度,针对LPA算法划分中的低运行效率和低融合收敛速度,本文从标签传播的网络连接矩阵本质出发,将该矩阵的最大非零特征值与网络标签信息传播的阀值相结合,提出了新的基于传染病传播模型的社团划分方法（简称ESLPA算法,Epidemic Spreading LPA）.通过经典LFR Benchmark模拟测试网络、随机网络以及真实社交网络数据上的算法验证,结果表明该算法时间复杂度大幅优于经典LPA算法,在重叠社团划分上精确度优于基于LPA模型的经典COPRA算法,特别是在重叠社团较明显时,划分精度接近精度较高GA、N-cut和A-cut算法,明显优于GN、FastGN和CPM等经典算法.     

基于社团结构的链接预测和属性推断联合解决方法

链接预测与属性推断是社交网络数据挖掘的两项重要任务.之前的大部分研究工作将链接预测和属性推断视为不同的问题,分别研究解决方法.然而,根据网络结构的同质性理论,社交网络中的链接与属性之间具有内在关联.本文提出了基于社团结构的链接预测和属性推断联合解决方法（LAIC）,将社团结构作为链接预测与属性推断的关联因子,利用用户属性和社团结构进行链接预测,利用链接信息得到社团属性进而推断用户属性.LAIC不仅同时解决了链接预测和属性推断问题,而且通过迭代使链接预测和属性推断的准确率可以相互提升.两个真实数据集上的实验证明LAIC方法是有效的.     

机会网络中基于有权社团结构图的路由协议研究

基于社团检测的机会网络路由算法大多采用无权重网络拓扑划分社团,仅将节点间的关系抽象为一条简单的无权重的边,忽略了节点关系的强弱程度。本文通过引入权重策略改进了QCA社团更新算法,提出了一种基于有权社团结构的路由算法,该算法解决了社团关系定量化单一的问题,更能真实反映出社团成员之间的关系。算法中,节点间的交互信息转化为权重,根据不同的网络环境选择不同的权重转化方案———归一化权重（normalized weight）和非归一化权重（non-normalized weight）。路由算法在检测到周围网络环境变化时自动切换权重计算方案以适应网络环境的变化。通过在仿真环境和真实数据集上测试和分析,该算法能够将网络中的节点划分出合理的社团结构,并在保证较高的传输成功率的情况下降低网络开销。     

融合面积估算和多目标优化的硬件任务划分算法

针对可重构计算机系统配置次数(划分块数)的最小化问题,提出了一种融合面积估算和多目标优化的硬件任务划分算法。该算法每次划分均进行硬件资源面积的估算,并且通过充分考虑可重构资源的使用、一个数据流图所有划分块执行延迟总和、划分模块间边数等因素构造了新的探测函数prior_assigned(),该函数能够计算每个就绪节点的优先权值,新算法通过该值能动态调整就绪列表任务节点的调度次序。实验结果表明,与现有的层划分、簇划分、增强静态列表、多目标时域划分、簇层次敏感等5种划分算法相比,该算法能获得最少的模块数,并且随着可重构处理单元面积的增大,除层划分算法之外,其执行延迟的均值也是最小的。     

一种考虑执行延迟最小化和资源约束的改进层划分算法

 本文提出了一种改进的层划分算法.该算法充分考虑了划分块的最小执行延迟和尽可能充分利用可重构资源,能够跟踪层划分算法节点分配过程并进行调整,消除了经典层划分算法不能动态更新就绪节点列表选取节点进行划分的缺陷.实验结果表明,与层划分算法相比,所提出的改进层划分算法在模块数、执行延迟和跨模块间的I/O边数等三个方面均获得了改进.与现有的簇划分、增强静态列表、多目标时域划分、簇层次敏感等四种划分算法相比,新算法能获得最少的执行延迟,并且随着可重构处理单元面积的增大,模块数的均值也是最小的.     

基于个人意愿的社会网络团体结构与信息检测方案

个人意愿对于形成网络社团和传播信息有着重要的影响力,因此本文提出一种基于个人意愿的社团结构与信息检测方案.该方案中的社团检测算法初次检测以融入节点属性的模块度,再次检测以兴趣度并能发现重叠社团,最后精细检测以个人意愿,本文社团检测算法（ε_CSDA）较之前的算法更有效的是可以发现重叠社团;同时,该方案建立的信息传播模型在指数模型基础上构建边特征向量（边属性）、节点特征向量（节点属性）和意愿向量（用户意愿、社团意愿和节点意愿）,并以传播概率和传播延迟构建模型基本关系,从而使得该模型实现了基于个人意愿的信息传播.实验结果表明,加入个人意愿的社团检测和信息传播方案,能够保证社团检测的有效性和实用性,能够实现用户间信息传播的主动性和可靠性.     

并行K均值聚类和贪婪算法融合的软硬件划分

提出了一种并行K均值聚类和贪婪算法融合的软硬件划分算法.算法首先将有相似属性的任务节点通过并行K均值聚类算法组成一个大的任务节点,而后使用贪婪算法划分由大的任务节点组成的系统.实验结果表明,这种软硬件划分的方法具有高效率及高面积利用率的特点,尤其对多节点的复杂任务算法的求解时间远小于贪婪算法.     

社会合作网络中社团结构的搜索算法研究

许多实际的网络都具有一个共同性质,即它们都是由各个社团通过公共节点连接而成网络,因此,网络中社团的数目以及每个节点归属于社团的数目对于研究复杂网络都具有重要的意义。通过分析复杂网络的社团结构和寻找网络社团数目的传统算法,针对传统算法所存在的缺陷,提出了一种搜索社团结构的算法。该算法正确的对网络的社团结构进行了划分,且较好的改进了其运行效率。最后指出了进一步的研究方向。     

基于节点影响力的标签传播社区划分算法

针对高效的LPA社区划分算法存在结果不稳定性的问题,提出一种新的基于节点影响力的标签传播社区划分算法(Node Influence based Label Propagation Algorithm for Community Discovery,简称NIB算法),使得保持社区划分高效的同时可以尽可能地降低由于社区划分不合理带来的核心节点影响精度的损失。该算法首先为每个节点分配唯一标签并评估节点的影响力,然后按照影响力大小由高到低的次序迭代更新节点的标签,更新完毕可得到一个稳定的社区划分结果。最后在真实数据集上对NIB算法的稳定性与划分质量进行验证。     

基于多元属性的社团挖掘在意见领袖发现中的应用

意见领袖是网络舆论传播中的关键,在舆情分析中有重要意义.采用无向图建模,将链接两端节点的PageRank值与相似度,作为链接的双重属性,通过二次判别式对链接进行主次划分,将整个网络划分为核心与非核心两类用户,并将网络中的大社团进行细化,结合细化后的社团跟核心用户的划分结果找出其中相应的子社团中的意见领袖,提出了一种基于二元分类的意见领袖发现算法.     

融合节点分析与边分析的复杂网络社区识别算法

针对边社区识别与节点型社区识别两类算法在识别社区过程中均存在相应缺陷,影响复杂网络社区识别质量的问题,提出融合节点分析与边分析的复杂网络社区识别（CDHNE）算法。该算法首先运用边在网络中较为稳定的特点,在算法执行初期通过边社区识别构建较为准确的社区结构;然后利用节点较为灵活的特点,在边社区形成后,对边社区的边缘进行精确识别,更准确地识别出复杂网络中的社区结构。在计算机生成网络实验中,当网络的社区结构逐渐变得模糊、重叠节点数量与重叠节点归属社区数量不断增加时,CDHNE算法的社区识别精度较传统算法平均提高10%,在重叠节点识别精度上较传统算法平均提高15%;在真实网络实验中,算法识别的社区结构紧密度较好,特别是面对拥有十几万个节点的大规模网络时,CDHNE算法高质量地完成了识别任务,EQ值达到0.412 1。实验结果表明,CDHNE算法在运行稳定性和处理大规模网络方面具有优势。     

基于复杂网络的社区划分算法分析

近年来,复杂网咯吸引了大量的学者,作为一个新兴起来的学科,来自各个领域的学者们都开始对其进行研究分析。社区划分是复杂网络的重要特征之一。针对复杂网络中社区划分问题,对三种的社区划分算法进行了研究,传统GN算法、FN算法和谱聚类算法,分别阐述了各种算法的基本原理,并对这两种算法基于真实世界网络模型进行了适当的分析和比较,选取出较为高效的谱聚类算法,用于现实世界复杂网络中的社区划分,为实际应用中社区划分算法的认识与应用提供了方法参考。     

基于微博媒体的社区发现技术研究

微博社交网络是由节点构成的,每个节点代表一个微博用户。节点与节点间存在着关系,因此连接紧密的节点形成了社区。如何从微博社交网络中挖掘出社区,已成为Web2．0的团体挖掘研究热点。详细介绍了传统的网络团体挖掘算法,并提出了一种新的社区发现的算法,称为基于用户兴趣的社区发现算法。该算法不论在计算效率还是社区发现效果上比传统算法都具有明显的提升,取得了不错的实验效果。     

二进制指数退避的Gossip算法研究

为减少Gossip算法进行信息传播的通信开销,该文提出一个将二进制指数退避算法与经典Gossip算法相结合的二进制指数退避的Gossip算法(BEBG),其信息传播策略是一个节点收到同一信息的次数越多,继续传播该信息的概率就越低。理论分析与仿真实验表明,BEBG能够有效减少信息传播冗余,网络中有104个节点时比经典Gossip算法减少了约61%网络负载。为解决BEBG存在的边缘节点问题,进一步提出了两个BEBG改进算法,引入Pull的PBEBG和引入向邻居节点Push的NBEBG。实验结果表明,两个算法能够消除边缘节点,当网络中有104个节点时,它们与相应的分别引入相同Pull和Push的经典Gossip算法相比,分别减少了约34%和37%的网络负载。     

基于社会属性的PSN消息路由算法

在PSN（pocket switched network）中实现数据传输成功率与传输延迟的有效平衡是当前有待解决的问题。提出一种基于社会属性的PSN路由算法——BridgingCom算法,该算法使用带有衰退机制的局部社区识别方法,引入桥接中心度（bridging centrality）作为中继节点的选择依据,将社会网络中节点重要性与移动社会网络的特征相结合,考虑了节点社区关系和节点活跃度对路由算法的影响。实验表明,该算法与现有经典算法相比能够获得较高的传输效率和较低的传输延迟。     

Power and cost aware localized routing with guaranteed delivery in unit graph based ad hoc networks

In a localized routing algorithm, each node currently holding a message makes forwarding decision solely based on the position information about itself, its neighbors and destination. In a unit graph, two nodes can communicate if and only if the distance between them is no more than the transmission radius, which is the same for each node. This paper proposes localized routing algorithms, aimed at minimizing total power for routing a message or maximizing the total number of routing tasks that a network can perform before a partition. The algorithms are combinations of known greedy power and/or cost aware localized routing algorithms and an algorithm that guarantees delivery. A shortcut procedure is introduced in later algorithm to enhance its performance. Another improvement is to restrict the routing to nodes in a dominating set. These improvements require two‐hop knowledge at each node. The efficiency of proposed algorithms is verified experimentally by comparing their power savings, and the number of routing tasks a network can perform before a node loses all its energy, with the corresponding shortest weighted path algorithms and localized algorithms that use fixed transmission power at each node. Significant energy savings are obtained, and feasibility of applying power and cost‐aware localized schemes is demonstrated. Copyright © 2004 John Wiley & Sons, Ltd.     

Overlapping community detection in complex networks based on multi kernel label propagation

In view of the strong randomness and pre-setting the related threshold of traditional overlapping community detection method based on label propagation,overlapping community detection in complex networks based on multi kernel label propagation (OMKLP) was proposed.Evaluation model of kernel nodes was proposed after analyzing the node's degree and local covering density of nodes and their neighbor nodes.And on this basis,the detection method of local kernel nodes was also presented.Based on local kernel nodes,a new asynchronous label propagation strategy ori-ented to overlapping community was proposed,which can rapidly distinguish inner nodes and outer nodes of communi-ties so as to obtain overlapping community structure.The analysis method of overlapping nodes was proposed to increase the accuracy of detecting overlapping nodes.Without any prior knowledge,only on the basis of the basic network infor-mation (nodes and links),the algorithm can detect the structure of overlapping communities accurately.Therefore,it ef-fectively solved the defect of the traditional label propagation algorithm.The algorithm was tested over benchmark net-works and real-world networks and also compared with some classic algorithms.The experiment results verify the valid-ity and feasibility of OMKLP.     

基于图正则化非负矩阵分解的二分网络社区发现算法

现实世界存在大量二分网络,研究其社区结构有助于从新角度认识和理解异质复杂网络。非负矩阵分解模型能够克服二分结构的限制,有效地挖掘二分网络的潜在结构,但也存在着时间复杂度高、收敛慢等问题。该文提出一种基于图正则化的三重非负矩阵分解(NMTF)算法应用于二分网络社区发现,通过图正则化将用户子空间和目标子空间的内部连接关系作为约束项引入到三重非负矩阵分解模型中;同时将NMTF分解为两个最小化近似误差的子问题,并给出了乘性迭代算法以交替更新因子矩阵,从而简化矩阵分解迭代,加快收敛速度。实验和分析证明:对于计算机生成网络和真实网络,该文提出的社区划分方法均表现出较高的准确率和稳定性,能够快速准确地挖掘二分网络的社区结构。