不确定图
不确定图的相关文献在2009年到2022年内共计95篇,主要集中在自动化技术、计算机技术
等领域,其中期刊论文63篇、会议论文9篇、专利文献138613篇;相关期刊36种,包括中国管理信息化、燕山大学学报、东南大学学报(自然科学版)等;
相关会议4种,包括2013中国计算机大会、第28届中国数据库学术会议、第27届中国数据库学术会议等;不确定图的相关文献由175位作者贡献,包括李建中、邹兆年、赵翔等。
不确定图—发文量
专利文献>
论文:138613篇
占比:99.95%
总计:138685篇
不确定图
-研究学者
- 李建中
- 邹兆年
- 赵翔
- 陈一帆
- 张柏礼
- 杨健
- 吕建华
- 周军锋
- 徐周波
- 杜明
- 肖卫东
- 葛斌
- 高宏
- 黄文文
- 冯文全
- 刘华东
- 尚学群
- 张炜
- 朱楠
- 朱鎔
- 李景文
- 王冬
- 王勇
- 韩蒙
- 黄鑫
- 丁悦
- 于东晓
- 仲悦
- 何向南
- 傅星珵
- 刘鹏
- 周傲英
- 周广露
- 姜守旭
- 孟雅
- 常亮
- 张一楠
- 张安珍
- 张应龙
- 张旭
- 张春英
- 张海杰
- 张硕
- 张阳
- 张雪
- 徐亚军
- 李先贤
- 李富豪
- 李峰
- 李翠平
-
-
郑剑;
杨立聪
-
-
摘要:
在社交网络的隐私保护中,针对三元闭包算法存在无法提供可控的隐私保护和无法抵御背景知识攻击的问题,结合差分隐私技术,提出基于三元闭包的不确定图差分隐私保护改进算法。改进算法首先利用三元闭包原理对原始社交网络图进行加边形成三角形,然后对三角形的边赋予符合拉普拉斯分布的存在概率,最后,根据社交网络图中每条边的存在概率生成新的社交网络图。改进算法将差分隐私应用于保护社交网络图的边关系,不仅提供了可控的隐私保护,而且可以抵御背景知识攻击。理论证明,改进算法满足差分隐私,针对算法的隐私保护性分析设计了一个基于信息熵的实验,实验结果表明,改进算法的隐私保护性优于三元闭包算法,适合需要更高隐私保护性的场景。
-
-
仲悦;
杜明;
周军锋
-
-
摘要:
目的给定一个不确定图,k步可达查询返回u到v在k步以内可达的概率。方法目前关于k步可达的索引方法都只适用于确定图,而不确定图上通常采用直接抽样求估计值。结果本文提出一种两阶段概率图上k步可达查询策略:首先基于顶点覆盖集构建确定图的k步索引,用于快速过滤肯定不可达的查询;其次针对不确定图,使用基于路径和提前抽样的方法来回答查询。结论实验结果验证了本文方法的高效性。
-
-
仲悦;
杜明;
周军锋
-
-
摘要:
目的 给定一个不确定图,k步可达查询返回u到v在k步以内可达的概率.方法 目前关于k步可达的索引方法都只适用于确定图,而不确定图上通常采用直接抽样求估计值.结果 本文提出一种两阶段概率图上k步可达查询策略:首先基于顶点覆盖集构建确定图的k步索引,用于快速过滤肯定不可达的查询;其次针对不确定图,使用基于路径和提前抽样的方法来回答查询.结论 实验结果验证了本文方法的高效性.
-
-
张艺;
邹晓红
-
-
摘要:
为了提高不确定图中极大团挖掘的效率,针对经典极大团挖掘算法中递归次数多与顶点集合更新耗时的问题,结合团概率的定义,提出了递归前计算集合概率来减少递归次数的不确定图中极大团挖掘算法.在已有算法的基础上只维持候选顶点集合,删除已使用顶点集合的计算,根据候选顶点集合和待扩展顶点集合的大小,从两种情况计算扩展后的集合概率,验证是否为α-团.对于挖掘到的全部α-团,提出了改进的极大团验证算法,结合伪极大团首先被顶点数量最多的极大团包含的特性,利用顶点的倒排表去除伪极大团.通过在不同的真实数据集上进行实验测试,验证了改进后的算法具有更高的执行效率.
-
-
-
赵孟
-
-
摘要:
为了更加高效地枚举出不确定图极大团,通过对现有确定图和不确定图极大团枚举算法进行研究,结合在相同图结构下确定图极大团与不确定图极大团之间的关系,提出了一种基于相同图结构确定图极大团子图划分的高效不确定图极大团枚举算法D-MULE-D。通过在不同的真实数据集上进行实验测试,对比D-MULE-D算法和MULE算法的运行时间,验证D-MULE-D算法的可行性和高效性。
-
-
杜明;
钟鹏;
周军锋
-
-
摘要:
极大团作为稠密子图中具有代表性的一种,一直是数据挖掘领域关注的重点。极大团中蕴含的重要数据信息也被广泛应用于各种领域,例如社交网络中的社区发现等。本文研究在不确定图上枚举所有极大团的问题。现有方法基于"子图划分-求解-验证"的思想,可以有效利用极大团性质加速计算过程,但其问题在于验证算法DPMC的效率不稳定。当满足条件的极大团数量增多时,验证的效率会急速下降,严重影响系统的整体性能。本文提出一种高效的验证算法FDPMU,通过构建映射表以及动态构建的倒排表,提高了算法的运行效率。最后,在多个真实数据集上进行比较,实验结果验证了FDPMU算法的高效性。
-
-
吴振强;
胡静;
田堉攀;
史武超;
颜军
-
-
摘要:
社交网络平台的快速普及使得社交网络中的个人隐私泄露问题愈发受到用户的关心,传统的数据隐私保护方法无法满足用户数量巨大、关系复杂的社交网络隐私保护需求.图修改技术是针对社交网络数据的隐私保护所提出的一系列隐私保护措施,其中不确定图是将确定图转化为概率图的一种隐私保护方法.主要研究了不确定图中边概率赋值算法,提出了基于差分隐私的不确定图边概率赋值算法,该算法具有双重隐私保障,适合社交网络隐私保护要求高的场景.同时提出了基于三元闭包的不确定图边概率分配算法,该算法在实现隐私保护的同时保持了较高的数据效用,适合简单的社交网络隐私保护场景.分析与比较表明:与(κ,ε)-混淆算法相比,基于差分隐私的不确定图边概率赋值算法可以实现较高的隐私保护效果,基于三元闭包的不确定图边概率分配算法具有较高的数据效用性.最后,为了衡量网络结构的失真程度,提出了基于网络结构熵的数据效用性度量算法,该算法能够度量不确定图与原始图结构的相似程度.
-
-
黄睿智;
黄德才
-
-
摘要:
传统的无监督关键词抽取算法往往无法反应词汇语义信息,而通过词频等方式来衡量一个词的重要性使其在面对短文本时准确率较低.为能兼顾词间语义关系、词位置关系及词频,结合word2vec提出了一种词间的文本局部相似度公式,并通过词间关系建立了不确定图模型,在提出顶点密度概念及候选关键词评价指标DEN的基础上,提出了基于不确定图的候选关键词抽取算法,并结合IDF提出了关键词评价的优化标准DEN-IDF.这种关键词抽取的新方法不依赖于外部人工标注数据,能够实现全程无监督.通过大量文本实验仿真发现,DEN-IDF的准确率比TF-IDF提高了8%左右,比TextRank提高了12%左右.%The traditional unsupervised keyword extraction algorithm cannot reflect the semantic information of the words, and its way to measure the importance of a word through word frequency makes it always has a lowprecision in the face of short texts. In order to take into account the semantic relations between words, the word position and word frequency, we proposed a text local similarity formula between words in use of word2 vec, and transform the relationship between words into uncertain graph model. We proposed the concept of vertex density and candidate keyword evaluation index, and candidate keyword extraction algorithm based on uncertain graph, finally combined with IDF, proposed the DEN-IDF as the final keyword evaluation criteria. This method of keyword extraction does not depend on external manual annotation data, and can be completely unsupervised. The experimental results showthat the accuracy of TF-IDF is improved by about 8% and the accuracy of TextRank is improved by about 12%.
-
-
-
ZOU Zhao-Nian;
邹兆年;
ZHU Rong;
朱鎔
- 《2013中国计算机大会》
| 2013年
-
摘要:
该文研究了从不确定图中挖掘出前k个出现概率最高的极大团的问题,提出了一种基于划分的高效并行算法.在该算法中,输入的大规模不确定图首先被划分为若干互不重叠的规模较小的子图,每个子图通过扩展邻居结点信息成为扩展子图.而后,应用改进后的分支界限搜索策略,并行挖掘各个扩展子图,以得到局部top-k结果.最后,归并所有的局部top-k结果,得到全局top-k极大团.同时,该文还提出了两种预处理策略,以提高算法效率.并且严格证明了算法的正确性.在多组不确定图数据集上的实验结果表明,算法具有很高的效率和很好的实用性.
-
-
Li Mingpeng;
李鸣鹏;
Zou Zhaonian;
邹兆年;
Gao Hong;
高宏;
Zhao Zhengli;
赵正理
- 《第29届中国数据库学术会议》
| 2012年
-
摘要:
研究了不确定图上的最短距离问题,提出了期望最短距离的概念,证明了该问题不存在多项式时间的算法.为了解决该问题,使用了随机采样技术获得不确定图的一些可能世界,在每个可能世界上计算有穷的最短距离,最后计算出平均值作为期望最短距离的估计值.为提高计算效率,使用了过滤条件来减少采样过程中采样的边数从而加快随机采样.在此基础上,提出了一种基于对称变量的、无偏的随机采样近似算法,并证明了与直接随机采样方法相比,该方法在不增加时间开销的同时能减小采样方差.通过真实数据上的实验表明,提出的算法在时间开销和采样方差上均明显好于直接随机采样方法.
-
-
CAI Wei;
蔡伟;
ZHANG Bai-Li;
张柏礼;
LV Jian-Hua;
吕建华
- 《第29届中国数据库学术会议》
| 2012年
-
摘要:
文中首先基于可能世界模型提出了不确定图的最可靠最大流问题和可靠性计算模型,这对于构建可靠性网络、可靠传输路径选择以及系统薄弱环节分析等一系列实际问题具有重要意义;然后基于简单路径组合思想提出了一种求解最可靠最大流的算法SPCA,通过简单路径流量的组合,在无需求得所有最大流分布的情况下获得最可靠最大流,并在组合过程中引入概率剪枝与约束剪枝策略,对无效组合进行过滤,从而显著地提高了算法效率;接着文中针对SPCA算法易受路径数量及瓶颈容量影响的问题,又提出一种基于状态空间划分的最可靠最大流算法SDBA,该算法的主要思想是将不确定图所蕴含的子图空间划分为互不相交且满足最大流值的闭合区间集合,进而寻找所有闭合区间中概率最大的下界状态,经证明这个下界状态对应子图中的最大流分布为最可靠最大流;最后通过实验,比较了两种算法的性能.实验结果表明SDBA算法相对于SPCA算法其空间复杂度有一定的增加,但时间复杂度方面具有较大的优势,能够很好地解决SPCA算法性能受制于容量的问题,具有更好的性能与适用性.
-
-
张旭;
何向南;
金澈清;
周傲英
- 《第28届中国数据库学术会议》
| 2011年
-
摘要:
生物网络、社会网络、交际网络等复杂的网络被广泛的研究,由于数据抽出时引入的噪声和错误使这些数据具有不确定性,因此可以对这些应用使用不确定图模型建模,k最近邻查询问题是查询一个图上的距离某个特定点最近的k个邻居节点的问题,它是不确定图上的一个基础问题。设计了一个解决不确定图上最近邻问题的框架,首先定义了一种新颖的不确定图上的k最近邻查询,然后提出了针对该查询的一般处理算法,同时对该算法进行了优化,使算法效率得到极大提高。理论分析和实验结果表明提出的算法能够高效地处理不确定图上的k最近邻查询。
-
-
张应龙;
李翠平;
陈红;
杜凌霞
- 《第28届中国数据库学术会议》
| 2011年
-
摘要:
在现实中的许多领域产生大量不确定的图结构的数据,例如分子化合物、蛋白质交互网络等。同时现实中有很多应用例如推荐系统中的推荐过滤、欺诈检测和社会网络的链接预测等,需要查询给定节点的k个最相似节点,针对这一问题,提出了用基于SimRank度量的方法来求解。由于图的动态演变和不确定性导致用现有的SimRank计算方法求k个最近邻的代价昂贵,因此提出一个有效算法,在保证一定准确性的前提下,通过引入路径阈值,算法只需考虑查询点的邻居区域无需考虑整个图从而达到明显的剪枝效果,该方法在确定图和不确定图上都可以适用。在此基础上为了进一步提高效率,算法在不确定图上引入采样技术。最后从理论、实验说明验证了算法的高效性和有效性。
-
-
张海杰;
姜守旭;
邹兆年
- 《第28届中国数据库学术会议》
| 2011年
-
摘要:
图的不确定性普遍存在,研究不确定图的高效查询处理具有重要意义。文中提出了不确定图上一种新型查询——近邻查询。给定一个查询标签集R和距离约束σ,在不确定图G上进行近邻查询是要找到标签集包含R并且任意两个顶点间距离不超过σ的匹配顶点集。为解决该问题,文中首先提出了“可靠期望距离”,然后基于可靠期望距离建立了高效的近邻关系图索引,将不确定图上的近邻查询等价地转化为近邻关系图上的团查询问题,最后使用树搜索算法解决近邻关系图上的团查询问题。理论分析和实验结果表明文中提出的算法能够高效地完成不确定图上的top-k近邻查询。
-
-
韩蒙;
张炜;
李建中
- 《第27届中国数据库学术会议》
| 2010年
-
摘要:
由于不确定图蕴含了指数级的可能图实例,基于确定图模型的频繁图模式挖掘算法通常难以在不确定图集合上高效运行。文中提出了一种不确定图数据集上的基于随机游走的K极大频繁子模式挖掘算法。首先,将每个不确定图转换为相应的确定图并挖掘候选频繁模式;然后,将候选频繁模式恢复为不确定图并生成极大频繁模式搜索空间;最后,通过随机游走以相同概率随机地选择K个极大频繁模式。理论分析和实验结果表明文中提出的算法能够高效地获得不确定图集合的K-极大频繁模式。
-
-
韩璐;
王朝坤;
邹鹏;
徐亚军
- 《第27届中国数据库学术会议》
| 2010年
-
摘要:
图数据结构广泛应用于各种领域的数据建模,由于测量手段和问题特性的限制,数据的不确定性普遍存在。这种不确定性表现在图结构数据中,形成不确定图。之前对于不确定图数据上查询处理的研究,主要是在不确定的图结构数据上查找某一结构确定的图。然而,针对不确定的图数据,其查询很可能也是不确定的。该项工作主要是实现查询过程中的双向匹配,即对于一个不确定的查询,在不确定的图上,得到查询与图的一个可能性最大的匹配组合。这样的研究是具有现实意义的,通过不确定图上对于不确定查询的匹配,可以找到两个不确定结构间存在的最大相似结构,并度量其相似性。
-
-
袁野;
王国仁
- 《第27届中国数据库学术会议》
| 2010年
-
摘要:
图的可达性查询被广泛应用于生物网络、社会网络、本体网络、RDF数据库和XML数据库等。由于对数据操作时引入的噪声和错误使这些图数据具有不确定性,已经有大量的针对不确定RDF和XML数据库的研究。文中使用可能世界语义模型构建不确定图,基于该模型,研究了概率可达查询(PR)。处理PR查询是#P完全问题,对此文中首先给出一个基本随机算法,可快速地估算出可达概率,并且该值有很高的精确度。进一步,文中为随机算法引入条件分布(称为"条件随机算法"),采用图的不相交路径集和割集作为条件概率分布,因此改进的随机算法可准确地并且是在多项式时间内处理查询。最后基于真实不确定图数据的大量实验结果验证了文中的设计。