Algorithm for complex network diameter based on distance matrix

doi:10.21629/JSEE.2018.02.14

Journal of Systems Engineering and Electronics ›› 2018, Vol. 29 ›› Issue (2): 336-342.doi: 10.21629/JSEE.2018.02.14

• Systems Engineering • Previous Articles Next Articles

Algorithm for complex network diameter based on distance matrix

Bin CHEN^1,^2,*(), Weixing ZHU¹(), Ying LIU³()

¹ Institute of Command Information System, PLA University of Science and Technology, Nanjing 210007, China
² College of Computer Science and Engineering, Sanjiang University, Nanjing 210012, China
³ Institute of Field Engineering, PLA University of Science and Technology, Nanjing 210007, China

Received:2017-01-03 Online:2018-04-26 Published:2018-04-27
Contact: Bin CHEN E-mail:156735905@qq.com;fly_fox_2008@139.com;13913867236@139.com
About author:CHEN Bin was born in 1979. He is a Ph.D. and an associate professor in People's Liberation Army University of Science and Technology. In 2008, he graduated from this university. After graduation, he has been engaged in related scientific research and teaching work. He participated in the National High Technology Research and Development Program ("863" Program) of China (capabilities requirements analysis technology about large-scale complex system, 2007AA01Z126), the National Natural Science Foundation of China (analysis and verification for command and control system capability requirements model, 61273210) and other army key projects. He published more than 30 academic papers in this research field on authoritative domestic or foreign journals or international academic conferences. His research interests are complex system and complex network. E-mail: 156735905@qq.com|ZHU Weixing was born in 1978. He is a doctor and a lecturer in PLA University of Science and Technology. His research interest is algorithm design. In 2012, he graduated from this university. After graduation, he has been engaged in related scientific research. He has published more than ten academic papers in this research field on authoritative domestic or foreign journals or international academic conferences. E-mail: fly_fox_2008@139.com|LIU Ying was born in 1977. She is a doctor and a lecturer in PLA University of Science and Technology. Her research interest is complex system. In 2008, she graduated from this university. After graduation, she has been engaged in related scientific research and teaching work. She has published more than 20 academic papers in this research field on authoritative domestic or foreign journals or international academic conferences. E-mail: 13913867236@139.com
Supported by:
the National Natural Science Foundation of China(61273210);This work was supported by the National Natural Science Foundation of China (61273210)

Abstract

Abstract:

The network diameter is an important characteristic parameter of a complex network. Calculation for a large-scale complex network's diameter has been an important subject in the study of complex networks. If the network diameter is calculated directly, the problem mainly exists in efficiency for searching and counting the shortest paths. If the network diameter is calculated indirectly by studying the statistical function about the relationship between the network diameter and parameters affecting the diameter, the problems not only exist in the efficiency of statistic, but also exist in the function which may be not applicable to all kinds of networks. An algorithm for the complex network diameter based on the k order distance matrix is proposed with a matrix multiplication approach, and a mathematical proof for the algorithm correctness is given as well. Furthermore, some relevant propositions and deductions for reducing the complexity of this algorithm are put forward. With a good theoretical basis and a simple calculation process, this algorithm can be used to calculate the diameter of a large-scale complex network with small-world effect more accurately and efficiently. Two cases about the advanced research projects agency (ARPA) network model and the Chinese airline network model are adopted to verify the effect of this algorithm.

Key words: complex network, network diameter, distance matrix

Bin CHEN, Weixing ZHU, Ying LIU. Algorithm for complex network diameter based on distance matrix[J]. Journal of Systems Engineering and Electronics, 2018, 29(2): 336-342.

Figures/Tables 6

Fig 1

Fig 2

Fig 3

Fig 4

Fig 5

Fig 6

References 25

