基于几何邻居的半监督节点分类

目前基于网络结构的节点分类方法只注重局部网络连接关系。为了能获取更广泛的网络信息,提出一种基于邻居节点结构信息的半监督节点分类算法CBGN。首先,在网络中加入惩罚因子来改进随机游走策略以获取节点的不定长游走序列,这些节点序列被当做句子输入到word2vec模型中,从而将网络结构的潜在信息转换成向量作为节点的特征表示;其次,改进支持向量机算法,结合梯度下降法和坐标下降法来优化参数空间,以对未标记节点进行更准确的分类;最后,在四个标准数据集上与目前较先进的几种方法进行了对比实验。结果表明,CBGN算法提高了分类精度,相比之前已有的方法具有更好的分类效果。     

基于节点-属性二部图的网络表示学习模型

在图结构数据上开展推理计算是一项重大的任务,该任务的主要挑战是如何表示图结构知识使机器可以快速理解并利用图数据。对比现有表示学习模型发现,基于随机游走方法的表示学习模型容易忽略属性对节点关联关系的特殊作用,因此提出一种基于节点邻接关系与属性关联关系的混合随机游走方法。首先通过邻接节点间的共同属性分布计算属性权重,并获取节点到每个属性的采样概率;然后分别从邻接节点与含有共有属性的非邻接节点中提取网络信息;最后构建基于节点-属性二部图的网络表示学习模型,并通过上述采样序列学习得到节点向量表达。在Flickr、BlogCatalog、Cora公开数据集上,用所提模型得到的节点向量表达进行节点分类的Micro-F1平均准确率为89.38%,比GraphRNA（Graph Recurrent Networks with Attributed random walks）高出了2.02个百分点,比经典工作DeepWalk高出了21.12个百分点;同时,对比不同随机游走方法发现,提高对节点关联有促进作用的属性的采样概率可以增加采样序列所含信息。     

基于随机游走的网络故障节点定位算法仿真

网络规模逐渐增大,路由节点呈现出了较大的随机性分布,节点的位置关联性被打破,很难建立准确的定位模型,造成传统的基于特征匹配的节点故障定位方法很难描述较大的随机性变化特性,造成故障定位的不准确.为了解决上述问题,提出一种随机游走的网络故障节点检测算法,通过把检测到的故障特征作为随机游走的初值种子点和节点故障配准的特征点,将故障特征配准和位置随机变化检测结合起来,提高了变化检测的效率.改进方法采用了一种最小化特征权值策略来提取故障特征的不透明度,能检测到大范围的节点异常变化,包括一些细微的变化.仿真结果表明,改进方法能够提高故障节点定位的准确性.     

基于节点和信息特征的社会网络信息传播模型

随着在线社会网络的快速发展,越来越多的人开始利用微博或Twitter来传播信息或分享观点.研究社会网络中的信息传播规律对于意见领袖挖掘、舆情监控、品牌营销等有着重要意义.虽然有关社会网络中的信息传播模型已经得到广泛研究,但是影响网络中节点之间信息传播的因素有哪些,以及如何刻画信息传播过程,仍然是一个有待深入研究的重要内容.传统的传播模型及其扩展模型更多地从网络结构出发研究信息传播,很大程度上忽视了节点属性和信息内容的影响.从多个维度提取信息传播的特征,包括节点属性特征和信息内容特征,对节点间传播概率和传播延迟进行建模,提出一个细粒度的在线社会网络信息传播模型.利用随机梯度下降算法学习模型中的各个特征的权重.另外,针对模型的传播预测功能,在新浪微博真实数据集上进行了实验,结果表明,在预测准确率方面,所提出的模型要优于其他同类模型,如异步独立级联模型、NetRate模型.     

结合重要节点信任传播的社会化推荐算法

融合社交信息的推荐算法有效缓解了推荐算法中的数据稀疏性问题和冷启动问题,近年来受到极大的关注.但社交信息依然存在数据稀疏性问题,而且社交网络提供的二值数据无法衡量不同用户间的信任程度.针对这些问题,利用重启随机游走算法获取社交网络中的重要节点.提出重要节点信任传播算法建立重要节点和其他用户节点之间的信任关系,同时利用节...     

DiffRank:一种新型社会网络信息传播检测算法

