Bridging centrality: Graph mining from element level to group level

Despite the pervasiveness of networks as models for real world systems ranging from the Internet, the World Wide Web to gene regulation and scientific collaborations, only a limited number of metrics capable of characterizing these systems are available. The existing metrics for characterizing networks have broad specificity and lack the selectivity for many applications. The purpose of this paper is to identify and critically evaluate a metric, termed bridging centrality, which is highly selective for identifying bridges in networks. The properties of bridges are unique compared to the other network metrics. For a diverse range of data sets, we found that networks are highly susceptible to disruption but robust to loss structural integrity upon targeted deletion of bridging nodes. A novel graph clustering approach, termed 'bridge cut', utilizing bridging edges as module boundary is also proposed. The modules identified by the bridge cut algorithm are more effective than the other graph clustering methods. Thus, bridging centrality is a network metric with unique properties that may aid in network analysis from element to group level in various areas including systems biology and national security applications.