{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,12]],"date-time":"2025-10-12T04:10:57Z","timestamp":1760242257730,"version":"build-2065373602"},"reference-count":30,"publisher":"MDPI AG","issue":"2","license":[{"start":{"date-parts":[[2017,2,22]],"date-time":"2017-02-22T00:00:00Z","timestamp":1487721600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"name":"Key Project of the National Natural Science Foundation of China","award":["91318301"],"award-info":[{"award-number":["91318301"]}]},{"DOI":"10.13039\/501100002858","name":"China Postdoctoral Science Foundation","doi-asserted-by":"publisher","award":["2015M581032"],"award-info":[{"award-number":["2015M581032"]}],"id":[{"id":"10.13039\/501100002858","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"publisher","award":["61202080"],"award-info":[{"award-number":["61202080"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Entropy"],"abstract":"<jats:p>This paper presents a novel theory and method to calculate the canonical labelings of digraphs whose definition is entirely different from the traditional definition of Nauty. It indicates the mutual relationships that exist between the canonical labeling of a digraph and the canonical labeling of its complement graph. It systematically examines the link between computing the canonical labeling of a digraph and the k-neighborhood and k-mix-neighborhood subdigraphs. To facilitate the presentation, it introduces several concepts including mix diffusion outdegree sequence and entire mix diffusion outdegree sequences. For each node in a digraph G, it assigns an attribute m_NearestNode to enhance the accuracy of calculating canonical labeling. The four theorems proved here demonstrate how to determine the first nodes added into     M a x Q ( G )    . Further, the other two theorems stated below deal with identifying the second nodes added into     M a x Q ( G )    . When computing      C  m a x    ( G )     , if     M a x Q ( G )     already contains the first i vertices      u 1  ,  u 2  , \u22ef ,  u i     , Diffusion Theorem provides a guideline on how to choose the subsequent node of     M a x Q ( G )    . Besides, the Mix Diffusion Theorem shows that the selection of the     ( i + 1 )    th vertex of     M a x Q ( G )     for computing      C  m a x    ( G )      is from the open mix-neighborhood subdigraph      N  + +    ( Q )      of the nodes set     Q = {  u 1  ,  u 2  , \u22ef ,  u i  }    . It also offers two theorems to calculate the      C  m a x    ( G )      of the disconnected digraphs. The four algorithms implemented in it illustrate how to calculate     M a x Q ( G )     of a digraph. Through software testing, the correctness of our algorithms is preliminarily verified. Our method can be utilized to mine the frequent subdigraph. We also guess that if there exists a vertex     v \u2208  S +   ( G )      satisfying conditions      C  m a x    ( G \u2212 v )  \u2a7d  C  m a x    ( G \u2212 w )      for each     w \u2208  S +   ( G )  \u2227 w \u2260 v    , then      u 1  = v     for     M a x Q ( G )    .<\/jats:p>","DOI":"10.3390\/e19020079","type":"journal-article","created":{"date-parts":[[2017,2,22]],"date-time":"2017-02-22T11:36:58Z","timestamp":1487763418000},"page":"79","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Using k-Mix-Neighborhood Subdigraphs to Compute Canonical Labelings of Digraphs"],"prefix":"10.3390","volume":"19","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-6103-0137","authenticated-orcid":false,"given":"Jianqiang","family":"Hao","sequence":"first","affiliation":[{"name":"State Key Laboratory of Networking and Switching Technology, Beijing University of Posts and Telecommunications, 100876 Beijing, China"},{"name":"School of Computer and Information Engineering, Beijing Technology and Business University, 100048 Beijing, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yunzhan","family":"Gong","sequence":"additional","affiliation":[{"name":"State Key Laboratory of Networking and Switching Technology, Beijing University of Posts and Telecommunications, 100876 Beijing, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yawen","family":"Wang","sequence":"additional","affiliation":[{"name":"State Key Laboratory of Networking and Switching Technology, Beijing University of Posts and Telecommunications, 100876 Beijing, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Li","family":"Tan","sequence":"additional","affiliation":[{"name":"School of Computer and Information Engineering, Beijing Technology and Business University, 100048 Beijing, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jianzhi","family":"Sun","sequence":"additional","affiliation":[{"name":"School of Computer and Information Engineering, Beijing Technology and Business University, 100048 Beijing, China"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"1968","published-online":{"date-parts":[[2017,2,22]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","first-page":"223","DOI":"10.1007\/BFb0062536","article-title":"Computing automorphisms and canonical labellings of graphs","volume":"Volume 686","author":"McKay","year":"1978","journal-title":"Combinatorial Mathematics"},{"key":"ref_2","unstructured":"Piperno, A. (2008). Search space contraction in canonical labeling of graphs. arXiv."},{"key":"ref_3","doi-asserted-by":"crossref","unstructured":"Junttila, T., and Kaski, P. (2007, January 6). Engineering an Efficient Canonical Labeling Tool for Large and Sparse Graphs. Proceedings of the Ninth Workshop on Algorithm Engineering and Experiments and the Fourth Workshop on Analytic Algorithmics and Combinatorics, New Orleans, LA, USA.","DOI":"10.1137\/1.9781611972870.13"},{"key":"ref_4","unstructured":"Babai, L., and Luks, E.M. (1983). Proceedings of the Fifteenth Annual ACM Symposium on Theory of Computing, ACM."},{"key":"ref_5","unstructured":"Ivanciuc, O. (2008). Handbook of Chemoinformatics, Wiley-VCH Verlag GmbH."},{"key":"ref_6","doi-asserted-by":"crossref","first-page":"313","DOI":"10.1109\/TSMC.1974.5409142","article-title":"Optimum Featurs and Graph Isomorphism","volume":"3","author":"Shah","year":"1974","journal-title":"IEEE Trans. Syst. Man Cybern."},{"key":"ref_7","doi-asserted-by":"crossref","first-page":"40","DOI":"10.1007\/978-3-540-79709-8_8","article-title":"A Logspace Algorithm for Partial 2-Tree Canonization","volume":"Volume 5010","author":"Arvind","year":"2008","journal-title":"Computer Science\u2014Theory and Applications"},{"key":"ref_8","unstructured":"Huan, J., Wang, W., and Prins, J. (2003). Efficient Mining of Frequent Subgraphs in the Presence of Isomorphism, IEEE Computer Society."},{"key":"ref_9","doi-asserted-by":"crossref","first-page":"243","DOI":"10.1007\/s10618-005-0003-9","article-title":"Finding Frequent Patterns in a Large Sparse Graph","volume":"11","author":"Kuramochi","year":"2005","journal-title":"Data Min. Knowl. Discov."},{"key":"ref_10","doi-asserted-by":"crossref","first-page":"1038","DOI":"10.1109\/TKDE.2004.33","article-title":"An efficient algorithm for discovering frequent subgraphs","volume":"16","author":"Kuramochi","year":"2004","journal-title":"IEEE Trans. Knowl. Data Eng."},{"key":"ref_11","doi-asserted-by":"crossref","first-page":"657","DOI":"10.1016\/j.jfranklin.2005.04.006","article-title":"Some further development on the eigensystem approach for graph isomorphism detection","volume":"342","author":"He","year":"2005","journal-title":"J. Frankl. Inst. Eng. Appl. Math."},{"key":"ref_12","doi-asserted-by":"crossref","unstructured":"Kashani, Z., Ahrabian, H., Elahi, E., Nowzari-Dalini, A., Ansari, E., Asadi, S., Mohammadi, S., Schreiber, F., and Masoudi-Nejad, A. (2009). Kavosh: A new algorithm for finding network motifs. BMC Bioinform., 10.","DOI":"10.1186\/1471-2105-10-318"},{"key":"ref_13","doi-asserted-by":"crossref","unstructured":"Babai, L., and Kucera, L. (1979, January 29\u201331). Canonical labelling of graphs in linear average time. Proceedings of the 20th Annual Symposium on Foundations of Computer Science, San Juan, Puerto Rico.","DOI":"10.1109\/SFCS.1979.8"},{"key":"ref_14","first-page":"197","article-title":"Canonical Representations of Partial 2- and 3-Trees","volume":"Volume 477","author":"Arnborg","year":"1990","journal-title":"Proceedings of the 2nd Scandinavian Workshop on Algorithm Theory"},{"key":"ref_15","doi-asserted-by":"crossref","first-page":"241","DOI":"10.14257\/ijgdc.2016.9.5.21","article-title":"Apply Partition Tree to Compute Canonical Labelings of Graphs","volume":"9","author":"Hao","year":"2016","journal-title":"Int. J. Grid Distrib. Comput."},{"key":"ref_16","first-page":"45","article-title":"Practical Graph Isomorphism","volume":"30","author":"McKay","year":"1981","journal-title":"Congr. Numer."},{"key":"ref_17","doi-asserted-by":"crossref","first-page":"306","DOI":"10.1006\/jagm.1997.0898","article-title":"Isomorph-Free Exhaustive Generation","volume":"26","author":"McKay","year":"1998","journal-title":"J. Algorithms"},{"key":"ref_18","doi-asserted-by":"crossref","first-page":"94","DOI":"10.1016\/j.jsc.2013.09.003","article-title":"Practical graph isomorphism, II","volume":"60","author":"McKay","year":"2014","journal-title":"J. Symb. Comput."},{"key":"ref_19","doi-asserted-by":"crossref","first-page":"31","DOI":"10.1145\/321921.321925","article-title":"An Algorithm for Subgraph Isomorphism","volume":"23","author":"Ullmann","year":"1976","journal-title":"J. ACM"},{"key":"ref_20","unstructured":"Yan, X., and Han, J. (2002, January 9\u201312). gSpan: Graph-based substructure pattern mining. Proceedings of the 2002 IEEE International Conference on Data Mining (ICDM 2003), Maebashi City, Japan."},{"key":"ref_21","doi-asserted-by":"crossref","first-page":"239","DOI":"10.1090\/dimacs\/028\/14","article-title":"The complexity of McKay\u2019s canonical labeling algorithm","volume":"Volume 28","author":"Miyazaki","year":"1997","journal-title":"Groups and Computation II"},{"key":"ref_22","first-page":"7","article-title":"Efficient isomorphism of miyazaki graphs","volume":"5","author":"Tener","year":"2008","journal-title":"Algorithms"},{"key":"ref_23","doi-asserted-by":"crossref","first-page":"151","DOI":"10.1007\/978-3-642-19754-3_16","article-title":"Conflict Propagation and Component Recursion for Canonical Labeling","volume":"Volume 6595","author":"Junttila","year":"2011","journal-title":"Theory and Practice of Algorithms in (Computer) Systems"},{"key":"ref_24","unstructured":"L\u00f3pez-Presa, J.L., Anta, A.F., and Chiroque, L.N. (2011). Conauto-2.0: Fast Isomorphism Testing and Automorphism Group Computation. arXiv."},{"key":"ref_25","first-page":"181","article-title":"Graph Symmetry Detection and Canonical Labeling: Differences and Synergies","volume":"Volume 10","author":"Katebi","year":"2012","journal-title":"Proceedings Turing-100"},{"key":"ref_26","doi-asserted-by":"crossref","unstructured":"Bang-Jensen, J., and Gutin, G.Z. (2008). Digraphs: Theory, Algorithms and Applications, Springer. [2nd ed.].","DOI":"10.1007\/978-1-84800-998-1"},{"key":"ref_27","doi-asserted-by":"crossref","unstructured":"Bollob\u00e1s, B. (2013). Modern Graph Theory, Springer.","DOI":"10.1201\/b16132-57"},{"key":"ref_28","doi-asserted-by":"crossref","first-page":"15","DOI":"10.1016\/S0898-1221(97)00216-2","article-title":"Distance in digraphs","volume":"34","author":"Chartrand","year":"1997","journal-title":"Comput. Math. Appl."},{"key":"ref_29","unstructured":"ALENEX 2007 Submission: Source Code, Benchmark Instances, and Summary Results. Available online: http:\/\/www.tcs.hut.fi\/Software\/benchmarks\/ALENEX-2007\/."},{"key":"ref_30","unstructured":"Weisstein, E.W. Simple Directed Graph. From MathWorld\u2014A Wolfram Web Resource. Available online: http:\/\/mathworld.wolfram.com\/SimpleDirectedGraph.html."}],"container-title":["Entropy"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1099-4300\/19\/2\/79\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T18:28:55Z","timestamp":1760207335000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1099-4300\/19\/2\/79"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,2,22]]},"references-count":30,"journal-issue":{"issue":"2","published-online":{"date-parts":[[2017,2]]}},"alternative-id":["e19020079"],"URL":"https:\/\/doi.org\/10.3390\/e19020079","relation":{},"ISSN":["1099-4300"],"issn-type":[{"type":"electronic","value":"1099-4300"}],"subject":[],"published":{"date-parts":[[2017,2,22]]}}}