信息传播检测是给定一个传播网络,如何选择最有效的节点集合作为观察节点或部署传感器,以尽早尽快检测到网络中传播的信息,这对于社会网络中的意见领袖挖掘、谣言传播检测、舆情监控等应用具有重要意义.文中结合网络结构特点、节点内容属性、历史传播数据等信息,提出了一个基于随机游走模型的传播能力排序算法DiffRank,根据该算法的结果选择传播能力最强的top-k个节点作为观察节点来检测网络中可能出现的信息传播.基于新浪微博真实数据的实验结果表明,与其他同类算法相比,DiffRank算法在检测覆盖率、检测时间和信息感染人数下降比率3个指标上,都优于同类算法.在算法的可扩展性方面,DiffRank算法更加适用于并行或分布式计算,可扩展性更好.     

节点传播能力的偏好随机行走的信息传播方法

随机行走是社交和生物系统中用来模拟传播过程的标准化工具,针对真实社交网络中任意程度的有偏随机行走过程和由优先转移概率定义的偏向性,提出了一种新的用于研究社交网络的影响力传播范围最大化的方法,称之为基于节点传播能力的偏向性随机行走的网络信息传播方法（DCID）,该方法随机从网络中选择一个信息传播源节点,使得该模型更加符合真实的社交网络;通过节点能承受的传播信息的内容量参数以及偏向性随机行走的参数来作为节点的优先转移概率;并通过影响力传播函数来衡量信息的影响力传播范围,以此达到信息传播范围的最大化。从真实的不同规模的社交网络中选定这两个参数值,并验证了提出的模型在不同规模社交网络中信息的覆盖率和算法运行时间的性能上有所提升。     

融合节点描述属性信息的网络表示学习算法

为融合节点描述信息提升网络表示学习质量，针对社会网络中节点描述属性信息存在的语义信息分散和不完备性问题，提出一种融合节点描述属性的网络表示（NPA-NRL）学习算法。首先，对属性信息进行独热编码，并引入随机扰动的数据集增强策略解决属性信息不完备问题；然后，将属性编码和结构编码拼接作为深度神经网络输入，实现两方面信息的相互补充制约；最后，设计了基于网络同质性的属性相似性度量函数和基于SkipGram模型的结构相似性度量函数，通过联合训练实现融合语义信息挖掘。在GPLUS、OKLAHOMA和UNC三个真实网络数据集上的实验结果表明，和经典的DeepWalk、TADW（Text-Associated DeepWalk）、UPP-SNE（User Profile Preserving Social Network Embedding）和SNE（Social Network Embedding）算法相比，NPA-NRL算法的链路预测AUC（Area Under Curve of ROC）值平均提升2.75%，节点分类F1值平均提升7.10%。     

基于超图卷积的异质网络半监督节点分类

近几年,图神经网络(Graph Neural Network)由于能够较好地提取网络结构信息以获得网络表示,逐渐成为网络节点分类的主流算法.然而,与广泛研究的同质信息网络相比,真实世界中网络往往是由不同类型的对象通过复杂关系相互连接所构成的异质信息网络.异质信息网络包含复杂的结构信息和丰富的语义信息,这也给网络节点分类提供了新的机遇与挑战.在异质信息网络中,网络模体(Motif)能够用于理解和探索复杂网络,其既能描述复杂的语义信息,又能保存网络中高阶近邻结构信息.因此,提出基于网络模体的异质超图卷积网络模型MHGCN(Motif-based HyperGraph Convolutional Network).首先,将重复出现的高阶网络模体建模为多个相关节点所构成的超边(hyperedge),进而将整个异质信息网络转换成由不同超边构成的超图,以克服同质网络中只能描述节点之间(pair-wise)关系的缺点;然后,利用超图的基本性质和谱理论设计超图上的卷积操作,同时引入超边自注意力机制聚合超图内部不同类型的节点,并通过在超图网络中加入自环解决在模型的前向传播过程中对异质信息网络覆盖不足的问题;最后,通过注意力机制对于不同语义的超图表示进行聚合,从而使最终的节点表示可以有效保持高阶近邻关系和复杂的语义信息.由于MHGCN是端到端的,最终模型直接学习得到节点的分类标签,并通过半监督节点分类任务进行验证,与其它方法相比,MHGCN在DBLP-P、DBLP-A数据集上比最好的基准方法micro-F1提高了0.56％～3.51％,macro-F1提高了0.54％～4.37％,验证了MHGCN模型的有效性.     

