Hi, this is Mat again. And now we're ready to start talking about how we can represent networks and talk about their properties. And in terms of simplifying the complexity that we're facing in describing networks we're going to think about different kinds of patterns that might be. So one is going to be that there's global patterns of networks. So overall big picture items. So, how are the different constructiveness of individuals distributed through the society? Are there some people who are really well connected and, and serve as hubs and other people who are not so well connected, or is everything very evenly distributed, so that's something. Path links. How far does it take to get on an average from one node to another. There's going to be segregation patterns, so if we begin to think of nodes as having characteristics, say if people's ages, their genders and so forth, do we see separations between nodes of different types. Or are things fairly well integrated. local patterns. do we see tight clusters of nodes that are all tightly connected to each other, cliques. Do we see that if I'm connected to somebody else and they're connected to a third person that I also tend to be connected to that third person. Transitivity. do relationships have friends in common? Are they supported? so we'll look at local patterns, little, you know, zooming in on particular parts. Well also talk about nodes positions in networks so how central is somebody, how influential are they, what does their neighborhood structure look like? So there will be different ways that we'll be talking about networks overall and we'll also be looking at nodes in positions in networks and other kinds of things so there's going to be a series of definitions that we have to go through to keep track of these things. So the basics in terms of representing networks in, there's going to be some set of nodes, vertices, players, depending on what literature you're looking at these will have different names. I might go back and forth between the names and the course. Sometimes I'll call them nodes, sometimes I'll call them agents, sometimes I'll call them players, vertices, etcetera. But there's, tend to be some finite number, little and will be our typical characterization of how many there are. And one basic way of representing a network is just by what's called the adjacency matrix. So it's going to be a matrix of zeroes and ones so an n by n matrix, and what it indicates is 2 nodes connected to each others. So gij equals 1 indicates a link or a tie or an edge between 2 nodes i and j. Now generally in less otherwise stated in the course we'll be dealing with ones which are not directed, so if i is connected to j, than j is connected to i. So if we're friends with each other, we're both friends it's a mutual relationship. Or if we're allies with each other, we're both allied to each other. It can't be that one country is ally to another, and not vice versa. So we'll tend to look at it that, that way and we'll tend to, to work generically with zeroes and ones as, as the structure of it. So there's either a relationship or not. But we could allow for directed networks. We could allow for weighted networks. so when we looked at the financial relationships, so the amount of debt that was held inside one country of the sovereign debt of another country. That's going to tend to be a directed network and it's going to be a weighted network. So it's going to have different intensities on things. when we think about an alternative notation it's going to be very useful for representing networks. Sometimes we'll just use instead of thinking of an adjacency matrix we'll think of, of representing a graph or network. By just listing all the relationships that are present. So a notation will, will have, is it will say that i and j is in g, if that means that there's a link between nodes i and j. So very simple, succinct notation will just keep track of the sets of links that are present and depending on whether these are ordered or not ordered they'll be directed or not directed. so a network is going to be a pair of a set of nodes. And either an adjacency matrix, or a list of all the links that are present depending on the particular context. Which was it's easiest to represent the network. Okay. so, basic definitions. 1 thing we're going to want to keep track of is, sort of. ways of navigating through a network, other known as walks or paths. a walk in a network from, say, node i1 to node, ik, is going to be a sequence of nodes. i2, i2, blah, blah, blah, through ik, and the sequence of links, i1 is connected to i2, i2 to i3, and so forth, ending up at k, such that each one of those links is in the network g, okay? So a walk in a network from one node to another is a sequence of links that take you from that first node to the last node. so [INAUDIBLE] often in, in this kind of setting it's just going to be convenient to represent it just as the corresponding sequence of nodes such that we know that each subsequence pair are connected in the network g. So in terms of a picture well before, before I go to a picture, let's also talk about paths, cycles and, and geodesics. So a walk is going to be some set of, of links, each connecting to another node but they can possibly cycle back on each other. A path is going to be a walk where each node is distinct. So we start at i1. We go to a new node, i2. Then we go to some node, i3, which is not in the previous sequence and so forth. Until, eventually, we reach ik. A cycle is going to be a walk where we end up back at the node that we started at. So the n node is the same as the starting node. one other term that's going to be very useful, geodesic. A geodesic is a shortest path between two nodes. And shortest means we just count how many links there are in that path and we want to find what's the fewest number of links we need to go from. Node say 1 to node 7. How many links do we need to get from one to another? So in terms of pictures here's a set of networks on 7 nodes and the first one represents a path and a walk. From node 1 to node 7, right? So we go from 1 to 2, 2 to 3, right? So we start 1 to 2, 2 to 3, 3 to 4, 4 to 5, 5 to 6, 6 to 7. Okay, so that's that's going to be a path which is also in this case, a walk. if we look at a walk that's not a path we could have from 1 to 2, 2 to 3, 3 to 4, 4 to 5, 5 back to 3, so now we've hit 3 twice and then gone to 7. So that's a walk that's not a path. And if we wanted the geodesic in this case from 1 to 7. Then the shortest path would actually have gone just 1, 3 to 7, right, so this is a path which is longer than a geodesic. When we look at cycles, 1 to 2, 2 to 3, 3 to 1, that's a cycle, it's also known as a simple cycle because it just, the only node that repeats itself is the first and last node. And a cycle and a walk, which is a more complicated one, is we could go from 1 to 2, 2 to 3, 3 to 4, 4 to 5, 5 back to 3, back to 1. We cycled, but we actually cycled through 3 and 1 in that case. So it's a more complicated cycle. So these are different terms, we'll talk about cycles as we go through. They're going to be important. Paths are going to be important. Walks are going to be important,. So these are distinct items in that works and it's going to be important to keep these definitions and this terminology in our heads as we go through. So if we want to count how many walks there are in a network. Let's look at a simple example here on 4 nodes. So this is the network we're looking at. So 1 is connected to to 2 and 4, 3 is connected just to 4, 4 is connected to everybody. So that is represented here, in this particular adjacency matrix. And generally, we're not going to have nodes connected to each other. So when we look at the diagonal, we'll have diagonal being 0's. there'll be some applications where it's going to be useful to have nodes connected to each other, or to themselves. For instance, if. If we're doing learning, I might be able to learn from myself that will be one application where we'll have non zero entries on the diagonal. But generally we're going to have situations where this will be the kind of, matrix we're looking at. Now if we square this matrix, so we raise it to the second power, so what we're looking at here is, so there's a relationship between 1 and 2 captured by this entry right here of a 1. And so that indicates that 1 is connected to 2. And so if we ask how many ways there are, how many walks of length 2 there are from i to j. Then, the, when we square the matrix, that actually gives us the answer of exactly how many walks there are of length 2 from node, whatever to whatever. So this is the number of walks of length 1. This is the number of walk, walks of length 2. If you take it to the 3rd power, you'll get the number of, of walks of length 3. And here it says that there's two different walks of going from node 1 to node 1. I could go up to 2 and then back. I could go to 4 and back, and you get that by looking, so why is the 2 coming out in this part of the matrix? When you multiply the matrix it says I could go from 1 to 2 and then 2 back to 1. So that gives us one entry. If I could go from 1 to 4, and then 4 back to 1, and when you multiply the matrix, it'll pick up the 1 times the 1 plus the 1 times the 1. It gives us a 2 in this particular entry. So when you multiply the matrix, it gives you how many walks of different path times. So now we've got you know path of length 2 from each node to each other node. so it's impossible to get from node 3 to node 4 in a walk of length 2. All the other ones you can get by actually except, and also from 4 to 3. But all the other ones are possible. And if we keep raising these to powers. Then we end up with you know, how many walks of length 3 from node i to node j? And so forth. And so this is a very useful thing to keep track of because it's going to help is in defining centrality, it's going to help us in keeping track of diffusion processes, and other kinds of things where we look at information moving subsequently from node to node in a network. Okay. So another thing that's going to be very important to keep track of in a, in a network is its component structure. What are its components, these are the connected sub graphs that make up a network. So we'll say that a network N, g is connected if there's a path between every two nodes. And a component of a network's going to be a maximally connected subgraph. What do we mean by a, a maximally connected subgraph? We're going to mean that the we look at a subgraph that's a subset of nodes and a subset of the, of the links in the, the network, so that we have those being, of course, bonding subsets of the original nodes and original set of links. We want this to be path connected. So from every node i in N prime, and every node g in g in N prime there exists a path in G prime connecting those 2. So this is a connected subgraph. And if we look at somebody, some node who's in N prime and any link in the original network then any link that we find in the original network if there's some node j at the end of it, then ij has to be in g prime as well. Okay. And so what does that, what does that mean? in terms of. A picture when we look at components then this part of the network is a component. But this part of the network is not a component. Why is it not a component? It doesn't satisfy that last part of a definition. Because we've got 5 in there, 5 is connected to 1 and yet we didn't include 1 in our, our little picture here. So we have to include that and, and so it's a maximally connected subgraph that would you have include 1, 4, 3 and 5. And it would have to include all the links there. So component is going to be a maximally connected subgraph. Another component here it would be 2, another component 6 and 10 together with air link And then, 7, 8 and 9 together with air links. So this is a network with four different components and we can keep track of those. So a simple concept that's going to be useful in understand how, again, diffusion works, learning, etcetera, in understanding how separate the network is in terms of different component structures. [BLANK_AUDIO] Okay, so that, that does it for this lecture. our next lecture is going to start looking at path lengths and diameters.
