关键词： 复杂网络   社团检测   图卷积神经网络   模块度   图生成模型  

摘要： 现实世界中大量的复杂系统可以抽象成复杂网络,因此针对复杂网络的研究一直是信息领域的热点问题,而社团结构作为复杂网络的一个重要特征,对其进行深入研究有助于理解复杂网络的结构和功能特性。近年来,相关领域的学者们提出了很多用于复杂网络社团结构检测的算法,这些研究成果被应用于计算机科学、社会科学、生物科学等多个领域。随着深度学习的发展,学者们提出了图卷积神经网络,该网络能够提取拓扑结构中的高阶特征,弥补传统神经网络不能处理非欧空间数据的缺点,推动了深度学习在图结构数据中的应用。目前针对图神经网络的研究大多集中在有监督和半监督学习领域,针对无监督的社团检测任务研究相对较少。此外,基于深度学习的社团检测方法也集中于非重叠社团的检测,而缺乏针对重叠社团检测的研究。本文提出了两种基于图卷积神经网络的社团检测方法,适用于具有高维属性信息的大规模图结构数据,主要工作如下: (1)针对传统社团检测算法不能提取非线性特征的问题,提出了基于模块度的图卷积非重叠社团检测算法CDMG。该算法使用图卷积神经网络结构来提取图结构和节点属性中的高阶信息,生成隐藏的节点嵌入表示。同时应用了图池化技术,通过迭代粗化来处理图的层次性质,将相似的节点进行聚合。算法采用最大化模块度的概念来定义损失函数,使用了一个能够计算梯度的松弛的模块度公式,从而能够实现端到端训练来捕获图结构和节点特征,完成社团结构划分。 (2)为了解决重叠社团检测问题,提出了一种基于生成模型的重叠社团检测算法OCDGM。算法采用了深度自编码器架构,编码器部分由两层的图卷积神经网络组成,通过输入拓扑结构和节点属性特征来获取节点社团归属和隶属强度两种嵌入表示。解码器部分采用伯努利-泊松生成模型来重建图形结构,通过最小化重建损失来得到可能性最大的社团划分。算法还添加了一个正则化项,以提升高相似度的节点划分到同一社团的概率。 (3)通过在人工数据集和真实网络上进行对比试验,表明本文提出的两个算法具有良好的社团检测性能。此外,为了验证算法在实际应用中的检测效果,本文还将两种社团检测算法应用于公共安全领域,在犯罪团伙的识别任务中取得了较为理想的效果,为社团检测在公共安全领域的应用研究提供了一定的参考价值。

关键词： 复杂网络   社团检测   节点相似度   节点密度   节点吸引力  

摘要： 复杂网络是对复杂系统的抽象表示,其反映出复杂系统中各个个体间的连接关系。社团作为复杂网络的基本功能,普遍存在于实际网络中,通过挖掘社团结构,有助于认识网络功能和研究网络拓扑结构,以此揭示复杂网络中存在的潜在规律,预测复杂网络的演化趋势,因此对于复杂网络社团检测研究具有重要实际应用价值。专家们从各个角度入手,提出了种类繁多的社团检测算法,在基于节点相似度社团检测的这类算法中,其本质是对节点相似度的度量,但现有基于节点相似度的这类算法都存在着不同程度的缺陷。本文通过改进节点相似度的度量和融合聚类算法的框架,分别设计以下两种算法。(1)针对传统依靠节点邻居衡量节点相似度准确性低、随机选取聚类中心节点导致最终社团检测质量不稳定等问题,提出一种基于节点密度和相似度的社团检测算法。算法考虑到节点最短路径对节点相似度的影响,给出一种结合节点邻居和节点最短路径来改进节点相似度的度量方法;定义节点密度,为聚类中心节点的选取提供依据。首先根据节点密度最大且节点之间相似度小的原则选取初始聚类节点,然后利用最大相似度原则进行社团划分,最后以优化模块度为指标进行社团检测。(2)为了解决传统依靠节点边权值衡量节点相似度准确性低、社团评价指标单一等问题,提出一种基于吸引力的节点相似度社团检测算法。算法依据节点吸引力计算出节点的结构相似性,依据K模式的简单匹配计算出节点的属性相似性,结合节点结构相似性和属性相似性来计算节点相似度;引入社团密合度,当作社团合并时的评价指标。首先根据节点密度最大原则选取聚类中心,然后以节点相似度对社团进行初始划分,最后根据最优社团密合度合并社团,直到社团密合度不再增加,此时得到社团检测结果。为了验证上述两种算法的性能,本文分别在人工网络和真实世界网络中进行了充分的实验,并且对所得到的实验结果和其他算法进行了深入对比,实验结果表明,本文所提的两种算法均能有效的检测出高质量的社团结构。

