关键词： Potts Spin-glass   合谋   复杂网络   社团检测  

摘要： 工程招投标作为项目前期资本规模控制的一种重要方式,在项目全生命周期的成本控制方面扮演着至关重要的角色,并随着经济的发展在各行各业得到了广泛的应用并取得良好的效果,为各项投资节省了大量资源,但是由于建筑行业本身的特点,招投标阶段被认为是腐败现象频发的阶段,存在包括围标串标等诸多不合理行为,甚至在一些地区存在着“无标不围、无标不串”的严重情况。而如何识别合谋行为一直是监管机构的痛点和难点。本文从影响合谋行为发生的主要因素及其表现形式,分析了国内外对合谋行为界定的主要方法,提出将行为科学中的复杂网络技术应用到建设项目招投标阶段的合谋行为检测中。广东省是我国实施招投标较早的地区,其招投标数据完善程度较高。因此,文章利用文献调研法对需要收集数据和模型对应指标进行统计分析,采用爬虫技术获取广东省2015-2020年间关于招标、资格审查、中标以及投标企业负责人等信息,建立ACCESS数据库对以上信息进行整合,建立数据之间的连贯性。利用python3.6.3对数据中的缺失值、噪声值及异常值进行预处理,以Graph模块建立投标人无向加权复杂网络,结合基于动态社区检测方法的Potts Spin-glass算法进行社团结构挖掘。该算法相较其他方法,具有自动识别最稳定基态达到最优划分的优点。为了使社团划分更加合理,文章首先将社团划分为10个较大社团,针对社团中的典型社团结构,对其进行二次社团结构挖掘,分析特征值,验证了该算法对合谋行为挖掘的适用性,并对其他社团结构二次挖掘,得出最优投标人社团结构。最后,将该算法与其他算法进行时间复杂度对比,验证spin-glass算法在社团结构挖掘方面的优势及适用性,利用项目投标报价规律分析和网络中公开的围标串标行为处罚通知对挖掘出的社团结构进行验证,进一步证明了复杂网络中社团结构挖掘技术对招投标合谋行为识别的正确性和适用性,并结合大数据和区块链技术,提出相应的合谋行为治理机制。

关键词： 有向无环网络   社团检测   聚类   近似度   网络嵌入   节点角色  

摘要： 有向无环网络是一类特殊的不包含环的网络,普遍存在于生物学、遗传学、金融学等领域。社团是网络介观尺度上最突出的结构特征之一,对网络功能有着至关重要的影响。网络社团结构检测和分析已成为一个重要的主题,吸引了众多不同领域学者的关注。对有向无环网络中社团结构的检测是深入理解整个网络功能的重要途径之一。通常,由实际系统构建的有向无环网络的边具有对抗或相似两种关系。现有的大多数社团检测算法并不适用于边对抗有向无环网络,对于边相似有向无环网络也存在与聚类算法割裂、复杂度高的问题。针对以上现象,本文探究了两种类型的有向无环网络中的社团检测,主要研究内容和成果如下:提出了可用于寻找边对抗有向无环网络中社团的Katz-Simrank方法,分别利用Katz和Simrank++近似度捕捉节点的序和相似度信息,将有向无环网络中的社团检测问题转化为有权无向网络中的派系检测问题。在对四种不同类型的有向无环网络的测试中,该方法获得的社团划分的标准化互信息、调整兰德系数、同质性和多样性指标均优于先前的基于模块度的方法和分层方法,验证了该方法的有效性。针对边相似有向无环网络,利用Katz近似度来刻画节点之间的相互作用紧密程度,将其作为它们的相似度对相似度量图嵌入(FVERSE)算法进行改进,结合Kmeans提出基于Katz-FVERSE的社团检测框架。在各人工网络和真实网络上进行测试后发现,该框架获得的标准化互信息和模块度指标有87.5%的比例超越和接近其他最优框架,验证了该框架的有效性。将基于Katz-FVERSE的社团检测框架分别应用于不同度分布的人工引文网络和真实网络中,发现基于社团结构的节点角色和节点重要性之间存在显著联系。多数边位于所属社团和许多边连接不同社团的中心节点有81.4%和75%的概率是重要节点,远高于其他角色的节点并具有统计显著性。因此,可以通过社团检测来判断网络中节点的角色从而实现重要节点的预测。

关键词： 复杂网络   社团检测   非负矩阵分解   节点特征   层次信息  

