New algorithm for solving connectivity of networks

doi:10.3778/j.issn.1002-8331.2009.34.025

Computer Engineering and Applications ›› 2009, Vol. 45 ›› Issue (34): 82-84.DOI: 10.3778/j.issn.1002-8331.2009.34.025

• 网络、通信、安全 • Previous Articles Next Articles

New algorithm for solving connectivity of networks

SUN Xiao-jun¹，LIU San-yang²，WANG Zhi-qiang³

1.Department of Mathematics，Baoji University of Arts & Science，Baoji，Shaanxi 721013，China
2.School of Science，Xidian University，Xi’an 710071，China
3.General Armament Department Military Representative Office in Tianshui Region，Baoji，Shaanxi 721006，China

Received:2009-07-06 Revised:2009-08-14 Online:2009-12-01 Published:2009-12-01
Contact: SUN Xiao-jun

求解网络连通度问题的新算法

孙小军¹，刘三阳²，王志强³

1.宝鸡文理学院数学系，陕西宝鸡 721013
2.西安电子科技大学理学院，西安 710071
3.总装备部驻天水地区军事代表室，陕西宝鸡 721006

通讯作者: 孙小军

Abstract

Abstract: Connectivity is not only an index to evaluate the status of network connectivity and survivability，but also an important feature of the network structure.Regarding the deficiency of the present algorithm for solving the connectivity of networks，which needs to change existing network to capacity network，a new algorithm is proposed in this paper，basing on inspiration of the paralysis of transportation network.By introducing two influencing degree-vector to stress the importance of the point in network，it shows that the new algorithm can not only solve network connectivity and determine the minimum vertex-cut，but also simple and easy to implement.Finally，the effectiveness is proved through simulation experiment and example.

Key words: networks, invulnerability, influence, minimum vertex-cut, connectivity

摘要： 连通度是评价网络系统连通状况及抗毁性的重要指标，也是网络结构的重要特征。针对现有算法在求解网络连通度时需要将原有网络转化为容量网络或进行其他变换的不足，受交通网络瘫痪事例的启发，提出了一种求解网络连通度的新算法。该算法通过引入点影响度和网络影响度来刻画各顶点在网络中的重要程度，不仅能求解网络连通度，同时还可以确定网络的最小点割，算法步骤简单、易于实现。最后算法分析和仿真实验表明了新算法的有效性。

关键词: 网络, 可靠性, 影响度, 最小点割, 连通度

CLC Number:

TP301.6

SUN Xiao-jun¹，LIU San-yang²，WANG Zhi-qiang³. New algorithm for solving connectivity of networks[J]. Computer Engineering and Applications, 2009, 45(34): 82-84.

孙小军¹，刘三阳²，王志强³. 求解网络连通度问题的新算法[J]. 计算机工程与应用, 2009, 45(34): 82-84.

[1]	RAN Rong, XU Xinghua, QIU Shaohua, CUI Xiaopeng, OUYANG Bin. Review of Crack Detection Methods Based on Deep Convolutional Neural Networks [J]. Computer Engineering and Applications, 2021, 57(9): 23-35.
[2]	JIA Xiang’en, DONG Yihong, ZHU Feng, QIAN Jiangbo. Research Progress of Heterogeneous Graph Convolutional Networks [J]. Computer Engineering and Applications, 2021, 57(9): 36-49.
[3]	SUN Zeyu, XU Chen, SU Yanchao, LI Chuanfeng, NIE Yalin. CCRP：Cross-Layer-Sensing Clustering Routing Protocol in Fog Computing [J]. Computer Engineering and Applications, 2021, 57(9): 109-117.
[4]	MOU Qingping, ZHANG Ying, ZHANG Dongbo, WANG Xinjie, YANG Zhiqiao. Research on Visual Tracking Algorithm and Application of Target Loss Discrimination Mechanism [J]. Computer Engineering and Applications, 2021, 57(9): 140-147.
[5]	HUANG Dongyi, YANG Bing, WU Zihao, KUANG Jiayi, YAN Zeming. Spatio-Temporal Fully Connected Convolutional Neural Networks for Citywide Cellular Prediction [J]. Computer Engineering and Applications, 2021, 57(9): 168-175.
[6]	CHAI Xu, FANG Ming, FU Feiran, SHAO Zhen. Sight Estimation Algorithms for Examinee in Examination Room Environment [J]. Computer Engineering and Applications, 2021, 57(9): 199-206.
[7]	MA Zhexu, YANG Feng, QIAO Xu. Intelligent Detection Method of Railway Subgrade Defect [J]. Computer Engineering and Applications, 2021, 57(9): 272-278.
[8]	YANG Peiwei, ZHOU Yuhong, XING Gang, TIAN Zhiqiang, XU Xiayu. Applications of Convolutional Neural Network in Biomedical Image [J]. Computer Engineering and Applications, 2021, 57(7): 44-58.
[9]	XU Xiaochun, DONG Hongwei, WEI Chengfeng. Application of Improved CAGAN in Virtual Try-on [J]. Computer Engineering and Applications, 2021, 57(6): 152-158.
[10]	LI Junxia, ZHANG Qin, ZHENG Guimei. Overview of Human Posture Recognition by Ultra-wideband Radar [J]. Computer Engineering and Applications, 2021, 57(3): 14-23.
[11]	ZHOU Huaqiang, CAO Lin, DU Kangning. Sketch Face Synthesis Based on Multi-discriminator Cyclic Generative Adversarial Network [J]. Computer Engineering and Applications, 2021, 57(3): 231-238.
[12]	XU Xianfeng, CAI Lulu, ZHANG Li. Photovoltaic Power Generation Prediction Algorithm Based on MLP and DBN [J]. Computer Engineering and Applications, 2021, 57(3): 266-272.
[13]	MA Jinlin, ZHU Yanbin, MA Ziping, GONG Yuanwen, CHEN Deguang, LIU Yuhao. Review of Deep Learning Methods for Lip Recognition [J]. Computer Engineering and Applications, 2021, 57(24): 61-73.
[14]	CHENG Shuai, WU Huafeng, MEI Xiaojun. Alternative Nonnegative Constrained Framework-Based Cooperative Localization Algorithm in Ocean Sensor Networks [J]. Computer Engineering and Applications, 2021, 57(23): 129-136.
[15]	WANG Haiyong, LI Haiyang, GAO Xuejiao. Research on Image Restoration Method Based on Structure Embedding [J]. Computer Engineering and Applications, 2021, 57(22): 241-246.

New algorithm for solving connectivity of networks

求解网络连通度问题的新算法

PDF

Knowledge

Abstract

Cite this article

share this article

References

Related Articles 15

Recommended Articles

Metrics