关键词： 复杂网络   社团检测   重叠社团   标签传播   K-shell分解  

摘要： 复杂网络是由真实世界中的复杂系统抽象而成的,挖掘复杂网络的特征对理解复杂系统有重要意义。重叠社团普遍存在于复杂网络中,检测重叠社团对分析网络的特征和发掘节点的隐藏属性有很大帮助。近年来,多种检测重叠社团的算法被提出,其中基于多标签传播方法的算法因其原理简单、易于实现以及其近似线性的时间复杂度受到广泛关注,但是这种算法存在稳定性差和精度不足的问题。因此,本文对节点的拓扑结构以及多标签传播算法的标签传播过程进行研究,提出了两方面的改进措施,以进一步提高多标签传播算法的精度和稳定性:（1）提出一种基于双层过滤策略的节点标签更新算法。本文对多标签传播算法中节点更新标签这一行为进行分析,设计了一种双层过滤策略,该策略的第一层用于帮助节点过滤接收标签,第二层用于帮助节点选择传播标签。然后基于双层过滤策略提出一种节点标签更新算法,以提高多标签传播算法的精度。（2）生成两种不同的节点更新顺序。本文对K-shell分解算法进行研究,提出了改进的K-shell分解算法。然后基于节点邻居关系和改进的K-shell分解算法提出两种节点社团中心性NC和NCK,并根据NC和NCK分别生成两种不同的节点更新顺序,以提高多标签传播算法的稳定性和精度。基于上述的两项措施,本文提出MLPA-DF和DFKS这两种改进的多标签传播算法。使用人造网络数据集和真实世界网络数据集对这两种算法进行实验,并用NMI指标和Q指标对实验结果进行评估。实验结果表明,MLPA-DF算法和DFKS算法有良好的稳定性。并且MLPA-DF算法在部分人造网络上的NMI指标比经典的多标签传播算法（COPRA算法、SLPA算法和LPANNI算法）提升5%到10%,在部分真实世界网络上的Q指标比经典算法提升1%到3%。而DFKS算法的NMI指标和Q指标比MLPA-DF算法有进一步提升,但是需要更长的运行时间。

关键词： 社团结构   中心性度量   谱聚类   非负张量分解   同步模型  

摘要： 复杂网络是分析各类复杂系统的重要工具。各类复杂系统可以被转化成网络模型进行研究,系统中的基本组件转化成网络中的节点,组件之间的联系或相互作用转化成网络中的边。随着复杂网络的不断发展,复杂网络的研究热点逐渐从网络的宏观(Macroscale)结构特征转向网络的中观(Mescocale)结构特征和微观(Microscale)结构特征。社团结构作为复杂网络的一种中观结构特征,它通常对应于网络的基本结构单元或系统的功能模块。检测复杂网络的社团结构,可以在网络的中观结构层面分析网络的结构单元与系统的功能模块之间的对应关系。复杂网络的中心性度量是从微观个体的角度出发,评估网络中每个节点的相对重要程度。通过分析网络中各个节点的相对重要程度,可以从微观层面分析节点对网络的拓扑结构以及动力学过程的影响。因此,复杂网络的社团结构检测算法和中心性度量是复杂网络研究的重要课题。本文主要研究内容是复杂网络的社团结构检测及其节点的中心性度量。本文主要研究工作如下:1.基于网络的电阻距离给出一种新的相似性度量,并将其用于复杂网络的社团结构检测。电阻距离(Resistance Distance)作为网络节点之间的一种距离度量,可将其作为分析复杂网络社团结构的相似度。该方法首先计算网络中任意节点之间的电阻距离;然后,将电阻距离的高斯核函数作为网络中边的权值;接着在Cheeger常数的约束下,使用谱二分法将加权网络划分为两个子网络;最后,在子网络中重复上述过程,得到最终的社团结构。该方法在空手道俱乐部网络、海豚社会网络和足球队网络中进行测试,验证了该方法的准确性和有效性。2.基于网络中节点的二元关系和三角形关系,给出一种检测复杂网络社团结构的方法。网络的三角形结构能够反应网络节点的聚类特性。因此,可以使用节点之间的三角形结构分析复杂网络的社团结构。首先,使用3一致超图描述网络的三角形关系;然后,设计了融合二元关系和三角形关系的矩阵,并结合谱方法分析了复杂网络的社团结构;最后,在随机网络,人工基准网络和真实网络中进行了实验分析。实验结果显示该方法具有更高的有效性和准确性。3.基于非负张量分解评估了多层复杂网络的重要节点和关键网络层。首先,根据非负矩阵分解评估了单层网络的重要节点,并说明了该方法与类度中心性、特征向量中心性之间的等价关系;然后,分析了单层复杂网络模型的局限性,并引出了多层复杂网络模型;最后,基于非负张量分解,提出一种研究多层网络的中心性度量,并将该中心性与现有多层网络特征向量中心性进行了对比分析。4.基于复杂网络的同步过程评估了网络节点的重要程度。该中心性度量不仅考虑了网络的拓扑结构,而且还考虑了网络的同步动力学过程。首先,将网络中的节点看做一个振子,并且使得网络中所有的振子处于同步状态;然后,扰动网络中的每个节点,通过受扰动节点与同步状态之间的相位差随时间的演化过程揭示受扰动节点的重要程度。最后,将该中心性与经典的特征向量中心性度量进行了比较,实验结果验证了该方法的有效性。

