关键词： 动态网络   进化聚类   谱分优化   社团检测   社团演化分析  

摘要： 随着对复杂网络理论研究不断深入,人们发现,现实世界中的大量现象能够使用复杂网络来刻画,复杂网络是由网络拓扑图中相互之间具有复杂关系的一些节点以某种方式连接在一起所构成的系统。社团检测能揭示社会中自然现象的变化和发展规律,对于研究动态网络具有很强的现实意义。对动态网络进行社团演化分析的传统方法,基本上均采用提取每个时刻网络快照的方式来找出此时刻的社团结构,将相邻时刻的社团相结合进行分析。针对传统的社团检测算法不能形象地刻画动态网络、并且算法时间复杂度高的缺点,本文提出了在时间平滑度框架下,对能够表征社团质量优劣的函数进行优化分析,找出最优社团。传统的社团检测算法具有时间复杂度较高的缺点,而谱分析法所花费的时间复杂度低,且能够将矩阵转换为容易理解的迹的形式。但是谱分析法需要事先知道社团的数目,将谱分析法和k-means算法相结合,能够很好地解决这个问题。基于以上基础知识,本文将谱分析法与k-means算法相结合,采用进化聚类框架以引入历史信息来指导当前时刻的社团合并策略。对能够表征社团质量好坏的模块函数Q,模块密度函数D,以及否定平均函数NA进行了优化。由此,既解决了动态网络社团质量检测的问题,又克服了需要预先知道社团数目的缺点。本文借助人工合成数据集和真实网络数据集,.并结合归一化互信息NMI和基因概率这两种评估标准,将本文提出的算法与FaceNet算法、动态多目标遗传算法(DYNOMGA)等进行仿真对比。从实验结果可以看出,跟其他算法相比,在有效的时间内,本文提出的算法在检测社团时取得了更好的效果,可用于大规模的复杂动态网络社团演化分析。

关键词： 社团检测   社团结构   强化社团   加边   删边   链路预测  

摘要： 现今复杂网络中的社团检测问题吸引了各个领域学者的广泛关注,如何精确的检测出网络中的社团结构是该领域研究的主要问题。对于社团结构不明显的网络,如今的社团检测算法大都难以得到令人满意的社团划分。其原因是当网络中的社团结构不明显时,社团内边的数目与社团间边的数目的差异性变小,社团的独立性变弱。本文针对这种情况,提出了基于局部团加边删边的社团检测算法和基于中心节点链路预测的社团检测算法。本文主要研究工作总结如下:(1)当今存在的大部分社团检测算法社团结构明显的网络中,大都能表现出较高的精度。但当网络的社团结构不明显时,社团检测算法性能都出现了急剧下降的问题。针对上述问题,本文提出了一种基于局部团加边删边的社团检测算法,简称CSE。CSE算法通过找到网络中的局部社团,来得到更完整的社团信息,在局部团之间按照一定的策略加入或者删除一些边,使得社团内的边增加,社团间的边减少,让网络的社团结构比原始网络的社团结构变得更加明显,在一定程度上强化了网络的社团结构。通过实验验证,CSE算法在计算机生成数据和真实网络数据上都表现出了较高的性能。(2)链路预测算法作为复杂网络研究的分支,其主要是预测网络中存在但未被发现的连边,以及未来可能出现的连边。链路预测具备改变网络结构的特性。由于链路预测算法预测得到的连边并不一定是社团内的边,也有可能是社团间的边。基于此,本文提出基于中心节点链路预测的社团检测算法,简称CLPE算法。CLPE算法根据网络的中心节点来缩小链路预测的范围,并且提出了一种更充分考虑了社团特性的预测指标完成加边操作,同时进行删边操作,最后通过社团扩充的方式得到社团划分。通过实验验证,CLPE算法在计算机生成数据与真实数据上的性能表现较好。

关键词： 复杂网络   社团检测   矩阵分解   节点属性   半监督信息  

