关键词： 复杂网络   社团检测   特征矩阵   平均向量   加权特征距离  

摘要： 随着互联网技术的快速发展,复杂网络研究已遍及到人类社会的方方面面。社团检测作为复杂网络研究中的一个热门领域,通过社团检测算法划分网络的社团结构,为理解网络的结构和功能特征,解决网络社会的问题提供了重要的理论依据。近年来,专家们也从不同的角度陆续提出了大量优秀的社团检测算法,谱聚类算法就是其中比较经典的一个,该算法具有收敛于全局最优,可对任意形状样本空间进行聚类等优点而被广泛应用于社团检测中,但现有的谱聚类的算法仍然存在着不同程度的问题,对此,本文通过结合网络的层次化结构特征设计了以下两种算法:(1)针对无权网络中谱聚类算法存在需要预先输入聚类数目,准确性受初始节点选取影响较大的问题,提出了一种基于平均向量层次优化的谱聚类无权网络社团检测算法eh-SC算法。由于不同的特征向量对节点全局拓扑的影响力不同,算法首先提出了度量网络矩阵不同特征向量对社团聚合影响力大小的疏密加权函数;然后结合网络中的节点属性和网络拓扑属性来构建平均向量模型,从而提高了算法选择初始节点的准确性;最后以节点之间特征距离最小为依据使用层次划分算法对平均向量进行层次优化,结合模块度函数检测社团结构,避免了谱聚类算法需要预先选择聚类数目的缺点。(2)针对加权网络,当前加权网络社团检测算法主要通过考虑网络的边权进行社团检测,而未能考虑加权网络中节点本身的影响力。由于在谱聚类算法中,可以方便地将权重引入到网络矩阵中,基于此,本章改进了 eh-SC算法,提出了基于加权特征距离的谱聚类加权网络社团检测算法Weh-SC算法。首先引入权重信息构造出了网络正规加权矩阵,计算出具有权重属性的初始向量,使其具有节点在网络中的全局属性和边的权重属性;然后提出加权特征距离用以度量加权网络中节点的相似性;最后对初始向量进行层次优化结合加权模块度检测出加权网络社团结构。为验证eh-SC算法和Weh-SC算法的有效性,在人工合成数据集和真实社交网络数据集上进行了实验,以模块度与标准化互信息作为评价指标,与多种算法进行对比分析,研究结果表明,上述两种算法均可以划分出高质量的社团结构。

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

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

关键词： 社交网络   结点相似度   模块度   音乐偏好分析  

摘要： 随着信息技术的高速发展,各种各样的社交网络数据也随之出现,同时,社交网络的规模也变得越来越庞大,使得社交网络拓扑结构变得越来越复杂。在如此的大数据时代背景下,传统的社团检测算法从全局特征出发,算法复杂度随着社交网络规模的大型化而变得极其庞大,显然不再适用于现阶段的大部分社交网络。因此,本文考虑从局部特征出发,去探索社交网络中比较显著的社团结构。本文在基于相似度的社团检测算法基础上,对传统相似度度量提出了调整,并引入了新的定义——结点质量,用以探索社交网络中的关键结点。然后参考K-means++的改进思想,基于结点质量与结点相似度矩阵,以模块度为优化目标,对社团检测数量与社团划分进行探索,探索得出的社团应尽可能显著,并且社团间的距离应尽可能远。同时,本文基于一个简单社交网络,通过与GN算法对比,验证了本文算法在社团检测方面的可行性。本文数据为罗马尼亚(RO)社交网络数据集,基于数据特点,对实验数据分别进行零处理与加权处理,再分别对处理后的社交网络进行社团检测,最后基于社团检测结果,对社团进行描述性统计,发现各社团成员对Pop音乐的偏好最为显著,其次为Alternative、Rock、Dance和Rap/Hip Hop,且各社团的偏好表现有所差异。同时,实验表明,对社交网络的边基于兴趣偏好进行适当加权后,社团检测结果会更接近期望效果。

关键词： 动态加权国际贸易网络   动态社团检测   时序链路预测   节点重要性识别  

摘要： 国际贸易网络可以用来衡量国家的经济实力,具有复杂性和动态性的特点。准确地对动态加权国际贸易网络进行社团检测能够找到更为紧密的区域性贸易合作组织,对于各国制定相应的贸易政策和未来的发展计划具有指导意义。目前,如何提高动态加权国际贸易网络社团检测的精度有待进一步研究。本学位论文研究动态加权国际贸易网络的节点重要性排序和有向边权重预测,进而对动态加权国际贸易网络的社团检测进行研究。主要研究内容和成果如下:为了提高动态加权国际贸易网络中节点重要性识别精度,建立了加权国际贸易网络,提出了基于指数时序聚合模型的加权主分量中心性算法(WPCC-ETSAM)。选定UNCTAD数据库,将国家之间的贸易额作为加权国际贸易网络中连边的权重。在加权主分量中心性算法的基础上,WPCC-ETSAM算法通过引入指数时序聚合模型对动态加权国际贸易网络的节点重要性进行识别。经过实验对比,WPCCETSAM算法相比于三种经典算法在动态加权国际贸易网络节点重要性识别的准确性方面表现出很大的优越性。为了提高动态加权国际贸易网络中有向边权重预测精度,构建了基于图神经网络的时序链路预测模型,并基于该模型提出了有向边权重预测算法(DEWPATLPM)。通过在以生成对抗网络、长短期记忆网络和图卷积网络为基础的时序链路预测模型中引入矩阵分解变换模块对动态加权国际贸易网络中有向边进行权重预测。DEWPA-TLPM算法通过引入重构损失函数提高动态加权国际贸易网络中有向边的权重预测精度。实验结果表明,DEWPA-TLPM算法对动态加权国际贸易网络有向边权重的预测准确度比四种经典算法表现的更佳。为了提高动态加权国际贸易网络中社团结构的检测精度,提出了基于节点重要性和链路预测的多目标动态社团检测算法(MDCDA-NILP)。MDCDA-NILP算法采用基于节点重要性的标签传播策略对动态加权国际贸易网络的社团结构进行初始化,进而采用多目标动态社团检测策略对动态加权国际贸易网络的社团结构进行检测。经过实验对比,MDCDA-NILP算法对动态加权国际贸易网络中社团结构的检测精度比三种经典算法表现的更优。

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

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

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

摘要： 现实生活中存在着形形色色的网络,如社交网络、论文引用网络和蛋白质相互作用网络等,人们将这些网络统称为“复杂网络”。复杂网络具有社团结构的特性。社团检测算法旨在高效、准确地从复杂网络中划分出社团结构。社团检测算法有很多类,基于种子扩展社团检测算法就是其中之一。一些基于种子扩展的算法在社团扩展时未考虑社团的聚类特征,其次在社团优化时存在筛选稀疏社团不准确的问题,这两个问题的存在降低了种子扩展算法社团检测的准确性。通过分析现有的种子扩展社团检测算法,本文提出基于社团聚类特征的种子扩展社团检测算法。本文的主要工作如下:（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从微博文本中识别出具有潜在舆情价值的优质短语;然后,基于短语相关统计信息,识别出主题性、流行性、突发性均较大的高舆情价值的突发短语集合;最后,构建突发短语共现网络,利用模块度优化算法对短语聚类,从而得到不同的舆情事件。[结果/结论]基于推特数据的实验结果表明,与基于单词和命名实体的方法相比,该方法可以获得更好的事件检测效果。[局限]仅针对特定主题的英文推特数据进行了实验验证。