复杂网络社区挖掘综述

复杂网络社区挖掘是近10年来多学科交叉的前沿研究热点之一,其研究不仅有重要的理论意义,而且有广泛的应用前景.介绍了社区挖掘及重叠社区挖掘的研究背景和研究意义,分析了研究现状,讨论了该研究所面临的一些主要问题及未来的发展方向.同时,为了对不同的社区挖掘算法进行更好地评估,选择了有代表性的6个社区挖掘算法和3个重叠社区挖掘算法进行测试,并给出了对比分析结果,试图为这个新兴研究领域勾画出一个较为全面和清晰的轮廓.

社会网络中基于局部信息的边社区挖掘

近年来,随着社交网络的发展,许多重叠社区挖掘算法被提出来.传统的方法都是将节点作为研究对象,而最近的一些研究表明,以边为研究对象的边社区挖掘方法相对于点社区挖掘方法来说具有更加明显的优势.因此,我们提出了基于局部边社区的挖掘算法(LLCM),利用网络中的局部信息去挖掘边社区结构.给定一条初始的边,通过不断最大化一个适应度函数来获取该边所在的局部社区,而这条初始的边可以预先通过一些排序算法进行选择.算法经过在计算机生成网络和真实网络上测试,并且同其他边社区挖掘算法进行了比较,实验结果表明LLCM算法获取了合理的边社区的结构.

一种集成链接和属性信息的社区挖掘方法

现有复杂网络社区挖掘方法由于单一利用节点链接信息或属性信息,从而无法有效发现成员链接紧密且属性高度相同的社区,针对该问题提出一种可集成节点链接和属性信息进行社区挖掘的方法:LANMF.LANMF基于非负矩阵分解模型,以联合矩阵分解的形式统一分解复杂网络节点链接矩阵以及属性关联矩阵,可直接获得节点与社区归属关系矩阵以及属性与社区关联矩阵,社区成员在链接结构紧密度以及属性相关性上可得到很好的保证.设计了乘性迭代更新规则作为联合矩阵分解优化算法并从数学上严格证明了其正确性和收敛性.实验结果表明:LANMF的社区挖掘质量优于现有典型的同类社区挖掘方法,能直接有效挖掘社区,而且实际应用表明LANMF适合用于挖掘现实世界复杂网络中的主题社区以及重叠社区.

基于环路紧密度的复杂网络社区挖掘方法

提出了一种基于环路紧密度的复杂网络社区挖掘算法(LTA):首先提出一种快速发现网络环路和计算其紧密值的算法,然后根据环路紧密值将网络聚类,再次揭示网络环路与社区结构的联系。并使用人工合成网络和真实网络数据集对LTA进行了验证,实验结果证明了LTA对复杂网络社区挖掘问题的有效性和高效性。

基于随机网络集成模型的广义网络社区挖掘算法

根据结点的属性和链接关系,现实世界中的复杂网络大多可分为同配网络和异配网络,社区结构在这两类网络中均普遍存在.准确地挖掘出两种不同类型网络的社区结构具有重要的理论意义和广泛的应用领域.由于待处理的网络类型通常未知,因而难以事先确定应当选择何种类型的网络社区挖掘算法才能获得有意义的社区结构.针对该问题,本文提出了广义网络社区概念,力图将同配和异配网络社区结构统一起来.本文提出了随机网络集成模型,进而提出了广义网络社区挖掘算法G-NCMA.实验结果表明:该算法能够在网络类型未知的前提下准确地挖掘出有意义的社区结构,并能分析出所得社区的类型特征.

力导向模型的复杂网络社区挖掘算法

在复杂网络中发现和刻画社区结构是近年来复杂网络研究的重点方向之一。提出了一种社区挖掘的新思路,即根据力导向模型的原理,通过计算社区与节点之间的作用力来决定节点的社区归属。根据该思路设计了基于力导向模型的算法框架FDCD(Force-directed Community Detect),并利用FR模型、KK模型、LL模型和Q模型进行了验证。实验表明,基于FDCD算法框架的多种不同算法不仅能较好地识别社区结构,而且基于LL模型的FDCD算法达到了线性计算复杂度,能适用于大规模网络的社区挖掘。

基于改进遗传算法的社区挖掘研究