摘要： 社团检测是复杂网络分析的重要组成部分,通过社团检测算法对网络进行社团结构划分,能够帮助人们挖掘出复杂网络的结构特征和与之相关的功能特性。近几十年来,学者们已经提出了大量的社团检测算法,但是这些算法通常只关注网络的拓扑结构信息,不能够对于图中的孤立点进行有效地划分。本文在深入分析现有社团检测算法的基础上,结合节点特征信息和网络层次信息提出两种新的社团检测算法,旨在提升社团检测的准确性,主要研究内容如下:(1)为了将社交网络中的孤立点划分到合适的社团中,本文提出了一种结合节点特征信息和拓扑结构信息的社团检测算法——CSNMF。CSNMF使用由解码器和编码器构成的自编码非负矩阵分解框架整合网络的拓扑结构信息与节点特征信息,基于拓扑结构信息与节点特征信息的相似度设定自适应参数,有效地控制了节点特征信息对于社团划分的贡献率,确保节点特征信息对拓扑结构信息进行有效地补充,从而提高社团检测的准确性。此外,CSNMF保留了非负矩阵分解框架良好的可解释性,能够对所划分的社团结构的特征进行准确地描述。(2)此外,本文提出了一种结合节点特征信息与拓扑结构信息的深度自编码器非负矩阵分解模型——DSCNMF,进一步提升社团检测的准确性。DSCNMF通过深度自编码器框架,将原始网络的拓扑结构信息进行层次化分析,从而学习原始网络和最终社团划分之间的分层映射,能够在中间层学习原始网络隐含的从低到高隐藏层次信息;DCSNMF不仅利用了节点特征信息,而且将节点特征信息建模到深度自编码器框架,同时通过调节系数控制节点特征信息的贡献率,以此来保证该算法对于非完全图的社团检测性能。为了验证CSNMF和DCSNMF的有效性,本文在多个真实的社交网络数据集上进行了实验。与最新的相关社团检测算法相比,CSNMF和DCSNMF均能够有效地划分出网络中存在的社团结构,而且DCSNMF在层次信息较为丰富的网络中具有更好的社团检测性能。

关键词： 社团检测   多层网络   重叠社团   稀疏表示   非负矩阵分解  

摘要： 随着数据获取技术的快速发展,规模庞大、类型多样、结构复杂的数据日益增多,如果能对数据进行有效地分析与处理,发现数据之间潜在的内部关系,对相关领域的研究将具有重要意义。当前,现实世界中的数据大都可以表示为不同个体以及个体之间的相互联系,因此可以映射成网络的形式。网络中的节点表示个体,边表示个体之间的连接关系。社团检测是网络分析中一个重要的研究方向,旨在将复杂网络中的数据点划分到不同的簇中,使得簇内的联系尽量地稠密,簇之间的联系尽可能地稀疏,从而挖掘出复杂网络中潜在的社团结构,使人们更好地认识和理解复杂网络,研究网络结构、功能和特性,因此被广泛应用于大数据与人工智能的相关研究中。目前已经有许多学者对社团检测问题进行了研究,这些工作主要集中于单层网络,即网络的节点之间只存在一种连接形式,但是现实环境中的网络可能同时具备多种连接类型。比如在社交网络中,个体之间会通过电话、短信、微博等多种方式进行联系,只有获取所有平台的信息,才能准确判断网络中的两个个体是否属于同一个社团。为了涵盖这些关系的多类型特性,通过相同的节点集合,分层描述不同连接,以构成多层网络,并对其进行社团检测显然具有更强的科学意义,因此在最近几年引起了网络科学界的广泛关注。然而,现有方法只是将多层网络的连接简单地平均融合为单层网络,而没有考虑不同连接类型对社团检测的重要程度,从而严重干扰融合后单层网络的社团结构。此外,多层网络中层间连接差异性很大,且多层结构可能会进一步加剧层内连接稀疏性,目前尚缺乏鲁棒的多层网络社团检测策略以系统地挖掘网络结构。针对上述问题,本文对多层网络中社团检测进行了深入研究,取得了如下研究成果:(1)提出了一种新的分层联合表示算法以识别多层网络中的社团。考虑到多层网络中不同连接的噪声差异会导致社团检测性能参差不齐,该算法提出了一种自适应地层加权策略,通过不断更新不同层的权重,以描述各层网络对社团检测的重要程度。此外,算法以非负矩阵分解为基础,同时强制相邻层网络的低维表示向量彼此接近,以获取一致的低维表示,从而揭示跨层共享的社团结构。此外,我们还设计了相关优化方法,通过交替迭代的方式同时优化分解因子和不同层的权重,直到收敛。在包括引文,社交,经济和生物网络等各种类型的复杂网络上的大量实验结果表明该方法具有良好的社团检测准确性。(2)提出了一种基于子空间的多层网络社团检测算法。面对多层网络的稀疏性与连接差异,该方法将稀疏子空间思想推广到多层网络中以提升社团检测鲁棒性,并将不同层之间的低维表示相似性约束作为距离正则项,和非负约束条件共同集成到稀疏子空间聚类框架中,使其能够同时利用数据的全局和局部信息进行图学习。并进一步引入了一种新颖的稀疏约束,以促进学习到的图具有更为清晰的聚类结构。针对该问题,我们还特别设计了一种有效的迭代算法对框架进行优化求解。在多个领域的数据集的实验结果表明该方法可以显著提高复杂网络的社团聚类性能。