关键词： 社团检测   局部优化   种子节点   节点重要性   节点相似性  

摘要： 社团检测旨在发现复杂网络中最突出的结构特征,可广泛应用于计算机科学、生物学、医学等多个领域,为人类探索网络的本质,应对网络社会的挑战提供重要的理论依据。启发式的社团检测算法主要包括基于全局优化的算法和基于局部优化的算法,其中基于局部优化的算法由于具有良好的时间效率,受到广泛的关注。为进一步提升此类算法的准确性和稳定性,本文分析当前局部优化算法存在的缺点,提出两个基于局部优化的社团检测算法,主要的研究工作如下:（1）提出基于种子节点和引力的局部优化算法LOSG,在种子选择阶段,将局部重要性和全局重要性指标相结合挑选种子节点,避免随机选取种子节点导致的社团划分结果缺乏稳定性的问题,提高了算法稳定性;在社团扩展阶段,将节点的属性和万有引力定律结合,定义节点引力指导邻近节点扩展进社团,避免将邻居节点直接扩展进社团导致准确性不高的问题;在后处理阶段,通过边界节点重新分配和将小社团与其连接边数最多的相邻大社团合并的方式,提高算法的准确性。当前部分社团检测算法需要提前设定社团划分数量,但此参数难以确定,LOSG算法不需要指定社团划分数量,提高了算法在不同网络场景的适用性。（2）提出基于节点相似性和种子节点的局部优化算法LONS,在种子选择阶段,将节点自身和邻居结点的影响结合,使用LH-index算法衡量节点重要性,通过节点过滤的方式挑选种子节点,算法具备良好的稳定性;在社团扩展阶段,将种子节点作为初始化社团,构建节点对相似性序列,根据节点相似性完成社团扩展;在后处理阶段,LONS继承LOSG算法的边界节点分配和小社团合并的方法,算法具备较高的准确性。另外,LONS算法不需要设置任何参数,对多种网络场景具备良好的适应性。（3）在多组人工数据集和四种真实数据集上分别将LOSG算法和LONS算法与经典社团检测算法进行比对分析,通过标准化信息NMI和模块度Q验证本文算法的稳定性和准确性。

关键词： 隐藏社团结构   社团检测   HICODE   模块度   理论研究  

