图论在网络研究中的一些应用

姚 兵

PDF(5231 KB)
PDF(5231 KB)
广州大学学报(自然科学版) ›› 2019, Vol. 18 ›› Issue (4) : 28-49.

图论在网络研究中的一些应用

  • 姚 兵
作者信息 +

Some applications of graph theory in networks research

  • YAO Bing
Author information +
History +

摘要

拓扑图属于数学中的一个叫做图论的分支.文章综合部分网络研究运用了图论的理论和技术,而不是用图论的拓扑图来描绘、解释网络.聚焦人工智能中的图网络和图匹配网络、无标度图定义和物联网定义、新累计分布、撕裂连通性等新概念的研究;侧重优质网络和特种性质网络的构造、生成树计数、控制集、控制图、崩溃度等新算法的建立;突出动态偏微分方程、概率、图论等数学技术在网络研究中的运用.

Abstract

Topological graph belongs to graph theory, a branch of mathematics. In this paper, the theory and technique of graph theory are applied in networks research, but only for networks descript. This paper focuses on new concepts such as Graph Network and Graph Matching Network, scale-free graph definition, definition of “Internet of Things”, new cumulative distributions, and splitting connectivity in artificial intelligence. The review emphasis is placed on the construction of high-quality networks and special properties of networks, the establishment of new algorithms such as spanning tree count, dominating set, dominating graph, and collapse degree; the applications of dynamic partial differential equations, probability, graph theory and other mathematical techniques in network research are highlighted.

关键词

动态网络 / 物联网 / 拓扑图 / 连通性 / 生成树 / 概率 / 控制集

Key words

dynamic network / Internet of Things / topological graph / connectivity / spanning trees / probability / dominating set

引用本文

导出引用
姚 兵. 图论在网络研究中的一些应用. 广州大学学报(自然科学版). 2019, 18(4): 28-49
YAO Bing. Some applications of graph theory in networks research. Journal of Guangzhou University(Natural Science Edition). 2019, 18(4): 28-49

参考文献