基于SIR模型的社交网络推手节点发现及信息传播抑制

推手节点对社交网络信息传播有非常重要的作用。在传统SIR模型中引入推手节点概念,研究该类节点所造成的热门话题在网络中的传播规律,以及对社交网络信息传播的影响和控制。利用You Tube数据构建社交网络拓扑结构,实验发现,当节点传播概率大于0.7时,可设置为推手节点,对于信息传播抑制可采用目标免疫算法。而在一个社交网络中传播节点的整体信息免疫大于0.2时能有效抑制信息传播,该值为使用重要熟人免疫策略对信息传播进行抑制的参数值。     

基于粗糙集的快速KNN文本分类算法

传统K最近邻一个明显缺陷是样本相似度的计算量很大,在具有大量高维样本的文本分类中,由于复杂度太高而缺乏实用性。为此,将粗糙集理论引入到文本分类中,利用上下近似概念刻画各类训练样本的分布,并在训练过程中计算出各类上下近似的范围。在分类过程中根据待分类文本向量在样本空间中的分布位置,改进算法可以直接判定一些文本的归属,缩小K最近邻搜索范围。实验表明,该算法可以在保持K最近邻分类性能基本不变的情况下,显著提高分类效率。     

基于移动锚节点的模糊信息三维定位算法

为有效抑制复杂环境对无线传感器网络节点定位精度的影响,在三边定位的基础上,基于移动锚节点和节点之间的模糊信息,提出一种三维空间中的节点定位算法( MANLFI)。该算法通过测量锚节点和未知节点的方向角、俯仰角实现节点定位,每轮定位结束后更新锚节点的速度和方向,节点被定位后充当静态锚节点对其他节点定位。仿真实验结果表明,与APIT-3D和Bounding cube算法相比,MANLFI算法可提高节点定位精度和网络稳定性,且时延短、能耗低。     

基于结构深度网络嵌入模型的节点标签分类算法

在海量数据呈现爆炸增长态势的互联网时代,传统算法已无法满足处理大规模、多类型数据的需求.近年来最新的图嵌入算法通过学习图网络特征,在链路预测、网络重构和节点分类实践中普遍取得了极佳的效果.文中基于传统自动编码器模型,创新地提出了一种融合Sdne算法与链路预测相似度矩阵的新算法,通过在反向传播过程中引入高阶损失函数,依据...     

Variational Gridded Graph Convolution Network for Node Classification

The existing graph convolution methods usually suffer high computational burdens, large memory requirements, and intractable batch-processing. In this paper, we propose a high-efficient variational gridded graph convolution network (VG-GCN) to encode non-regular graph data, which overcomes all these aforementioned problems. To capture graph topology structures efficiently, in the proposed framework, we propose a hierarchically-coarsened random walk (hcr-walk) by taking advantage of the classic random walk and node/edge encapsulation. The hcr-walk greatly mitigates the problem of exponentially explosive sampling times which occur in the classic version, while preserving graph structures well. To efficiently encode local hcr-walk around one reference node, we project hcr-walk into an ordered space to form image-like grid data, which favors those conventional convolution networks. Instead of the direct 2-D convolution filtering, a variational convolution block (VCB) is designed to model the distribution of the random-sampling hcr-walk inspired by the well-formulated variational inference. We experimentally validate the efficiency and effectiveness of our proposed VG-GCN, which has high computation speed, and the comparable or even better performance when compared with baseline GCNs.      

基于反向可达集的影响力最大化算法

现有影响力最大化算法多数因时间复杂度较高或影响力传播范围有限,不适用于大规模社交网络。基于独立级联模型,结合反向可达集采样提出一种改进的影响力最大化算法D-RIS。在影响力传播函数满足单调性和子模性的前提下,通过自动调试确定反向可达集生成数量的临界值。在Slashdot和Epinions真实数据集上的实验结果表明,D-RIS算法在影响力传播范围上接近CELF算法且优于RIS、HighDegree、LIR和pBmH启发式算法,同时在运行时间上相比CELF算法减少近百倍,具有更好的通用性与稳定性,适用于拓扑结构变化和规模较大的社交网络。     

