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

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

一种基于标签传播算法的关键链路探测方法

随着网络脆弱性逐渐引起人们的关注,对于一个复杂网络,对其关键链路的探测已经越来越重要。根据网络所具有的社团结构特征,立足于网络的社团划分,结合GN算法思想,把标签传播算法引入关键链路探测中。针对原有算法在迭代过程中出现的每个顶点都会得到一个标签而造成的资源浪费和随机迭代出现结果不稳定的问题,采用一次传播标签把结构较紧密的顶点绑定在一起和依据度顺序来更新标签的方法。通过实验验证,该算法能快速、稳定、高效地查找复杂网络中的关键链路。     

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

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

基于局部社团和节点相关性的链路预测算法

基于网络拓扑结构信息的链路预测算法是预测网络未知连边或未来连边的有效方法。在实际应用中,通过进一步提取网络结构信息可以提高网络链路预测结果的精度。文中提出了一种基于局部社团和节点相关性的链路预测算法(HCRP)。该算法把种子节点对的一阶局部社团扩展到二阶局部社团,获得了比一阶局部社团更多的网络结构信息;在用皮尔逊系数计算两个种子节点的相关系数时,该算法也考虑了二阶局部社团的最短路径、边聚类系数和连边密度对两个种子节点相似度的影响,获得了良好的预测网络连边的效果。实验采用了10个真实网络的数据,并对比了HCRP算法和11种知名算法,数值实验结果表明所提算法具有优良的链路预测性能。     

基于相关拓扑势的社团发现算法

针对传统算法社团划分精度较低以及模块度函数分辨率低的问题,提出一种基于相关拓扑势的社团发现算法,简称BITP算法。该算法考虑节点的相关性因素,引入相关拓扑势来衡量节点的影响力,寻找出其中的极大势值点,采用标签传播的思想对社团的规模进行控制。在人工合成网络和真实网络上,与多种算法进行实验对比,结果表明该算法多次运行结果相对稳定且社团划分精度较高。算法时间复杂度为O(n),且不需要先验知识,更适合大规模复杂网络上的社团结构挖掘。     

基于节点内聚系数的局部社团发现算法

为了能够快速有效地发现复杂网络中的局部社团,提出一种基于节点内聚系数的局部社团发现算法。该算法选取最大度节点作为起始社团,不断搜索其邻居节点,将满足条件的节点不断加入起始社团从而形成新的社团。在不同规模的真实网络数据集和人工合成数据集上进行实验,并与其他三种局部社团发现算法进行社团划分效果的对比。实验结果表明,该算法能够在较短的运行时间内保持较高模块度来识别复杂网络中的局部社团结构,更适合于大规模复杂网络的社团结构挖掘。     

基于核心图的标签传播算法

网络中的社团发现是当前的一个研究热点.在众多社团发现算法中,标签传播算法因简单快速而被广泛应用,但标签传播算法也存在结果稳定性较差的问题.基于此对标签传播算法的初始化过程进行改进,提出了基于核心图的标签传播算法.通过计算图中任意两点的k阶公共邻居,将具有最大相似性的节点及k阶邻居作为初始核心社团,并为其分配初始标签.通过上述过程,提取一些较为紧密的子结构来作为标签传播的初始社团,并给这些结构分配初始社团标签.在真实网络中的实验结果表明,该算法可以大幅提高结果的稳定性.     

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

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

基于圈结构的LPANNI优化算法

针对重叠社区发现准确率提升问题,提出了一种基于圈结构的LPANNI优化算法CLPANNI（cycle label propagation algorithm with neighbor node influence）。该算法通过挖掘节点的最小圈信息,依据圈比指标衡量节点的重要性并按升序进行标签更新,增加了标签传播过程的稳定性,按照邻居节点影响力大小加权接收邻居节点传递的标签。与四种基准算法在NMI_LFK、NMI_MGH、MOV指标下进行测试比较,CLPANNI算法在社区发现准确率方面表现较好。实验结果表明,该算法能够有效探测网络重叠社团结构,发现网络的紧密子团,识别的社团分布与真实网络结构更为接近。     

