关键词： 公共安全   数据分析   关联融合   社团检测  

摘要： 随着大数据时代的到来,大数据分析技术在商业应用、工业生产、社会服务和政府管理等各个领域得到高度重视和广泛应用,有效地提高了各行各业的决策能力、服务效率和运营管理水平,同时也为支撑公共安全领域管控模式创新,实现实时化、精确化、个性化的敏感人群洞察和敏捷响应提供了丰富的应用场景。本文结合某市公共安全部门的实际需求,利用复杂网络的社团结构检测技术,开展有组织犯罪活动的大数据辅助分析研判模型的应用研究,主要工作如下:1、将来自于外部的各社交媒体数据和来自于组织内部的各业务流程数据进行收集、清洗、转换,实现多源异构数据的关联融合,并将处理完成的数据按照不同的主题分类管理,实现面向主题分析的数据仓库。2、设计一种基于社团结构检测算法的有组织犯罪活动的结构检测模型。该模型将个案嫌疑人的动态行为数据和静态关系数据进行关联融合,构建个案嫌疑人群通联网络,通过多种社团结构检测算法（LPA标签传播算法、Louvain算法等）进行集成分析,刻画目标群体中频繁联系人、活跃人物、核心人物,逐层精简网络结构,初步呈现出核心团伙结构,并以直观可视化形式呈现。3、设计一种基于社团结构的指数判别模型。该模型综合考虑关联人员的通话行为特征、通信录好友关联以及通联强度。基于KL散度,开展通话行为的特征提取和度量;基于六度空间、重叠网理论,设定了通信录好友的关联指数以及通联强度指数,综合这三部分,构造了指数判别模型,以便快速锁定嫌疑人,有效缩小早期布控的范围,同时也为个案的后期循线深挖调查提供了一定的方向,弥补人工摸排的缺陷。4、设计一种基于社团结构检测算法的串并案模型。该模型利用相同类型的犯罪团伙之间的一定存在勾结的特征,通过多种社团检测算法进行集成分析,刻画团伙间的中间人和桥节点,实现对重要嫌疑人的锁定,支撑多案件串并案分析,挖掘案件的潜在可能性,实现以人找案。目前以上研究工作已经投入实际应用,在多起有组织犯罪案件侦破中提供了有价值的数据分析和辅助研判情报,验证了论文所提技术路线和模型的有效性,也为积极构建以大数据分析应用为核心的公共安全管控模式创新进行了有意义的尝试。

关键词： 社团检测   模块度   k-Plex   小社团  

摘要： 复杂网络是一种呈现高度复杂性的网络,也是复杂系统的抽象形式,其研究受到广泛关注。复杂网络可以用于各种复杂系统的模型建立,如应用于物理、生物、经济、社会和信息系统。复杂网络呈现出无标度特性、小世界特性和社团结构特性。其中,社团结构是复杂网络中最重要的特性,其对应着网络的功能单元。检测网络中的社团可以揭示网络的内部结构与功能之间的关系,从而预测网络的功能。在众多社团检测算法中,基于模块度优化的算法是最为广泛应用的。但已有研究证明该类算法存在“检测局限性”的缺点。在实际应用中,小社团的存在有着非常重要的意义。因此,针对该问题,本文进行了以下研究:(1)基于k-plexes,本文提出了一种新的社团检测算法(简称MOKP算法),MOKP算法用k-plexes构建网络的种子社团,然后利用模块度优化的概念来分配网络中剩余的顶点。该算法在进行社团检测时不受社团规模的限制,可以检测出网络中存在的小社团。(2)为了进一步节省MOKP算法的时间,本文从以下两个方面来进行改进(简称IMOKP算法)。(i)在进行种子社团生成之前,利用k-core的检测方法来对网络规模进行缩减。(ii)将网络剩余顶点的分配顺序从字母序调整为顶点的度的降序,同时在顶点分配过程中引入了社团标签。(3)为了验证本文算法的有效性,本文进行了大量的实验。实验在5个真实的数据集和4个人工数据集上进行,利用三种经典的评价指标来评估社团检测,并提出了新的小社团评价指标,称为小社团等级。实验结果表明MOKP算法的社团检测准确率优于多个其他经典的算法,并且能够有效地检测出小社团。IMOKP算法的运行时间和社团检测准确率都优于MOKP算法,实验最后在真实的蛋白质网络上验证了社团检测以及小社团检测的有效性。

