Bridges in Complex Networks

A bridge in a graph is an edge whose removal disconnects the graph and increases the number of connected components. We calculate the fraction of bridges in a wide range of real-world networks and their randomized counterparts. We nd that real networks typically have more bridges than their completely randomized counterparts, but very similar fraction of bridges as their degreepreserving randomizations. We de ne a new edge centrality measure, called bridgeness, to quantify the importance of a bridge in damaging a network. We nd that certain real networks have very large average and variance of bridgeness compared to their degree-preserving randomizations and other real networks. Finally, we o er an analytical framework to calculate the bridge fraction, the average and variance of bridgeness for uncorrelated random networks with arbitrary degree distributions.