Quantifying Importance of Edges in Networks

Bo Ouyang, Yongxiang Xia, Cong Wang, Qiang Ye, Zhi Yan, Qiu Tang

Research output: Contribution to journalArticlepeer-review

23 Scopus citations


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.

Original languageEnglish (US)
Article number8326527
Pages (from-to)1244-1248
Number of pages5
JournalIEEE Transactions on Circuits and Systems II: Express Briefs
Issue number9
StatePublished - Sep 2018

All Science Journal Classification (ASJC) codes

  • Electrical and Electronic Engineering


  • Complex systems
  • edge importance
  • giant component


Dive into the research topics of 'Quantifying Importance of Edges in Networks'. Together they form a unique fingerprint.

Cite this