关键词： 复杂网络   社团检测   聚类系数   标签传播  

摘要： 复杂网络种类繁多,遍及人类社会的方方面面,涉及到的学科领域也复杂多样,复杂网络研究工作吸引了相关领域研究人员的关注,也越来越受重视。特别是二十一世纪以来,互联网技术取得了前所未有的跨越式发展,对复杂网络研究工作具有很大的推进作用。近年来,来自相关领域的专家学者提出了很多复杂网络进行社团检测算法,标签传播算法就是其中比较经典的一个,该算法具有高效快速、无需先验信息等优点,但也存在稳定性不足、容易形成巨型社区等缺点。本文对已有的复杂网络社团检测算法做了较为细致的研究,尤其对标签传播算法的具体步骤和优缺点进行了认真研究,并对网络的聚类系数性质进行深入分析,由节点的聚类系数和网络的聚类系数,扩展提出了社团聚类系数的概念。针对标签传播算法存在的结果不稳定、容易形成巨片社区等问题,本文结合点聚类系数和社团聚类系数的概念,分别提出了基于点聚类系数的标签传播改进算法和基于社团聚类系数的标签传播改进算法。其中,基于点聚类系数的标签传播改进算法首先根据节点的聚类系数和度对节点进行优先级排序,在初始化标签阶段改进策略,仅对优先级较高的节点进行标签初始化,在标签传播过程中根据节点的聚类系数对邻节点进行排序,选择最优标签,避免了传统标签传播算法随机性高的问题。而基于社团聚类系数的标签传播改进算法,在对节点进行优先级排序和改进初始化标签策略的基础上,使用本文提出的社团聚类系数改进标签传播策略,同样提高了算法的稳定性和检测效果。最后将两种改进算法应用于真实网络数据集和大型的人工网络数据集,实验结果表明,本文提出的两种改进算法均具有稳定的检测结果,与网络的真实社团结构相比准确性也比较高。

关键词： 舆情情报分析   符号网络   非负矩阵分解   深度学习   社团检测  

摘要： 舆情情报分析作为情报分析社会层面中的重要一环,对了解公众对于某些社会热点事件的情绪、态度有着重要作用。本文基于实验室构建的利用复杂网络挖掘算法对人(账号)、物、组织、真假事件及相互关系的感知、理解、预测的智能情报分析框架IAF,提出利用符号网络社团检测进行舆情情报分析。相较于普通复杂网络,符号网络可以更全面地表达网络中节点间的正负情感。且社团检测作为情报分析框架IAF中理解模块的关键,通过挖掘网络中的社团结构,可以发现舆情系统中的群体对于某些热点事件的不同态度划分。本文从网络空间帖子、转发、评论、回复及其情感等海量数据构建具有正边/负边的符号网络,并围绕符号网络社团检测算法进行舆情情报分析,开展了如下工作:首先,提出了一种双非负矩阵分解算法(DouNMF)来挖掘符号网络中的社团结构。该算法将符号网络分解为正负两个分量,在两个分量上利用非负矩阵分解算法求解节点的社团指示向量,以此得到网络的社团划分。此外针对非负矩阵分解过程中的随机性,该算法引入了度修正约束了非负矩阵分解过程,得到了更加准确的社团指示向量,且与其它优秀算法的对比实验也验证了我们DouNMF算法的准确性。其次,针对双非负矩阵分解算法(DouNMF)计算复杂度高,难以应用于大规模符号网络的缺点,提出了深度半非负矩阵分解社团检测算法(DSNMF)。该算法在半非负矩阵分解模型基础上引入了深度学习的机制提升半非负矩阵分解算法的效率,有效地扩展了非负矩阵分解算法在大规模数据集上的可实用性。最后利用实证模型验证了DSNMF社团检测算法的实用性。本文利用疫情期间舆情数据构建了用户基于某些舆情话题的情感符号网络。将DSNMF算法运用到现实世界符号网络中,利用社团检测结果得到了疫情期舆情传播的群体结构及演化趋势,验证了提出模型的实用性。本文面向舆情情报分析,以符号网络社团检测为技术核心,创新性地基于非负矩阵分解算法和符号网络特性设计了符号网络社团检测的算法。在多个人工合成的符号网络数据集和真实符号网络数据集上进行了大量的实验,验证了提出算法的有效性和准确性。并通过疫情舆情数据构建了符号网络,验证了算法模型在舆情情报分析中的实用性。

