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

摘要： 随着信息技术的高速发展,各种各样的社交网络数据也随之出现,同时,社交网络的规模也变得越来越庞大,使得社交网络拓扑结构变得越来越复杂。在如此的大数据时代背景下,传统的社团检测算法从全局特征出发,算法复杂度随着社交网络规模的大型化而变得极其庞大,显然不再适用于现阶段的大部分社交网络。因此,本文考虑从局部特征出发,去探索社交网络中比较显著的社团结构。 本文在基于相似度的社团检测算法基础上,对传统相似度度量提出了调整,并引入了新的定义——结点质量,用以探索社交网络中的关键结点。然后参考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从微博文本中识别出具有潜在舆情价值的优质短语;然后,基于短语相关统计信息,识别出主题性、流行性、突发性均较大的高舆情价值的突发短语集合;最后,构建突发短语共现网络,利用模块度优化算法对短语聚类,从而得到不同的舆情事件。[结果/结论]基于推特数据的实验结果表明,与基于单词和命名实体的方法相比,该方法可以获得更好的事件检测效果。[局限]仅针对特定主题的英文推特数据进行了实验验证。

关键词： 复杂网络   重叠社团检测   双编码   多目标优化  

摘要： 近年来,多目标进化方法已被广泛应用于重叠社团检测问题并取得了较好的社团划分性能.如何设计合适的个体编码以及进化策略是提高基于多目标进化重叠社团检测算法性能的重要因素.为此,本文设计了一种双编码表示方法对非重叠社团结构和重叠点分别进行编码,能够有效解码得到重叠社团结构.在双编码表示的基础上,本文提出了一种基于双编码的重叠社团检测多目标优化方法(DRMOEA).在DRMOEA中,为了获得好的初始个体并提高算法检测性能,本文提出了一种基于社团边界点的初始化策略.除此之外,针对双编码中的重叠点编码部分,本文提出了基于精英个体边界点的交叉策略,该策略利用社团边界信息引导种群向好的方向进化,从而有效提高了算法的检测性能.最后,在9个真实世界网络上的实验结果表明DRMOEA算法优于其他5个代表性重叠社团检测算法.

关键词： 技术演进   多路径识别   创新特性   专利引证网络   社团检测  

摘要： [目的/意义]开展科技领域技术演进多路径识别及其创新特性分析,可为技术起源探究和技术价值评估提供有效帮助。[方法/过程]构建科技领域专利引证网络,通过Louvain社团检测和SPC主路径提取进行技术演进多路径识别。在此基础上,利用技术—功效共词矩阵来探究各技术演进路径的核心技术演化,利用结构洞约束度指标和技术邻近度指标来识别各技术路径节点专利的创新类型。[结果/结论]利用德温特专利索引数据库中1963—2018年柔性显示领域的9121条专利记录进行实证研究,结果表明提出的方法能够较为全面地识别科技领域技术演进的多个路径方向及其核心技术,通过结构洞约束度和技术邻近度指标能够有效检测技术演进过程中的渐进性创新和突破性创新技术。

关键词： 复杂网络   社团结构   局部随机游走   轮廓系数  

摘要： 在近几十年中,复杂网络在数据挖掘和知识发现起着越来越重要的作用。复杂网络中的社团检测引起了许多领域的极大关注。提出了一种基于局部随机游走距离LRWD轮廓系数的网络社团检测新算法(SIL算法)。此外,通过一些具有代表性的真实世界网络和计算机生成网络(GN准则和LFR准则)来测试该算法的准确性和效率。实验结果表明,SIL算法可以准确有效地检测这些网络的真实社团结构。