Computer Science

Computer Science ›› 2021, Vol. 48 ›› Issue (6A): 543-551.doi: 10.11896/jsjkx.201100167

• Interdiscipline & Application • Previous Articles     Next Articles

Algorithms Based on Lattice Thought for Graph Structure Similarity

WANG Xiao-min1,2, SU Jing1,2, YAO Bing3   

  1. 1 School of Electronic Engineering and Computer Science,Peking University,Beijing 100871,China
    2 Key Laboratory of High Confidence Software Technologies,Peking University,Beijing 100871,China
    3 College of Mathematics and Statistics,Northwest Normal University,Lanzhou 730070,China
  • Online:2021-06-10 Published:2021-06-17
  • About author:WANG Xiao-min,born in 1989,Ph.D student.Her main research interests include graph theory and complex networks.
    SU Jing,born in 1993,Ph.D.Her main research interests include graph theory and complex network.
  • Supported by:
    Major Research Plan of the National Natural Science Foundation of China(2019YFA0706401),Key Program of the National Natural Science Foundation of China(61632002),General Program of the National Natural Science Foundation of China(61872166),Young Scientists Fund of the National Natural Science Foundation of China(61902005,62002002) and National Natural Science Foundation of China(61662066).

PDF (PC)

525

Abstract: This paper gives the definition of vertex-splitting operation and vertex-coinciding operation,introduces a new kind of connectivity－vertex-splitting connectivity based on the definition of vertex-splitting operations,proves that vertex-splitting connectivity is equivalent to connectivity of the connected graph,gives the definition of W-similarity.Secondly,it presents the definition of graph-splitting group and isomorphic subgraphs,and introduces a method for special graph-splitting group and special graph-splitting group matching.Again,it describes the operations and algorithms of graphs and graph-splitting groups,including,deterministic graph-splitting group algorithm,graph-splitting contracting algorithms,vertex expending and contracting algorithm of a graph.Then,it discusses the basic similarities of isomorphic subgraphs of graphs.Finally,it makes a brief conclusion and puts forward a few issues for further study.

Key words: Connectivity, Graph structure similarity, Lattice, Splitting operation

CLC Number: 

  • TP311
[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] WANG Kun-shu, ZHANG Ze-hui, GAO Tie-gang. Reversible Hidden Algorithm for Remote Sensing Images Based on Hachimoji DNA and QR Decomposition [J]. Computer Science, 2022, 49(8): 127-135.
[2] XU Si-yu, QIN Ke-yun. Topological Properties of Fuzzy Rough Sets Based on Residuated Lattices [J]. Computer Science, 2022, 49(6A): 140-143.
[3] YI Yi, FAN Jian-xi, WANG Yan, LIU Zhao, DONG Hui. Fault-tolerant Routing Algorithm in BCube Under 2-restricted Connectivity [J]. Computer Science, 2021, 48(6): 253-260.
[4] QIAN Xin-yuan, WU Wen-yuan. Identity-based Encryption Scheme Based on R-SIS/R-LWE [J]. Computer Science, 2021, 48(6): 315-323.
[5] SHEN Xia-jiong, YANG Ji-yong, ZHANG Lei. Attribute Exploration Algorithm Based on Unrelated Attribute Set [J]. Computer Science, 2021, 48(4): 54-62.
[6] ZHENG Jia-tong, WU Wen-yuan. Practical Bi-deniable Encryption Scheme Based on MLWE [J]. Computer Science, 2021, 48(3): 307-312.
[7] WEN Xin, YAN Xin-yi, CHEN Ze-hua. Minimal Optimistic Concept Generation Algorithm Based on Equivalent Relations [J]. Computer Science, 2021, 48(3): 163-167.
[8] NI Liang, WANG Nian-ping, GU Wei-li, ZHANG Qian, LIU Ji-zhao, SHAN Fang-fang. Research on Lattice-based Quantum-resistant Authenticated Key Agreement Protocols:A Survey [J]. Computer Science, 2020, 47(9): 293-303.
[9] YUE Xiao-wei, PENG Sha and QIN Ke-yun. Attribute Reduction Methods of Formal Context Based on ObJect (Attribute) Oriented Concept Lattice [J]. Computer Science, 2020, 47(6A): 436-439.
[10] LV Xiao-jing, LIU Zhao, CHU Xue-sen, SHI Shu-peng, MENG Hong-song, HUANG Zhen-chun. Extreme-scale Simulation Based LBM Computing Fluid Dynamics Simulations [J]. Computer Science, 2020, 47(4): 13-17.
[11] GENG Hai-jun, ZHANG Wen-xiang, YIN Xia. Intra-domain Energy Efficient Routing Algorithm Based on Algebraic Connectivity [J]. Computer Science, 2020, 47(4): 238-242.
[12] GUO Qing-chun,MA Jian-min. Judgment Methods of Interval-set Consistent Sets of Dual Interval-set Concept Lattices [J]. Computer Science, 2020, 47(3): 98-102.
[13] LI Shu-quan,LIU Lei,ZHU Da-yong,XIONG Chao,LI Rui. Protocol of Dynamic Provable Data Integrity for Cloud Storage [J]. Computer Science, 2020, 47(2): 256-261.
[14] SU Fan-jun,DU Ke-yi. Trust Based Energy Efficient Opportunistic Routing Algorithm in Wireless Sensor Networks [J]. Computer Science, 2020, 47(2): 300-305.
[15] QIAN Xiao-mei,LIU Jia-yong,CHENG Peng-sen. Distant Supervised Relation Extraction Based on Densely Connected Convolutional Networks [J]. Computer Science, 2020, 47(2): 157-162.
Viewed
Full text


Abstract

Cited
  Shared   
  Discussed   
No Suggested Reading articles found!
渝ICP备16013121号-4
Add:18# Honghu West Rd., Yubei ,Chongqing,China    Post Code: 401121
Tel: 023-63500828/023-67039612/023-67039623
E-mail: jsjkx12@163.com
Powered by Beijing Magtech Co., Ltd.