摘要： 现实世界的许多复杂系统可以抽象为复杂网络,社团结构是复杂网络的一个重要性质。研究社团结构对于理解复杂网络的拓扑结构与功能特性具有重要意义。真实的网络结构通常比较稀疏,部分网络的社团结构不够明晰。现有的社团检测算法大多只考虑网络拓扑,在处理稀疏网络和模糊社团时具有局限性。网络中未被充分利用但广泛存在的节点属性与半监督信息,可有效地弥补结构信息的不足。因此本文融合节点属性与半监督信息,对社团检测算法进行研究。主要工作如下:首先,提出了一种融合节点属性的半监督社团检测算法(SCDAN),基于非负矩阵分解模型,将网络拓扑、节点属性与半监督信息有效地融合在统一的目标函数中,实现了结构与内容信息、半监督与属性信息的互补。其次,推导出目标函数对应的更新规则,利用KKT条件优化目标函数,进而得到较为准确的社团检测结果。并用实验验证了网络结构、节点属性与半监督信息三者均对社团检测结果有不同程度的提升。最后,在真实数据集上对模型进行验证,与多种对比算法进行比较分析,证明SCDAN算法在社团检测的准确度和稳定性上具有优越性。并且该算法可获得社团的具体属性,对社团的真实语义进行解释。另外研究了半监督信息的比例对社团检测结果的影响,同时对实验参数进行了敏感性分析。最后利用Aminer数据集进行实证分析,提取社团语义信息,探究生物方面几个子领域各自的研究重点与研究兴趣,为研究者进行科研活动提供参考。综上,本文基于非负矩阵分解模型,提出了融合属性信息的半监督社团检测算法,具有较高准确率与稳定性,可对社团进行语义解释。

关键词： 复杂网络   社团检测   模块密度   化学反应优化算法  

摘要： 随着社会科技的迅速发展,复杂系统已经遍布我们生活的方方面面。复杂网络作为复杂系统的一种抽象表现形式而存在,它通常可以抽象为图的形式,即把节点表示为对象,节点之间的连线表示节点之间存在的一定联系。而社团结构又是复杂网络的一个重要特性。一般情况下,社团内部的节点之间连接比较紧密,社团之间的节点连接都比较稀疏。因此发现复杂网络内部的社团结构,对理解网络的拓扑结构和作用具有非常重要的意义。复杂网络社团结构划分算法主要是发现复杂网络中真实存在的社团结构,研究人员提出了一系列的算法来检测复杂网络中潜在的社团结构,以便更好地分析复杂网络。传统社团发现算法大多选择模块度作为社团结构的评判函数,近年来有关研究表明模块度存在一定的分辨率问题,为了解决该问题,有关研究人员提出了模块密度作为新的社团评判函数。本文选择模块密度作为社团结构的评判函数,采用化学反应算法,提出了一种新的社团结构检测算法。本文主要工作及创新点如下:(1)研究了复杂网络社团的评判函数及其相关的一些社团结构发现算法。社团结构作为复杂网络的一个重要方面,研究者提出了很多发现算法,寻求最优划分方法一直是研究重点。论文研究了相关算法各自的优点及缺点。(2)研究了化学反应优化算法。化学反应优化算法是计算机领域与化学领域相结合而孕育出来的,是一种元启发式算法。该算法模拟了化学反应中分子与分子间的相互作用,通过寻找整个分子集中的最小分子势能得到最优解。(3)提出了基于化学反应算法优化模块密度的复杂网络社团检测算法。本文利用模块密度作为适应度函数,采用化学反应优化算法,设计实现了单分子撞墙反应算子、单分子分解反应算子、多分子交换反应算子和多分子合成反应算子。实验结果表明,与几种经典的算法相比,所提算法划分结果更加精确高效。(4)引入精英保留策略,从而提高算法的收敛速度。在化学反应算法中,由于分子动能的存在,使得原本结构较好的分子在反应过程中改变为相对结构不优的分子。这种现象使分子种群丰富,但有可能在有限的迭代次数中找不到最优解,使得算法收敛速度比较慢。精英保留策略在分子反应前搜寻最低势能分子,保留下来,在下次反应迭代前用势能最低分子替换掉势能最高分子。(5)引入爬山局部搜索算子,提高算法局部搜索能力。化学反应优化算法具有良好的全局搜索能力,为了提高其局部搜索能力,在算法中加入爬山法局部搜索法作为局部搜索算子,使得算法更加精确高效。

