Biological network comparison using graphlet degree distribution
arXiv:0901.4589 · doi:10.1093/bioinformatics/btl301
Abstract
Analogous to biological sequence comparison, comparing cellular networks is an important problem that could provide insight into biological understanding and therapeutics. For technical reasons, comparing large networks is computationally infeasible, and thus heuristics such as the degree distribution have been sought. It is easy to demonstrate that two networks are different by simply showing a short list of properties in which they differ. It is much harder to show that two networks are similar, as it requires demonstrating their similarity in all of their exponentially many properties. Clearly, it is computationally prohibitive to analyze all network properties, but the larger the number of constraints we impose in determining network similarity, the more likely it is that the networks will truly be similar. We introduce a new systematic measure of a network's local structure that imposes a large number of similarity constraints on networks being compared. In particular, we generalize the degree distribution, which measures the number of nodes 'touching' k edges, into distributions measuring the number of nodes 'touching' k graphlets, where graphlets are small connected non-isomorphic subgraphs of a large network. Our new measure of network local structure consists of 73 graphlet degree distributions (GDDs) of graphlets with 2-5 nodes, but it is easily extendible to a greater number of constraints (i.e. graphlets). Furthermore, we show a way to combine the 73 GDDs into a network 'agreement' measure. Based on this new network agreement measure, we show that almost all of the 14 eukaryotic PPI networks, including human, are better modeled by geometric random graphs than by Erdos-Reny, random scale-free, or Barabasi-Albert scale-free networks.
Proceedings of the 2006 European Conference on Computational Biology, ECCB'06, Eilat, Israel, January 21-24, 2007
References in corpus (1)
Cited by in corpus (64)
- Predicting multicellular function through multi-layer tissue networks
- Current and future directions in network biology
- Emergent Complex Network Geometry
- Distance Encoding: Design Provably More Powerful Neural Networks for Graph Representation Learning
- What Would a Graph Look Like in This Layout? A Machine Learning Approach to Large Graph Visualization
- The Power of Pivoting for Exact Clique Counting
- Degree Relations of Triangles in Real-world Networks and Models
- GraphCrop: Subgraph Cropping for Graph Classification
- Continuous-time quantum walk spatial search on the Bollobás scale-free network
- A Framework for Generalizing Graph-based Representation Learning Methods
- Proper network randomization is key to assessing social balance
- odeN: Simultaneous Approximation of Multiple Motif Counts in Large Temporal Networks
- Counterfactual Learning on Graphs: A Survey
- Human Mobility Networks Manifest Dissimilar Resilience Characteristics at Macroscopic, Substructure, and Microscopic Scales
- Discriminative structural graph classification
- Motif-driven Dense Subgraph Discovery in Directed and Labeled Networks
- Provably and Efficiently Approximating Near-cliques using the Turán Shadow: PEANUTS
- Size-Invariant Graph Representations for Graph Classification Extrapolations
- Ultra High-Dimensional Nonlinear Feature Selection for Big Biological Data
- Heterogeneous Network Motifs
- A novel similarity measure for mining missing links in long-path networks
- Evolution of Directed Triangle Motifs in the Google+ OSN
- Growing Graphs with Hyperedge Replacement Graph Grammars
- Modeling and Measuring Graph Similarity: The Case for Centrality Distance
- Mining and modeling character networks
- Kaleido: An Efficient Out-of-core Graph Mining System on A Single Machine
- Efficiently Counting Vertex Orbits of All 5-vertex Subgraphs, by EVOKE
- Comparing directed networks via denoising graphlet distributions
- Network Motifs Analysis of Croatian Literature
- Edge crossings in random linear arrangements
- Compression-based inference of network motif sets
- Metrics for network comparison using egonet feature distribution
- Fair Evaluation of Global Network Aligners
- GraphZip: Dictionary-based Compression for Mining Graph Streams
- Local, global and scale-dependent node roles
- GraLSP: Graph Neural Networks with Local Structural Patterns
- A GraphBLAS Approach for Subgraph Counting
- Quantum Motif Clustering
- Construction of edge-ordered multidirected graphlets for comparing dynamics of spatial temporal neural networks
- Quantum evolution kernel : Machine learning on graphs with programmable arrays of qubits
- Nonparametric Two-Sample Test for Networks Using Joint Graphon Estimation
- GREAT: GRaphlet Edge-based network AlignmenT
- Simultaneous Optimization of Both Node and Edge Conservation in Network Alignment via WAVE
- The Structurally Smoothed Graphlet Kernel
- Fast counting of medium-sized rooted subgraphs
- A Visual Analytics Framework for Contrastive Network Analysis
- Distributed Subgraph Enumeration via Backtracking-based Framework
- Theoretically Improving Graph Neural Networks via Anonymous Walk Graph Kernels
- ThunderRW: An In-Memory Graph Random Walk Engine (Complete Version)
- A Return to Biased Nets: New Specifications and Approximate Bayesian Inference
- An egonet-based approach to effective weighted network comparison
- Attributed-graphs kernel implementation using local detuning of neutral-atoms Rydberg Hamiltonian
- One Node at a Time: Node-Level Network Classification
- Permutation-Invariant Subgraph Discovery
- Efficient Sampling Algorithms for Approximate Temporal Motif Counting (Extended Version)
- Ranking Users in Social Networks with Motif-based PageRank
- Network Medicine in the age of biomedical big data
- An interdisciplinary survey of network similarity methods
- Investigating cognitive ability using action-based models of structural brain networks
- A Temporal Tree Decomposition for Generating Temporal Graphs
- Differential analysis of biological networks
- Graphlets in multilayer networks
- Hierarchical sequencing of online social graphs
- Graphlet-based lazy associative graph classification