摘要： 在现实世界中,存在着各式各样的系统,这些系统往往可以抽象成图论中的网络。从网络中寻找到有价值的社团信息是重要且有意义的。近几十年来,社团检测在社会学、生物学、流行性疾病学等研究中被广泛研究并得到了快速的发展,出现了许多揭示网络结构算法。这些方法大多数用于不重叠或重叠的社团结构,或从全局社团结构转换为局部社团结构。2015年,何琨等人提出了一种新的图论概念:“隐藏社团结构”。如果一个社团的大部分成员属于更强大的社团,这个社团被称为隐藏社团。一个社团的强大可以通过一些社团度量指标如模块度来定义。他们还提出了一种既能探测显层结构也能探测隐藏结构的框架HICODE(Hidden community detection)。但是他们仅通过实验对HICODE的有效性进行了说明,并没有从理论上去证明。本研究对隐藏的社团结构进行了全面而系统的理论分析;提出了多层随机块模型作为现实网络的抽象,其中每一层都是网络节点的一组不重叠的社团划分(最强的一层是显层,其他所有层都称为隐藏层);同时,从理论方面证明了与等效随机噪音相比,隐藏结构噪音会使得显层划分的模块度更低,并且带隐藏结构噪音的网络会呈现双峰的结构。这解释了为什么隐藏结构噪音会导致传统社团检测算法检测显层更加困难;另外在两层,三层,多层随机块模型上证明了对目标层外某层和对目标层外所有层使用弱化方法(移除内边、削弱内边、削弱权重)后,目标层的模块度上升。这展现了HICODE在带隐藏结构噪音的随机块模型上的有效性,体现了HICODE不仅可以探测隐藏结构,同时可以提高显层的探测准确度;最后在两层和三层随机块模型上进行了HICODE的仿真,再次验证了HICODE算法的有效性。

关键词： 数据聚类   演化计算   社团检测   文化基因算法  

摘要： 演化计算是一种适用于求解复杂、高维、大规模问题的全局搜索算法。通过将数据向量模拟为生物中的基因型,模拟自然界中物种的进化过程,对数据向量进行交叉、变异等操作,并从新生成的个体以及原有个体中选取更加适应环境的个体作为新的种群,从而不断迭代对数据进行优化,最终寻找全局最优解。在聚类问题中,作为一种经典的全局优化算法,演化计算提供了强大的求解办法。根据应用的场景,聚类算法又可以分为在向量空间和图空间上的应用:在向量空间上,本文发现演化聚类算法中的个体编码方案存在冗余和不一致的问题,不仅浪费了搜索资源,而且扰乱了个体之间的相互学习过程。为了解决聚类冗余的问题,本文提出了一种基因序列重排列的方法。该方法首先选取当前适应度最佳的参考向量,然后根据每个个体内的基因到参考向量的距离,重新排列基因型的编码顺序。这样,每个个体所代表的聚类方案是统一且相互对应的,从而消除冗余并解决算法中个体间相互学习不一致的问题。结合以上方法,本文针对基于距离的凸聚类和基于密度的非凸聚类两种不同类型的聚类算法进行改进,开发了一种通用的演化聚类框架。实验表明,该方法可以有效地提高演化聚类算法在不同形状数据集上的性能。另一方面,在图空间上,演化算法使用局部邻接编码方案时由于相邻的类之间存在连接的边,导致随机选取邻接边的过程中会将本应属于不同类的节点错误地选取到同一类中,造成不可行解的产生。针对以上问题,本文设计了一种基于线图的边关闭局部邻接编码方案,通过在邻接列表中引入假想空边的概念临时关闭部分边,从而获取正确的局部划分方案。另外,本文设计了一种启发式的初始化策略,对于邻接边的选择更倾向于与当前边更接近或在簇中处于更中心位置的边,以加快算法的收敛速度。基于以上编码方案和初始化策略,本文提出一种基于线图的文化基因算法LGMA(Line Graph Memetic Algorithm),该方法在经典文化基因算法的基础上,使用模拟退火算法和带有精英策略的爬山算法进行局部优化。实验结果表明,基于线图的文化基因算法可以有效地解决节点划分错误的问题,提高文化基因算法在图聚类中的搜索精度和稳定性。

关键词： 移动社会网络   重要节点识别   社团检测   传播模型   局部密度聚类  