关键词： 社团检测   灰狼优化   标签传播   重叠社团  

摘要： 研究人员发现复杂网络中有一些具有相同功能或属性的节点,这些节点聚集在一起形成具有特定功能的模块,节点集合称为社团。复杂网络可以划分为若干个社团组成的社团结构,该结构是复杂网络重要的特征。通过分析社团结构,可以加深对复杂网络的拓扑关系与模块功能的了解,有助于解决生活中的实际问题。近年来,研究人员从谱分析方法、基于标签传播的方法、随机游走方法、网络动力学方法和基于优化的方法等不同角度提出了多种社团检测算法,其中有一类基于群智能优化算法的社团检测算法表现突出。本文对传统算法和基于群智能优化算法的社团检测算法进行了分析,提出了基于灰狼优化算法的两种社团检测算法。(1)基于离散化灰狼优化算法并利用标签传播思想的非重叠社团检测算法GWO-net:针对非重叠社团检测问题,将灰狼优化算法的编码和相关公式离散化,使用两种基于标签传播思想的初始化方法,并加入突变操作和爬山搜索策略,设计了用于检测非重叠社团结构的GWO-net算法。其中离散化灰狼优化算法框架,使用线性的离散化编码,用以表示非重叠社团结构。算法定义了进化过程的数学公式和相关操作,并使用模块度密度作为目标函数,评价非重叠社团结构的优劣。搜索节点在进化过程中,不断优化目标函数,最终得到质量较高的社团结构。两种初始化方法,一种作用于网络全局,倾向于得到精度较高的社团结构;一种作用于节点局部,倾向于得到得到多样性较强的社团结构。算法在迭代时对最优搜索节点使用爬山搜索策略,以增强算法的局部搜索能力。算法在进化后期加入突变操作,以保持种群多样性。为验证GWO-net算法性能,本文在一些实际网络数据集上进行实验,并将算法的检测结果与其它一些非重叠社团检测算法的结果进行对比,结果表明GWO-net可以得到精度较高的社团结构,相比其他算法具有明显优势。(2)基于离散化灰狼优化算法并利用节点邻居社团内度之和的重叠社团检测算法OLGWO-net:在GWO-net的基础上,针对重叠社团检测问题,定义了非线性离散化编码和相关公式,使用节点邻居社团内度之和及其标准差寻找重叠节点,设计了用于检测重叠社团结构的OLGWO-net算法。框架使用非线性离散化编码,使搜索节点的每一维可以存储多个社团的类标。算法定义了灰狼优化算法中进化过程的数学公式和相关操作,使用扩展模块度作为目标函数,用以评价重叠社团结构的优劣。为寻找网络中的重叠节点,算法使用节点邻居社团内度之和,衡量节点与周围社团联系的紧密程度,并使用节点邻居社团内度之和的标准差判断节点与周围社团联系是否平衡,当节点与邻居社团联系紧密且平衡时,节点被划分为重叠节点,然后获得网络的重叠社团结构。算法对最优搜索节点使用爬山搜索策略,该策略在种群进化前期倾向于探索非重叠社团结构,在进化后期倾向于探索重叠社团结构。为了验证算法性能,本文将OLGWO-net在实际网络数据集上进行实验,与一些重叠社团检测算法的检测结果进行对比。结果表明,OLGWO-net可以检测出较为合理的重叠社团结构,具有较强的重叠社团检测能力。

关键词： 复杂网络   社团检测   核心顶点   社团结构  