基于元胞自动机的小样本集分类算法

样本集中的数据数量过少会影响最后的分类精度。为此,提出基于元胞自动机模型的小样本集分类算法,利用元胞自动机的状态转换规则和分类规则,通过元胞空间的演化实现对数据集的分类。对标准数据集的测试结果表明,在小样本集和样本集中数据分布不均匀的情况下,该算法具有较高的分类精度。     

Community Discovery Algorithm Based on Multi-Relationship Embedding

Complex systems in the real world often can be modeled as network structures, and community discovery algorithms for complex networks enable researchers to understand the internal structure and implicit information of networks. Existing community discovery algorithms are usually designed for single-layer networks or single-interaction relationships and do not consider the attribute information of nodes. However, many real-world networks consist of multiple types of nodes and edges, and there may be rich semantic information on nodes and edges. The methods for single-layer networks cannot effectively tackle multi-layer information, multi-relationship information, and attribute information. This paper proposes a community discovery algorithm based on multi-relationship embedding. The proposed algorithm first models the nodes in the network to obtain the embedding matrix for each node relationship type and generates the node embedding matrix for each specific relationship type in the network by node encoder. The node embedding matrix is provided as input for aggregating the node embedding matrix of each specific relationship type using a Graph Convolutional Network (GCN) to obtain the final node embedding matrix. This strategy allows capturing of rich structural and attributes information in multi-relational networks. Experiments were conducted on different datasets with baselines, and the results show that the proposed algorithm obtains significant performance improvement in community discovery, node clustering, and similarity search tasks, and compared to the baseline with the best performance, the proposed algorithm achieves an average improvement of 3.1% on Macro-F1 and 4.7% on Micro-F1, which proves the effectiveness of the proposed algorithm.     

基于LeaderRank和节点相似性的多标签传播重叠社团挖掘算法

针对基于多标签传播重叠社团挖掘算法COPRA因随机更新策略带来的不稳定性以及需要预先输入参数的局限性等问题,提出一种基于LeaderRank和节点相似性的多标签传播重叠社团挖掘算法.该算法首先利用LeaderRank算法对网络中的节点进行重要性排序从而确定节点的更新顺序,减少标签不必要的更新.在标签传播过程中,根据节点相似性重新设计标签的更新策略,提高算法的稳定性.将算法应用于人工网络和真实网络中进行实验,实验结果表明该算法在挖掘重叠社团上具有较高的准确性和稳定性.     

一种基于点割集的感应失效节点容错算法

感应器失效节点通常发送错误数据,干扰全局信息判断,若转为睡眠状态则容易造成网络连通度下降,增加其他节点的路由转发负载.因此,对这些感应器失效节点的剩余能量进行利用,并进行自身估值,对于获取更准确的全局信息,保持网络负载平衡,具有重要的意义.提出一种基于点割集的感应失效节点容错算法,该算法基于数据相关图,筛选出与失效节点具有强数据相关性的点割集,然后利用所监听到的点割子集的观测量,进行正交估算,获取失效节点的最小均方误差估值.理论分析和实验结果表明,所提出的容错算法能较准确地估计失效点观测盲区,获取较完整的全局信息,同时由于算法使网络内的失效节点可以继续工作,保证了已有的网络负载平衡,维持原有的网络连通度.     

基于图编码网络的社交网络节点分类方法

针对如何融合节点自身属性以及网络结构信息实现社交网络节点分类的问题,提出了一种基于图编码网络的社交网络节点分类算法。首先,每个节点向邻域节点传播其携带的信息;其次,每个节点通过神经网络挖掘其与邻域节点之间可能隐含的关系,并且将这些关系进行融合;最后,每个节点根据自身信息以及与邻域节点关系的信息提取更高层次的特征,作为节点的表示,并且根据该表示对节点进行分类。在微博数据集上,与经典的深度随机游走模型、逻辑回归算法有以及最近提出的图卷积网络算法相比,所提算法分类准确率均有大于8%的提升;在DBLP数据集上,与多层感知器相比分类准确率提升4.83%,与图卷积网络相比分类准确率提升0.91%。