一种基于最大公共子图的社交网络对齐方法

随着Internet的普及,各类社交网络走进人们的视野,用户为满足不同的服务需求,往往不会局限于单一社交网络中,因此,跨社交网络环境下的用户识别问题成为研究者的热门话题.主要利用网络结构信息,针对社交网络对齐问题进行研究,主要包含以下研究点：首先,将网络对齐问题抽象为最大公共子图问题（α-MCS）,并提出求解自适应参数α的方法,相比于传统的基于启发式定义参数α的方法,该方法可有效区分不同类型网络中匹配用户与非匹配用户;其次,为快速而准确地解决α-MCS,提出了基于最大公共子图的迭代式网络对齐算法MCS_INA（α-MCS based iterative network alignment algorithm）,该算法每次迭代过程主要包含两个阶段.第1个阶段,分别在两个社交网络中选取各自的候选匹配用户,第2个阶段,针对候选匹配用户进行识别.相比于其他算法,MCS_INA时间代价低,且依据不同网络特征,通过参数估计,可保证较高的识别精度;最后,在真实数据集和合成数据集中验证了算法MCS_INA的有效性.     

基于类别信息的特征子图选择策略

选择频繁的特征子图在基于频繁子图的图数据分类中起着非常重要的作用.提出了一种基于类别信息的特征子图选择策略,即从候选的频繁子图中选出独有频繁子图和显著频繁子图作为特征子图.实验结果显示,在对化合物数据分类时,该选择策略在分类性能上优于SVM方法特征选择策略和CEP方法的特征选择策略.     

基于子图选择和图核降维的脑网络分类方法

脑网络分类在脑科学研究和脑疾病诊断等领域引起了学者们的广泛关注。目前大多数有关脑网络分类的研究都是以单个脑区或成对脑区之间的相关性作为分类特征,其缺点是不能反映多个脑区之间的拓扑结构信息。为克服上述缺点,提出了一种基于子图选择和图核降维的脑网络分类方法。具体包括：（1）分别从正类训练样本组及负类训练样本组中提取多个频繁子图,进而利用基于频度差的子图选择算法选取最具判别性的子图集;（2）基于上述过程中得到的子图集,利用图核主成分分析（graph-kernel-based principal component analysis,GK-PCA）方法对经过子图选择后的图数据进行特征提取;（3）利用支持向量机（support vector machine, SVM）在特征提取后的数据上进行分类。在真实的轻度认知障碍（mild cognitive impairment,MCI）脑网络数据集上对该方法进行了验证,实验结果表明了该方法的有效性。     

一种基于代价子图的子字并行指令选择算法

子字并行能够充分利用多媒体算法的数据精度小、内部循环处理形式规则的特点,是加速多媒体处理的有效方式。然而,如何充分挖掘多媒体应用中的子字并行仍然是一个难题。本文说明传统的并行技术可以有效地开发循环中的子字并行性,同时提出一种基于代价子图的子字并行指令自动识别的方法。与其他方法相比,该方法利用代价模型对子子字并行指令选择进行定量评估。本文在TTA体系结构框架下实现了这一方法。实验结果表明,该方法可以充分地提取循环中的子字并行性。     

基于FSG的最大频繁子图挖掘算法*

图挖掘已成为数据挖掘领域研究的热点,然而挖掘全部频繁子图很困难且得到的频繁子图过多,影响结果的理解和应用。可通过挖掘最大频繁子图来解决挖掘结果数量巨大的问题,最大频繁子图挖掘得到的结果数量很少且不丢失信息,节省了空间和以后的分析工作。基于算法FSG提出了最大频繁子图挖掘算法FSG-MaxGraph;结合节点的度、标记及邻接列表来计算规范编码,提出两个定理来减少子图同构判断的次数,并应用改进后的决策树来计算支持度。实验证明,新算法解决了挖掘结果太多理解困难的问题,且提高了挖掘效率。     

一种基于最大频繁子图基因的模糊图神经网络检测模型

针对恶意软件检测的准确性和时间效率问题,提出一种基于最大频繁子图基因的模糊图神经网络检测模型。首先利用SFFSM-SPIN-MGM方法挖掘恶意软件函数调用图的最大频繁子图,然后利用模糊图神经网络完成恶意软件同源性检测。实验结果表明,该方法具有较强的泛化能力,能够有效地检测现有恶意软件的变种测试集,平均准确率92.1%,平均误报率4.3%、平均漏报率1.4%。     