关键词： 复杂网络   社团检测   GN算法   FN算法   矩阵   公共安全  

摘要： 复杂网络是由节点和边构成的反映个体间复杂关系的网络结构,是对现实世界中各种复杂系统的抽象,可用来挖掘和分析错综复杂关系中个体间的关联信息和社团倾向,近年在社交网络、神经网络、互联网和电力传输网络等方面被应用甚广。区分社团并反映与现实世界更为接近的社团结构是复杂网络中重要的研究方向,社团检测技术可根据网络拓扑结构性质实现网络的聚类,进而发现个体之间的共性和群体之间的差异,具有重要的研究价值。GN算法是社团检测算法中的典型代表,具有高准确度的优点,但时间复杂度较高、效率较低。本文在GN算法的基础上提出两种改进算法,并将其应用到公共安全领域。本文的主要研究内容和成果如下: (1)针对GN算法时间复杂度较高的问题,本文提出基于层次聚类的社团检测算法TNGN,该算法分为分裂和凝聚两个步骤。分裂阶段使用双层邻域重合度TN代替边介数的计算,大幅降低计算时间并更深层考虑多层节点的重要性;凝聚阶段使用改进的FN算法将小型社团融合以提升模块度。通过多组网络实验证明,TNGN算法在降低耗时的同时提升了社团划分的准确度和模块度。 (2)针对TNGN算法的实验效果,本文分析了TNGN算法存在的不足及原因并进一步提出CM-TNGN社团检测算法。该算法引入矩阵存储,并选择性地更新矩阵信息,解决迭代过程中存在大量重复无用计算的问题,进一步降低算法的时间复杂度,同时解决TN系数相等时随机删边的问题,降低算法的随机性。通过实验证明,CM-TNGN算法进一步缩短了算法运行时间并小幅度提升了社团划分的准确度,可应用性更高。 (3)为了检验算法的实用性,本文将CM-TNGN算法应用于某市公安局的“公共安全大数据分析”实战项目中。通过对涉案数据分析和整理并以其为基础构建嫌疑人资金流动网络,结合社团检测算法描绘嫌疑人所在团伙的社团结构和人物关联,为案件提供更多价值线索,助力案件侦破。

关键词： 重叠社团   模块化密度   社团领导度   节点领导度   加权网络   从属度树  