摘要： 现实世界中有许多事物都可以被视为复杂网络,如社会交际圈、论文的引用关系、生物之间的联系、航空线路等。社团是复杂网络中一个最典型的特征结构,社团之间的相互联系决定了复杂网络的构成。通过对复杂网络中社团的研究,可以探索出复杂网络潜在的规律,同时,可以从复杂网络的内部构造中进一步了解网络的性质。社团检测是理解复杂网络的重要方法,可以为现实生活中的很多复杂问题提供解决思路。因此,研究社团检测算法不仅在学术上具有重要的理论意义,而且在实际生活中具有重要的现实意义。目前许多社团检测算法都可以识别复杂网络中的社团结构,本文对已有的社团检测算法进行了深入的研究,发现了算法中的一些问题与不足,如参数难以确定、时间复杂度过高、检测精度较低等。针对这些算法中存在的缺点,提出了两个无需输入任何参数的社团检测方法。第一个是基于PageRank的核心顶点扩张社团检测算法(CEPR)。CEPR关注的是如何检测到尽可能准确的、高质量的社团结构,以改善一些社团检测算法检测精度不高的问题。该算法将相似的顶点分配到同一个社团后,再利用PageRank算法发现复杂网络中的核心顶点并进一步划分为核心社团,然后把剩余未标记的顶点按照度的大小加入到核心社团中,最后通过社团间的合并形成稳定的社团结构。实验部分在九个包含不同结构、不同规模的网络数据集上,与四个算法进行了比较。而且,还利用三种常用评价指标对CEPR进行了全面的评价,展示了该算法的有效性。实验结果表明,CEPR整体上比对比算法更优,能更准确地检测出社团结构。第二个是基于局部密度的核心顶点扩张社团检测算法(CELD)。CELD注重的是如何从复杂网络中快速地获取准确的、合理的社团结构,以克服一些社团检测算法时间复杂度较高的缺点。CELD定义了一个选择核心顶点的局部密度公式,即顶点的局部密度与其邻居的个数成正比,与邻居点到该点间的距离和成反比。该算法先将相似的顶点放到一个社团中,接着根据局部密度对顶点进行排序并将密度较大的顶点视为核心顶点,然后将剩余的顶点分配到核心社团,最后通过合并社团得到合理的社团结构。本文在实验部分与四个社团检测算法在六个有真实社团结构、三个无真实社团结构的大网络数据集上进行了比较显示,同时通过三种评价指标对该算法进行了评价。实验结果显示,CELD拥有较低的时间复杂度,并且结果大多数情况下优于对比算法。两个算法都可以在无需任何输入参数的条件下,得到更准确的社团结构。其中,CEPR算法能够合理的选择核心顶点,而CELD算法能够在较低的时间复杂度下更高效地工作。

关键词： 动态网络   增量聚类   社团检测   连接密度  

摘要： 复杂网络作为刻画现实世界复杂系统的工具,已经广泛用于社会学、生物学等领域。但是真实的复杂系统是随着时间缓慢变化的,将不同时刻的系统进行建模,并按照时间排序即可得到动态网络。社团是网络的一个重要特征,对动态网络进行社团挖掘,可以使人们更好地了解网络的特征及其演化规律,有重要的理论价值与实际意义。然而,如果使用传统的聚类算法,会忽略相邻时刻网络间的关系;演化聚类的算法准确度高,但是受限于时间复杂度,在大规模网络中并不适用;增量聚类算法利用动态网络缓慢变化的特点,基于前一时刻发现的社团结构,避免了对网络中全部节点的重新划分,不仅有效降低了时间复杂度,还保证了相邻时刻社团检测结果的一致性。本文提出了一种基于增量聚类与连接密度的动态网络社团检测算法IPSCAN。工作主要分为两部分,首先,根据动态网络中边的增删对节点结构相似性与相似度值的影响,分析了边更新影响的区域,重新定义了增量节点的集合。然后,将增量节点集合中的节点根据相似度值分为核心节点与非核心节点,当处理某一时刻新增的核心节点时,尝试从此节点扩展并判断是否生成新社团,克服了IC等增量算法社团数目固定、不能发现新出现的社团的缺陷。通过对时间复杂度的分析发现IPSCAN算法具有增量算法高效率的特点。对本文提出的算法在合成数据集与真实数据集上进行实验,从准确性与时间复杂度两方面验证算法的性能,并与演化聚类算法Facetnet、增量聚类算法IC及DABP进行对比。例如在真实动态网络数据集Football上,IPSCAN算法得到的社团结果的模块度比Facetnet算法高5%,比IC算法高12%,比DABP算法高11%;在大规模真实数据集DBLP上的结果显示,本文算法得到的社团结果的模块度比DABP算法高11%,且显著高于IC算法,而IPSCAN算法在每个时刻的运行时间控制在6秒以内,DABP算法的运行时间最高达67秒。实验结果表明,IPSCAN算法的准确度高于IC算法,而DABP算法虽然可以发现新社团,但是准确度低于IPSCAN算法,且时间效率比IPSCAN算法低。本文提出的算法不仅具有良好的社团检测能力,可以发现新出现的社团;而且还具有增量算法高效的优点,可以用于大规模动态网络的社团发现。

