[SOUND] [BLANK_AUDIO] In this lecture, I will describe to you how one can analyze networks and what one can learn from this type of analysis. So let's start off with what we can, learn about cell biological systems as casting them as networks. overall, the organiza, the, one can learn about how the system is organized in terms of binary reactions. Indeed, every protein or gene or other molecules interact with other molecules and it is from these interactions that biological functions arise. So understanding how these binary interactions are organized, and how this organization leads to function is sort of a very important and useful facet of systems biology studies. It also helps us to identify key nodes that are important cellular co, components in terms of the connectivity, which means those nodes that connect to a lot, or it connect or interact with a lot of other cellular components. These are called hubs and they are like important in both network structure and in biological functions. One can also, by studying networks, understand how much of the system is susceptible to disruption by, say, removal or inactivation of various types of nodes, either by the mutation of a gene or degradation of a protein or whatever. So sort of understanding whether the system is fragile, or robust in terms of its nodes and interactions is a very useful part of network analysis. Identifying the potential for vectorial information flow as well as information flow to loops such as positive or negative feedback loops. I won't cover this in this lecture but in the next lecture, I talk about directed graphs. We'll spend some time on understanding vectorial flow of information. And, of course, all of these kinds of informations allow us to understand the ability of a cellular system to process signals, to affect input output relationships, which means that the cellular, the cell has a system that's not just a response system, but it's also an information processing system where the response is altered and respond altered in by this capability of the cell, to process information even as information flows through the system. Let us start with the analysis of undirected graphs. Undirected Graphs are connectivity between nodes where there is no specification of directions. You can clearly see this in the diagram shown right here where there is no arrow between how E and F are connected. A key characteristic of graphs or networks is the node degree and this is actually a key characteristic of the nodes. Nodes are characterized by a number of edges that they have. And the symbol for the node degree is k. The Degree Distribution which is the distribution of edges for node ratio for the whole network uses the symbol Pk. And for many real networks degree distribution follows a function, which is called a power law. And and I'll describe the power law in the next in, in greater detail in the next slide. the, per the Degree Distribution is given by the equation shown here, which is P sub k equals Ak raised to a gamma, where gamma, the, the exponent is gamma is usually in the range of two to three. You can you can see this in the this brief equation in Ricky Albert's review. This is actually a very good review which are used as required reading for this, week. The network on this right, the network, shown here is composed of really two islands. And you can see the two parts that aren't connected to each other and that's why they're called islands. And these characteristics are defined by its degree and degree distribution. The island IJK, this little one here, is called a clique, because the island is completely connected. All the nodes in the island are completely connected with one another. So Scale Free Networks. The term Scale Free indicates that there is not really a, so we can say it's, it's not a typical degree or scale for the number of edges a node has. Graphs representing real systems suggest signaling networks are organized differently from random graphs. Random graphs are graphs that are constructed by randomly connecting a given number of node by a given number of edges. This was first done these kinds of graphs were first constructed by these mathematicians Erdos and Renyi and these are sometimes called Erdos-Renyi graphs. The degree distribution of a random graph is bell shaped, as you can see in the left panel. And the majority of the nodes have a degree close to the average node, close to the average node here. In contrast, real distribution, in contrast, in real network, the degree distribution follows a power law. Here, there is a large number of nodes with different degrees and, and in reality, there is no typical node that could be used to characterize the rest of the nodes. The absence of a typical node or a typical scale is why these networks are called Scale Free. And I've taken this quotation from Ricky Albert's review. And you can see that it's a very clear description of what scale free means. And if one plots the degree distribution as a function of as a function of the degree, one can see the Scale Free Networks in a log plot produce a straight line and the slope of this line will give you the the power law coefficient. So this kind of Scale Free Network leads to a property that is called network robustness. That is, robustness is defined as a resistance of a network to be fractured into smaller pieces or smaller islands. Remember the network that I showed you previously in two slides ago that had two little islands? So we can break the network which is one connecting group of nodes, one fully connected group of nodes into multiple small subgroups and this is called fracturing. And the fracturing of the network can be a, it's, can sometimes, for scale free network is diffi, difficult to accomplish by removal of a small number of nodes. Indeed Scale Free Networks are robust and they, they cannot be fractured by removal of a small number of nodes randomly. This has been studied extensively in mathematics using a theory called Percolation Theory. And there's a very nice paper in what, Physical, which was published in Physical Reviews letter, a free version of which is is available in arXiv. And you can look at this paper to see how network robustness is associated with scale free networks. The opposite of robustness is, of course, fragile. And scale free networks are fragile to the removal of specific hubs. So if you remove a hub that connects many, many proteins or many, many components within the network, then, indeed, the network is likely to fall apart. So both robustness and fragility can be computed as as defined quantities based on the power law and the scale free nature of a real network. A useful characteristic of networks is the distances. And the distances sort of give rise to what is called network topology or organization. And topology is really the organization of the links and nodes. And one of the distances that is most commonly calculated is the average path length. Average path length is the average of the shortest paths between any two nodes in a graph. So if you start from one node, for instance, and want to go to the other node, the the shortest path would be the one that is that is used to calculate the average path. Another feature of a node, which tells you how important the node is in terms of being part of a hub is this is this term called betweenness centrality. And betweenness centrality is part of betweenness centrality is a measure of the number of the shortest paths from all nodes to all other nodes that pass through a node of interest. So in this particular graph shown here, one can see that the blue nodes have the highest betweenness centrality because going from this red node to the next red node, if you pass through the blue node, you will sort of get the maximum number of lines going through and you can do this in any direction you want to, for instance. In contrast to the average path length, network diameter is sort of the as it says, is the longest pa, of the short path in a in a network that is the distance from the furthest node to the furthest node going through the center of the network. So one can see that by calculating path lengths, one can get overall view of how the network is organized. And for these many little kinds of topological networks, such as a ring, which which is also called a cycle or a feedback loop or a tree, where you cannot feedback at all represents various kinds of configuration a network can take. Another property of networks are what are called small world characteristics. Small World Networks are those in which one can get from any node to any other node with a small number of steps. In a classic paper published by Watts and Strogatz in 1998, they showed that most real networks are Small World Networks. And the configuration of Small World Networks is very nicely illustrated in this cartoon taken from their paper. It shows that in addition to co co, connectivity with its neighbors, that is, direct connectivity between node nodes that might be distally located and this kind of excess direct connectivity allows for this small world characteristic to be manifested. The connectivity, the between nodes in a certain region of a network can be measured by a metric called the clustering co-efficient, which is a local property that measures the density of connectivity within the network. And Small World Networks are very densely connected. The cartoon shown below here illustrates how clustering coefficients may be calculated. Consider the central black node that has four neighboring nodes. And for these four neighboring nodes, only two of the connections possible edges are connected. There can be another four edges that are not operational. And so to calculate the clustering coefficient around the black node, one would consider the two operational edges versus the total of six possible edges, leading to a ratio of 0.33. Clustering coefficients are very useful metrics in understanding how densely a network is connected within regions of the network, a region's subgraph or subnetwork, and as a network as a whole, and is often a property that people consider in understanding how modules, functional modules might exist within networks. So these kinds of properties such as clustering coefficient so, and degree distribution and others can be broadly classified into two groups, global network properties or local network properties. And global network properties describe the network as a whole. And one can call a network either cyclic or acyclic depending on the presence or absence of loops. A network can be a bipartite graph, which is often useful in understanding relationship between its two known overlapping sets of nodes, which is drugs and drug targets. Directed graphs, and we'll talk about that in in greater detail the next lecture. Scale free network, as I showed you, which shows that the distribution of edges and nodes follow a power law. And, of course, robustness, which is the, depending on its topology, the network is particularly resistant to breakup after random ro removal of nodes. Local properties of network including cluster coefficient, describing how densely a particular region within a network is connected. One can also look at, for cliques, which are regions which are fully connected between nodes within the region. [SOUND]