关键词： 特征选择   粒子群优化   社团检测   高维数据  

摘要： 随着社会的发展和科技的进步,数据量呈现出爆炸式的增长,通常在机器学习领域中,学习算法的性能会随着数据集特征过多而下降。近些年来,特征选择作为解决这个问题的有效手段,得到了广泛的关注,诸多的学者也相继开发、改进了许多特征选择的方法,取得了可观的成效。在这些有效的算法中,粒子群优化算法具有参数少、操作简单、局部搜索能力强等优点,使得粒子群优化算法解决特征选择问题变为当前研究的重点。本文通过进一步的分析粒子群优化算法和特征选择问题,并结合社团检测,利用社团检测算法深度挖掘特征之间隐藏的信息去指导种群进化。主要工作包括以下两方面:(1)针对粒子群优化算法在解决特征选择问题中,容易陷入局部最优,难以找到高质量特征子集的问题。提出了一种基于社团的粒子群优化特征选择算法CBPSOFS。算法的大致思想如下:首先,将特征转化为特征图,并结合社团检测的算法将特征划分为不同的特征社团,根据同一特征社团包含相似信息设计了基于社团的自适应更新策略,来保持种群的多样性,同时平衡了局部搜索和全局搜索,有效的克服了过早陷入局部最优的现象;此外设计了基于信息增益的初始化策略和基于历史信息的重置策略,进一步提高了算法的性能。通过真实数据集与现有的四种特征选择方法的比较,验证了所提出的算法CBPSOFS的有效性。(2)针对高维数据集中含有大量的冗余、不相关的特征,导致特征选择算法性能低下等问题,提出了一种针对高维数据集的特征选择算法KBPSOFS。该方法结合社团检测算法提出了核心粒子的概念,当种群的全局最优值Gbest连续几次不变的情况下,利用核心粒子代替Gbest指导种群进化,增强算法的搜索能力;此外,当整个种群Pbest未改变时,利用当前种群非支配解提出了一个种群变换策略,目的是重置种群,去除不相关及冗余的特征,随着种群的变化算法的计算复杂度也有明显的降低。通过在真实数据集上面的实验,说明了算法KBPSOFS可以有效性的降低特征数量和提高分类精度。

关键词： 复杂网络   社团检测   EBIAS算法   蛋白质分子   IFPM算法  

摘要： 复杂网络是现实世界中复杂系统的高度抽象化,挖掘复杂网络中的结构特性是认识和理解复杂网络的手段之一。复杂网络的社团结构是一种外部稀疏关联、内部紧密连接的聚簇,通过利用社团检测算法对复杂网络中的社团结构进行挖掘,是研究网络结构、特性和功能的重要方法,社团检测算法的研究成果还可以应用于信息检索、蛋白质复合物分析等领域。尽管目前存在大量优秀的社团检测算法,但其仍具有一定的局限性。因此,本文改进了两种社团检测算法,主要内容和贡献如下:针对大规模网络的社团检测问题,本文提出扩展基于中间节点隶属强度的社团检测算法（EBIAS）,该算法基于BIAS算法进行改进。BIAS算法利用对中间节点的隶属关系进行计算来划分社团,提高了在大规模网络下社团结构检测算法的性能。但实验结果表明,当在社团结构复杂的情况下,例如在LFR生成混合系数大于0.5的数据时,BIAS算法的性能受到影响,导致算法不稳定,针对此问题,本文通过引入聚集系数和HDI指标,改进BIAS算法的初始化过程和中间节点隶属度划分过程,从而提高针对大规模网络社团检测算法的效率。针对蛋白质复合物划分问题,本文提出了一种基于蛋白质分子之间相互作用力的IFPM算法。IFPM算法受到范德华力定义的启发,根据蛋白质分子之间的相互作用力,选择邻近蛋白质的最大作用力为标签,并在标签传播的迭代过程中更新蛋白质标签。通过标记传播,相同复合物中的蛋白质将被分配为相同的标记,从而对蛋白质复合物的类别进行划分。最后,本文也采用多个人工数据集和真实数据集进行实验,实验结果表明,EBIAS算法和IFPM算法均能探测出高质量的社团结构。

关键词： 社团检测   相似度   局部密度   核心节点  

