稳定的标签传播社团划分算法研究

快速稳定地发现复杂网络中的社团是近年来社团划分研究的热点。标签传播算法(LPA)具有接近线性的时间复杂度,能快速发现复杂网络中的社团结构,但是该算法在标签传播过程中存在不确定性和随机性,降低了划分结果的准确性和稳定性。为了解决这一问题,设计了一种稳定的标签传播社团划分算法(S-LPA)。该算法利用改进的K-Shell算法来计算节点全局影响力,并结合能反映节点局部影响力的度值以及邻居节点信息,计算节点综合影响力;在标签传播过程中,根据标签影响力更新标签;当网络中所有节点的标签不再变化或者迭代次数达到最大值时,拥有相同标签的节点划分到同一社团中。在真实网络和人工合成网络上的实验结果表明,S-LPA算法不仅具有线性时间复杂度,而且提高了社团划分的质量和稳定性。     

基于链路标签传播的重叠社团发现算法

为挖掘复杂网络中的重叠社团结构,在标签传播算法的基础上,从链路的角度出发,提出一种新的标签更新策略。考虑不同邻居对链路标签贡献值的不同特点,使其更新过程更加快速,克服当前基于节点的标签传播算法需要指定节点所属社团个数的缺陷,在无需人工干预的情况下得到稳定的重叠社团结构。将该算法分别应用于人工网络和真实的社会网络中,实验结果表明,该算法能够快速、有效地挖掘稳定的重叠社团结构。     

基于聚类的复杂网络社团发现算法

对基于聚类技术的复杂网络社团发现算法进行研究,分析网络中结点间的相似性度量方法,提出把复杂网络中的结点转化为向量的顶点到向量映射(MVV)算法,把网络中的结点转化成适合聚类算法的数据结构形式.对不同聚类算法及相似性度量方法的性能进行比较分析,结果表明,MVV算法可以提高发现复杂网络中社团的能力.     

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

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

基于相对密度的社团结构探测算法

社团结构发现方法已经成为复杂网络的一个研究热点。在分析目前一些典型的社团探测算法的基础上,该文提出基于相对密度的社团结构划分方法,该方法可以有效地解决SCAN算法中对参数值过于敏感、参数值难以设置以及高密度社团完全被相连的低密度所包含等问题。把该算法应用到已知社团结构的计算机生成网络中,并与SCAN算法的划分结果进行比较。实验结果表明,该算法是有效可行的。     

基于物理场论的探测复杂网络社团结构的分布估计算法

探测社团结构是复杂网络分析中一个基本和重要的问题。为提高探测社团结构的效率,本文提出了基于复杂网络场论的社团结构分布估计算法。通过设置不同种群规模,本文算法运用经典物理场论理论构建节点间场论模型,并在此基础上建立了社团结构概率模型,按照社团结构概率模型建立了分布估计算法。将该算法与GN(Girvan Newman)算法、遗传算法及启发式算法比较其产生的最优解,并分析它们的均值及方差的差异,结果表明：基于复杂网络场论的社团结构分布估计算法收敛速度较快,划分效果较好。     

基于标签传播能力的改进LPA算法

随着网络规模的不断增大,在时间复杂度上具有明显优势的标签传播算法受到广泛关注,但是其内在机制存在不确定性和随机性,导致社团发现结果不够准确和稳定。为此,提出一种新的改进标签传播算法。在K-shell分解算法的基础上,构造节点重要性计算方法,利用节点重要性分析标签传播算法中的标签传播能力,通过节点重要性排序和标签传播能力制定新的标签更新策略,得出最终的社团划分结果。在人工网络和真实网络上的实验结果表明,该算法有较高的准确性和稳定性。     

基于核心节点扩散的有向网络重叠社团发现算法

复杂网络中的社团结构探测是当前复杂网络研究领域的一个热点问题。传统的社团划分算法主要以无向、无权网络作为分析对象,不能够适用于现实世界中各种有向网络、加权网络。在分析和研究各种社团划分算法的基础上,提出一种新的重叠社团发现算法。该算法从网络中的核心节点开始,不断合并适应度最大邻居节点,最终将网络划分为多个重叠的社团。最后,将该算法应用到两个有向网络中,实验表明该算法能够很好地划分出有向网络中的重叠社团。     

基于结构相似度仿射传播的社团检测算法