利用改进蚁群算法的重叠社团检测分析方法

针对重叠社团检测准确率提升问题,提出了一种基于改进蚁群算法的新型重叠社团检测算法。该算法包含位置初始化、运动和后处理三个阶段,分别通过初始位置识别与标签列表存储、基于节点间相似度的启发式信息重定义、合作保持标签列表等方式,使算法在合成数据集与现实世界数据集中的重叠社团与节点检测方面具有更好的性能。实验结果表明,在合成网络与现实世界网络平台上使用不同检测算法,所提出的方法对重叠社团与重叠节点的检测准确率较传统检测方法来说更高,因而对重叠社区检测问题求解与理解网络功能结构具有重要的参考与借鉴意义。     

LinkLPA: A Link‐Based Label Propagation Algorithm for Overlapping Community Detection in Networks

Community detection is an important methodology for understanding the intrinsic structure and function of complex networks. Because overlapping community is one of the characteristics of real‐world networks and should be considered for community detection, in this article, we propose an algorithm, called link‐based label propagation algorithm (LinkLPA), to detect overlapping communities. Because the link partition is conceptually natural for the problem of overlapping community detection, LinkLPA first transforms node partition problem into link partition problem and employs a new label propagation algorithm with preference on links instead of nodes to detect communities due to the simplicity and efficiency of label propagation algorithm. Then the proposed LinkLPA performs a postprocessing to refine the detected overlapping communities by avoiding over‐overlapping and incorrect partition of weak ties. Experimental results on a large number of real‐world and synthetic networks show that the proposed method achieves high accuracy on detecting overlapping communities in networks.     

基于最大流HITS的改进算法

HITS是一种经典的链接分析算法,其主要问题是容易发生主题漂移。针对这一问题,提出了一种改进的算法：MCHITS。MCHITS利用最大流算法对HITS进行改进：首先将root集扩展两层,然后将root中的结点作为种子结点通过最大流最小割算法发现以root集为中心的社区,社区中的页面作为MC-base集。实验结果表明MCHITS提高了查询结果的相关度,减少了主题漂移的发生。     

Web社区发现技术综述

Web是一个复杂超文本所组成的巨大的信息源,而且以很快的速度在不断的扩大．针对这样一个不断变化的信息源,如何利用和发现Web中的有用信息变得具有挑战性．Web在发展过程中存在着大量的社区,这些社区是Web组织中非常重要的信息．通过对社区信息的认识可以帮助我们总览Web的全貌．而将Web按照社区来组织有许多优点．社区可以引导用户找到感兴趣的信息;社区可以帮助Internet／Intranet服务提供者有效地组织门户;社区可以帮助制造商准确地找到消费者．社区还代表了Web的社会活动,因为Web就是一个社会性的网络．目前,许多社区的发现和维护是依靠人工来完成的,维护成本较高,修改也困难;此外,还存在着许多不为人知或者称为潜在的社区,而这些社区是无法通过人工来发现的．因此,许多研究都在致力于社区的自动或半自动发现技术．社区的发现主要采用基于Web图形的链接分析技术．在方法上大致上分为两类,一类是面向某个主题的社区发现,而另一个是无主题的社区发现技术．对于社区的发现技术做了较为全面的分析,并且总结了社区发现技术中依然存在的、挑战性的问题和未来的研究趋势．     

基于形式概念分析的博客社区发现