传统遗传算法应用于社区挖掘时初始种群划分精确度不高,且容易降低算法整体搜索性能。为此,提出一种改进的遗传算法,并将其引入到社区挖掘研究中。结合结构相似度与轮盘赌选择法,使染色体的每个基因趋向于选择结构相似度较大的邻居节点,提高初始种群的社区划分质量并加速算法收敛速度。实验结果表明,在人工基准网络中,该算法的初始种群划分精确度和模块度比传统遗传算法平均提高18%和12%,整体划分精确度比FEC和FN算法平均提高24. 02%和22. 01%,在真实世界网络中,社区划分精确度均优于FN、FEC和LPA算法,从而验证该算法具有较好的社团挖掘性能。

应用非负值矩阵分解模型的社区挖掘方法

在线社交网络增长迅速,对其进行社区挖掘对于了解网络结构特征具有重要意义.提出一种基于非负值矩阵分解的社区挖掘方法,能够将社交网络矩阵分解为适合于发现用户与社区所属关系以及社区之间重叠关系的矩阵组合形式.该方法应用迭代更新规则对分解矩阵进行了优化求解,并证明了更新规则的收敛性.另外针对社交网络存在的无标度特性,通过利用用户节点属性信息计算用户间的相似性,对大量孤立用户建立隐式联系,可以将孤立用户纳入统一的挖掘框架进行社区划分,从而解决了孤立用户无法准确划分社区的问题.相关实验以及实际应用表明该方法可以有效对现实中的在线社交网络进行社区挖掘.

动态社会网络中的社区挖掘算法研究

为解决社区挖掘问题,针对社会网络的动态特性,给出了新的社区定义,并结合连通性和频繁性概念提出一种新的算法DCSMA(Dynamic Community Structure Mining Algorithm)。挖掘时刻连通的个体集合作为社区,采用层状结构模型,根据重要性权重区分社区内个体,使社区结构更加清晰。在标准测试数据集上的实验结果表明了该算法的可行性和有效性。

面向异质关系的社区挖掘

利用数据挖掘技术,并结合最优化理论知识,研究了基于文献数据的异质关系挖掘问题,应用最小分割最大化的关系抽取算法,挖掘具有共同研究兴趣的研究者社区。在此基础上实现了基于关系链的挖掘分析,解决了应用当中的实际问题,能够更好地辅助研究者进行研究工作。

基于局部结构特征的重叠社区挖掘研究进展

社区挖掘是复杂网络研究的核心内容之一.基于局部结构建模的重叠社区发现方法由于可利用局部先验知识,具有适应网络动态环境,建模速度快,可多角度呈现局部结构特征等优点,当前已成为大规模网络发现研究的前沿热点.从理论发展沿革与现实应用的视角,介绍重叠社区发现研究近来的相关研究进展.通过分析重叠社区发现研究存在的关键问题,给出基于局部结构特征的重叠社区挖掘研究框架,并对几类典型的重叠社区发现方法展开分析比较.然后进一步阐述和探讨如何面对现实超大规模网络、多态异构网络、不确定性数据、动态演化结构等方面面临的巨大挑战.最后总结并展望了基于局部结构的重叠社区发现研究的未来方向和前景.

基于蚁群优化的二分网络社区挖掘

近年来,网络社区挖掘得到了极大的关注,尤其是针对二分网络的社区挖掘。二分网络社区挖掘对于研究复杂网络有非常重要的理论意义和实用价值。提出了一个基于蚁群优化的二分网络社区挖掘算法。该算法首先将二分网络社区挖掘问题转化成一个优化问题,建立一个可供蚂蚁搜索的图模型。同时,根据顶点的拓扑结构定义启发式信息。每只蚂蚁根据每条路径上的信息素和启发式信息选择路径,构造出一个社区的划分,再用二分模块度去衡量社区划分的优劣。实验结果表明,该算法不但可以较准确地识别二分网络的社区数,而且可以获得高质量的社区划分。

旅游游客社会网络局部社区挖掘方法

为解决游客社会网络构建与关系分类问题,以真实的游客旅游记录为基础,设计一种游客社会网络构建方法,提出一种基于中心节点扩张的局部社区挖掘算法。通过修改PageRank算法对游客社会网络节点进行排名,选取中心度值最大的且没有被其它局部社区包含的节点作为中心节点,用贪心算法对中心节点进行扩张形成局部社区,重复执行,覆盖整个游客社会网络。实验结果表明,该算法可以有效挖掘出游客社会网络中存在的局部社区,具有较小的时间复杂度。

社区挖掘技术研究

