关键词： 多任务聚类   非负矩阵分解   动态社团检测   共正则化  

摘要： 如今,数据的大规模增长致使工程领域中产生了大量具有高维性,动态性,层次性和相关性的复杂数据。针对复杂数据的研究对科技的进步具有重要意义。多任务聚类和动态社团检测作为研究复杂数据的重要方式,受到了学者们越来越多的关注。多任务聚类共同学习多个任务,通过在相关任务间迁移知识提升每个任务的聚类性能。社团检测通过揭示节点间相互关系,找出紧密相连的节点簇,使得簇内节点强连接,而簇间的节点弱连接。动态社团检测跳出静态网络社团检测的局限,结合网络的时序性对社团进行检测。然而,数据的复杂性降低了现有算法在系统功能研究上的准确性,极大的阻碍了多任务聚类和动态社团检测算法的发展。非负矩阵分解(Non-negative Matrix Factorization,NMF)不仅能够提取数据的潜在特征,且可直接用于数据聚类,在复杂数据聚类分析领域受到越来越多的关注。然而,NMF方法仍存在一些问题:(1)NMF模型为欠定方程,致使方程解不唯一;(2)NMF结果不稳定,严重受到随机初始值的影响。为减弱这些问题带来的影响,论文改进了NMF算法并提出了基于模型相关性的多任务聚类算法(MTMC)和基于共正则化非负矩阵分解的动态网络社团检测算法(ACr-ENMF)。论文的主要贡献概括如下:(1)基于模型相关性的多任务聚类算法,构建了联合学习任务内聚类和任务间聚类的多任务学习框架。具体地说,考虑多任务数据维度高、噪声大的特点,任务内聚类采用对称非负矩阵分解(Symmetric Non-negative Matrix Factorization,SNMF)对数据进行降维,通过引入线性回归预测任务内聚类标签,降低直接采用SNMF聚类的不稳定性,提高聚类准确性;任务间聚类利用二部图联合任务与特征进行共聚类,将任务内参数迁移至任务间模型,加强对不同任务间相关性的学习。MTMC算法通过参数迁移将任务内聚类和任务间聚类联合至同一优化模型中,并且通过交替迭代优化得到聚类结果。(2)基于共正则化非负矩阵分解的动态网络社团检测算法,在动态网络进化社团检测中同时考虑了聚类精度和聚类漂移。ACr-ENMF算法利用相邻时刻网络信息的相关性,将前一时刻的特征信息迁移至当前时刻进行社团聚类,进而将不同时刻的时序信息关联起来。具体地说,为了提高动态进化社团检测的准确性,利用前一时刻的网络和社团描述聚类漂移,并通过共正则化将其纳入到ACr-ENMF的目标函数中。ACr-ENMF算法不仅约简了维数、降低了时间复杂度,且更好地描述了动态社团的演化规律。(3)为了验证所提算法的性能,论文在3个多任务数据集和4个动态网络数据集上与现有最先进的相关算法进行实验对比,并采用不同的测量方法消除测量指标带来的误差。实验结果表明,所提算法在各种测量方法上明显优于其他算法。

关键词： 视频摘要   密度峰值聚类   镜头切分   关键帧提取   社团检测  

摘要： 数字视频是多媒体技术的一个重要传播途径,被广泛应用于社会的各行各业之中。如何让用户能够快速捕捉到视频的内容,从而决定是否需要继续观看是需要关注的问题。在这样的背景下,视频摘要技术应运产生。视频摘要是一种新的基于内容的视频压缩技术,它能有效地从视频中发现重要信息,消除冗余数据,是对视频内容的概括。近年来视频摘要技术有了很大的发展,但是如何生成高效、准确率高的视频摘要仍然在不断的探索中,本文围绕视频摘要生成技术展开研究,主要工作有:(1)提出了基于密度峰值聚类(DPC)的视频摘要生成算法(简称DPC算法)。首先,提取视频帧色调直方图的特征,应用DPC聚类对视频帧的色调直方图特征向量聚类,以聚类的结果为依据进行视频镜头切分。其次在关键帧提取阶段,选取离聚类中心最近的帧作为关键帧,同时用直方图相交法去除关键帧中的相似帧,生成视频摘要。实验表明,该方法得到了较好的视频摘要结果。(2)提出了基于T-DPC的视频摘要生成算法(简称T-DPC算法)。在DPC算法中加入视频帧的时间特性,提出了具有时间特性的密度峰值聚类算法,并将其应用于镜头切分中。在关键帧提取阶段,综合考虑了视频帧的信息熵和与聚类中心的相似程度来提取关键帧,并剔除相似帧。实验结果表明,该方法得到的视频摘要质量均高于对比算法。(3)提出了基于Fast Newman社团检测算法的视频摘要生成算法(简称FN算法)。该算法以视频帧作为网络节点,以帧与帧间的相似度作为连边的权重,构建全连接无向加权网络,利用Fast Newman算法进行社团检测,提取出每个社团中离节点度均值最近的帧作为关键帧。同时采用颜色特征与SURF特征双重去除相似帧,得到了理想的视频摘要。

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

摘要： 现实世界中大量的复杂系统可以抽象成复杂网络,因此针对复杂网络的研究一直是信息领域的热点问题,而社团结构作为复杂网络的一个重要特征,对其进行深入研究有助于理解复杂网络的结构和功能特性。近年来,相关领域的学者们提出了很多用于复杂网络社团结构检测的算法,这些研究成果被应用于计算机科学、社会科学、生物科学等多个领域。随着深度学习的发展,学者们提出了图卷积神经网络,该网络能够提取拓扑结构中的高阶特征,弥补传统神经网络不能处理非欧空间数据的缺点,推动了深度学习在图结构数据中的应用。目前针对图神经网络的研究大多集中在有监督和半监督学习领域,针对无监督的社团检测任务研究相对较少。此外,基于深度学习的社团检测方法也集中于非重叠社团的检测,而缺乏针对重叠社团检测的研究。本文提出了两种基于图卷积神经网络的社团检测方法,适用于具有高维属性信息的大规模图结构数据,主要工作如下: (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算法的有效性。

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

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

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

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

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

摘要： 真实世界中的各类系统往往可以结合图论映射到一个网络中,网络中的节点和拓扑结构反映了真实世界的成员及其关系,其中,最为显著的特征就是网络的社团结构。近年来,许多用于挖掘复杂网络中的拓扑结构特征及隐含关系的社团检测算法被提出,其成果被广泛应用于生物科学、社会科学等诸多领域。同时,由于真实世界中,网络中的节点在结构上和功能上差异巨大,对网络中的核心节点的精确识别,在控制谣言传播、遏制疫情传播、广告投放等领域具有重要意义。本文在研究现有社团检测算法的基础上,聚焦于通话网络,结合公共安全领域的实际需求,提出了一种针对通话网络的社团结构检测算法,同时结合随机游走理论提出了一种针对通话网络的核心节点挖掘算法,主要研究内容及工作包含以下几个方面: (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三个指标进行算法性能评估。