摘要： 移动社会网络作为移动通信网络和社会网络的交叉网络,支持移动用户间的数据或信息传输。一方面,幂律分布的普遍存在性使得移动社会网络中用户的重要性存在差异;另一方面,社团结构的普遍存在性使得移动社会网络中用户的相似性得以体现。然而,如何有效利用这一特定场景下的数据信息来实现重要节点的识别和社团检测等问题仍未得到有效解决。因此,本文的研究主要针对移动社会网络中重要节点识别和社团检测问题。与网络中其它节点相比,重要节点往往可能会影响网络的结构,甚至对其功能产生较大的影响。此外,他们在信息传播中也起着决定作用。节点的重要性序列就是按照相关指标值进行排序从而生成的节点序列。重要节点往往容易吸引其他节点依附在其周围,进而形成社团。社团是指处于宏观网络和微观节点之间的一种结构,具有内部连接紧密而外部连接稀疏的特点,理解其结构有助于我们更好地检测社团。1.针对移动社会网络中现有重要节点识别方法未充分考虑节点活跃度,从而导致未能精确识别重要节点的问题,提出一种基于节点活跃度的重要节点识别方法。该方法分别从节点的拓扑结构和行为特性两个角度出发,给出了节点活跃度的定义,并筛选出活跃度较大的节点作为种子节点。然后使用SIS(疑似感染-感染-疑似感染)传播模型对信息传播过程进行了模拟,并对种子节点的传播能力给出了度量。通过对四个真实数据集上的实验结果分析可以发现,与现有的基于中心性的方法和基于优化的方法相比,所提方法能够保证在不提高复杂度的情况下更有效地识别出重要节点。2.针对移动社会网络中现有节点影响力评估方法未充分考虑拓扑结构和社会属性,从而造成评估社会影响力比较片面的问题,提出一种基于拓扑结构和社会属性的重要节点识别方案。该方案分别从节点的拓扑结构和社会属性两个角度出发,给出了节点间相似度的定义和改进的节点网络约束值。在此基础上,进一步给出了节点社会影响力的定义,并筛选出社会影响力较大的节点作为种子节点。然后使用SIR(疑似感染-感染-恢复)传播模型对信息传播过程进行了模拟,并对种子节点的传播能力给出了度量。通过对四个真实数据集上的实验结果分析可以发现,与现有的方法相比,所提方法能够更为精确地识别出重要节点。此外,我们还从网络鲁棒性的角度对所提方法的效果进行了验证。3.针对移动社会网络中现有社团检测算法忽略节点的社会属性和行为特性对社团形成的影响,从而导致部分社团划分精度不高的问题,提出一种基于局部密度聚类的社团检测算法。该算法分别从节点的拓扑结构、社会属性和行为特性三个角度出发,将网络中的节点映射为聚类算法中的数据点,相应的,节点在上述三个角度的值映射为节点对应的三个维度上的特征。在此基础上,借助基于局部密度聚类的算法来进行社团检测。通过对四个真实数据集上的实验结果分析可以发现,所提方法能够有效检测到社团,且在模块度和标准互信息指数两个指标上具有一定优势。

关键词： 社团检测   谱方法   节点重要性   随机游走   通话记录   公共安全  

摘要： 真实世界中的各类系统往往可以结合图论映射到一个网络中,网络中的节点和拓扑结构反映了真实世界的成员及其关系,其中,最为显著的特征就是网络的社团结构。近年来,许多用于挖掘复杂网络中的拓扑结构特征及隐含关系的社团检测算法被提出,其成果被广泛应用于生物科学、社会科学等诸多领域。同时,由于真实世界中,网络中的节点在结构上和功能上差异巨大,对网络中的核心节点的精确识别,在控制谣言传播、遏制疫情传播、广告投放等领域具有重要意义。本文在研究现有社团检测算法的基础上,聚焦于通话网络,结合公共安全领域的实际需求,提出了一种针对通话网络的社团结构检测算法,同时结合随机游走理论提出了一种针对通话网络的核心节点挖掘算法,主要研究内容及工作包含以下几个方面: (1)为了提升社团检测算法在通话网络上的准确率,本文提出了基于谱方法的社团检测算法,该算法首先将目标人群的通话记录根据通话时间映射多个到图中形成多个复杂网络,结合节点间的通话时长和通话频次两种特性,使用图分割方法将每个网络划分成数个不重叠的社区,最后根据每个节点的隶属社团进行投票,得到每个节点最终的归属社团。在公开数据集和真实通话记录上的实验结果表明,本文提出的基于谱方法的社团结构检测算法可以有效刻画网络中的社团结构。 (2)针对已知社团结构的网络,本文以社团内部核心节点挖掘为目标,提出了基于不等概率随机游走的核心节点挖掘算法,该算法以信息在网络中的传播过程中经过的节点作为衡量节点重要性的依据,通过刻画节点携带的信息数来挖掘网络中的核心节点。在通话记录网络和公开数据集的实验中,验证了本文提出算法的有效性。 本文研究工作参与警校合作项目“社团检测在公共安全领域的应用”,成功将基于谱方法的社团检测算法和基于随意游走的核心节点挖掘算法应用于公共安全领域,在犯罪团伙的组织架构识别和团伙核心人员的挖掘中取得了较为理想的实际应用效果,为社团检测在公共安全领域的应用研究提供了一定的参考价值。

