TY - JOUR
T1 - Quantifying Importance of Edges in Networks
AU - Ouyang, Bo
AU - Xia, Yongxiang
AU - Wang, Cong
AU - Ye, Qiang
AU - Yan, Zhi
AU - Tang, Qiu
N1 - Funding Information:
Manuscript received February 19, 2018; accepted March 19, 2018. Date of publication March 27, 2018; date of current version August 28, 2018. This work was supported in part by the National Natural Science Foundation of China under Grant 61573310 and Grant 61603131, in part by the Zhejiang Provincial Natural Science Foundation of China under Grant LY15F030006, and in part by the Open Foundation of State Key Laboratory of Networking and Switching Technology, Beijing University of Posts and Telecommunications under Grant SKLNST-2016-2-21. This brief was recommended by Associate Editor H. H.-C. Iu. (Corresponding author: Yongxiang Xia.) B. Ouyang is with the College of Electrical and Information Engineering, Hunan University, Changsha 410082, China, and also with the State Key Laboratory of Networking and Switching Technology, Beijing University of Posts and Telecommunications, Beijing 100876, China.
Funding Information:
This work was supported in part by the National Natural Science Foundation of China under Grant 61573310 and Grant 61603131, in part by the Zhejiang Provincial Natural Science Foundation of China under Grant LY15F030006, and in part by the Open Foundation of State Key Laboratory of Networking and Switching Technology, Beijing University of Posts and Telecommunications under Grant SKLNST-2016-2-21.
Publisher Copyright:
© 2018 IEEE.
PY - 2018/9
Y1 - 2018/9
N2 - Modern society relies heavily on complex infrastructures, such as power systems and communication systems, which makes it vulnerable to intentional attacks or unpredictable failures. Being able to locate critical components in such systems allows us to protect it from attacks or failures with minimal effort. From a network science perspective, two fundamental types of components in a system are its constituent nodes and edges. The importance of nodes recently attracts a lot of interests. However, edges are paid less attention to, although in the case of protection, edge targeted methods are less invasive and more flexible. In this brief, we address the issue of quantifying importance of edges. The importance of edges is defined as how their removal affects the connectivity of the network, since connectivity is the most important property that ensures the network's function. The proposed importance measure, nearest-neighbor connectivity-based edge importance, can be used to quantify the importance of a single edge or a set of edges. The result on real-world network data shows that the proposed measure is more efficient than the most widely used measures. As another result, we show that the importance of a single edge is not necessarily positive correlated with the importance of incident nodes, which is widely assumed in literatures.
AB - Modern society relies heavily on complex infrastructures, such as power systems and communication systems, which makes it vulnerable to intentional attacks or unpredictable failures. Being able to locate critical components in such systems allows us to protect it from attacks or failures with minimal effort. From a network science perspective, two fundamental types of components in a system are its constituent nodes and edges. The importance of nodes recently attracts a lot of interests. However, edges are paid less attention to, although in the case of protection, edge targeted methods are less invasive and more flexible. In this brief, we address the issue of quantifying importance of edges. The importance of edges is defined as how their removal affects the connectivity of the network, since connectivity is the most important property that ensures the network's function. The proposed importance measure, nearest-neighbor connectivity-based edge importance, can be used to quantify the importance of a single edge or a set of edges. The result on real-world network data shows that the proposed measure is more efficient than the most widely used measures. As another result, we show that the importance of a single edge is not necessarily positive correlated with the importance of incident nodes, which is widely assumed in literatures.
KW - Complex systems
KW - edge importance
KW - giant component
UR - http://www.scopus.com/inward/record.url?scp=85044853477&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85044853477&partnerID=8YFLogxK
U2 - 10.1109/TCSII.2018.2820090
DO - 10.1109/TCSII.2018.2820090
M3 - Article
AN - SCOPUS:85044853477
SN - 1549-7747
VL - 65
SP - 1244
EP - 1248
JO - IEEE Transactions on Circuits and Systems II: Express Briefs
JF - IEEE Transactions on Circuits and Systems II: Express Briefs
IS - 9
M1 - 8326527
ER -