针对拖网算法存在的发现Web社区数量过多、社区间页面重复率较高以及严格的社区定义形成孤立社区等问题,提出一种基于形式概念分析(FCA)的博客社区发现算法。根据博客网络之间的链接关系构造概念格,通过格的代数消解对原始概念格进行等价划分,度量每个划分中概念间外延和内涵的结构相似性进而合并社区核心形成社区。实验结果表明：测试数据集中社区核心的网络密度大于40%的占全部的83.420%,合并社区的网络直径为3,且社区内容丰富程度得到提高。所提算法可以有效地运用于博客、微博等社交网络的社区发现,具有显著的应用价值和现实意义。     

基于边图的线性流重叠社区发现算法

重叠网络的社区发现是复杂网络研究中的重要问题。为了提高网络中重叠社区发现的时间效率，提出一种基于边图的线性流重叠社区发现算法LBSA。算法首先对于边图网络中的边进行随机的依次处理，完成节点的初步社区划分，再将其中重叠小社区合并到相似度最大的其他大社区中得到最终的社区。通过以上步骤，算法能够以接近线性的时间复杂度得到网络的重叠结构。从最终的实验结果来看，与其他算法相比，该算法能够在更短的时间有质量地发现网络中的重叠社区。     

基于链接分析和用户兴趣的微博社区发现算法

微博网络中的每一个节点代表一个微博用户,微博用户之间除了存在一定的社会关系外,用户本身也具有一定的特性。用户之间明显的链接关系可以为社区发现提供重要的线索,但两个用户之间如果有相似的兴趣,那么即使用户之间没有明显的链接关系他们也可能加入到同一个社区,而传统的社区发现方法大多基于单个方面进行考虑。所以,提出一种结合链接分析和用户兴趣的微博社区发现方法。真实数据集上的仿真实验验证了该方法的合理性和有效性。     

基于K means聚类算法的复杂网络社团发现新方法*

提出了一种基于Kmeans 聚类算法的复杂网络社团结构划分方法。算法基于Fortunato等人提出的边的信息中心度,定义了节点的关联度,并通过节点关联度矩阵来进行聚类中心的选择和节点聚类,从而将复杂网络划分成k个社团,然后通过模块度来确定网络理想的社团结构。该算法有效地避免了Kmeans 聚类算法对初始化选值敏感性的问题。通过Zachary Karate Club和College Football Network两个经典模型验证了该算法的可行性。     

基于K-means聚类算法的复杂网络社团发现新方法

提出了一种基于K-means聚类算法的复杂网络社团结构划分方法。算法基于Fortunato等人提出的边的信息中心度,定义了节点的关联度,并通过节点关联度矩阵来进行聚类中心的选择和节点聚类,从而将复杂网络划分成k个社团,然后通过模块度来确定网络理想的社团结构。该算法有效地避免了K-means聚类算法对初始化选值敏感性的问题。通过Zachary Karate Club和College Football Network两个经典模型验证了该算法的可行性。     

基于社区结构的影响力最大化算法

现有的社会网络影响力算法及模型的较高的时间复杂度已不适用于网络规模不断壮大的社会网络服务。针对上述问题,提出了一种基于网络社区结构的影响力最大化算法。首先评估各个社区中节点的影响力,挖掘其核心节点成员;继而在核心节点集和连接社区间的弱纽带节点中选取若干具有影响潜力的初始节点集,使其以最小的代价让信息在网络中得到最广泛的传播。实验结果表明:该算法不仅大大降低了时间复杂度,还获得了接近贪心算法的影响范围,影响覆盖率达到了90%以上。     

基于链接聚类的代谢网络社团结构研究

社团结构分析有助于识别代谢网络中的功能模块,有助于理解代谢网络的结构和功能关系,是代谢网络研究领域的一个重要研究课题。然而,当前的社团结构分析方法均依赖于对网络中的节点进行聚类分析,导致每个节点只能属于某一个社团。采用了一种对复杂网络中的链接进行聚类分析的方法,对高质量金黄色葡萄球菌代谢网络模型的巨强连通体进行了社团结构分析,得到了10个具有生物学意义的功能模块,结果表明链接聚类可用于识别新陈代谢网络中的功能社团。