关键词： 协同过滤   推荐算法   完全子图   社团检测   重叠社区  

摘要： 随着现代互联网信息时代的发展,网络上的信息越来越庞杂。网络的发展进步无疑是一把双刃剑,在给人们日常生活工作带来很多便利之余,也带来了信息的过载。当网络上的信息过于冗余的时候,人们常常需要从其中提取自己需要的网络信息。为了能够挖掘出更多的符合网络用户兴趣的信息,推荐算法应运而生。推荐算法被广泛应用于处理信息过滤问题,已成为复杂网络分析领域中的重要问题,它从用户的历史信息中分析兴趣模型,并基于用户的兴趣模型选择合适的项目以推荐给用户。由于现实网络的日渐庞大与冗杂,推荐算法常常会有一些不必要的计算,因此对其进行研究具有一定的现实意义。为了改进因网络规模发展而引起的推荐算法计算冗杂问题,本文提出了一种基于社团检测的推荐算法(Recommendation Algorithm based on Community Detection,RACD)。具体工作如下:(1)为了改进传统基于物品的协同过滤算法,提出了一种基于非重叠社团检测的协同过滤推荐算法模型(Recommendation Algorithm based on Non-Overlapping Community Detection,RANOCD),在对数据进行预处理后加入一个社团推荐物品检测步骤,将关联性较强的物品提前地划分到一个社区,以有效减少推荐算法计算的冗余度,之后找到待测试用户评分高于3分的物品并计算用户对其所在的社区中所有物品的预测兴趣度,得出推荐结果并对其进行分析。本文采用多种类型的社团检测算法与不同规模数据进行了实验对比,以及为适应本文研究的目标,对Louvain算法进行了基于派系的改进,在开始社团检测之前就已经对数据进行预处理从而提高了后续推荐算法的准确性。(2)在上一部分的基础上继续思考网络中重叠节点的存在对推荐算法的影响,提出基于重叠社团检测的协同过滤推荐算法模型(Recommendation Algorithm based on Overlapping Community Detection,RAOCD),在对物品关系网络进行重叠社团检测之后,找到待测试用户评分高于3分的物品并计算用户对其所在的社区中所有物品的预测兴趣度,得出推荐结果并进行分析。(3)实验选择的数据集为推荐算法常用数据集Movie Lens,为了得出准确的研究结果并进行分析,选择不同规模的数据集进行训练测试。最终实验表明,基于社团检测的推荐算法能有效的减少推荐算法的计算冗余量。在基于非重叠社团检测的推荐算法中,采用基于派系的改进Louvain算法(CLA)作为社团检测模块的算法性能较为优越。同时考虑了网络中重叠节点对推荐结果的影响,提出了基于重叠社团的推荐算法,当推荐列表长度k值较大时,RAOCD算法性能较好。实验中采用了准确率(precision),召回率(recall)以及F-score三个指标进行算法性能评估。

关键词： 股票市场   已实现波动率跳跃   轮廓系数   网络动态演化   社团检测  