1	DA F, COSTA L, EVSUKOFF A, et al. Communications in computer and information. Berlin: Springer Verlag, 2011.
2	GU L, HUANG H L, ZHANG X D. The clustering coefficient and the diameter of small-world networks. Acta Mathematica Sinica, 2013, 29 (1): 199- 208. doi: 10.1007/s10114-012-0387-6
3	HUNG J, YEN N, LI K C. Frontier computing. Singapore: Springer Verlag, 2016.
4	SQUILLERO G, SIM K. Applications of evolutionary computation. Zug: Springer Verlag, 2017.
5	GAO J, EFRAT A, FEKETE S, et al. Algorithms for sensor systems. Berlin: Springer Verlag, 2015.
6	YANG J, FANG F, SUN C. Intelligent science and intelligent data engineering. Berlin: Springer Verlag, 2013.
7	SU X, HE T. Chinese lexical semantics. Zug: Springer Verlag, 2014.
8	HERNÁNDEZ C B, GITLER I, KLAPP J. High performance computing. Zug: Springer Verlag, 2017.
9	HOFNER P, MOLLER B. Dijkstra Floyd and Warshall meet Kleene. Formal Aspects of Computing, 2012, 24 (4/6): 459- 476.
10	CORMEN T H, LEISERSON C E. Introduction to algorithm. London: The MIT Press, 3rd ed 2009.
11	COLORNI A, DORIGO M, MANIEZZO V. Distributed optimization by ant colonies. Proc. of CAL91-European Conference on Artificial Life, 1991: 134-142.
12	NI X J, ZHANG N, WANG M J. An MPI based parallel algorithm to calculate the shortest path of CERNET. Computer Engineering and Applications, 2006, 42 (12): 135- 137.
13	ALBERT R, JEONG H, BARABASI A L. Internet: diameter of the world-wide web. Nature, 1999, 401 (6749): 130- 131. doi: 10.1038/43601
14	FAN C, LU L Y. The diameter of sparse random graphs. http://math.ucsd.edu/~fan/dia.pdf.
15	ALBERT R, JEONG H, BARABASI A L. Error and attack tolerance of complex networks. Nature, 2000, 406 (6794): 378- 382. doi: 10.1038/35019019
16	LI Y, SHAN X M, REN Y. Average path length of internet with power law degree distribution. Acta Physica Sinica, 2004, 53 (11): 3695- 3700.
17	HASSANA S A, HEMEIDAB A M, MAHMOUDA M M M. Performance evaluation of matrix-matrix multiplications using Intel's advanced vector extensions (AVX). Microprocessors and Microsystems, 2016, 47 (B): 369- 374.
18	STRASSEN V. Gaussian elimination is not optimal. Numerische Mathematik, 1969, 13 (4): 354- 356. doi: 10.1007/BF02165411
19	PAN V Y. New combinations of methods for the acceleration of matrix multiplications. Computers & Mathematics with Applications, 1987, 7 (1): 73- 125.
20	COPPERSMITH D, WINOGRAD S. Matrix multiplication via arithmetic progressions. Journal of Symbolic Computation, 1987, 9 (3): 251- 280.
21	KHAN A H, AL-MOUHAMED M, FATAYER A, et al. Optimizing the matrix multiplication using Strassen and Winograd algorithms with limited recursions on many-core. International Journal of Parallel Programming, 2016, 44 (4): 801- 830. doi: 10.1007/s10766-015-0378-1
22	STOTHERS A J. On the complexity of matrix multiplication. Edinburgh, UK: University of Edinburgh, 2010.
23	WILLIAMS V V. Multiplying matrices faster than coppersmith-winograd. Proc. of the 44th Annual ACM Symposium on Theory of Computing, 2012: 887-898.
24	GALL L F. Powers of tensors and fast matrix multiplication. arXiv preprint arXiv, 2014, 1401, 7714.
25	ZENG X Z. Empirical study of Chinese airline network structure based on complex network theory. Nanjing, China: Nanjing University of Aeronautics and Astronautics, 2011. (in Chinese)

[1]	Yinghui YANG, Jianhua LI, Di SHEN, Mingli NAN, Qiong CUI. Evolutionary dynamics analysis of complex network with fusion nodes and overlap edges [J]. Journal of Systems Engineering and Electronics, 2018, 29(3): 549-559.
[2]	Chao GENG, Shiyou QU, Yingying XIAO, Mei WANG, Guoqiang SHI, Tingyu LIN, Junjie XUE, Zhengxuan JIA. Diffusion mechanism simulation of cloud manufacturing complex network based on cooperative game theory [J]. Journal of Systems Engineering and Electronics, 2018, 29(2): 321-335.
[3]	Bin Chen, Zhixue Wang, and Chen Luo. Integrated evaluation approach for node importance of complex networks based on relative entropy [J]. Journal of Systems Engineering and Electronics, 2016, 27(6): 1219-1226.
[4]	Yushi Lan, Kebo Deng, Shaojie Mao, Heng Wang, Kan Yi, and Ming Lei. Adaptive evolvement of information age C⁴ISR structure [J]. Journal of Systems Engineering and Electronics, 2015, 26(2): 301-316.
[5]	Hongming Mo, Cai Gao, and Yong Deng. Evidential method to identify influential nodes in complex networks [J]. Journal of Systems Engineering and Electronics, 2015, 26(2): 381-387.
[6]	Qi Gao, Xiaoting Li, and Feng Pan. Research on variance of subnets in network sampling [J]. Journal of Systems Engineering and Electronics, 2014, 25(6): 1098-1106.

Algorithm for complex network diameter based on distance matrix

RichHTML

PDF (PC)

Knowledge

Abstract

Cite this article

Share this article

Figures/Tables 6

References 25

Related Articles 6

Recommended Articles

Metrics

Comments