摘要： 随着对复杂网络的物理结构和功能特征的深入研究,研究者们发现许多复杂网络都具有社团结构的特征。通过检测社团结构,有助于发现复杂网络中一些潜藏的规则和定律,对解决现实生活中的问题具有较强的应用价值。基于优化模块度函数的社团检测算法无需事先输入社团数目,但其本身存在分辨极限问题。另外核心节点选择的随机性以及社团的边缘节点难以划分影响了社团检测的准确性。对此本文提出了基于社团领导度和模块化密度的重叠社团检测CL-MD(Community Leading And Modularity Density)算法。该算法一方面根据社团领导度以及节点中心度选取核心节点进行划分,解决了节点的随机性选取问题。另一方面模块化密度函数能够克服分辨极限问题,并通过矫正因子实现边缘节点的划分,从而提高社团划分的准确性。相比较于无权网络,加权网络更贴近现实世界。针对加权网络所提出的社团检测算法普遍存在关键节点的随机性所导致社团划分的准确性较低的问题。为此,本文构建了一种基于加权领导度和从属度树的复杂网络重叠社团检测方法模型。该模型中首先依据共同邻居节点的权重和,定义了加权领导度,其次根据影响力较大的节点作为关键节点建立从属度树,依据树的层次结构,对从属度树进行划分,提高其社团检测准确性。在计算机人工网络和真实网络上与其他四个加权网络社团检测算法进行对比,实验表明加权领导度和从属度树的算法模型检测社团结构的准确性更好。

关键词： 复杂网络   社团检测   标签传播   节点重要性   公共安全数据分析  

摘要： 复杂网络是由真实世界里对应复杂系统经过建模得到的一种网络结构,常见的复杂网络有金融交易网络、蛋白质网络、人际关系网络等,在数字化的时代背景下,这类网络已经成为了研究信息传播的重要工具。社团检测是研究复杂网络结构的一种常用技术,研究人员通过社团检测可以揭示复杂网络的拓扑信息,探究各群体之间以及个体之间的潜在关系,因此社团检测及其相关课题具有重要的研究价值和意义。原始的标签传播算法LPA具有简单高效的特点,在社团检测领域具有较高的热度,但其存在稳定性较差且不能适用于重叠社团的检测等问题。本文在深入研究了LPA算法的思想和运行原理后,提出了三种基于LPA改进的算法。论文的主要研究内容如下:(1)针对原始LPA算法的高随机性而导致检测结果不稳定的问题,本文提出一种基于节点重要性的标签传播算法LPANI。首先本文基于k-shell算法和节点活跃度定义了一种节点重要性指标KSNI,并按该重要性递减的顺序对节点进行排序从而确定标签初始化以及标签更新的序列;然后提出一种基于节点影响力的标签初始化方法,运用该方法进行标签初始化可以减少网络中冗余标签的出现,从而有效减少标签迭代的次数;接着本文基于Salton指标定义了标签影响力并利用节点邻接信息定义了新的网络约束系数,用于解决标签更新冲突的问题;最后本文基于模块度增量提出一种社团后处理方法,进一步提高了算法的准确度。(2)为了弥补LPANI算法的不足,让算法的检测结果更贴近真实社团结构。本文提出了一种基于马尔可夫聚类的标签传播算法LPAMC。算法主要做出两点改进:首先,为了更加全面的定义节点重要性,本文利用MCL算法构建节点重要性矩阵,并将其与KSNI指标相结合提出新的节点重要性指标;然后,本文提出了一种基于社团相似度的社团合并策略,避免了模块度增量的分辨率限制问题带来的影响,使社团合并结果更接近真实结构。(3)为了完成重叠社团的检测,本文将LPAMC算进行拓展,提出了SLPAMC算法。主要有以下三个改进点:算法为每个节点设置标签存储列表,允许节点同时携带多个标签;在标签传播阶段筛选出对待更新节点网络约束最大的邻居节点作为标签传播节点,减少了标签传播过程中冗余标签带来的干扰;最后利用预设阈值对节点标签存储列表中的标签进行筛选,去除出现频率低于阈值的标签,剩下的标签则为节点所归属的社团。(4)本文将LPAMC算法和SLPAMC算法应用于某市“公共安全大数据分析”项目。将真实案件中的资金交易信息构建成人员关系网络,利用社团检测技术挖掘网络中的团伙结构,刻画网络中的核心成员,为刑侦工作寻找出更多潜在线索,最后通过案件的侦破验证了算法的在公共安全领域内的可行性。