复杂网络中普遍存在着一定的社团结构,社团检测具有重要的理论意义和实际价值。为了提高复杂网络中社团检测的性能,提出了一种基于结构相似度仿射传播的社团检测算法。首先,选取结构相似度作为节点之间的相似性度量,并采用了一种优化的方法来计算复杂网络的相似度矩阵;其次,将计算得到的相似度矩阵作为输入,采用快速仿射传播(FAP)算法进行聚类;最后,得到最终的社团结构。实验结果表明,所提算法在LFR(Lancichinetti-Fortunato-Radicchi)模拟网络上的社团检测平均标准化互信息(NMI)值为65.1%,要高于标签传播算法(LPA)的45.3%以及CNM(Clauset-Newman-Moore)算法的49.8%;在真实网络上的社团检测平均模块度值为53.1%,要高于LPA算法的39.9%以及CNM算法的47.8%,具有更好的社团检测能力,能够发现更高质量的社团结构。     

一种基于节点相似度的社团探测算法

文章借鉴节点密度等性质,提出了一种基于节点间相似度的复杂网络社团结构探测算法(BSTN)。在实际网络中进行验证,本文使用的是空手道俱乐部网络(Karate网络)和美国大学足球俱乐部网络(Football网络),实验结果与Newman算法进行了比较。本文提出的算法拥有更少的迭代次数,近似的模块度值,说明此算是有效的,并且对算法得出的社团结构进行了合理的解释,说明算法得出的结果是符合实际的、是合理的。     

面向大规模学术社交网络的社区发现模型

针对基于标签传播的复杂网络重叠社区发现算法中预先输入参数在真实网络中的局限性以及标签冗余等问题,提出一种基于标签传播的面向大规模学术社交网络的社区发现模型。该模型通过寻找网络中互不相交的最大极大团(UMC)并对每个UMC中的节点赋予唯一标签来减少冗余标签,提高社区发现的效率以及稳定性。标签更新时以UMC作为核心单位采用亲密度的方式由中心向四周更新UMC邻接节点的标签及权重,以权重最大值的方式更新网络中非UMC邻接节点的权重。后期处理阶段采用自适应阈值方式去除节点标签中的噪声,有效克服了预先输入重叠社区个数在真实网络中的局限性。通过在学术社交网络平台——学者网数据集上的实验表明,该模型能够将具有一定共性的节点划分到同一个社区中,并为学术社交网络平台进一步的好友推荐、论文分享等精确的个性化服务提供了支持。     

复杂网络簇结构探测——基于随机游走的蚁群算法

网络簇结构是复杂网络最普遍和最重要的拓扑属性之一,网络聚类问题就是要找出给定网络中的所有类簇.有很多实际应用问题可被建模成网络聚类问题.尽管目前已有许多网络聚类方法被提出,但如何进一步提高聚类精度,特别是在没有先验知识(如网络簇个数)的情况下如何发现合理的网络簇结构,仍是一个未能很好解决的难题.针对该问题,在马尔可夫随机游走思想的启发下,从仿生角度出发提出一种全新的网络聚类算法——基于随机游走的蚁群算法RWACO.该算法将蚁群算法的框架作为RWACO的基本框架,对于每一代,以马尔可夫随机游走模型作为启发式规则;基于集成学习思想,将蚂蚁的局部解融合为全局解,并用其更新信息素矩阵.通过“强化簇内连接,弱化簇间连接”这一进化策略,使网络簇结构逐渐地呈现出来.实验结果表明,对一些典型的计算机生成网络和真实网络,该算法能够较准确地探测出网络的真实类簇数与一些有代表性的算法相比,具有较高的聚类精度.     

软件定义承载网中基于负载均衡的虚拟网络重配置方法*

在软件定义承载网(Carrier-SDN)中应用网络虚拟化技术为虚拟网络请求分配资源是解决传统网络结构僵化问题的重要方法之一。针对虚拟网络初次配置产生的瓶颈节点和瓶颈链路造成的底层网络负载不均衡问题,提出一种基于负载均衡的虚拟网络重配置方法(Load Balance Virtual Network Reconfiguration,LB-VNR)。该方法着重设计了虚拟节点的迁移算法、虚拟链路的迁移算法以及重路由映射路径规划算法。仿真结果表明,所提方法在虚拟网络请求接受率、网络收益代价比和虚拟网络负载均衡性方面均具有良好的性能。     

一种面向语义重叠社区发现的Link-Block算法

语义社会网络是一种由信息节点及社会关系构成的新型复杂网络,传统语义社会网络分析算法在进行社区挖掘时需要预先设定社区个数,且无法发现重叠社区.针对这一问题,提出一种面向语义社区发现的link-block算法.该算法首先以LDA模型为语义信息模型,创新性地建立了以link为核心的block区域LBT(link-block-topic)取样模型;其次,根据link-block语义分析结果,建立可度量link-block区域的语义链接权重方法,实现了语义信息的可度量化;最后,根据语义链接权重建立了以link-block为单位的聚类算法以及可评价语义社区的SQ模型,并通过实验分析,验证了该算法及SQ模型的有效性及可行性.     

基于多标签传播的重叠社区发现优化算法

