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.
%0 Conference Paper
%1 Hwang2008Bridging
%A Hwang, Woochang
%A Kim, Taehyong
%A Ramanathan, Murali
%A Zhang, Aidong
%B Proceeding of the 14th ACM SIGKDD international conference on Knowledge discovery and data mining
%C New York, NY, USA
%D 2008
%I ACM
%K bridging centrality network-parameters networks
%P 336--344
%R 10.1145/1401890.1401934
%T Bridging centrality: graph mining from element level to group level
%U http://dx.doi.org/10.1145/1401890.1401934
%X 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.
%@ 978-1-60558-193-4
@inproceedings{Hwang2008Bridging,
abstract = {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.},
added-at = {2018-12-02T16:09:07.000+0100},
address = {New York, NY, USA},
author = {Hwang, Woochang and Kim, Taehyong and Ramanathan, Murali and Zhang, Aidong},
biburl = {https://www.bibsonomy.org/bibtex/28f4124c40de5977bd6b5e0713b7fceb6/karthikraman},
booktitle = {Proceeding of the 14th ACM SIGKDD international conference on Knowledge discovery and data mining},
citeulike-article-id = {6093608},
citeulike-linkout-0 = {http://portal.acm.org/citation.cfm?id=1401934},
citeulike-linkout-1 = {http://dx.doi.org/10.1145/1401890.1401934},
doi = {10.1145/1401890.1401934},
interhash = {9791703915b3b6907c91d890f6958eb7},
intrahash = {8f4124c40de5977bd6b5e0713b7fceb6},
isbn = {978-1-60558-193-4},
keywords = {bridging centrality network-parameters networks},
location = {Las Vegas, Nevada, USA},
pages = {336--344},
posted-at = {2010-06-04 14:17:27},
priority = {2},
publisher = {ACM},
series = {KDD '08},
timestamp = {2018-12-02T16:09:07.000+0100},
title = {Bridging centrality: graph mining from element level to group level},
url = {http://dx.doi.org/10.1145/1401890.1401934},
year = 2008
}