摘要： 现实世界中存在许多不同类型的复杂网络,它们都蕴含着各自内在的社团结构。社团检测算法可帮助我们发现复杂网络的内在结构与拓扑特征。目前已有多种社团检测算法被提出,因其巨大的实用价值而被广泛应用于现实生活的各个领域。大多数社团检测算法都是基于相似度度量或模块度最大化而提出的。而基于相似度的社团检测算法面临输入参数难以确定以及对特定复杂网络无法准确划分的问题;基于模块度最大化的社团检测算法寻找最优划分的时间复杂度非常高,并且在很多情况下,最大的模块度不一定对应网络的真实划分。为了解决此问题,本文致力于提出快速的、精确的社团检测算法。本文首先从邻居节点间关系入手,提出了一种新的相似性度量方式。不同于传统相似度,此相似度除考虑节点间的公共邻居外,还考虑了节点间的互斥程度。从而,它能更加客观、全面地从节点结构出发反映节点间的相似程度。然后,为了快速、准确地找到不同社团中的核心节点,本文基于节点对其邻居的影响,定义了一种新的局部密度计算方式,并将社团中局部密度最大的节点定义为此社团的核心节点。该密度计算方式认为,一个节点的密度是其对所有邻居节点的影响力之和。节点影响力越大,其密度就越大,对其他节点吸引力也越大。通过此局部密度,可使网络中的核心节点更易被发现,从而避免了核心节点选择的随机性,使算法结果更加稳定。在此相似度和局部密度的基础上,本文提出了一种简单的、有效的基于节点间邻居关系的社团检测算法(CDRN)。CDRN使用节点间邻居关系,将基于相似度与基于核心点扩张这两种方法的优点巧妙结合起来,既不需要优化目标函数,也不需要掌握网络中社团个数的信息,并且可以在多次运行中提供唯一且准确的网络划分。算法利用新的相似度计算方式,首先将节点初步划分,获得初始社团结构。接着,通过新的局部密度计算方式来调整初始社团结构。最后通过核心社团扩张,获得最终的社团结构。为客观评估CDRN的性能,本文将CDRN与7个经典的社团检测算法分别在6个具有真实社团结构的小网络和5个没有真实社团结构且规模较大的网络上进行了综合地、全面地对比分析。实验结果表明,CDRN算法在绝大多数情况下优于这7种对比算法。而且,实验还通过LFR基准网络验证了本文提出的相似度的阈值范围在不同结构的网络上的稳定性。最后,在具有真实社团结构的网络进行抽样形成的不完整网络上验证了CDRN的鲁棒性。综合以上研究与实验可知,CDRN可以快速发现社团的核心节点,进而稳定、准确地从不同结构和规模的网络中自动检测出社团的真实结构,是一种非启发式的、时间复杂度接近线性的、鲁棒的社团检测算法。

关键词： 复杂网络   社团结构   社团检测   标签传播算法   网络节点特性  

摘要： 现实世界中复杂系统可由复杂网络进行高度抽象,其社团结构特性是复杂网络中最显著的特征。通过社团检测算法挖掘复杂网络的社团结构可以深入探索网络的拓扑结构与隐含特性间的关联。此外,复杂网络中的社团检测研究成果已广泛地应用于犯罪团伙识别、蛋白质复合物分析、个性化推荐和信息检索等多个领域。近年来文献中提出大量的社团检测算法来划分网络中的社团结构,然而大部分算法在准确性或效率上都不能达到良好的效果。本文在分析阐述现有的社团检测算法基础上,针对其中存在的问题提出了两种新颖的社团检测算法。主要的研究工作和贡献如下:(1)为了提升标签传播算法LPA的准确性和稳定性,本文中提出了一种基于节点引力的标签传播算法。该算法首先基于网络全局特征的LeaderRank算法计算网络中所有节点的重要性,以重要性升序的方式序列化节点的更新顺序。然后,该算法结合网络的拓扑特征和引力理论来定义网络中节点间的虚拟引力,该引力的定义同时考虑到了节点重要性和节点相似性两种节点特性。算法在标签迭代更新过程中选取引力和最大的标签来更新当前节点的标签,以此来提高算法的稳定性和准确性。(2)针对大规模网络中的社团检测问题,本文中提出基于中间节点隶属强度的社团检测算法,通过分析中间节点在不同社团中的隶属强度来划分网络的社团结构。该算法首先根据网络的局部拓扑特征来定义网络的中间节点及其在社团中的隶属强度,其中隶属强度的定义仅基于网络中节点的局部拓扑特性以提高计算效率。考虑到网络的先验知识和节点不同特性对其所属社团的影响,隶属强度的定义中加入调节参数以控制不同特性的影响程度。迭代地分析中间节点在不同社团中的隶属强度以此来划分网络的社团结构。为了提升算法的效率和准确性,还提出两种简单的初始化方法与后处理方法。为了验证本文中提出的算法的有效性,本文实验部分采用了多个不同特性的网络数据集在多个指标上比较本文提出的算法与对比算法的性能。通过实验结果分析表明本文中的社团检测算法能够高效地检测出高质量的社团结构。