标签传播算法是一种被广泛应用的社区发现算法,该算法为网络中的每个节点分配一个初始标签,然后通过传播标签来发现复杂网络中的潜在社区,具有时间复杂度低的特点。当前基于标签传播的重叠社区发现算法存在忽略节点重要性差异、需要人为设置参数等不足。针对该类算法在重叠社区发现方面的缺陷,提出一种基于多标签传播的重叠社区发现优化算法。该算法使用K-核分解方法找出若干个社区核心节点,以这些节点为种子节点,逐层向外传播标签;在进行标签选择的时候以邻居节点标签的种类来决定重叠节点的标签个数。实验表明,该算法明显改善了社区发现的性能,提高了划分结果的稳定性和准确性。     

Enhancing multi-label classification by modeling dependencies among labels

In this paper, we propose a novel framework for multi-label classification, which directly models the dependencies among labels using a Bayesian network. Each node of the Bayesian network represents a label, and the links and conditional probabilities capture the probabilistic dependencies among multiple labels. We employ our Bayesian network structure learning method, which guarantees to find the global optimum structure, independent of the initial structure. After structure learning, maximum likelihood estimation is used to learn the conditional probabilities among nodes. Any current multi-label classifier can be employed to obtain the measurements of labels. Then, using the learned Bayesian network, the true labels are inferred by combining the relationship among labels with the labels? estimates obtained from a current multi-labeling method. We further extend the proposed multi-label classification method to deal with incomplete label assignments. Structural Expectation-Maximization algorithm is adopted for both structure and parameter learning. Experimental results on two benchmark multi-label databases show that our approach can effectively capture the co-occurrent and the mutual exclusive relation among labels. The relation modeled by our approach is more flexible than the pairwise or fixed subset labels captured by current multi-label learning methods. Thus, our approach improves the performance over current multi-label classifiers. Furthermore, our approach demonstrates its robustness to incomplete multi-label classification.     

基于网络社区发现的标签传播聚类算法

高维数据的聚类特性通常难以直接观测. 将其构建为复杂网络, 节点间的拓扑结构可以反映样本之间的关系. 对网络中的节点进行社区发现, 可实现对数据更直观的聚类. 提出一种基于网络社区发现的低随机性标签传播聚类算法. 首先, 用半径和最近邻方法将数据集构建为稀疏的全连通网络. 之后, 根据节点相似度进行节点标签预处理, 使得相似的节点具有相同的标签. 用节点的影响力值改进标签传播过程, 降低标签选择的随机性. 最后, 基于内聚度进行社区的优化合并, 提高社区的质量. 在真实数据集和人工数据集上的实验结果表明, 该算法对各种类型的数据都具有较好的适应性.     

Toward online node classification on streaming networks

The proliferation of networked data in various disciplines motivates a surge of research interests on network or graph mining. Among them, node classification is a typical learning task that focuses on exploiting the node interactions to infer the missing labels of unlabeled nodes in the network. A vast majority of existing node classification algorithms overwhelmingly focus on static networks and they assume the whole network structure is readily available before performing learning algorithms. However, it is not the case in many real-world scenarios where new nodes and new links are continuously being added in the network. Considering the streaming nature of networks, we study how to perform online node classification on this kind of streaming networks (a.k.a. online learning on streaming networks). As the existence of noisy links may negatively affect the node classification performance, we first present an online network embedding algorithm to alleviate this problem by obtaining the embedding representation of new nodes on the fly. Then we feed the learned embedding representation into a novel online soft margin kernel learning algorithm to predict the node labels in a sequential manner. Theoretical analysis is presented to show the superiority of the proposed framework of online learning on streaming networks (OLSN). Extensive experiments on real-world networks further demonstrate the effectiveness and efficiency of the proposed OLSN framework.     

基于图深度学习的金融文本多标签分类算法

金融文本多标签分类算法可以根据用户需求在海量金融资讯中实现信息检索。为进一步提升金融文本标签识别能力,建模金融文本多标签分类中标签之间的相关性,提出基于图深度学习的金融文本多标签分类算法。图深度学习通过深度网络学习局部和全局的图结构特征,可以刻画节点之间的复杂关系。通过建模标签关联实现标签之间的知识迁移,是构造具有强泛化能力算法的关键。所提算法结合标签之间的关联信息,采用基于双向门控循环网络和标签注意力机制得到的新闻文本对应不同标签的特征表示,通过图神经网络学习标签之间的复杂依赖关系。在真实数据集上的实验结果表明,显式建模标签之间的相关性能够极大地增强模型的泛化能力,在尾部标签上的性能提升尤其显著,相比CAML、BIGRU-LWAN和ZACNN算法,该算法在所有标签和尾部标签的宏观F1值上最高提升3.1%和6.9%。