摘要： 随着世界经济的快速发展,经济全球化的趋势已势不可挡。各行业之间的发展也是环环相扣紧密相连。但我国股票市场发展并不完善,某一行业的突发事件,可能会影响多个行业的股票价格。为了帮助消费者更好地了解股票之间的相关关系以及及时掌握股票市场变化情况,本文以上证380成分股2018年5月2日至2020年4月17日股票价格为研究对象,利用R软件,通过已实现波动率理论和Min RV统计量提取已实现波动率中的跳跃,利用复杂网络技术建立已实现波动跳跃动态网络,并且对所构建的动态网络进行分析。首先,本文提出了一种基于局部随机游走距离轮廓系数的网络社团检测算法(SIL算法),并给出一个新的定量函数平均轮廓来评估质量网络社团结构。通过一些具有代表性的真实世界网络和计算机生成网络(GN网络和LFR网络)来测试该算法的准确性和效率。实验结果表明,与FG、LE、FP算法相比,SIL算法可以更有效地检测这些网络的真实社团结构。其次,本文基于已实现波动率及已实现波动率跳跃相关理论提取上证380成分股的已实现波动率,对已实现波动率跳跃构建股票动态网络。接着,通过上述跳跃动态网络的统计特征(最短路径长度、聚类系数、网络异质性、度分布、无标度特性及小世界特性),分析跳跃动态网络统计特征的动态演化,并且通过中心性指标识别出演化过程的关键节点。最后,使用社团检测算法对网络进行社团结构划分,通过与其它三种社团检测算法划分结果的模块度进行比较,本文所提出的算法(SIL算法)的模块度值最大。社团划分结果表明,跳跃动态网络中的社团在演化过程中是以行业划分。通过对股票跳跃动态网络重要节点挖掘发现制造业在股票市场占核心地位,金融业、媒体行业、高新技术行业对其它行业也具有较大影响力;对股票跳跃动态网络社团结构划分结果分析得到制造业内部,制造业、房地产业和采矿业之间存在密切联系。因此,投资者想要规避风险,就要做到“不把鸡蛋放在同一个篮子里”。

关键词： 水军识别   社团检测   网络表征学习   无监督学习   社会网络  

摘要： 现如今,互联网的发展让人们已经习惯了从网络中获取各类信息。然而,网络上的信息却可能是虚假的。商业界、政界以及其他一些领域,都饱受着网络水军都带来的恶劣影响。水军识别是互联网平台健康发展不可或缺的一项任务。而另一方面,水军的行为越来越专业、智能,识别水军的难度也越来越大。他们刻意模仿正常用户的在网络中的各种行为、评论用语,这使得传统的水军识别方法检测效果越来越差。仅通过阅读评论,难以获取具有准确标签的训练数据。而且水军会根据平台治理不断调整自己的行为,水军识别模型也需要不断更新。因此有监督水军识别人工标注成本过高且可能标签不准确,而现有的无监督水军识别算法的准确度低。面对水军识别的巨大挑战及重要意义,本文根据水军越来越组织化、团体化的现状,以及水军难以模仿正常用户关系特征的本质特点去挖掘水军团体。水军团体若想要影响更多的用户,需要先制造舆论,因此需要大批水军在相近的时间对同一帖子发表相近的言论,而且他们会有多次这样的活动,这能明显区别于正常用户。据此,本文通过研究提出一种基于网络表征学习的无监督识别方法,将识别目标定位于这类具有巨大破坏力、有组织联系紧密的水军团体而忽略影响力较小的单个水军。本方法根据网络媒体或购物网站中水军团体联系较紧密、评论对象有较高相似度,而正常用户间为弱连接关系的特点,使用评论内容、用户行为等多种特征去建立用户相似性网络,并根据水军特点提出了新的基于网络表征学习的社团挖掘方法去检测网络中联系紧密的社团,并识别网络中的水军团体。在四个真实的数据集上进行实验,本研究提出的方法在各指标上都优于其他多种最新的或者经典的无监督水军识别算法,验证了本文提出的模型的有效性与准确性。