关键词： 社团检测   k核   加权图   紧密子图   贪婪策略  

摘要： k核查询是一种社团查询,由于其可以在线性时间内被有效计算,因此在社团检测中具有较广泛的应用。图中边的权值在很多场景下具有较强的语义关系,但现有研究较少考虑图中边的权值。为提升k核查询的效率,在k核的基础上定义加权图中的紧密k核子图查询(CRKSQ)问题,并使用归约方法证明该问题是NP-难的。基于贪婪策略设计启发式算法CRK-G,通过迭代删除节点为CRKSQ问题找到一个近似解。在此基础上,从降低图规模和减少迭代次数两方面研究CRK-G算法的优化策略,分别提出使用图压缩策略的算法CRK-C及使用单次多节点删除策略的算法CRK-F。在Bio-GRID、Email-Enron、DBLP 3个数据集上的实验结果表明,相对于CRK-G算法,CRK-C、CRK-F算法在查询速度上有较大的提升,且平均误差均在8%以内。

关键词： 动态网络   社团发现   增量   网络突变   累积误差  

摘要： 当前主流的动态社团检测算法通常基于社团结构平稳变化的假设,不能很好地处理网络突变和累积误差,提出一种增量式动态社团检测模型。将前一时刻的社团结构作为初始聚类结果,利用链路变化找出增量相关社团,利用网络变化度和社团稳定度局部调整初始聚类,得到符合当前网络拓扑的社团结构。在真实网络和合成的动态网络中的实验结果表明,所提算法可以准确地发现动态网络社团结构,能有效解决网络突变和累积误差等问题。

关键词： 院校竞争网络   社团检测   复杂网络   平行志愿  

摘要： 平行志愿录取规则与优质生源的紧缺使得院校在高考招生时存在激烈的竞争关系。从网络科学视角正确理解院校竞争关系,能够合理地指导考生进行志愿填报。利用2019年山西省高考理科录取成绩,通过改进的Jaccard相似度计算方法,构建院校竞争网络的邻接矩阵。基于复杂网络度量方法,实证研究院校竞争网络得到:1)度分布存在一定的异质性,且具有较大的平均度;2)簇度负相关表明院校竞争网络存在层次结构;3)富人俱乐部连通性表明度数大于375的院校完全连通构成富人俱乐部;4)利用基于节点标签与网络结构的社团划分算法,通过基尼不纯度评估社团内院校的同质性,进一步利用Louvain算法识别社团内院校存在层次化差异结构。这些实证结果刻画了院校竞争关系,在此基础上归纳了一些指导考生进行合理、分梯度志愿填报的建议和策略。

关键词： 用频规划   多目标优化   蚁群算法   贪心策略   社团检测  

摘要： 为全面描述联合作战用频规划问题,引入多目标优化理论,以干扰冲突最少、需求满足最高和邻频风险最低作为优化目标建立了多目标的联合作战用频规划模型,并提出一种求解联合作战用频规划问题的非支配排序蚁群算法.在蚁群初始化阶段使用带贪心策略的爬山算法获取次优解集合以提升蚁群前期收敛速度,并运用社团检测机制将用频装备分簇以减少电磁干扰分析的计算复杂度从而加快算法进程.同时,在算法每次迭代中对得到的用频规划方案执行调度改进操作,并自适应调整信息素挥发系数等参数,以提升算法全局优化性能.仿真实验验证了模型的有效性,并通过反转世代距离与超体积指标证明了算法在收敛性、分布性与收敛速度上的优越性.

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

摘要： [研究目的]面向在线社交网络舆情数据,基于符号网络建模舆情实体的正负关系,研究符号网络社团检测模型挖掘舆情数据中的语义社团,进一步推演出对于某事件群众的普遍看法,适用于真实社会网络中的事件检测,有助于创新舆情情报分析方法。[研究方法]主要从符号网络特性入手,在半非负分解过程中引入深度学习的框架,提出深度半非负矩阵分解模型(DSNMF),进一步将舆情情报分析及复杂网络科学有机结合,利用“‘司马3忌’举报韩红爱心慈善基金会”热点事件所产生的微博舆情数据构建舆情情感符号网络,基于DSNMF模型进行舆情情报实证分析。[研究结论]大量实验表明:DSNMF模型有效提升了符号网络社团检测性能;证实了符号网络社团检测模型在舆情情报分析中的有效性。

关键词： 犯罪数据分析   复杂网络   社团检测   诈骗模式  

摘要： 近年诈骗犯罪呈现高发事态增长,对人民的生产与生活产生重大影响。从诸多犯罪数据中挖掘诈骗犯罪的模式有助于制定合适的措施以节制诈骗案件的发生,有力保护人民财产,构建和谐社会。基于诈骗犯罪数据,通过抽取涉案人员、地点、时间等实体构建犯罪复杂网络,用于挖掘犯罪事件中的主体对象、对象间关系与团伙结构,由此确定了六类典型欺诈模式,为诈骗犯罪的侦破与预防提供理论和技术支撑。

关键词： 固件比对   社团检测   复杂网络   函数相似性   BGLL算法  

