Transitive closure and metric inequality of weighted graphs: detecting protein interaction modules using cliques

Chris Ding; Xiaofeng He; Hui Xiong; Hanchuan Peng; Stephen R. Holbrook

doi:10.1504/IJDMB.2006.010854

Transitive closure and metric inequality of weighted graphs: detecting protein interaction modules using cliques

Chris Ding, Xiaofeng He, Hui Xiong, Hanchuan Peng, Stephen R. Holbrook

Research output: Contribution to journal › Article › peer-review

17 Scopus citations

Abstract

We study transitivity properties of edge weights in complex networks. We show that enforcing transitivity leads to a transitivity inequality which is equivalent to ultra-metric inequality. This can be used to define transitive closure on weighted undirected graphs, which can be computed using a modified Floyd-Warshall algorithm. These new concepts are extended to dissimilarity graphs and triangle inequalities. From this, we extend the clique concept from unweighted graph to weighted graph. We outline several applications and present results of detecting protein functional modules in a protein interaction network.

Original language	English (US)
Pages (from-to)	162-177
Number of pages	16
Journal	International Journal of Data Mining and Bioinformatics
Volume	1
Issue number	2
DOIs	https://doi.org/10.1504/IJDMB.2006.010854
State	Published - 2006
Externally published	Yes

All Science Journal Classification (ASJC) codes

Information Systems
Biochemistry, Genetics and Molecular Biology(all)
Library and Information Sciences

Keywords

protein interaction
transitive closure
triangle inequality
ultrametric
weighted graph

Access to Document

10.1504/IJDMB.2006.010854

Cite this

@article{1e1eac5830f4487a9febc8b743a5d61c,

title = "Transitive closure and metric inequality of weighted graphs: detecting protein interaction modules using cliques",

abstract = "We study transitivity properties of edge weights in complex networks. We show that enforcing transitivity leads to a transitivity inequality which is equivalent to ultra-metric inequality. This can be used to define transitive closure on weighted undirected graphs, which can be computed using a modified Floyd-Warshall algorithm. These new concepts are extended to dissimilarity graphs and triangle inequalities. From this, we extend the clique concept from unweighted graph to weighted graph. We outline several applications and present results of detecting protein functional modules in a protein interaction network.",

keywords = "protein interaction, transitive closure, triangle inequality, ultrametric, weighted graph",

author = "Chris Ding and Xiaofeng He and Hui Xiong and Hanchuan Peng and Holbrook, {Stephen R.}",

year = "2006",

doi = "10.1504/IJDMB.2006.010854",

language = "English (US)",

volume = "1",

pages = "162--177",

journal = "International Journal of Data Mining and Bioinformatics",

issn = "1748-5673",

publisher = "Inderscience Enterprises Ltd",

number = "2",

}

TY - JOUR

T1 - Transitive closure and metric inequality of weighted graphs

T2 - detecting protein interaction modules using cliques

AU - Ding, Chris

AU - He, Xiaofeng

AU - Xiong, Hui

AU - Peng, Hanchuan

AU - Holbrook, Stephen R.

PY - 2006

Y1 - 2006

N2 - We study transitivity properties of edge weights in complex networks. We show that enforcing transitivity leads to a transitivity inequality which is equivalent to ultra-metric inequality. This can be used to define transitive closure on weighted undirected graphs, which can be computed using a modified Floyd-Warshall algorithm. These new concepts are extended to dissimilarity graphs and triangle inequalities. From this, we extend the clique concept from unweighted graph to weighted graph. We outline several applications and present results of detecting protein functional modules in a protein interaction network.

AB - We study transitivity properties of edge weights in complex networks. We show that enforcing transitivity leads to a transitivity inequality which is equivalent to ultra-metric inequality. This can be used to define transitive closure on weighted undirected graphs, which can be computed using a modified Floyd-Warshall algorithm. These new concepts are extended to dissimilarity graphs and triangle inequalities. From this, we extend the clique concept from unweighted graph to weighted graph. We outline several applications and present results of detecting protein functional modules in a protein interaction network.

KW - protein interaction

KW - transitive closure

KW - triangle inequality

KW - ultrametric

KW - weighted graph

UR - http://www.scopus.com/inward/record.url?scp=43549087161&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=43549087161&partnerID=8YFLogxK

U2 - 10.1504/IJDMB.2006.010854

DO - 10.1504/IJDMB.2006.010854

M3 - Article

C2 - 18399069

AN - SCOPUS:43549087161

SN - 1748-5673

VL - 1

SP - 162

EP - 177

JO - International Journal of Data Mining and Bioinformatics

JF - International Journal of Data Mining and Bioinformatics

IS - 2

ER -

Transitive closure and metric inequality of weighted graphs: detecting protein interaction modules using cliques

Abstract

All Science Journal Classification (ASJC) codes

Keywords

Access to Document

Other files and links

Fingerprint

Cite this