关键词： 社会网络   区块链   社团检测   信息传播   资源请求   个人意愿  

摘要： 随着以互联网为主的社会网络的广泛应用,越来越多的人们参与社会网络的信息传播和信息获取。以Facebook、Twitter、新浪微博等为代表的在线社交软件,它们急剧增加的用户数量和信息传播量,给社会网络的应用研究带来了新的活力。本文基于个人意愿提出了社会网络社团检测和信息传播方案以及基于区块链的社会网络社团资源请求机制。个人意愿对于形成网络社团和传播信息有着重要的影响力,因此本文提出一种基于个人意愿的社团检测和信息传播方案。该方案中的社团检测算法提取了节点属性,利用模块度、兴趣度和个人意愿进行更精细的社团检测;同时,该方案建立的信息传播模型在指数模型的基础上提取边特征和节点特征构建属性向量,以个人意愿和社团意愿构建意愿向量,并以传播概率和传播延迟构建模型基本关系,从而使得该模型实现了基于个人意愿的信息传播。在社交网络中,用户的需求和人际关系变得非常丰富,因此社交网络可以通过一些社交软件向用户快速传播各种信息,同时也产生了版权控制与网络数字资源免费共享的直接矛盾。因此,本文基于区块链提出了社团资源请求机制,实现了社团共享网络数字资源,在区块链的基础上,该机制保证了网络数字资源每笔交易的可靠性和公平性,网络数字资源交易可以通过社团进行自动交易支付,并基于区块链智能合约制定了一个激励机制,鼓励社团成员传播网络数字资源。本文对社团检测和信息传播进行实验验证,实验结果表明,加入个人意愿的社团检测和信息传播方案,能够保证社团检测的稳定性和可靠性,能够实现用户间信息传播的主动性和有效性。本文对区块链的社会网络社团资源请求机制进行安全分析,充分分析了该机制的安全漏洞以及该机制如何能够有效的进行防范,保证了该机制的有效性和安全性。

关键词： 复杂网络   社团检测   非负矩阵分解   半监督学习   图正则  

