计算机科学 ›› 2021, Vol. 48 ›› Issue (6A): 543-551.doi: 10.11896/jsjkx.201100167
王晓敏1,2, 苏静1,2, 姚兵3
WANG Xiao-min1,2, SU Jing1,2, YAO Bing3
摘要： 文中首先给出了顶点撕裂运算与顶点重合运算的定义,基于顶点撕裂连通度的定义证明了连通图的顶点撕裂连通度等价于连通图的连通度;给出了图的 W-相似的定义。其次,给出了图撕裂组以及同构子图相似的定义,介绍了一种特殊图撕裂组和特殊图撕裂组匹配方法。再次,讲述了有关图和图撕裂组的运算和算法,主要有确定图撕裂组的算法、图撕裂收缩算法、图的顶点扩展和收缩算法。然后,给出了图的同构子图相似的基本定理。最后,总结全文并提出了几个值得以后深入研究的问题。
中图分类号:
| [1] BONDY J A,MURTY U S R.Graph theory[M].New YorkSpringer,2008. [2] LI Q,WANG LP,LIU W Y,et al.Method and system for measuring similarity of graph structure[P].CN101256594A,2008. [3] LIU H L,DEGN W C,SU H.A flow chart similarity method based on topological structure[P].CN104462414A,2015. [4] WANG X Y,LIU M J.A Survey of lattice-based cryptography[J].Journal of Cryptologic Research,2014,1(1):13-27. [5] YAO B.Graphic lattices and matrix lattices of topological coding[J].arXiv:2005.03937,2020. [6] HAUSSLER D.Convolutional kernels on discrete structures[R].Computer Science Department,UC Santa Cruz.Technical Report,1999. [7] HORATH T,GARTNER T,STEFA W.Cyclic pattern kernels for predictive graph mining[C]//Proceedings of the Tenth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining.ACM,2004:158-167. [8] GARTNER T,FLACH P.WROBEL S.On graph kernels:hardness results and efficient alternatives[C]//Lecture Notes in Artificial Intelligence (Subseries of Lecture Notes in Computer Science).2003:2777,129-143. [9] BORGWARDT K M,KRIEGEL H P.Shortest-path kernels on graphs[C]//Fifth IEEE International Conference on Data Mining (ICDM'05).IEEE;2005:8-81. [10] MACRO A,QI X J,YAN C H.A shortest-path graph kernel for estimating gene product semantic similarity[J].Journal of Biomedical Semantics,2011,2(1):129-143. [11] SHERVASHIDZE N,SCHWEITZER P,VAN L,et al.Weisfeiler-Lehman graph kernels[J].Journal of Machine Learning Research,2011,12:2539-2561. [12] SHERVASHIDZE N.Efficient graphlet kernels for large graph comparison[C]//Proceedings of Machine Learning Research.2009:488-495. [13] JIN G,CHEN Z,ZHANG J,et al.Detecting user interaction anomaly based on social network graph similarity[C]//2020 IEEE 10th International Conference on Electronics Information and Emergency Communication (ICEIEC).IEEE,2020:131-136. [14] FYBIAK M,WALLAT S,REIHARD S,et al.Graph similarity and its applications to hardware security[C]//IEEE Transactions on Computers.2020:505-519. [15] WANG B,LYU X,TANG Z,et al.Comparison of moleculegraph representation with similarity consistency[C]//2019 IEEE International Conference on Bioinformatics and Biomedicine (BIBM).IEEE,2019:1250-1252. [16] ZHU Y,QIN L,YU J X,et al.Answering top-k k graph similarity queries in graph databases[J].IEEE Transactions on Knowledge and Data Engineering,2020,32:1459-1474. |
| [1] | 王坤姝, 张泽辉, 高铁杠. 基于Hachimoji DNA和QR分解的遥感图像可逆隐藏算法 Reversible Hidden Algorithm for Remote Sensing Images Based on Hachimoji DNA and QR Decomposition 计算机科学, 2022, 49(8): 127-135. https://doi.org/10.11896/jsjkx.210700216 |
| [2] | 张颖涛, 张杰, 张睿, 张文强. 全局信息引导的真实图像风格迁移 Photorealistic Style Transfer Guided by Global Information 计算机科学, 2022, 49(7): 100-105. https://doi.org/10.11896/jsjkx.210600036 |
| [3] | 刘畅, 魏为民, 孟繁星, 才智. 语音风格迁移研究进展 Research Progress on Speech Style Transfer 计算机科学, 2022, 49(6A): 301-308. https://doi.org/10.11896/jsjkx.210300134 |
| [4] | 杨玥, 冯涛, 梁虹, 杨扬. 融合交叉注意力机制的图像任意风格迁移 Image Arbitrary Style Transfer via Criss-cross Attention 计算机科学, 2022, 49(6A): 345-352. https://doi.org/10.11896/jsjkx.210700236 |
| [5] | 许思雨, 秦克云. 基于剩余格的模糊粗糙集的拓扑性质 Topological Properties of Fuzzy Rough Sets Based on Residuated Lattices 计算机科学, 2022, 49(6A): 140-143. https://doi.org/10.11896/jsjkx.210200123 |
| [6] | 陈章辉, 熊贇. 基于解耦-检索-生成的图像风格化描述生成模型 Stylized Image Captioning Model Based on Disentangle-Retrieve-Generate 计算机科学, 2022, 49(6): 180-186. https://doi.org/10.11896/jsjkx.211100129 |
| [7] | 许杰, 祝玉坤, 邢春晓. 机器学习在金融资产定价中的应用研究综述 Application of Machine Learning in Financial Asset Pricing:A Review 计算机科学, 2022, 49(6): 276-286. https://doi.org/10.11896/jsjkx.210900127 |
| [8] | 叶跃进, 李芳, 陈德训, 郭恒, 陈鑫. 基于国产众核架构的非结构网格分区块重构预处理算法研究 Study on Preprocessing Algorithm for Partition Reconnection of Unstructured-grid Based on Domestic Many-core Architecture 计算机科学, 2022, 49(6): 73-80. https://doi.org/10.11896/jsjkx.210900045 |
| [9] | 陈鑫, 李芳, 丁海昕, 孙唯哲, 刘鑫, 陈德训, 叶跃进, 何香. 面向国产异构众核架构的CFD非结构网格计算并行优化方法 Parallel Optimization Method of Unstructured-grid Computing in CFD for DomesticHeterogeneous Many-core Architecture 计算机科学, 2022, 49(6): 99-107. https://doi.org/10.11896/jsjkx.210400157 |
| [10] | 封雷, 朱登明, 李兆歆, 王兆其. 一种基于遮罩的稀疏点云滤波算法 Sparse Point Cloud Filtering Algorithm Based on Mask 计算机科学, 2022, 49(5): 25-32. https://doi.org/10.11896/jsjkx.210600129 |
| [11] | 刘江, 刘文博, 张矩. OpenFoam中多面体网格生成的MPI＋OpenMP混合并行方法 Hybrid MPI+OpenMP Parallel Method on Polyhedral Grid Generation in OpenFoam 计算机科学, 2022, 49(3): 3-10. https://doi.org/10.11896/jsjkx.210700060 |
| [12] | 宁秋怡, 史小静, 段湘煜, 张民. 基于风格感知的无监督领域适应算法 Unsupervised Domain Adaptation Based on Style Aware 计算机科学, 2022, 49(1): 271-278. https://doi.org/10.11896/jsjkx.201200094 |
| [13] | 陶星朋, 徐宏辉, 郑建炜, 陈婉君. 基于非凸低秩矩阵逼近和全变分正则化的高光谱图像去噪 Hyperspectral Image Denoising Based on Nonconvex Low Rank Matrix Approximation and TotalVariation Regularization 计算机科学, 2021, 48(8): 125-133. https://doi.org/10.11896/jsjkx.200400143 |
| [14] | 赵敏, 刘惊雷. 基于高斯场和自适应图正则的半监督聚类 Semi-supervised Clustering Based on Gaussian Fields and Adaptive Graph Regularization 计算机科学, 2021, 48(7): 137-144. https://doi.org/10.11896/jsjkx.200800190 |
| [15] | 裴莹, 李天祥, 王鏖清, 付加胜, 韩霄松. 基于新闻的国际天然气价格趋势预测方法 Prediction Method of International Natural Gas Price Trends Based on News 计算机科学, 2021, 48(6A): 235-239. https://doi.org/10.11896/jsjkx.201000056 |
|
||
首页