关键词： 社团检测   评分推荐算法   属性网络   稀疏性   图卷积  

摘要： 随着4G技术的普及和5G技术的飞速发展,线上文字、语音、视频数据呈指数级增长,推荐算法通过分析用户的历史行为为用户兴趣建模,主动推荐能够满足用户兴趣的信息,为互联网用户推送个性化信息。不仅可以降低用户获取需求信息的困难,还可以了解到用户的个人倾向,分析行业趋势,具有十分高的商业价值。设计高效准确地推荐算法成为众多学者的研究热点。 经典的推荐算法如基于协同过滤、基于内容的评分推荐算法通过分析用户的浏览、购买等历史行为获取用户偏好进行评分预测,但是对于历史数据偏少的冷启动用户往往无法准确获取其偏好信息。近年来一些基于社团检测的评分推荐算法被提出,通过直接引入社团检测算法对用户社交网络进行社团划分,使得相似度高的用户划分到一个社团,将同一社团内的其它用户作为服务用户的直接好友,然后根据好友关系定义自身偏好信息进行推荐可以有效缓解冷启动问题。但是用户社交网络具有稀疏性,而且传统的社团检测算法只考虑用户的低阶结构关联,这些因素会导致部分用户在社团检测时被错误划分,给目标用户添加噪声邻居,降低推荐精度。此外,目前基于社团检测的评分推荐算法中邻居之间的信任关系都是二进制的,无法表现用户之间的信任程度。针对用户社交网络具有稀疏性、只考虑用户低阶结构关联、二进制信赖值无法表现用户之间信任程度问题,本文提出一种属性网络社团检测算法(KGCN),并研究基于KGCN社团检测的评分推荐算法。 本文的主要工作包括以下内容: 1.针对用户社交网络稀疏性和只考虑低阶结构关联导致用户被错误划分问题,提出K阶图卷积属性网络社团检测算法(KGCN)。该方法可以有效地缓解原始网络的稀疏性并利用节点的高阶结构进行社团检测。首先根据节点的属性信息对原始网络进行重构,得到重构网络,缓解原始网络结构的稀疏性;其次,针对不同的属性网络考虑到高阶结构关联,采用K阶图卷积编码器对节点进行编码,获得节点的特征表示;最后使用k-means算法进行社团检测得到社团结构。实验对比表明,在Cora、Citeseer、Pubmed和Wiki 4个真实数据集上,相比现有算法KGCN方法取得更好的社团检测结果。 2.针对传统社团检测算法增加噪声邻居和二进制信赖值无法表达用户之间的信任程度问题,提出基于KGCN属性网络社团检测模型的评分推荐算法(KGCN-R)。该方法应用KGCN模型对用户社交网络进行划分,获取用户社团结构计算用户之间的的细粒度信赖值,并重新定义用户的偏好进行评分预测。首先根据用户的历史评级信息定义用户的属性信息,构建用户属性社交网络;接着使用属性网络社团检测算法(KGCN)对用户进行社团划分,得到用户的社团结构;然后使用网络表示学习模型分别对社交抽象网络和每个社团进行嵌入,得到用户的全局特征向量和局部特征向量,计算用户显性信赖值,根据历史评级信息计算用户之间的皮尔逊系数作为隐性信赖值,并融合用户隐性和显性的信赖值作为用户的细粒度信赖值;最后根据细粒度信赖值添加邻居,使用信任传播矩阵分解方法预测评分。实验对比表明,在Filmtrust和Ciao两个真实数据集上,相比现有算法KGCN-R算法可以有效提高推荐精度。

