Bridging centrality: graph mining from element level to group level

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.

REFERENCES

• 1: Proceedings of the Symposium on Graph Drawing, September 1996
• 2: Albert, R., Jeong, H. and Barabasi, A. L. Error and attack tolerance of complex networks. Nature, 406:378--82, 2000.
• 3: Bader, G.D. and Hogue. C.W. An automated method for finding molecular complexes in large protein interaction networks. BMC Bioinformatics, 4:2, 2003.
• 4: Barabasi, A.L. and Oltvai, Z.N. Network biology: understanding the cell's functional organization. Nat. Rev. Genet., 5:101--113, 2004.
• 5: Batagelj, V., and Mrvar, A. Pajek . Program for Large Network Analysis. Connections, :, 1998.
• 6: Brandes, U. and Fleischer, D. Centrality measures based on current flow . In Proceedings of the 22nd International Symposium on Theoretical Aspects of Computer Science (STACS'S05), volume , page , 2005.
• 7: Breitling R, Armengaud P, Amtmann A, Herzyk P. Rank products: a simple, yet powerful, new method to detect diffierentially regulated genes in replicated microarray experiments. FEBS Letter, 573:83--92, 2004
• 8: Sergey Brin , Lawrence Page, The anatomy of a large-scale hypertextual Web search engine, Proceedings of the seventh international conference on World Wide Web 7, p.107-117, April 1998, Brisbane, Australia
• 9: Bu, D. et al. Topological structure analysis of the protein-protein interaction network in budding yeast. Nucleic Acids Res., 31:2443--2450, 2003.
• 10: Davies, D., Bouldin, D. . A cluster separation measure. IEEE Trans. Pattern Reconit. Machine Intell., 1(2):224--227, 1979.
• 11: Deane, C.M., Salwinski, L., Xenarios, I. and Eisenberg, D. . Protein interactions: two methods for assessment of the reliability of high throughput observations. Mol. Cell Proteomics, 1:349--356, 2002.
• 12: Estrada, E. and Rodríguez-Velázquez, J. Subgraph centrality in complex networks. . Phys. Rev. E, 71:056103-1--9, 2005.
• 13: Freeman, L.C. A set of measures of centrality based upon betweeness. . Sociometry, 40:35Ü41, 1977.
• 14: Guimera, R. and Nunes Amaral, L. A. An automated method for finding molecular complexes in large protein interaction networks. Nature, 433:895--900, 2005.
• 15: Erez Hartuv , Ron Shamir, A clustering algorithm based on graph connectivity, Information Processing Letters, v.76 n.4-6, p.175-181, Dec.31 2000 [doi>10.1016/S0020-0190(00)00142-3]
• 16: Hwang, W. et al. A novel functional module detection algorithm for protein-protein interaction networks. Algorithms Mol Biol., 1:24, 2006.
• 17: Donald B. Johnson, Efficient Algorithms for Shortest Paths in Sparse Networks, Journal of the ACM (JACM), v.24 n.1, p.1-13, Jan. 1977 [doi>10.1145/321992.321993]
• 18: A. D. King , N. Pržulj , I. Jurisica, Protein complex prediction via cost-based clustering, Bioinformatics, v.20 n.17, p.3013-3020, November 2004 [doi>10.1093/bioinformatics/bth351]
• 19: Lind, P., Silva, L., Andrade, J., Hermann, H. . Spreading gossip in social networks. Phys. Rev. E., 76:036117, 2007.
• 20: Mewes, H. W. . MIPS: analysis and annotation of proteins from whole genome in 2005. Nucleic Acid Research, 34:D169--D172, 2006.
• 21: Newman, M. E. and Girvan, M. Finding and evaluating community structure in networks. . Phys Rev E Stat Nonlin Soft Matter Phys, 69:026113, 2004.
• 22: Newman, M.E.J. A measure of betweenness centrality based on random walks. . arxiv preprint, 1(3):215--239, 2003.
• 23: Park, J. and Newman, M. E. Origin of degree correlations in the Internet and other networks. Phys Rev E Stat Nonlin Soft Matter Phys, 68:026112, 2003.
• 24: Rives, A.W. and Galitski, T. Modular organization of cellular networks. Proc. Natl. Acad. Sci., 100(3):1128--33, 2003.
• 25: Samanta, M.P. and Liang,S. Redundancies in large-scale protein interaction networks. Proc. Natl Acad. Sci., 100:12579--12583, 2003.
• 26: Spellman, P. et al. Comprehensive Identification of Cell Cycle-regulated Genes of the Yeast Saccharomyces cerevisiae by Microarray Hybridization. Molecular Biology of the Cell, 9:3273--3279, 1998.
• 27: Spirin, V. and Mirny, L.A. . Protein complexes and functional modules in molecular networks. PNAS, 100:12123--12128, 2003.
• 28: Ulrik Brandes. A faster algorithm for betweenness centrality. Journal of Mathematical Sociology, 25(2):163--177, 2001.
• 29: Stijn Dongen, A cluster algorithm for graphs, CWI (Centre for Mathematics and Computer Science), Amsterdam, The Netherlands, 2000
• 30: Watts, D. J. and Strogatz, S. H. Collective dynamics of 'small-world' networks. Nature , 393:440--2, 1998.

INDEX TERMS

Primary Classification:
  E. Data
  E.1 DATA STRUCTURES
      Subjects: Graphs and networks

General Terms:
Algorithms, Measurement

Keywords:
bridging centrality, graph clustering