关键词： 生物领域   多层异质网络   研究团队   社团检测   关键性结点识别  

摘要： 近年来,国际上关于生物领域研究团队发展趋势研究的文献大量涌现,涉及内容及研究热点非常广泛并且呈现出了多种学科相结合的新态势,这也对其研究提出了更高的要求。基于以上背景,本课题运用复杂网络社团检测的方法,在对生物领域文献数据构建异质网络的基础上,对研究者互合著、研究机构的社团结构和关键结点进行了分析。具体工作如下:第一,基于生物领域文献数据构建了“论文-研究者-团队”的多层异质复杂网络,形式化描述了论文层、研究者层以及团队层的网络结构,介绍定义了网络统计特性指标,并对研究者网络及研究团队网络的网络统计特性进行了分析。第二,提出了一个动态网络社团检测的PPNMF算法,运用该算法对构建的多层异质复杂网络进行了社团检测。接着介绍了结点重要性评估指标c-index的形式化定义,对检测得到的社团中的重要性结点进行了识别和分析。运用可视化工具呈现出社团检测结果,标注出每个社团中的关键性结点以及这些结点之间的联系。本课题基于生物领域文献数据完成了多层异质复杂网络的构建,提出了动态网络的社团检测方法。并且分析了研究者网络和研究者团队网络的统计特性,对这两个网络进行了社团检测,识别出社团中的关键性的研究者以及研究者团队,以及分析了这些关键性结点之间的关系。最后通过可视化工具,将复杂网络社团检测及关键性结点识别的结果呈现出来。

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

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

关键词： 复杂网络   社团结构   化学反应优化算法   正交设计   模拟退火算法  

摘要： 随着复杂网络研究的发展,人们逐渐开始关注网络结构复杂性以及其与网络行为之间的关系。为了更好地理解网络结构和网络行为之间的关系,就需要详细了解网络所具备的特性。复杂网络中具有多种特性,社团结构是其中一个重要的性质,对其的深入研究在复杂网络研究领域占有重要的地位。社团结构通常表示为网络中一组节点的集合,整个网络则是由多个“团”构成的,每个社团内部节点之间的连接相对紧密,而各个社团之间的连接则比较稀疏。网络中的某些特性与社团结构关系密切,分析网络的社团结构,能够更好地了解网络结构和网络行为之间的关系。本文主要针对复杂网络中的社团结构检测问题,设计适用于发现复杂网络中隐藏的社团结构的算法,主要工作和创新点如下:1、提出了基于正交化学反应优化算法的社团检测方法。所提算法将社团结构检测问题转换为求解最低势能的优化问题,通过选择优化函数,分析社团结构的性质和特点,设计适用于社团检测问题的四个基本化学反应算子。为了避免算法早熟收敛,提高分子个体解分布的均匀性,本文基于正交试验设计对合成反应算子进行改进,将正交交叉算子作为合成反应的操作算子,其特点是利用正交表产生合成反应后的新的分子个体,提高了合成分子个体解的质量。2、将化学反应优化算法和模拟退火算法相结合,提出了一种局部搜索策略。通过将模拟退火算法作为一个局部搜索算子来提高本文算法的局部寻优能力,并且能够避免算法陷入局部最优。实验和分析表明本文算法在人工合成网络和真实网络数据中都具有较强的可行性和高效性,与传统的检测方法相比,在克服分辨率限制问题上有着显著的优越性。3、为了使实验结果的表现更加直观,本文基于Matlab GUI开发平台设计了一个社团结构的网络可视化界面。在设计过程中,本文采用了阿基米德螺线坐标方程来对网络中的节点进行布局,并且通过对这些节点进行着色来区分每个节点所属的社团。最后,通过绘制整个网络的拓扑结构图,来更方便地观察网络社团结构的划分结果。

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

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

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

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

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

摘要： 研究人员发现复杂网络中有一些具有相同功能或属性的节点,这些节点聚集在一起形成具有特定功能的模块,节点集合称为社团。复杂网络可以划分为若干个社团组成的社团结构,该结构是复杂网络重要的特征。通过分析社团结构,可以加深对复杂网络的拓扑关系与模块功能的了解,有助于解决生活中的实际问题。近年来,研究人员从谱分析方法、基于标签传播的方法、随机游走方法、网络动力学方法和基于优化的方法等不同角度提出了多种社团检测算法,其中有一类基于群智能优化算法的社团检测算法表现突出。本文对传统算法和基于群智能优化算法的社团检测算法进行了分析,提出了基于灰狼优化算法的两种社团检测算法。(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)融合强化网络结构的拓扑相似性信息,本文提出了图正则非负矩阵分解社团检测模型。基于网络的全局和局部拓扑结构,该模型定义了一个新的相似性指标作为辅助信息,并根据图正则的思想将其融入非负矩阵分解模型进行社团检测。生成网络和真实网络上的实验表明,拓扑相似性能强化原始网络中稀疏的拓扑结构,从而有助于提高模糊社团结构(如z=10的GN网络)的检测精度。2)融合成对约束先验信息并引入节点流行度,本文提出了流行度修正的半监督非负矩阵分解社团检测模型。通过引入流行度来减轻度异质性对一定连接先验信息利用率的影响,本文提出一定连接约束的社团检测模型。进而,考虑到一定不连接先验对社团检测的提升作用,本文通过构建负网络的思想,又提出一定连接和一定不连接同时约束的社团检测模型。这两个模型能够更充分地利用半监督先验信息,尤其对网络中模糊且不平衡的社团,具有更高的检测精度。3)进一步融合节点的内容信息,本文提出了一个融合辅助信息的社团检测及语义信息匹配框架。为了从语义上更好地理解社团的实际意义,针对社团检测和社团语义匹配问题,该框架首先利用半监督先验信息和节点的内容信息分别得到一个精度较高的拓扑驱动的社团结构和一个内容驱动的社团结构,进而引入两者之间的耦合关系矩阵修正社团结构的同时实现社团和内容的准确匹配。本文提出的四个社团检测模型不仅丰富了稀疏网络社团检测的方法体系和研究框架,还为模糊且不平衡等较复杂社团结构的识别提供了理论依据,尤其在恐怖组织、犯罪团伙识别等公共安全领域具有重要的应用价值。