关键词： 社团检测   动态网络   图聚类   图嵌入   乳腺癌早期诊断  

摘要： 现实世界中的复杂系统均可用复杂网络进行建模,复杂网络分析对探索现实世界中的运行机制及变化规律具有重要意义。社团检测作为复杂网络分析的研究热点之一,近年来受到了学者们广泛的关注。社团指的是一组与内部节点连接紧密,与外部节点连接稀疏的的节点集。社团检测能够揭示节点之间的相似关系和交互规律。当前的社团检测算法致力于静态网络社团检测,而真实世界是动态变化的。静态网络社团检测算法不能很好的追踪和描述动态网络社团的演化过程,极大地阻碍了社团检测在现实世界中的应用。因此,本文提出三种动态社团检测算法:基于三阶时序平滑的动态社团检测算法,基于边平滑的动态社团检测算法和基于属性融合的动态社团检测算法。在人工动态网络和真实世界动态网络上的实验结果表明,所提出的算法均能取得最好的效果。本文的主要贡献可总结如下:(1)“社团平滑”视角看,动态网络社团平滑需保证相邻时刻中同一社团内的成员不发生较大变化。本文提出了一种新的基于图嵌入的三阶时序局部平滑框架,通过引入图嵌入矩阵代替原邻接矩阵,不仅能对原矩阵进行维数约简、降低算法时间复杂度,还能更好的学习和保存原拓扑结构中的高阶相似度信息。通过引入三阶时序局部平滑,能更好的描述动态网络的演化规律,使得动态网络的聚类结果更加鲁邦。文中的实验结果表明该模型能够有效地追踪和检测动态网络的演化过程。(2)“边平滑”视角看,动态网络的边平滑需增强相邻时刻网络中公共边带来的聚类信息,消除噪音边带来的聚类干扰。本文提出了新的联合学习图嵌入与边平滑的动态社团检测框架。联合学习框架能够保证图嵌入过程学习到更适用于聚类的特征、同时图聚类受图嵌入的引导而得到更高的聚类准确率。边平滑策略的提出能够更有效的从微观动力学的角度分析动态社团的演化过程。文中实验结果表明该模型不仅能够获得融入聚类信息的图嵌入表示,还能得到准确、鲁邦的社团检测结果。(3)“属性融合”视角看,动态网络中除拓扑结构信息外,还有丰富的节点属性信息。本文提出联合分解动态网络拓扑结构信息和节点属性信息的框架,并将其应用于癌症动态模块的检测中。通过联合分解,图的拓扑结构信息与节点属性信息进行了充分的融合。在真实乳腺癌网络上的大量实验表明,我们的算法不仅能准确抓取某些已知乳腺癌的致病基因模块,还为乳腺癌的早期诊断提供了参考依据。本文提出的动态社团检测算法,是对动态网络社团检测的有效探索。所提出的多种算法不仅为复杂网络分析领域提供了新思路,而且具有理论意义和应用价值。

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

摘要： 如今,数据的大规模增长致使工程领域中产生了大量具有高维性,动态性,层次性和相关性的复杂数据。针对复杂数据的研究对科技的进步具有重要意义。多任务聚类和动态社团检测作为研究复杂数据的重要方式,受到了学者们越来越多的关注。多任务聚类共同学习多个任务,通过在相关任务间迁移知识提升每个任务的聚类性能。社团检测通过揭示节点间相互关系,找出紧密相连的节点簇,使得簇内节点强连接,而簇间的节点弱连接。动态社团检测跳出静态网络社团检测的局限,结合网络的时序性对社团进行检测。然而,数据的复杂性降低了现有算法在系统功能研究上的准确性,极大的阻碍了多任务聚类和动态社团检测算法的发展。非负矩阵分解（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)针对传统依靠节点邻居衡量节点相似度准确性低、随机选取聚类中心节点导致最终社团检测质量不稳定等问题,提出一种基于节点密度和相似度的社团检测算法。算法考虑到节点最短路径对节点相似度的影响,给出一种结合节点邻居和节点最短路径来改进节点相似度的度量方法;定义节点密度,为聚类中心节点的选取提供依据。首先根据节点密度最大且节点之间相似度小的原则选取初始聚类节点,然后利用最大相似度原则进行社团划分,最后以优化模块度为指标进行社团检测。(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算法的有效性。