摘要： 社团结构对分析和理解复杂网络的性质和功能具有重要的作用。因此社团检测成为复杂网络分析的一个有效工具,同时也是计算机科学等不同领域广大研究者关注的一个研究热点。然而,由于网络的稀疏性和噪音性,导致网络的社团存在结构模糊、大小不平衡等问题,从而仅依赖于拓扑结构的社团检测不仅不能精确地识别出这样的社团结构,而且不能从语义上理解每个社团的实际意义。针对网络中模糊或不平衡性社团检测问题,本文通过融合少量可用的半监督先验、内容等辅助信息来指导复杂网络的社团检测,研究了一类融合辅助信息的社团检测模型,主要研究内容和创新点可概括为下述三条:1)融合强化网络结构的拓扑相似性信息,本文提出了图正则非负矩阵分解社团检测模型。基于网络的全局和局部拓扑结构,该模型定义了一个新的相似性指标作为辅助信息,并根据图正则的思想将其融入非负矩阵分解模型进行社团检测。生成网络和真实网络上的实验表明,拓扑相似性能强化原始网络中稀疏的拓扑结构,从而有助于提高模糊社团结构(如zout=10的GN网络)的检测精度。2)融合成对约束先验信息并引入节点流行度,本文提出了流行度修正的半监督非负矩阵分解社团检测模型。通过引入流行度来减轻度异质性对一定连接先验信息利用率的影响,本文提出一定连接约束的社团检测模型。进而,考虑到一定不连接先验对社团检测的提升作用,本文通过构建负网络的思想,又提出一定连接和一定不连接同时约束的社团检测模型。这两个模型能够更充分地利用半监督先验信息,尤其对网络中模糊且不平衡的社团,具有更高的检测精度。3)进一步融合节点的内容信息,本文提出了一个融合辅助信息的社团检测及语义信息匹配框架。为了从语义上更好地理解社团的实际意义,针对社团检测和社团语义匹配问题,该框架首先利用半监督先验信息和节点的内容信息分别得到一个精度较高的拓扑驱动的社团结构和一个内容驱动的社团结构,进而引入两者之间的耦合关系矩阵修正社团结构的同时实现社团和内容的准确匹配。本文提出的四个社团检测模型不仅丰富了稀疏网络社团检测的方法体系和研究框架,还为模糊且不平衡等较复杂社团结构的识别提供了理论依据,尤其在恐怖组织、犯罪团伙识别等公共安全领域具有重要的应用价值。

关键词： 复杂网络   社团检测   图数据   并行化  

摘要： 随着计算机与互联网技术的不断发展,网络已成为人们日常生活不可或缺的一部分。人们现实生活中的大部分数据都可用网络或图(Graph)来表示,如通信网络,交通网络、社交网络、生物网络等。社团结构是复杂网络的一个重要结构特征,研究这些社团结构有利于更好地理解复杂网络的功能与特性。此外,复杂网络在社团结构层面通常会显示出一些单个节点或整个网络层面所不具备的特性。为了更深入地研究复杂网络,捕获更多有意义的潜在信息,需要使用社团检测技术。然而随着节点数量不断增加,网络结构不断复杂,传统的社团检测算法已不再适用于大规模复杂网络。而分布式并行处理技术为处理大规模复杂网络提供了有效手段。因此,研究复杂网络的社团检测并行算法对深入理解网络结构与性质具有重大理论意义与实际价值。基于上述原因,本文提出了一种针对大规模复杂网络的并行化社团检测算法——Parallel LPA-Attractor算法(简称PLA)。在设计这种算法的过程中涉及图表示、分割、存储、计算以及结果融合问题,其中最重要的是单个计算单元的社团检测算法。在对现有的社团检测算法进行多方面的权衡比较后,本文采用Attractor算法作为核心计算算法。但该算法会检测出大量单节点社团,本文提出的LPA-Attractor算法(简称LA)利用标签传播算法LPA进行预处理改进这一问题。针对LPA算法只能发现非重叠社团的缺陷,本文提出一种改进型算法Adjustable Multi-Label Propagation Algorithm(简称AMLPA),使节点携带多标签来检测重叠社团。在算法并行化的其他方面,针对已有的图表示方法不再适合于并行及大规模运算的问题,本文提出了耦合表的图表示方式,耦合表可使数据得到更高效的利用,提高计算速度;PLA算法使用METIS图分割算法对输入的图数据进行分割;在数据存储方面,本文提出一种改进的分布式存储方式,利用节点的深层复制解决了现有图数据的分布式存储方法通信开销大的问题;此外对并行处理的结果提出了有效的合并方案。相关实验结果表明,本文所提的并行化社团检测算法有效地减少了计算时间,具有时间复杂度较低,准确率较高等优点。其中核心计算算法LA大幅度地减少了单节点社团的发现数量。因此,PLA算法为解决大规模复杂网络的并行化社团检测问题提供了一种有效的解决方案。