Weighted Network Analysis Applications in Genomics and Systems Biolo
This book presents state-of-the-art methods, software and applications surrounding weighted networks. Most methods and results also apply to unweighted networks. Although aspects of weighted network analysis relate to standard data mining methods, the int
- PDF / 199,116 Bytes
- 9 Pages / 439 x 666 pts Page_size
- 96 Downloads / 199 Views
Approximately Factorizable Networks
Abstract In factorizable networks, the adjacency (connection strength) between two nodes can be factored into node-specific contributions, named node “conformity”. Often the ith node conformity, CF i is approximately equal to the scaled connectivity ki /sum(k) of the ith node. We describe (a) an algorithm for computing the conformity CF and for measuring the “factorizability” of a general network, and (b) a module- and CF-based decomposition of a general adjacency matrix, which can be used to arrive at a parsimonious description of a network. Approximately factorizable networks have important practical and theoretical applications, e.g., we use them to derive relationships between network concepts. Collaborative work with Jun Dong has shown that network modules (i.e., subnetworks comprised of module nodes) tend to be approximately factorizable (Dong and Horvath BMC Syst Biol 1(1):24, 2007).
2.1 Exactly Factorizable Networks We define an adjacency matrix A to be exactly factorizable if, and only if, there exists a vector CF with nonnegative elements such that Aij = CF i CF j for all i = j.
(2.1)
Below, we show that CF is uniquely defined if the network contains n ≥ 3 nodes and if Aij > 0. We call CF i the conformity of node i. While the term “factorizable network” was first proposed in Dong and Horvath (2007), numerous examples of these types of networks can be found in the literature. A recent physical model for experimentally determined protein–protein interactions is exactly factorizable (Deeds et al. 2006). In that model, the ‘affinity’ Aij between proteins i and j is the product of conformities CF i = exp(−Ki ), where Ki is the number of hydrophobic residues in the ith protein. Another related example is an exactly factorizable random network model for which the edges between pairs of nodes are drawn according to a linking probability function (Servedio et al. 2004). In multi-graph models, CF i has been used to represent the propensity for the ith node to form S. Horvath, Weighted Network Analysis: Applications in Genomics and Systems Biology, c Springer Science+Business Media, LLC 2011 DOI 10.1007/978-1-4419-8819-5 2,
35
36
2 Approximately Factorizable Networks
an edge (Ranola et al. 2010). One can easily show that the vector CF is not unique if an exactly factorizable network contains only n = 2 nodes. However, for n > 2 the conformity is uniquely defined when dealing with a weighted network where Aij > 0. In an exercise, you are asked to prove the uniqueness.
2.2 Conformity for a Non-Factorizable Network Equation (2.21) provides an explicit formula for the conformity of a weighted, exactly factorizable network. For a general, non-factorizable network, we describe here how to compute the conformity by optimizing an objective function (Dong and Horvath 2007). In the following, we assume a general n × n adjacency matrix A where n > 2. Let v = (v1 , v2 , . . . , vn ) be a vector of length n. We define the conformity as a vector v∗ that minimizes the following obje
Data Loading...
