Bridges in Random Graphs and Real Networks

A \emph{bridge} in a graph is an edge whose removal will disconnect the graph, i.e, increase the number of connected components. We analytically calculate the expected number of bridges for random graphs with arbitrary degree distributions. We also calculate the number of bridges for a wide range of real-world networks, finding that they typically have more bridges than their completely randomized counterparts. Finally, we define a new network metric, called \emph{bridgeness}, to quantify the network vulnerability from the edge attack perspective. We find that infrastructural networks (especially road networks and power grid networks) hold much larger maximum \emph{bridgeness} than other networks and their randomized counterpart.