关键词： 社团检测   重叠社团   标签传播   模块度   公共安全  

摘要： 近几年,大数据、人工智能持续发展,变得越来越高效,在日常生活中也得到了广泛的应用。网络承载着庞大而复杂的数据信息。其内部结构的研究无疑蕴含着丰富的信息量和强大的吸引力,社团结构检测技术应运而生。分析网络的结构,描述网络的特征能够更好地认识网络的特质,预测网络更替的规律。现有研究的传统的社团检测方法中,非重叠社团检测算法为更多人所选择。但随着研究的深入,与实际网络更为匹配的重叠社团检测方法后来居上,开辟了新的研究思路。本文通过对SLPA算法的了解与研究的基础上,提出了基于模块度优化的重叠社团检测算法MLPA+算法。将模块度优化思想与SLPA算法相互融合,减少了SLPA在传播标签时的随机性,模块度比率平方根最大化的展现使得算法在前期进行初始社团划分,在标签传播阶段,通过计算比较Adamic-Adar指标选择最优邻居节点,当最优邻居节点有多个时,则选择它们的标签中出现次数最多的标签,对当前节点进行更新标签,最终使得社团检测结果更符合真实社团结构。通过在五组人工网络数据集和四组真实网络数据集进行社团检测,实验结果对比分析表明,MLPA+算法在功能上存在着明显的优势。加之算法的收敛速度较为迅速,结果也较改进前更加稳定,综合得出本文提出的算法具有较好的稳定性和鲁棒性。本算法参与某市公共安全部门合作课题“社团检测在特定行业的应用软件”,为更好地在案件侦破过程中提供有效帮助,确定组织参与活动的敏感人群提供更有效的分析方法。通过MLPA+算法对于重叠节点进行准确检测,缩小敏感人群范围,给与侦破案件提供重要的辅助性作用。通过MLPA+改进算法确定重叠节点,改进非重叠算法准确性低的不足之处,同时也为刑侦提供更加精准的信息以加快案情的推进。

关键词： 正则化   矩阵扰动理论   特征谱   重叠社团检测  

摘要： 社团检测即机器学习中的聚类问题一直是机器学习的一大热点问题。随着数据规模日渐庞大,数据结构也变得纷繁复杂,传统的聚类方法由于对某种特定结构的数据有强依赖性而导致普适性偏低。谱聚类算法（Spectral clustering,SC）将降维的思想与k-means算法相结合,特别是对于高维数据（如文本数据）来说,谱聚类算法比k-means算法计算复杂度要小,聚类准确率更高。目前,谱聚类算法已经成为了机器学习、通信等领域最为流行的聚类算法之一。谱方法因为其易于实现,适用范围广的优点受到了学者们的广泛关注。然而,大量的实验结果表明:如果数据集中存在噪声,那么谱方法往往不能给出令人满意的聚类结果。与此同时,现实世界中的数据又不可避免地存在有噪声,因此如何减小噪声对谱方法的影响是谱方法在真实数据集上应用的关键,也是本文的研究重点。针对这一问题,本文从谱方法的核心——特征谱的研究入手来构建模型,本篇论文的主要工作包括以下三个方面:1)模型框架;鉴于正则化的方法能够有效地提高算法的抗噪性。本文在传统的正则化谱聚类框架之上,通过引入信息熵的概念构建出了基于熵扰动的正则化谱聚类模型,该模型不仅解放了正则化参数固定的问题,同时还提高了谱聚类算法的抗噪性能。2)理论推导;本文算法是基于矩阵扰动理论提出的一类正则方法,通过矩阵扰动分析以及Davis-Kahan理论,笔者推导出了本文算法在扰动迭代过程中的理论阈值,提高了算法的普适性,完善了算法的理论基础。3)重叠社团检测;在本文最后,笔者将所提出的算法应用于重叠社团检测,在DBLP、Youtube等数据集上的实验结果证明了本文算法的有效性。