摘要： 固件比对是二进制比对技术的重要分支.然而,既往研究关注于函数的表示方法的优化却忽略了对过滤器的设计优化,导致固件常因包含同构函数引发误匹配,以致现有二进制比对技术应用于固件比对时效果不够理想.为此,提出基于社团检测算法的固件比对技术,首次将复杂网络相关理论应用于二进制比对领域.通过社团检测算法将固件内的函数划分为若干社团,利用社团匹配实现过滤器的功能,再根据匹配社团寻找匹配函数;此外,优化了函数相似度计算方法,设计了操作数相似性计算方法.在实现原型系统后,使用1382个固件构建2个数据集进行实验,验证了可行性,分析了基于社团检测算法的固件比对方法的性能,确定了各参数的合理取值,设计了评估指标可信匹配率,并比较了该方法与Bindiff的比对效果.实验表明:该方法可以提升Bindiff比对结果5%~11%的正确率.

关键词： 复杂网络   社团检测   图像预分割   运动目标检测   多目标跟踪  

摘要： 近年来,计算机视觉研究蓬勃发展,在视频监控、无人驾驶、虚拟现实等领域带给人们新的体验。图像分割、目标检测和跟踪是计算机视觉领域内的重要任务,是一系列高级任务的基石。本文将复杂网络社团检测方法应用于图像分割、运动目标检测和多目标跟踪,具体工作内容如下: (1)提出了一种基于图像轮廓信息的网络构建和图像预分割算法。首先利用MS算法检测图像中的轮廓,将轮廓划分的区域作为网络中的节点,区域间的颜色相似性作为相应节点连边的权值,构建了图像的加权区域邻接网络;然后结合社团检测算法构建了图像的预分割算法。实验表明,本文的图像网络结构优于基于像素和超像素的图像网络,本文的图像预分割算法相比其他算法也有优势。 (2)提出了一种基于图像预分割和背景建模的运动目标检测算法。将首帧视频利用本文算法进行预分割,并将分割结果应用到后续视频帧,通过计算连续帧间不同分割区域颜色的绝对差和,建立背景模型;根据区域的熵值更新背景模型,与当前帧做背景差分,得到差分图像,对其再次用本文方法做预分割,分析差分图像不同区域的亮度平均值,得到自适应的前景阈值,从而检测出运动目标。实验结果表明,本文算法的检测结果令人满意,并且在前景目标短暂停止时的检测结果优于其他算法。 (3)提出了一种基于目标检测的视频帧间网络构建和多目标跟踪算法。首先将视频各帧的目标作为网络节点;然后综合目标的外观特征、HOG特征和位置特征计算相邻两帧中目标的相似性,为对应节点的边赋予权值;最后分组检测视频帧间网络的社团结构,得到该组视频中目标的轨迹片段,合并轨迹片段得到目标的最终轨迹。实验结果表明了本文算法跟踪目标的有效性,同时在MOT17数据集上的测试结果也表明,本文算法有着较高的跟踪准确度,并且对无严重遮挡的检测目标能够稳定跟踪。

关键词： 复杂网络   社团检测   潜在语义分析   图表示学习   聚类  

摘要： 在我们的日常工作和生活中,充斥着各种各样的复杂系统。在这些复杂系统中,看似纷繁复杂的实体及其之间的关系,实际上可以被抽象为节点和边。这样,由实体和实体之间的关系组成的复杂系统,就被抽象为由节点和边构成的复杂网络。社团结构作为复杂网络中的重要特征之一,其在复杂网络中通常对应于相应的功能模块,如何发现复杂网络中的社团结构成为研究人员探索复杂网络的一个研究热点,从而有大量的社团检测算法被提出。在对已有的社团检测算法进行了充分的研究后,本文也分别基于潜在语义分析(Latent Semantic Analysis,LSA)和节点关系强化策略,提出了两种社团检测算法。(1)基于潜在语义分析的社团检测算法LSACD。该算法采用LSA算法的思想,将网络中的节点当作词项,将从每一个节点出发进行随机游走得到的节点序列当作文档,构建节点-文档矩阵;然后通过向量空间模型(Vector Space Model,VSM)得到矩阵中每一个元素的词频-逆文档频率(Term Frequency-Inverse Document Frequency,TF-IDF)值,其中,矩阵的每一行表示每一个文档对应节点的初始向量表示;接着利用奇异值分解(Singular Value Decomposition,SVD)算法对节点-文档矩阵进行分解,得到节点-节点、节点-文档以及文档-文档之间的向量关系,并且获得每个节点的最终向量表示;最后,通过对节点向量进行聚类得到社团结构。(2)基于节点关系强化策略的社团检测算法FLLNE。FLLNE算法是在社团检测算法的基础上,与图表示学习算法和聚类算法相结合而提出的一种通过增强网络中的节点关系来进行社团检测的算法。该算法首先通过快速社团检测算法检测得到初始社团结构,属于同一个社团中的节点,它们之间的连接关系比不在同一个社团中的节点之间的连接关系更强。为了增强这些节点的连接有效性,使它们之间的连接关系更加紧密,对于节点之间已有连接关系的边,算法在其初始权值为1的基础上再增加初始社团结构的模块度作为权值;对于没有连接关系的节点对,算法对它们进行加边处理并赋予模块度作为新增边的权值。然后将得到节点关系强化处理的网络输入到图表示学习算法中,获得整个网络中所有节点的向量表示;最后,通过对节点向量进行聚类得到最终的社团结构。本文在多组人工合成网络和多个实际网络上对所提算法进行了大量实验,并与众多具有代表性的对比算法进行了对比实验。实验结果充分表明,本文所提算法能够在不同的网络中提取出高质量的社团结构。