[1] Pavlopoulos G, Secrier M, Moschopoulos C N, et al. Using graph theory to analyze biological networks[J]. Bio Data Mining, 2011,4(10): 1-27.
[2] Battaglia P W, Hamrick J B, Bapst V, et al. Relational inductive biases, deep learning, and graph networks[J]. arXiv: 1806. 01261v2 [cs. LG] 11 Jun 2018.
[3] Zhou J, Cui G Q, Zhang Z Y, et al. Graph neural networks: A review of methods and applications[J]. arXiv: 1812.08434v4 [cs.LG] 10 Jul 2019.
[4] Wu Z H, Pan S R, Chen F W, et al. A comprehensive survey on graph neural networks[J]. arXiv: 1901.00596v3 [cs.LG] 8 Aug 2019.
[5] Li Y J, Gu C J, Dullien T, et al. Graph matching networks for learning the similarity of graph structured objects[C]∥Proceedings of the 36th International Conference on Machine Learning, Long Beach, USA, 2019. arXiv: 1904.12787v1 [cs.LG] 29 Apr 2019.
[6] Newman M E J, Barabasi A L, Watts D J. The structure and dynamics of networks[M]. Princeton: Princeton University Press, 2006.
[7] Mieghem P V. Graph spectra for complex networks[M]. Cambridgeshire: Cambridge University Press, 2012.
[8] Jungnickel D. Graphs, networks and algorithms[M]. Berlin: Springer, 2010.
[9] Barabasi A L, Posfai M. Network science, data analysis and simulations[M]. Cambridge: Cambridge University Press, 2016.
[10]Barabasi A L, Zoltan N. Oltvai. Network biology: Understanding the cell's functional organization[J]. Nature Reviews, Genetics, 2004,5: 101-113.
[11]Bondy J A, Murty U S R. Graph theory[M]. London: Springer, 2008.
[12]Joseph A.Gallian. A dynamic survey of graph labeling[J]. The Electronic Journal of Combinatorics, 2018, 21:502.
[13]Li L, Alderson D, Tanaka R, et al. Towards a theory of scale-free graphs: Definition, properties, and implications[J]. Internet Mathematics, 2005, 2(4): 431-523.
[14]Barabasi A L, Albert R. Emergence of scaling in random networks[J]. Science, 1999,286: 509-512.
[15]Yao B, Zhou X Q, Zhang J J, et al. Labellings and invariants of models from complex networks[C]∥Proceeding of 2012 International Conference on Systems and Informatics. New York: Institue of Electrical and Electronics Engineers Inc, 2012: 1616-1620.
[16]Yao B, Yang C, Yao M, et al. Graphs as models of scale-free networks[C]∥2013 International Conference on Information Technology and Computer Applications, 2013, 380/384:2034-2037. DOI: 10.4028/www.scientific.net/AMM.380-384.2034
[17]Yao B, Zhang Z F, Yao M. A class of spanning trees[J]. International Journal of Computer, Mathematical Sciences and Applications, 2007,1(2/4): 191-198.
[18]Yao B, Zhang Z F, Wang J F. Some results on spanning trees[J]. Acta Mathematicae Applicatae Sinica, English Seriesvol, 2010,26(4): 607-616.
[19]Liu X, Yao B, Zhang W J, et al. Topological structure and spanning trees of rectangular growing network models[C]∥Proceeding of ISCCCA13, Paris: Atlantis Press, 2014: 1805-1808.
[20]Liu X, Yao B, Zhang W J, et al.Uniformly bound-growing network models and their spanning trees[C]∥The 2014 International Conference on Information and Communication Technologies, New York: Institue of Electrical and Electronics Engineers Inc, 2014: 714-718.
[21]Ma F, Yao B. An iteration method for computing the total number of spanning trees and its applications in graph theory[J]. Theoretical Computer Science (2018). https: //DOI.org/10.1016/j.tcs.2017.10.030.
[22]Ma F, Yao B. A family of deterministic small-world network models built by complete graph and iteration-function[J]. Physica A. DOI.org/10.1016/j.physa. 2017.11.136.
[23]Ma F, Su J, Hao Y X, et al. A class ofvertex-edge-growth small-world network models having scale-free, self-similar and hierarchical characters[J]. Physica A. https://DOI.org/10.1016/j.physa.2017.11.047
[24]Ma F, Yao B, Yao M. Non-planarunclustered peterson graphs as scale-free models of the Internet of Things[C]∥Information Technology, Networking, Electronic and Automation Control Conference, IEEE, 2016: 1040-1043.
[25]Ma F, Wang P, Yao B.Generating Fibonacci-model as evolution of networks withvertex-velocity and time-memory[J/OL]. https://DOI.org/10.1016/j.physa. 2019: 121295.
[26]Yao B, Liu X, Zhang W J, et al. Applying graph theory to the internet of things[C]∥2013 IEEE International Conference on High Performance Computing and Communications and 2013 IEEE International Conference on Embedded and Ubiquitous Computing, 2354-2361. DOI: 10.1109/HPCC.and.EUC.2013.339
[27]Yao B, Wang H Y, Yao M, et al. On the collapse of graphs related to scale-free networks[C]∥Proceeding of ICIST2013. Third International Conference on Information Science and Technology. New York: Institue of Electrical and Electronics Engineers Inc, 2013: 738-743. DOI: 10.1109/ICIST.2013.6747651.
[28]Strogatz S H. Exploring complex network[J]. Nature, 2001,410: 268-276.
[29]Sharom J R, Bellows D S, Tyers M. From large networks to small molecules[J]. Current Opinion in Chemical Biology, 2004(8): 81-90.
[30]Bollobas B, Riordan O. The diameter of a scale-free random graph[J]. Combinatorica, 2004,24(1): 5-34.
[31]车宏安, 顾基发. 无标度网络及其系统科学意义[J]. 系统工程理论与实践, 2004(4):11-16.
[32]Bollobas B, Riordan O. Robustness and vulnerability of scale-free random graphs[J]. Internet Mathematics, 2003,1(1): 1-35.
[33]Barabasi A L, Bonabeau E. Scale-free networks[J]. Scientific American, 2003,288: 60-69.
[34]Newman M E J. The structure and function of complex networks[J]. SIAM Review, 2003,45(167): 167-256.
[35]Newman M E J. Complex systems: A survey[J]. Siam Review, 2011(79): 800-810.
[36]Albert-Laszlo Barabasi. Love is all you need: Clauset's fruitless search for scale-free networks[EB/OL]. [2018-03-06]. https: //www.barabasilab.com/ Barabasi.
[37]Barabasi A L, Dezso Z, Ravasz E, et al. Scale-free and hierarchical structures in complex networks, modeling of complex systems: Seventh granada lectures[M]∥New York: Institue of Electrical and Electronics Engineers Inc, 2003.
[38]Ma F, Su J, Yao B, et al. The relations between classic and geometric probability and scale-free feature in social networks[C]∥International Conference on Computer Networks and Communication Technology, 2016:171-178. DOI: 10.2991/cnct-16.2017.23
[39]Ma F, Su J, Yao B, et al. Scale-free network models with parameters[C]∥Joint International Information Technology, Mechanical and Electronic Engineering Conference, 2016,59:155-162. DOI: 10.2991/jimec-16. 2016.26.
[40]Yao B, Ma F, Su J, et al. Scale-free multiple-partite models towards information networks[C]∥Proceedings of 2016 IEEE Advanced Information Management, Communicates, Electronic and Automation Control Conference, 2016: 549-554. Compliant PDF Files: IEEE Catalog Number: CFP16E32-ART ISBN: 978-1-4673-9613-4.
[41]Ma F, Su J, Yao B, et al. Models having tunable parameters in scale-free networks[C]∥Advances in Computer Science Research, (ACSR),2016,52: 449-452. 2016 International Conference on Computer Engineering and Information Systems (CEIS-16). DOI: 10.2991/ceis-16.2016.90.
[42]马飞, 姚兵. 基于两种不同择优概率下的无标度网络模型[J]. 华东师范大学学报, 2017(6): 42-49.
[43]Yao B, Zhang X H, Sun H, et al. Text-based passwords generated from topological graphic passwords[C]∥arXiv: 1809. 04727v1 [cs.IT] 13 Sep 2018.
[44]Yao B, Mu Y R, Sun Y R, et al. Using Chinese characters to generate Text-Based passwords for information security[C]∥arXiv: 1907.05406v1 [cs.IT] 11 Jul 2019.
[45]Wang X M, Ma F, Yao B. On Divided-type connectivity of graphs and networks[J]. Submitted, 2019.
[46]孙慧, 姚兵. 探索Euler图的等价命题[J]. 华东师范大学学报 (自然科学版), 2018(2): 23-30.
[47]Ma F, Yao B. The relations between network operation and topological-property in a scale-free and small-world network with community structure[J]. Physica A: Statistical Mechanics and its Applications, 2017: 182-193. https://DOI.org/10.1016/j.physa.2017.04.135.
[48]王宏宇. 一种拓扑型图形密码的结构及其理论分析[D]. 北京:北京大学, 2018.
[49]Su J, Yao B. Finding topological properties in dynamic hypernetwork models from the perspective of community structure[J]. Submitted, 2018.
[50]Yao B, Su J, Ma F, et al. Exploring network operations for data and information networks[C]∥Proceeding SPIE 10322, Seventh International Conference on Electronics and Information Engineering, SPIE Digital Library: 10322, 1032224-1-8 (January 23, 2017); DOI: 10.1117/12.2266006.http://www.spiedl.org.
[51]Lambiotte R, Rosvall M, Scholtes I. From networks to optimal higher-order models of complex systems[J]. Nature Physics, 2019(15): 313-320.
[52]Szabo G, Alava M, Janoskertesz. Clustering in complex networks[J]. Lecture Notes in Physics, 2004. 650: 139-162.
[53]Su J, Ma F, Yao B. Dynamic compound models towards internet of things[C]∥2017 IEEE 2nd Advanced Information Technology, Electronic and Automation Control Conference, 2017:127-130.https://www.ieee.org/.
[54]Yao B, Wang X M, Su J, et al. Methods and problems attempt in scale-free models from complex networks[C]∥International Information Technology, Mechanical and Electronic Engineering Conference, 2016,59:57-61. DOI: 10.2991/ jimec-16.2016.11.
[55]Dorogovstev S N, Goltsev A V, Mendes J F F. Pseufractal scale-free web[J]. Physiacal Review, 2002, 65: 066122-066125.
[56]Clauset A, Shalizi C R, Newman M E J. Power-law distributions in empirical data[J]. SIAM Review, 2009,51: 661-703. DOI: 10. 1137/070710111
[57]Dorogovtsev S N, Mendes J F F, Samukhin A N. Size-dependent degree distribution of a scale-free growing network[J]. Physics Review E, 2001,63: 062101.
[58]Charo I, Del Genio, Thilo Gross, et al. Fast generation of regular graphs and construction of cages[J]. Physical Review Letters, 2011,107: 178701.
[59]Francesc C. Recursive graphs with small-world scale-free properties[J]. physical review E, 2004, 69: 037101-037104.
[60]Zhang Z Z, Zhou S G, Fang L J,et al. Maximal planar scale-free Sierpinski networks with small-world effect and power-law strength-degree correlation[J]. Europhysics Letters, 2007, 79: 38007.
[61]Andrade J J S, Herrmann H J, Andrade R F S, et al. Apollonian network: Simultaneously scale-free, small world, euclidean, space filling, and with matching graphs[J]. Physical Review Letters, 2005, 94: 018702.
[62]Zhang Z Z, Comellas F, Fertin G, et al. High dimensional Apollonian networks[J]. Journal of Physics A: Mathematical and General, 2006, 39(8): 1811-1818.
[63]Zhang Z Z, Rong L L, Guo C H. A deterministic small-world network created by edge iterations[J]. Physica A, 2006,363: 567-572.
[64]Lu Z M, Su Y X, Guo S Z. Deterministic scale-free small-world networks of arbitrary order[J]. Physica A, 2013,392(17): 3555-3562.
[65]Douglas, Robert J. NP-completeness and degree restricted spanning trees[J]. Discrete Mathematics, 1992,105(1/3): 41-47.
[66]Yao B, Zhao M M, Rong Y, et al. Topological coding and topological matrices toward network overall security[J]. arXiv:1909.01587v1 [cs.IT] 4 Sep 2019.
[67]Jorgen B J, Gregory G. Digraphs theory, algorithms and applications[M]. Springer-Verlag, 2007.
[68]Wang X M, Yao B, Xu J. Connections between several distributions of scale-free networks[J]. arXiv: 1601.06357v1 [cs.SI] 24 Jan 2016.
[69]Su J, Yao B, Yao M. Some characteristics of a class of edge-iteration network models[C]∥2nd Information Technology and Mechatronics Engineering Conference. Paris: Atlantis Press, 2016: 15-19.
[70]Dorogovtsev S N, Goltsev A V, Mendes J F F. Pseudofractal scale-free web[J]. Physical Reviewer, 2002(65): 066122-066125.
[71]姚兵. 关于组合泛化中的拓扑编码和矩阵[R]. 2019 年中国人工智能学会离散智能计算专委会年会大会报告. 兰州:兰州交通大学, 2019.

基金

国家自然科学基金资助项目(61163054,61363060,61662066)
PDF(5231 KB)

533

Accesses

0

Citation

Detail

段落导航
相关文章

/