关键词： 数据挖掘   社团检测   复杂网络   种子扩展算法  

摘要： 现实生活中存在着形形色色的网络,如社交网络、论文引用网络和蛋白质相互作用网络等,人们将这些网络统称为“复杂网络”。复杂网络具有社团结构的特性。社团检测算法旨在高效、准确地从复杂网络中划分出社团结构。社团检测算法有很多类,基于种子扩展社团检测算法就是其中之一。一些基于种子扩展的算法在社团扩展时未考虑社团的聚类特征,其次在社团优化时存在筛选稀疏社团不准确的问题,这两个问题的存在降低了种子扩展算法社团检测的准确性。通过分析现有的种子扩展社团检测算法,本文提出基于社团聚类特征的种子扩展社团检测算法。本文的主要工作如下:（1）针对种子扩展社团检测算法在种子扩展阶段未考虑社团的聚类特征以及在社团优化阶段筛选稀疏社团不准确的问题,本文提出基于社团聚类特征的种子扩展社团检测算法SEA。SEA算法,在种子扩展阶段,用CEA算法完成社团的初步划分;在社团优化阶段,用MOA算法在CEA算法输出结果的基础上完成社团优化。在种子扩展阶段,本文定义了评估社团聚类能力的社团聚类系数,并以社团聚类系数定义了节点对于社团的聚类增量。CEA算法在种子扩展时,根据社团的聚类特征从尚未被划分社团的节点中选择局部聚类系数最大且度相对较小的节点作为种子节点,然后把社团的邻节点按局部聚类系数排序,最后把聚类增量大于0的节点扩展至社团;在社团优化阶段,本文引入了模块度增量,并以模块度最大化来优化社团,避免了筛选稀疏社团不准确的问题。MOA算法在社团优化时引入模块度增量矩阵,在每次迭代时选择把模块度增量最大的两个社团合并。（2）针对种子扩展算法在社团优化阶段筛选稀疏社团不准确的问题,本文重新定义了评估社团稀疏性的社团密度,并提出基于社团密度优化的种子扩社团检测算法D＿SEA。D＿SEA算法在CEA算法的社团检测的基础上,每次迭代时筛选择最稀疏的社团,并与其最相似的社团合并,直至社团划分结果中社团的稀疏性都大于阈值!时,算法执行结束。在真实网络和人工网络上,将本文提出的算法与具有代表性的算法进行对比实验。实验结果表明,本文提出的算法可以更准确地检测出复杂网络中的社团。

关键词： 复杂网络   社团检测   标签传播算法   图神经网络   自监督  