加权最大频繁子图挖掘算法的研究

如何从大量的图中挖掘出令人感兴趣的子图模式已经成为数据挖掘领域研究的热点之一。传统的频繁子图挖掘方法对满足最小支持度阈值的子图同等对待,但在真实数据库中不同的子图往往具有不同的重要程度。为解决上述问题,提出了一种深度优先的挖掘加权最大频繁子图的新算法。首先给出了一种新的用于计算图的邻接矩阵规范编码的结点排序策略,大大降低了求图规范编码的复杂度,并可以加速子图规范编码匹配的速度。其次,给出了加权最大频繁子图的定义,不仅可以找出较为重要的最大频繁子图,而且可以使挖掘结果同样具有反单调性,从而可加速剪枝。实验结果表明,提出的算法不仅可以有效地减少挖掘结果的数量,而且具有较高的效率。     

基于最大公共子图的本体映射方法研究

本体映射是对两个本体中的各元素建立语义关系,而影响本体映射的关键是相似度的计算方法。针对相似度计算方法中仍存在语义关系不精准的问题,提出一种本体映射方法,把本体映射问题转化为求解最大公共子图的问题。以图结构表示的本体可更好地体现本体结构之间潜在的语义关系,应用最大公共子图提取本体中的公共部分,并用最大公共子图的性质计算2个本体中元素之间的相似度,进而得到2个本体之间的映射关系。实验结果表明,与Ctx Match,COMA相比,该方法在召回率和准确率方面都有一定提高。     

基于最大频繁子图挖掘的动态污点分析方法

目前,传统面向恶意代码识别的动态污点分析方法广泛存在行为依赖图数量巨大、匹配时间消耗长的问题.提出一种动态污点分析方法——基于最大频繁子图挖掘的动态污点分析方法.该方法从恶意代码家族行为依赖图挖掘出代表家族显著共性特征的最大频繁子图,被挖掘出的最大频繁子图即为某类恶意代码家族以及该家族所有变种之间最为突出的共有特征,使用挖掘出的最大频繁子图与被测行为依赖图进行比较匹配即可.既能够保证原有恶意代码特征无丢失又削减了行为依赖图数量,并在此基础上进一步提升了识别效率.经实验分析,提出的这种新的动态污点分析方法相比于传统方法,当最小支持度为0.045时,行为依赖图数量减少了82%,识别效率提高了81.7%,准确率达到了92.15%.     

基于不确定性PPI网络的最大稠密子图挖掘*

研究表明使用PPI数据进行蛋白质功能预测是很有意义的。然而,从生物学实验得到的PPI数据一般是含有噪声的、不完全的和不精确的,这使得将PPI网络作为不确定图来处理变得更加合理。提出了一种基于深度优先搜索策略和点扩展的挖掘算法,它可以有效地从不确定的PPI网络中挖掘最大稠密子图。该算法使用了几种高效的剪枝技术来提高挖掘的时间效率。在酵母菌PPI数据上的实验结果表明该算法在精度和效率上都有很好的表现。     

最多叶子生成树问题的核化算法

对算法领域的最多叶子生成树问题进行了深入研究,提出了对简单连通图2度节点的化简规则,并证明了不含2度节点的图的生成树的叶子节点数的下限为(N+6)/4,给出了构造这样一棵生成树的构造性方法.基于上述化简规则和所证明的结论,给出了最多叶子生成树问题的核化算法,该核化算法可以在O(n2)时间内得到一个4k-6大小的线性核.对于这样一个较小的核,将大大提高相关的参数算法和近似算法的性能.     

无线Mesh网中可靠SIP呼叫连接的选路技术

在无线Mesh网中布设基于SIP的应用,是在缺少通信基础设施的地区实现多媒体应急通信的有效方式,但是易失效的无线链路会降低通信的可靠度。研究了如何在无线Mesh网中向SIP服务器高效地转发SIP呼叫请求消息。提出了一点对多点中任意一点的可靠度度量模型,用于描述实时、有限尝试次数的呼叫连接通信的可靠性;基于呼叫成功率、呼叫连接速度这两个优化目标提出了一种路集选择方法,并展开了对这种方法的通信可靠度上下界的分析和比较;最后通过仿真实验验证了此路集选择方法的有效性和优越性。