Analyzing Real-World Networks in Wolfram Language

Hello everyone. Just checking you can hear me. Yeah, welcome. Welcome to this webinar on networks and graphs, real world networks in the Wolfram language. So I know some of you are watching on YouTube, some of you are watching on Big Marker. Those of you who are watching on Big Marker should be able to download the files and actually follow along with me. So if you go to the chat panel and click the link for notebook access, you can download the notebook. And you should, once you've unzipped, you should get a file structure. A bit like this. Okay, so this, this has the notebook I'm working in this analyzing real world networks as well as the additional files you'll need to import. We also have this notebook bonus content which has some extra information on real world networks if we have time to get onto that. Okay, so someone is saying the video is turning on and off. So I'm just going to turn my camera off off and just see if, ask if there's any problems. Okay, can someone else just confirm how the video and audio quality is before I get started? If you're having problems, try leaving and re entering. Okay, someone said it looks fine on their end. Thank you very much, Christopher. All right, thank you everyone. That's really helpful. Okay, Yeah, sorry about this, but it's always good to check. Okay, so this will take approximately 1 hour 30 minutes and I'll go over the, the overview of the talk now. So I'm going to start with a couple of introductions, definitions of basic things you want in. In graph theory that you want to know, you ought to know before moving on to anything more complicated. Okay. Then we'll move on to basic measurements of graphs such as graph density and reciprocity, and will investigate communities with various definitions on how we define a community, that kind of thing. Okay. Some of the bullet points here are not actually touched on in this webinar. They, they can be explored in the Wolfram language and I'd encourage you to look at them such as assortativity and homophily, different kinds of centralities which we'll touch on. But yeah, this, it's an inexhaustive look at real world networks. Okay. I'm actually delivering a talk on graphs and Networks on 26 July, which is a more, more of a from the basics introduction. So I suppose the order of these webinars is somewhat unfortunate, but I want to focus on the real world aspect of networks in this webinar. Okay. So there will be some, some concepts that I go through slightly quickly. And if you want to know more about the basics of graphs and networks in the Wolfram language, I'd encourage you to come to this webinar on the 26th of July. Okay? But for now, we are looking at real world networks. Okay, so I've started with some definitions. Here we've got definition of a graph. And next to a lot of these definitions, I've just coded up and just saved the image of the corresponding graph that's been defined. So we have just a basic graph which is a set of vertices connected by edges. Okay. Sorry, everyone. All right, I'm back. Okay, we say that if an edge, so this line here connects to a vertex, then the edge is incident to the vertex and the vertex is an endpoint of that edge. Okay? Two vertices or nodes that are joined by the same edge are called adjacent. And we can create things like adjacency matrices which show this relationship in a network. Okay, We've got this example of a loop edge where this edge is in a sense connected to itself. Multiple edges mean there are multiple edges connecting two nodes. Okay? You can, you can go from this node to this node via this edge or via that one. These are called multiple or parallel edges. Okay, We've got different definitions of, of the different types of graphs. So simple graphs, connected graphs. An important one here is a directed graph where edges may only be traversed in one direction. So that's indicated by these arrows on the graphs. Okay. It's very simple to create a graph in the Wolfram language. I won't spend too much time on this as, as I said. But as an example, let's take this directed graph. So this is just a list of vertex connections where we say one goes to two and two say goes to three. Okay, so we just kind of build this, this graph, Last one. And I'll show you what happens when I just remove these vertices. As you can see, we've reproduced this. Let's see what happens where we don't have a directed edge. So in order to create that, we just press escape UE for undirected edge and then escape again. So this connection between 2 and 4 won't have an arrow. Okay. So actually reinterprets changes the shape of the graph as well. But as you can see, this edge on the right doesn't have an arrow anymore. Okay. We can also just completely take out one of the edges and see what happens to the shape of the graph. I encourage you to try this out for yourself. Okay. Another important definition, the degree of a vertex is the number of edges that are incident to that vertex. Okay, so you have, if you have one vertex with a significantly higher degree than another vertex, then that might tell you some interesting things about your graph. You may start to glean some information from it. Okay, also got the definition of a tree and a spanning tree here. So this function find spanning tree is built into the Wolfram language and. This just shows that you can explore your graph. You can use these built in functions to either generate graphs or find these little aspects of the graph, such as a spanning tree. Okay, Yes. So an inexhaustive list of these useful definitions. And as you can see, it took a very small amount of Wolfram language code to generate them. So I want to, I want to talk about what a, what a graph actually is, what it can represent. So an example would be a Facebook friendship. So let's say an edge represents a Facebook friendship between two accounts which are the vertices of the graph. Okay, this is quite a basic example, but you can generate graphs for all kinds of situations and I hope to explore some of those today. On that note, on a directed graph, for example, you might have in some graphs that relations aren't always reciprocated. So Twitter account A might follow account B, but account B might not follow A or account B might not follow anyone at all, in which case it's would be like A, maybe an isolated point. With no edges outgoing from it. Okay, also got the definition of a complete graph here, denoted kn. And I just want to show you how we can generate these complete graphs in, in Mathematica and we can actually animate the result. So this is going from 1 to 30, showing the complete graph with it I nodes. Okay, stop this. I wanted to talk about weighted graphs as well. So let me just run this code. I can. The code is not as important for this because I just want to show you the actual graph. This is a way of adding additional information to your graph. So you can annotate the nodes with numbers or names. You can also annotate the edges. Okay, so for example, the nodes could represent cities and the edges might be the price, the cheapest price of an airplane ticket between your cities or something like that. Or it might be some measurement of engagement between social media accounts, something like that. Okay. When you decorate the graph in this way, you've added this additional information. You have what's called a network. And as you can see, it's defined here. If we want to glean information from this network, we're doing network analysis. Okay. And you can. This is, this is, this is carried out with the Wolfram language at an academic level quite extensively. So my next point is to look at how we can find different types of graphs and networks using the Wolfram languages, repositories, that kind of thing. Okay, so if we just use this graph data all function and then find the length, we can see that there's around 12 and a half thousand different types of graph data. And let's just make a random choice of these. We have this strongly regular graph or lots of these names of graphs that are used by graph theorists. Okay, we can, you can explore this. So these, these graphs that kind of have these strict definitions and names attached to them. Now, because we're looking at real world networks, these graphs maybe not as useful to us, they might be useful to a mathematician. However, more appropriate for today's webinar is the example data network graphs. Okay, so we have 228 example networks we can call upon. And if I make a random choice here, you can see the different examples of networks that we have. Okay. Condensed matter collaborations in 2003, for example. And then. This is the first example of us using or importing an external file. So this is, this is a file that should have come in the handout you downloaded. If you're watching on big marker. Okay, I can just import this with a dot call extension. Okay. And then I can just plot the result. I can actually plot it in 3D because it's easier to explore and show the information that way. And I can actually interact with the graph and move it around. Okay, so there are ways we can, we can find built in data or use external data and we'll be doing a mixture of the two things today. Okay, I hope that sounds interesting to you and I'm intrigued to know how you might use these kind of network analysis tools in the Wolfram language in your own work, whether you're studying or you're working in your jobs in industry or you have university modules on this kind of thing. Yeah, I'd be keen to know. And I'm also keen to know where in the world people are tuning in from today as I sit in this small village outside of Oxford in the uk. Yes, it's a pleasure to present to all of you and I'll just check for questions. So Jack said, is all the diagramming standardized outside Wolfram as it is inside? Does this mean if you are exporting the graph to be used elsewhere? I'm not quite sure. The diagramming is the Wolfram standard. Take this graph for example. We can generate it with code, but then I can also copy it and then it's just like a graphics object. If I then wanted to use in another interface, I could. Not sure if that's what you mean, but. Okay. We might revisit these definitions if and when we need to over the course of the the webinar. And if you have any questions, please don't hesitate to answer, answer, ask, will try and answer them. Okay, So to start, I want to go over the ways we can generate graphs. We've looked at how we can create them ourselves, very basic ones, and how we can find them. However, you can create new graphs by these random processes. And the most common ways to do this are using uniform graph distribution and the Bernoulli graph distribution or otherwise known as Erdos Reni graphs. Okay, so we'll look at these examples one by one. The first one is we make a random choice of graph from the entirety of graphs that have 60 nodes and this many edges. Okay, this is just a number. It's being found using the, the binomial function and then rounded down. But it is just a number. Okay, so we make this choice and we also check that it is a connected graph. Okay, that was in the definitions before. A connected graph is a graph where there is a path between every pair of distinct vertices. Okay, so for our purposes we want these graphs to be connected. So that's what this, this while function does here. Okay, so we can run this and here we go. So this graph has 60 nodes and this many ED. Okay, The second example here is, is this er graph. So Erdos Rainey graph. But we use the Bernoulli graph distribution to find it. So it's a slightly different way of generating it. I'll go over how, how it's generated. So you start with a complete graph. So 60 nodes and every node is correct is connected to every other node. Okay, so again to our definitions, the complete graph as we shown here. So increase this to 60. You can imagine it gets very crowded, but yes, an edge between every pair of distinct nodes. So that's what we start with in this Erdos rainy process. However, Then we have this coin. We have to flip with some weighted probability and if it lands on heads, then we include this, we include an edge. So we do that for each of the edges on a complete graph. So you end up with a very. Yes, you, you end up with a graph that is definitely not a complete graph. It's a graph with the number of edges according to the probability that you give the function here. So if I can just hover over the function. All right. Actually, I can go to the documentation. We have n vertex graphs with an edge probability P. This is the probability that that weighted coin lands on heads. Okay. And we do the same thing. We make sure it's connected. Run this. Okay. You could run it again if you want to show how it's slightly different each time. Cool. Okay, Now both of these types of graphs are very useful in, let's say, like mathematical proofs or something like that, because all nodes are treated equally as it says here. So maybe if you were a mathematician, you'd say let V be a node of this graph and then it doesn't matter which node you consider because they're all treated equally. Okay. And this is not as useful to us because we're working with real world networks where, well, to give an example, celebrity social media account cannot be treated as equal to any given account. So what we move on to next is some graph distributions that are more realistic for the network analysis that we're going to do. As an example of how, Well, unrealistic the these kind of graphs are, we can plot a smooth histogram of the degrees of the vertex, so how many edges are incident to a node and we can see that they're normally distributed. Okay, so this will vary slightly depending on our random choice, but you will get a very similar distribution here. Okay. And the more realistic distributions are they lead to what are called scale free graphs. Okay. With the goal here being to break the symmetry between nodes so some nodes you can no longer treat as equal to others. Okay, so we have a situation here. You know, on the topic of social media networks that I've been discussing so far, assume that when someone joins a social network, they are more likely to follow someone who already has more followers. We can model this process by this Barabasi Albert graph distribution, also known as the rich get richer distribution. Okay, I want to talk through a bit about what this means. Okay, so again, it's like the process is like the Bernoulli case, where we have steps, and at each step here, a vertex with three edges in this case is added. Okay. Ultimately we get 60 vertices, 60 nodes, but at each step, three edges are added. Okay, you can see the, the drop down for the function here. The arguments are N and K for n vertex graphs where a new vertex with k edges is added at each step. Okay, now the way in which the edges are added is really important here because the edges are attached to vertices at random, but they follow a distribution that's proportional to the vertex degree. So if a vertex already has a high degree, it's more likely to obtain additional edges at each step. Okay, I hope that makes sense. And I'll show you. So it's not just my words. So you might be able to see certain nodes that just have a much higher degree than others. And maybe, you know, increasing this number will start to like exemplify this result. Okay, so we, we have maybe an even larger discrepancy between the higher degree vertices and the lower degree vertices. Okay. And you can play around with this yourself if you are following along in Mathematica. I'll go back to three for now for the rest of this. Okay. Hence the, the rich get richer distribution that this is. This is been called. Okay, and remember how the histogram we plotted last time showed normal distribution? Well, here the distribution of the vertex degrees falls off rapidly. So there are a large number with a small degree and then a smaller and smaller proportion with. With a high degree. Okay, so this is like the minority of social media accounts with hundreds of millions of followers. And it can be shown actually that the fraction of nodes with a degree is. Follows an inverse polynomial. So it follows a power law. Okay, so this, this is not normally distributed at all. It falls off via a power law that I'm sure with a bit of, a bit more use of the Wolfram language and a bit more analysis of this, you could find out what that relationship actually is for your network. Okay, so there's lots of kind of exercises left to the reader in this, in this webinar. Yeah. So if you do have a license and you can, you can keep the notebook, you can analyze these things further. And hopefully what I get onto at the end about how simple it is to go from just downloading a data set that represents a network and then visualizing it, you'll be encouraged to explore these things a bit further. Okay, so someone asks, could you explain again the difference between Bernoulli and uniform graph distribution? So, yeah, I'll just go back to this slide. So there are finitely many graphs with 60 nodes and this many edges. Okay, I'm just going to evaluate this so I don't keep saying this many. Okay. 126. So due to the nature of graph theory and you can't, you just can't have an infinite number of. Graphs that are showing the same information because you'll get to a certain point where the, The connections between nodes will be the same. Okay, so what, what we're doing is selecting from a distribution that's entire. That's all different. But all is showing the same kind of raw information of what's important in a graph, such like which is the nodes and the edges. Okay, so all we're doing here is selecting from this, this list for the uniform case. Okay. For the Bernoulli graph distribution, we are starting with a complete graph. And then for each edge we're flipping this coin, deciding whether to include or exclude that edge. So to emphasize what I mean here we're actually starting with this graph. As I said before, it's very crowded, but there is still some semblance of a graph. Here we're starting with this and going through each edge and deciding whether to include it with a probability of 1 over 14. This is why that this graph has far fewer edges than this graph. Okay, Just look at this a second. So here I've just decreased the probability and as you can see that the graph becomes less dense, shall we say? And graph density is a, is a measure that we'll explore in a couple of slides. But this is hopefully explaining what the Bernoulli graph distribution or selecting from that distribution is actually doing. So I hope that explains it. Increasing it to 0.8 here is clearly a lot more than 1 over 14. We have a much denser graph. We have a much higher probability of keeping an edge. Okay, so thank you for your question. Okay, so the next thing we're going to look at is a network that crops up a couple of times in this talk. It's quite a famous network in network analysis. And it's. It's Zachary's Karate Club. Okay. That's the name. It comes from a paper written about graph theory and it's become quite a popular way of. It's become quite a popular example in showing like community structures in networks. And this is available in the Wolfram data repository. As you can see here. I just collect it setting Zach equal to the example data network graph specified by this. You can peruse the Wikipedia page if you like. Goes into the history of it a bit and yeah, if you're curious. Okay, so we can just load these things and then we, we want to, we want to explore some, some metrics associated with this network. So I mentioned density before. So graph density gives you an idea of, of how social the network is. Okay, so if I go on the documentation of graph density here, The ratio of the number of edges divided by the number of edges of a complete graph with the same number of vertices. Okay, So a complete graph will have a graph density of 1. This graph has a density of around 14 of 14% 0.14. Okay, just to show that point, I'll do graph density of complete graph. Let's say number six, we get one. Okay, so hopefully that explains what graph density is. And now clearly with a fixed graph, the graph density isn't going to change. However, suppose some drama plays out over time and I've got a section here which is the drama. So it's just a kind of randomized evolution, let's say of the graph where certain nodes are no longer connected to one another, that kind of thing. The actual content of the code is not that important. So I can just close it away here. But I do have the useful thing, useful information contained within Zach list and I can use list animate to actually show this. So just look out for the edges that are there one second and gone the next. Okay. Okay. So what does this mean? I suppose I've just called it Zachary's Karate Club. But I should talk about what, what this actually is. So it was a karate club at a university with 34 members. And the edges represent these links between the pairs of members who interacted in a certain way. I'm not sure the details of this any any further, but that there was some events that happened which explore. Which we'll explore towards the end of the webinar. But yeah, so that's, that's what the, the edges and nodes represent. So you can infer what the, this evolution represents. Now I've got a line of text here that says you could track the social health of a karate club over time if you, if you measure social health by the number of connections in the, in the network. So how dense, how socially cohesive it is. And you can plot this. So according to this evolution that we've defined here, that's not necessarily what really happened, but my just simple code here which simulates some drama. So it uses this edge delete function to delete a random sample of the edges. Okay. The social health or the graph density as a proxy for social health is declining. Okay, so hopefully we're, we're getting into the real world aspect of these networks a bit. I don't want to lose sight of that because this is about real world networks after all. Okay, some more examples of real world networks. Well, we can just take from the example data and we're going to look at a metric called reciprocity here. So this is the fraction of edges that are reciprocated, the number of two cycles. So I'm just going to show the the documentation, again, it's defining a two cycle as something like this. Okay, this node goes to this node and this node goes back. Okay, and we can just use graph reciprocity to work this out and it gives, it returns a number between 0 and 1. Okay, so let's, let's find the graph reciprocity of Euclid's elements or the axioms, the things that Euclid was able to prove with his axioms. So before I run this, I'm intrigued to see if anyone has any thoughts onto what this might be. Why don't I run, I'll show the actual graph first. So if you know anything about Euclid's elements, it's this fundamental set of volumes of textbooks in, in Euclidean geometry, starting from a couple of axioms and, and then going on to proving very many. So reciprocity. This graph, having any reciprocity at all would imply this axiom is used to prove this axiom and vice versa, which doesn't really make any sense in the context of, of like geometric proofs. Otherwise your logic is just circular. Okay, so. If I actually run this, we get zero. And this is to be expected for this, this graph, because if something proves something, you can't then use the thing that it proved to prove what proved it. Hopefully that that's clear to everyone. Okay, this, this next graph is a, is a network graph on citations between complexity theory papers. Okay, so this kind of gives away what I posed as a question for the Euclid example, you might think this. If you write a paper, you will have cited lots of people in that paper, the people that you've cited in their own papers. Can their papers cite your paper? Well, you wouldn't think so. And it's that edge case where if their papers are updated, they might actually cite a paper that was published in the future from the point of view of their original release. Okay, so we're expecting a small value for graph reciprocity here, but a non 01. As you can see, we get around 3%. So in this particular field, wherever these papers are collated from, you have like a 3% chance of a paper being updated and citing, citing a paper that cited it. Okay, and then we have another network graph of, of Pearl. So Perl is a programming language, And then this is authors of a, of a particular Pearl of various Perl modules. Here's the description. And this is actually a weighted graph that I mentioned before, where the number of modules where you have this like, collaboration, I suppose, work out the reciprocity Here we get slightly higher and then finally we work out the graph reciprocity of word adjacencies. So if you're not sure what this actually means, then we can use the the same code as above and find the long description. Okay. Adjacency network of common adjectives and nouns in the novel David Copperfield by Charles Dickens. Okay. Vertex property contains a word class. So. I suppose we should plot the graph. Now we've seen the description. I'm intrigued to know what this looks like. Okay, so as you can see, There isn't a direction here, but the reciprocity. If I run this, you actually find that it's one. So there is what's called a two cycle between every pair of vertices in this graph. Okay. That it might just be that the, like the connection between these two vertices, for example, is two way. Okay, I'm just going to check for questions, but I don't think we have any right now. Okay, so the next slide is all about finding what are called cliques. Okay, so here's the definition. A clique in a graph is a set of vertices that are all connected to each other. And it's the kind of strictest definition of a community. And we'll go on to slightly looser definitions of community in the, in the following slides. So I just going to run this. It's kind of a repurposed network that was chosen randomly from the repository and we've just turned it into a friend network. Okay, so this just indicates friendships between students at a school, let's say. And we want to explore this graph and identify cliques in it. Now this first piece of code here, it's not actually finding a clique because we have a function to do that. It's the find clique function. It's just trying to get a sense of, I suppose, organization in this graph. And what you do is you find a spanning tree rooted at a specific node. So we've just chosen the node labeled by Olivia and we're going to find a spanning tree and then plot it. Okay, so we have Olivia at the root here connected to Ava and Ling. And then as you can see, this does connect everyone on the, on the original graph. It just removes a lot of the, the edges. And a spanning tree was defined in the earlier slides. If you have the notebook and want to go back to that. Okay, so let's move on to the cliques. So we want to use these functions maximal by and find clique to find the longest cliques because they all correspond to the cliques we're interested in. So these are cliques of maximum length. Okay, so here's it finds three of them. So we have a clique between Maria, Fatima, Guy, Abigail, Elvis, around here. Okay, and then these two. Now looking closely at these, you might notice these only differ by one person. So we have Noah in this one and John in this one. But the rest of the nodes are actually the same. So let's visualize these cliques. Okay, the yellow, if I can make this bigger, you might notice the pink kind of design feature here, indicating it's a member of a clique is kind of bordered with this yellow, indicating that these are members of both cliques. Okay, no, it is not. And John isn't there in their own clique. But as we said with the overlap, these four are in. Are in both. Okay, so given that we have technically two cliques that are only different by one, and if that's our means of detecting a community, we might want to loosen the definition of community, for example, or a more forgiving definition as it's called. Okay, so communities correspond to something weaker than a clique usually. And we can just use the built in function community graph plot to visualize communities. So let's run this and it actually finds three, well clear communities at least community graph plot deems them to be clear. So just groups the nodes together and then draws this gray kind of contour around them. Okay, and then we can actually specify methods of community graph plot. Go into the documentation here, go in details and options. You can specify two methods. So these are the spring electrical method and the hierarchical method. Will see that in this case run them both here you get the same communities. Okay, these, these are the same graphs, just rearranged. However, there are graphs where changing the method might find different communities. So it's important to keep that in mind. Okay, so we saw community graph plot. There's also a function called find graph communities. And here we're going straight in with a method that we've chosen. So the modularity method attempts to maximize the weight of edges falling within a community, sometimes leading to what's called a disjoint community. So I'll run this to show what I mean. You might see, you might interpret this as disjoint because Alejandro here is, is in a sense disjointed from the other nodes deemed to be in a community with them. Okay, So this is one method of find graph communities here. If I click here, I see the. The close bracket ends the function. So it's. This method is just an option of find graph communities. You can run it on its own, actually. And it just gives us the communities in list form. And the highlight graph is just visualizing these lists. Okay. So let's look at another method now called clique percolation. So what this does is if two cliques differ by one element, it's considered part of the same community. So it's, it's less strict. Okay. What I want to show here is that perhaps there's a chance of, if you use this method, you. Okay. Two cliques only differ by one. So they are now one community which maybe only differs by one, but a different one to another clique. And then it's all the same community. And what you have, what is a. Is a risk of every. The whole network being part of one community. Okay. And this might be okay, but depending on your goals and your reason for doing this network analysis, you might want like a moral. More resolution in your communities. Okay. And we can actually go back to this Zachary Karate network. And we see that the same method, clique percolation, doesn't necessarily result in. In all of the communities. Well, doesn't result in the whole graph being one community. And also doesn't necessarily give disjoint communities. We have this node here that's in two communities, the one specified by the red and the yellow nodes. Yeah. So what we can deduce here is that these yellow and red communities were cliques that differed by more than one node. So they weren't merged. Okay. Yep. So it's kept these communities separate despite using this method. So it all depends on what's appropriate for your network of interest. Okay, so before we move on to this, what's called the friendship paradox, I'll just answer this question. How can I create a graph. If I have a list of people belonging in different groups? List of people belonging in different groups. Just trying to think about the structure of that network, if, if it makes sense to represent it as a network. Because what's good about graphs is it's the, the interaction between groups that's of interest to us. So perhaps if, if you just have a list of people belonging, different groups, then kind of like a tabular data structure might, might be more appropriate. But I'm intrigued to know if you can tell me any more about this and I might have some more ideas. And I've got examples to show at the end of this. It's actually in the bonus content notebook, which, which shows like different graph structures depending on your data. Okay, so the friendship paradox, Again, I've got a link to it here. You can, you can have a look at this yourself. I'll try and explain the paradox as the best I can. So has been called a paradox, like many things, because it kind of doesn't seem intuitive, but once you recognize it, you can, you kind of appreciate it and you start to notice it everywhere. And really it's a kind of consequence of being in the network that you're trying to observe, if that makes sense. So it's framed as why your friends have more friends than you. For example, if you are friends with someone, you are more likely to be friends with someone who they themselves have lots of friends. Therefore, the mean number of friends of your friends is going to be greater than your mean number of friends. So someone told me about an example they came across where they went to university and the lectures. They were told that the average number of people who attend a lecture is around 20. But then they went to a lecture and there was 100 people there. And they kept noticing this and, and what happened was because they themselves were going to the lecture, they were more likely to go to a lecture where there are more people. So the statistic of the mean number of people in a lecture is really only useful for the university to share to its students than the students attending the lectures. Yeah. So I'm going to try and just explore this very briefly here. We create or generate a random graph according to this distribution we saw before, where this is the rich get richer one. Okay, so we'll just call this graph G and then let's, let's calculate the mean degree of the graph. Okay, so what's the mean number of edges incident to a node? I just want to go into this. So like first we, we do vertex degree and we just get a list of all the degrees of the vertices. As you can see here, you've got some stark inequality with the minimum kind of being around three or four. One of these nodes has a, has a degree of 27. Okay, so we calculate the mean of these and it's around, it's 5.8. Okay, Now the next part we want to find the mean, mean degree of your neighbors. So this is that idea of, of the friends of your friends kind of thing. So I will show the documentation for neighborhood graph. So we have given it the arguments of the graph and the vertex. We kind of run through the vertex list. So this gives the graph neighborhood of a vertex V and the graph G. So we can run, get neighbors. And then, so that, that gives us the list of vertices represented the neighbors. And then we find the mean of this. So I'll just make sure that this is outputted so we can interpret it. So this get neighbors is, is really a function that we define here. And then that's used in get neighbors degree, Which is itself a function. Okay, so get mean neighbors degree. I believe someone's asked to explain the code for this. So no problem. So first we, we. Well, we'll start from the inside and kind of work outwards. So we use this get neighbors function on an argument represented by this slot here. So this defines a pure function where this hash key is, is the argument to the function. And this ampersand essentially tells you that everything that came before it is the pure function. Okay. Yeah. And this get neighbors is in the part specification. So this, this kind of double square bracket here and here shows that we want that part of the vertex degree of the graph G. Okay, so I'll give you an example. The first part of this is just the number 27. It's the first element. The last part is just three. Okay. Remove this entirely and you'll see where I got these from. Just the first and the last part. Okay, so we, we find the mean of this and got 5.8. We write a function that gets the neighbors of a given vertex. And then we, we write a function that gets the mean degree of the neighbors of a given vertex. Okay. All right. And then we, we want to apply this function to the vertex list using this map here and then find the mean. So I'll, I'll evaluate this in place just to kind of see what we're finding the mean of. So these are all of our, these are all of our mean degrees of neighbors. And then we want the mean of this. Okay, so finally we can run this and we actually get 9.19. So compare this to 5.8. It's. It's actually a much, much bigger. So this is. I've run this before with, with different random graphs, and it hasn't been this high. So I can run it again just getting a new graph G gone through the same procedure. Okay. Already you're noticing one of the. The highest degree node is now 19 instead of 27. Okay. Mean is still 5.8. To find these. These won't have changed. These are slightly different. And this is now 8.37. Okay, so still higher than 5.8. As expected for the paradox to remain a paradox. But yeah, and what's important to note here is that this difference, this perceived paradox will hold for all graphs, as long as there's some variation in the degree of the vertices. So it's not just because I use this richer, get rich get richer distribution. It's just a useful way to show it. But, yeah, this is, this is always true. And thank you, Frederick. Thank you for your question. Yeah, pure functions are sometimes difficult to understand if you haven't had much exposure to them before. So I'm always happy to explain, explain the code in these webinars. Okay, Right now, I believe what's next is some analysis of the centrality of a graph. Okay, we're just going to show the Zachary Karate graph again and then give you a hint of this idea of centrality. There's, there's a lot more I could talk about on the point of centrality here, but I'm going to keep it short for this webinar. So I'm going to define a function here called show centrality, which. Highlighter graph uses this function highlight graph. It needs a graph as the argument. It needs a vertex list. It uses the vertex list of that graph. However, what's important is this, it rescales the graph according to this C fun, which corresponds to centrality function. Okay, now this, this allows us to use one of the many centrality functions for exploring graphs in the Wolfram language. Here's what I mean. If I use this question mark, system backtick, asterisk, centrality, I can get all of the system functions that feature the word centrality. Okay? As you can see, there's a lot. I'm not going to be able to go into them all, but one thing we'll use here is degree centrality. Okay, so this, what this does. Well, gives a list of vertex degrees for the vertices in the underlying simple graph of G. So if you go back to the definitions, you remember I used simple graph as one of the definitions. Graph with no loop edges or multiple edges. Okay, so we kind of get the underlying simple graph of the overlying complicated graph. And then what the highlight graph is really useful for doing is kind of showing these, Showing these important or central, you might say nodes as larger, perhaps. So in this very simple network, you know, Anna is very well connected with the, with the rest of the people. Whereas as we can see, Nora is only connected to Rose, Larry, and, and Anna herself. So that's why Anna's node here is, is exaggerated. Okay, so we can use this on the Zachary Karate Club network. And you can see that these nodes with higher degree are exaggerated. And it, it kind of makes sense. Why you might call These central nodes. Okay? But the main point here is that this degree centrality is quite simple to calculate and visually it makes sense. However, it's a local measurement of the degree of a particular vertex. So if something else happens in the graph, the degree centrality measure doesn't necessarily know about it. That's what all these other measures of centrality explore. Okay. And the documentation for these is, is very rigorous and you can have a look yourselves. Okay. So the next thing to move on to is the flow networks, which those of you who are watching on YouTube. This was promised in the YouTube description. So I will talk about it now after a brief introduction to what is flow through a network. Okay, we have these built in functions. Find maximum flow, optimum flow data, Find minimum cost flow. We're going to use these to essentially see how much stuff, be it water information you can push through your network. So push through the edges of your network to the nodes. Okay. The most common way to view this is water through like a pipe system. Okay. So first we're going to look at maximum flow without capacities. What I mean by this is the edges don't have different capacities, so these edges here just have capacity. One think of it as they're all pipes with the same diameter. Okay? So we've defined this very simple network. Don't pay too much attention to the nodes here. They're just kind of labeled numerically. And we have a source and a sink here. So the idea is to get as much water from source to sink. And we use this find maximum flow function. Okay, we get a flow value of 3, but we can explore the properties of this max flow to actually, you know, extract this value and show the, show the actual flow through the network. Okay, so here we can send one unit of water through there, there and there. And we have the edges to kind of push this water through the rest of the network. All right, let me just change this network a bit so you can see what happens. So I've just deleted the edge between three and five and let me delete the edge between two and five as well. Okay, so we've, we've kind of prevented or blocked two pipes. And then we run the same functions. Our flow value is now 2. Okay, same thing as you can see, if we were to send water along this edge, it would go along this edge, but then there's two units of water trying to go into a pipe that can only, only has the capacity for one unit. So that's why in this flow graph we just don't send any Water along this, along this pipe edge. Okay, yeah, hopefully that explains things and we can move on to an example where we do have capacities of the edges. And this example is using a railway network of the Western Soviet Union and Eastern European countries in the 50s. Okay, so this is just a graphics object, but we can define it as something useful to be used in Mathematica railway image. So this, this shows these origins which we can think of as sources here and then these kind of sinks which are the end, the target destination, let's say of these railways. Now the edges, as you can see here, you can see Here, it's number 12. This is, these are labeled with some quantity of thousands of tons of, of something that can be transferred, transported along those railway lines per unit time. Okay, so what we want to do is convert this image to a graph. And this is a bit of a tedious process and luckily it's been done for us. So we have railway graph which is shown here with the exact same information. We can actually overlay it onto the image with the sinks indicated in red here, 40 and 44, and these sources indicated in green. So these nodes here are our sources. We can find the maximum flow through this. So this find maximum flow just needs a graph. It needs you to specify the sources and specify the sinks and we obtain a maximum flow value of 163 thousands of tons per day or something like that. So as you can see, not much code for us to do. Once you have it in a graph format. Okay. Perhaps some image processing technology will come along where this is a lot easier than doing it manually. But yeah, so we've seen how to take a real world network, in this case a railway transporting goods, find the maximum flow through that network using built in Wolfram language functions. Considering you could perform this fine maximum flow algorithm yourself with a pen and paper. But you know, in this day and age with this technology available, it's almost unthinkable that you'd spend that time doing that when there's functions like find maximum flow. Okay, so we've, we've run an optimization algorithm, you could say. Now the other side of this is what's called the minimum cut theorem. So this is kind of abstracted and said. Say you want to disconnect the green node sources from the red node sinks at minimum cost. Now maybe an opposing army or something would want to sever the network so that the sources and the sinks are completely separate, halting the delivery of goods, that kind of thing. Okay, this is called a cut through a network. Okay. And the mathematical function corresponding to this is find edge cut, I. E. The cut through edges. Okay, now the thing about find edge cut is if we look on the drop down here, we need to specify a source and a sink, S and T. But we have multiple sources and multiple sinks. Okay, so we can do this. We can see our edges. We have to cut through and there's only three of them. And. Okay, that's interesting. We need to look at the graph to see where those three are. As you can see, it's just here, this, this might be, This might be a smallest minimum cut, for example. But we have other sources to contend with. Now the way we get around this is by specifying a super source and a super sync. Now anyone who's, who's studied these kind of networks before might be aware of this method. If you're not, it's quite simple and I hope to visualize it nicely. Here we kind of update the railway graph with one super source which has edges connected to all the sources, and a super sink which has edges connected to all the sinks. Now these edges, what are their capacities? Well, in order for them not to be included in the minimum cut, we define their capacities to be infinite. Okay, so there's our super sync, here's our super source, and then we just perform find edge cut on this graph. As you can see that they're labeled with infinite capacity here. Okay. So it's a little hard to see. You know, you could go into the code here and probably specify some design changes here. They're just indicated in red. So the cut is through the edges. 30, 17, 36, 16, 24, 6, 10, 5, 19. Sorry, I've just read out the capacities there. What actually defines the edge is the connection between nodes. So between 28, 37, 29, 37, etc. Okay, that's our minimum cut. Okay, this is, this is taking the least amount of energy resources, let's say, to separate completely the sources from the sinks. Okay. And visualize nicely. So yeah, hopefully that. It's another kind of optimization problem. Okay, and, and I'm sure you could find other networks where you could perform the same kind of analysis where you've got multiple sources and sinks. Okay, I have only got 10 minutes left, so. And there are some things I wanted to show. Okay, so this Zachary Karate network, it's cropped up again. We can use a similar kind of reasoning to explore what happens when, let's say there's, there's some dispute between two pseudonyms who are part of this network. Go by Mr. High and John A. So that the their nodes are indicated here. Okay, so if there's a pay dispute between these two people, the club will vision it will tear apart go into two different parties. Now if we assume that people tend to follow their friends, this vision will hopefully destroy as few friendships as possible such that we get two kind of separate karate clubs. Okay, now I know I've gone through that quite quickly, but the point is that this can be modeled as a minimum cut problem where we actually only have a. We don't need to do the super source and super sync method because we only have these two nodes. So here are kind of new graphs separated from the first. Okay, we can, this is just as determining which nodes are in these two separated groups separated there each their own graph at this point. And this graph here is just something I manually found and inputted. This is the actual group that formed around Mr. High. Okay, this is the real data and we've just performed a kind of naive cut to simulate this vision. But we can actually find the difference between what we did and the what really happened in this karate club. So this symmetric difference does that and we just get this output of 3. Now what does that mean? It means that the only thing that isn't in this, that's in this is the node 3. So that's the only one that we got wrong essentially. So yeah, quite a powerful tool and approach. Okay, just in the last because I have to finish soon. I do welcome your questions if, if you just want to send them in, I can spend my time answering them. And while I'm waiting for those, I can show you this bonus content that's just using networks that I found trying to show like how simple it is to go from. Okay, there's a website which has network data such as this one. Okay, this is the email communication network from EU research institutions in like 2003 or something like that. Okay, I can import this because it's in our, in our downloaded files. I can process it so it's interpretable as a graph. So I'm just taking raw data and processing it and getting process data. And yeah, I can plot a graph. I'm only going to use the first 1000 entries, but already we can see communities in this graph. Okay, what's better is I can use graph 3D to play around with this and identify the communities. Easy, easily. So these might be individual universities. As you can see, we have a couple of stray academics here. Someone even emailing themselves. It looks like. Okay, someone has asked. Oh, I Think this is a question from YouTube. Would you happen to know how this scales performance wise with respect to network sizes and degrees of connectivity in Wolfram language? Is it suited beyond the exploratory part of an analysis? Okay, great question. In terms of how it scales, you'd have to go into like the functions and, and see if there's any, any information on the, the order or complexity side of things you can use. Is it absolute time, absolute timing? Sorry. Yes. This evaluates for expression and also returns how long it takes. So you can kind of start to do this piece by piece on your code of choice to see how long it's going to take. Yeah, that's probably all, all I can provide on that for now, I would say. Well, I want to clarify these tools are very suited for high level analysis of networks, really very much large networks as well. You know, functions like community graph plot for example, take a long time to run but that's really, that's kind of the nice visual side of things. That's not the, the deep analysis, the, the analytical side can be done on extremely large networks. Yeah, I hope that answers your question. And to top it off, I will show this community graph plot of this data. So it's clearly identified the communities of email exchanges in these institutions. And yeah, if you have this notebook yourselves you can go into the, the other examples that I've, I've written. There's an example here of, of someone's Facebook friend network before I think this is downloaded 10 years ago because now you actually can't get that information anymore possibly due to privacy laws. But this friend network is not mine, but it was identified by a colleague of mine who, who had his, his friends and, and randomized the names, anonymized the names, but could actually identify communities within his friendship groups on Facebook according to different parts of his life. So yeah, hopefully this is kind of self explanatory if you'd like to have a look at it yourselves. And you can explore things like centrality in these graphs as well as you can see an old friend's family, physics what either studied physics university, that kind of thing. Okay. And if there are no more questions, I can take you back to the main notebook where I've got some resources here. There are courses you can take on graphs and networks and talks that we have and the elementary introduction to the Wolfram language. I'd very much recommend that as well as a source of information. And yeah, we have a webinar on 16 July, quick start to Wolfram Tech. You can sign up for that if you follow this link. Yeah, thank you all for coming. I hope you enjoyed. Hope you found it useful and yeah, I wish you the best in your work or study of this kind of thing. Thank you all for attending. Hope you enjoyed. Please, for participants through picmarker, fill in the feedback survey that comes up at the end. Thank you. Have a great weekend.