摘要： 复杂网络涉及现实世界的各个方面,可以将现实世界中的个体和相互之间的联系进行高度抽象,针对复杂网络的研究一直是计算机领域的热点。复杂网络具有明显的社团结构特性,通过划分复杂网络的社团结构可以分析复杂网络中各个部分的功能以及网络整体的拓扑结构。传统社团检测算法与基于深度学习的社团检测算法是两大社团检测算法类别,两种方式都存在着提升的空间,针对现有社团检测算法中存在的问题,论文在其中两个方面进行了改进,具体的工作内容如下: 传统社团检测算法中的标签传播算法具有接近线性的执行效率但同时在结果准确率和稳定性上存在劣势。论文提出了基于核心度向量改进标签传播算法的CLPA算法。该算法首先计算网络中节点的核心度,并通过邻居节点的核心度值,构建核心度向量,每个节点的邻居节点与该节点的核心度向量计算Pearson相关系数,该系数之和与节点的度综合作为节点更新的排序。Jaccard相关系数用于解决更新时的平局决胜问题,同时考虑了节点的ID和节点的标签,以此提升算法的稳定性和有效性。 基于自监督的社团检测方法通常使用自动编码器的方式,使用重构损失作为训练目标,构建节点的低维表示,通过经典聚类算法获得社团检测的结果,整个任务分成了上下游两部分,势必会造成算法的精确度不足。论文提出了基于自监督学习的AEAGC算法。通过使用KL散度衡量聚类结果的优劣,并且同时加入了邻接矩阵和特征矩阵的重构损失函数,调节三者间的占比以获得合适的目标函数。利用扩散函数的方式改进了邻接矩阵的连接性,利用低通滤波器获得了更加平滑的特征矩阵。如此改进了两矩阵使其更适合图神经网络的社团检测任务,借助DGI作为网络数据增强方式,进行特征矩阵的数据增强。 为了验证上述算法的有效性,论文使用了不同类别的真实网络及不同参数的人工网络作为实验数据集,采用了多种评价指标对社团的划分结果进行评估,加入了多个经典社团检测算法进行实验结果的对比。实验结果表明CLPA算法在5000节点的人工网络与对比算法相比有明显优势,在真实网络数据集中对比其他算法在以NMI作为评价指标时具有最高15%的提升。AEAGC算法在真实网络数据集中的执行结果准确率相比最优对比算法提升最高可达20%,引入DGI作为数据增强方式后对于四项评价指标提升最高可达15%。

关键词： 网络分析   图流   局部社团检测   近似电导  

摘要： 社团是网络中普遍存在的一种结构,通常由具有相同角色或者相似属性的成员组成,往往能反映网络中存在的某种局部特征和功能,社团检测也就成为网络分析的一项基础而重要的任务。随着信息的爆炸式增长,许多网络规模急速膨胀而出现数据过载现象,同时这些网络往往时刻处于动态变化中,而图流是一种能有效处理网络数据过载和快速动态变化的技术手段。但基于图流的局部社团检测是一个新的研究课题,相关研究还处于起步阶段。 形式化地定义了基于图流的局部社团检测任务,还分析了基于静态完整图的传统社团检测算法的局限性。因图流的有限内存开销和对数据访问的限制,传统算法不再适用于图流。进而设计了一个基于图流的局部社团检测算法——基于近似电导的图流社团检测(Streaming Community Detection via Approximate Conductance,SCDAC)。受社团局部性的启发,该算法首先在图流中采样查询节点的邻域结构,并用距离树来高效维护采样子图,同时引入周期性裁剪来平衡采样精度和算法开销。然后运用所提出的近似电导作为社团质量度量指标,从采样的子图上抽取出查询节点所属的目标社团。 实验结果表明,SCDAC算法无论是在检测精度还是在运行效率上,都要优于其他基于图流的局部社团检测算法。凭借着近似电导在采样子图上的优越性,SCDAC算法甚至取得了,和当前最先进的基于静态完整图的传统社团检测算法相近的检测精度。此外,SCDAC算法具有良好的可扩展性,能扩展应用于大规模网络,同时有着不错的鲁棒性,能检测不同尺寸、不同密度的局部社团。

关键词： 推特   舆情分析   突发事件   突发词   词汇挖掘   社团检测  

摘要： [目的/意义]微博是网络舆情传播的重要平台之一,为了对海量微博中的突发舆情事件进行监控预警,并获取开源情报。[方法/过程]文章以短语作为兴趣词项,提出了基于突发短语挖掘的微博舆情事件检测方法。首先,利用自动短语挖掘方法AutoPhrase从微博文本中识别出具有潜在舆情价值的优质短语;然后,基于短语相关统计信息,识别出主题性、流行性、突发性均较大的高舆情价值的突发短语集合;最后,构建突发短语共现网络,利用模块度优化算法对短语聚类,从而得到不同的舆情事件。[结果/结论]基于推特数据的实验结果表明,与基于单词和命名实体的方法相比,该方法可以获得更好的事件检测效果。[局限]仅针对特定主题的英文推特数据进行了实验验证。