Abstract:

Network structures were emerged broadly and frequently in real world systems ranging from the Internet, the World Wide Web to gene regulation and scientific collaborations. Several topological metrics were introduced to identify important elements or to measure importance of elements in network systems. Existing metrics for characterizing networks have broad specificity and lack the selectivity for many applications. The purpose of this research is to introduce an effective metric, termed bridging centrality, which is highly selective for identifying bridging nodes in networks for element level analysis. The bridging nodes identified by bridging centrality were distinguished from the nodes identified by the other metrics. Real world networks are highly susceptible to disruption but robust to loss structural integrity upon targeted deletion of bridging nodes. The components identified by bridging centrality are shown to be located on important paths between modules. Furthermore, these bridges were shown to be effectively used for graph clustering and drug target identification. Therefore, bridging centrality is an effective network metric identifying bridging elements with unique properties that may aid in network analysis in many areas like systems biology, drug target identification, network maintenance and national security applications.

Quantitative characterization of the topological characteristics of protein-protein interaction (PPI) networks can enable the elucidation of biological functional modules. Finding functional modules in complex networks should be a challenging problem. Two different approaches will be introduced in this research, i.e., bridging cut and information flow based clustering algorithms (CASCADE). Bridging Cut algorithm utilized the bridges identified by bridging centrality. Cutting those bridges enabled us to find effective sub-modules in networks. We present a novel clustering methodology for PPI networks wherein the biological and topological influence of each protein on other proteins is modeled using the probability distribution that the series of interactions necessary to link a pair of distant proteins in the network occur within a time constant (the occurrence probability). CASCADE selects representative nodes for each cluster and iteratively refines clusters based on a combination of the occurrence probability and graph topology between every protein pair. The CASCADE approach is compared to nine competing approaches. The clusters obtained by each technique are compared for enrichment of biological function. CASCADE generates larger clusters and the clusters identified have p-values for biological function that are approximately 1000-fold better than the other methods on the yeast PPI network dataset.