复杂网络分析已成为近年来的一个热点研究领域。如何快速有效地对复杂网络进行社区划分,并在社区划分的基础上找出网络中的重要节点有很强的现实意义。本文分析比较了近年来复杂网络分析中社区结构挖掘算法和社区节点等级排序算法的原理和特征,最后对复杂网络分析的发展进行了总结和展望。

基于模块度增量的二分网络社区挖掘算法

针对二分网络的社区挖掘问题,提出了一种基于模块度增量的二分网络社区挖掘算法。该算法假设每个顶点独自构成一个社区,并具有自己的标号。其中,一部分顶点将自己的标号复制并传递到另一部分中的某个顶点上,使之与其位于同一个社区;另一部分的顶点实施同样的操作。如此反复迭代,直至收敛。标号传播时,选择模块度增量最大的边进行传送,使整体模块度不断提高。在真实数据集上进行的测试表明,所提算法能对二分网络进行高质量的社区划分。

一种支持独立与重叠社区挖掘的质量评价模型

建立统一的独立社区和重叠社区挖掘结果评价标准,对于简化复杂网络社区挖掘、提高结果评估可比性有重要意义.目前的独立社区评价没有解决社区划分何时中止的问题,而重叠社区评价标准则往往具有较大的主观性.本文基于链接关联度和最优节点复制下的节点关联度,提出了一种支持独立和重叠社区挖掘、客观的统一评价模型,且基于该评价模型的社区挖掘方法可以进行多尺度的独立社区和重叠社区挖掘.理论分析和实际网络实验证实了该评价模型的合理性和可用性.

基于KL-Ball的社区挖掘方法

针对邻接矩阵的稀疏特性,采用KL散度来计算网络节点间的距离,提出了一种基于KL-Ball的社区挖掘方法。该方法中,一个KL-Ball代表一个社区,它从质心、半径、互信息及密度4个方面来描述社区,其中质心决定了社区在网络中的位置,半径刻画了社区所能覆盖的范围,互信息度量了社区中包含节点的一致性,密度反映了社区包含节点的数量。给定一个半径,期望从复杂网络中寻找具有低信息、高密度的社区,低信息使得社区包含的节点具有较强的一致性,高密度使得一个社区具有较强的凝聚性。为此,定义了一个基于KL-Ball的社区挖掘目标函数,给出它的优化算法,并从理论上证明了该算法的收敛性。依据社区半径的大小及质心的位置,该算法可应用于非重叠社区挖掘以及重叠社区挖掘。实验结果表明,基于KL-Ball的社区挖掘方法可有效地挖掘网络中蕴含的社区结构,包括非重叠的社区及重叠的社区。

从消息传播概率到概率亲密度矩阵的社区挖掘算法

随着现代网络的结构越来越复杂,规模越来越大,基于局部最优的社区挖掘算法受到了越来越多的关注.这些算法的计算速度快,但是结果精度较低.针对上述问题,对已有的CONCLUDE算法进行改进,利用消息传播概率代替结构相似性来构造亲密度矩阵,表示网络中的全局信息,计算过程的时间复杂度由O(珔d(v)2V)降低到O(珔d(v)V).与其它算法(LM,CONCLUDE)进行比较和分析,该算法具有较高的计算效率和精度.实验结果表明,该算法不仅提高了LFR基准网络上的NM I值,而且对真实网络上的模块度也有一定的提升.

基于标签传播的稳定重叠社区挖掘算法研究

为解决重叠社区挖掘算法中效率与稳定性不能兼顾的情况,本文提出了一种基于标签传播的稳定重叠社区挖掘算法(SOCLP)。该算法首先利用两种标签选择策略解决了基于标签传播算法中的稳定性问题,然后又通过引入平衡因子对算法的稳定性进行了有效的控制。实验结果证明,本文所提出的SOCLP算法可以同时关注社区挖掘的质量、效率和稳定性。

基于标签传播的社区挖掘算法研究综述

社会网络由于其流行程度已经成为众多学者的研究热点。通过社区挖掘算法可以发现存在于社会网络中的潜在社区,而重叠社区挖掘则可以挖掘出更具有现实意义的社区结构。但是在研究中社会网络所包含的庞大数据量又会为之带来种种不便,因此快速的社区挖掘算法就受到了越来越多的重视。基于标签传播的社区挖掘算法具有近乎线性的时间复杂度。文中将从多方面研究目前基于标签传播的社区挖掘算法的优劣,并且详细分析基于标签传播算法在以后研究中的改进思路。