EuroSciPy 2017: NetworkX
Seth, Mridul
This training session will introduce the basics of network theory and working with graphs using python and the NetworkX package. This will be a hands on tutorial and will require writing a lot of code snippets. The participants should be comfortable with basic python (loops, dictionaries, lists) and some(minimal) experience with working inside a jupyter notebook. Broadly the tutorial is divided into four parts: Part A (20 mins) - Basics of graph theory and various examples of networks in real life. - Introduction to the NetworkX API and various data structures Part B (30 mins) - Work with small synthetic networks (generated using random graph generators) to understand the structure of the network. - Analyse the network and study various properties of the network like centrality, connectivity, shortest paths, cliques. Part C (30 mins) - We'll use the various techniques we have learnt so far and model a network out of real world data like co-authorship network(-personal.umich.edu/~mejn/netdata/cond-mat-2005.zip) and study the structure and properties of this network. Part D (10 mins) - We'll work on some interesting problems like temporal networks and visualisation of networks. - We'll model the US Airport Network with respect to time and will try to make sense out of it. By the end of the tutorial everyone should be comfortable with hacking on the NetworkX API, modelling data as networks and basic analysis on networks using python.
 Okay, so before we start there are let's look at the structure of the tutorial. Like every notebook has two versions, one is exercise and the other one is lecture. So exercise is a more hands-on version, it's like you have to write code in the exercise one and if you are tired and so basically if you are feeling like this, so you know you can just go through the lecture with me and if you are in mood so you know you can go through the exercise notebooks and actually write code. So okay, is everyone set up? Any issues? Okay, so let's start network analysis with Python. So first question, what are networks? What is a graph? So like okay, so some issues with the, yeah. So a graph or a network is basically a way to symbolize link data. So like the red dots there are nodes or vertices and the lines joining them are known as edges or like links or anything like that. So what are some examples that we can think of? Like any real world network data, anyone? Yep, train station and the connections between them. Any other example? Yep, Facebook, Twitter, these are like social networks. Sorry? Yes, worldwide web. So these are a bunch of interesting examples. The first one is a transportation network. It's like if there is a flight between two airports, there's a link there. The second one is, I think it's like over the trade counters, derivative markets, some financial thing and it's like, it's a network of that and the third one is the Facebook's worldwide social network. Like it's the connections between all the friends on Facebook. So in this tutorial, first we'll go through network X. It's a Python package to do network analysis and model network data. Like a very quick intro to network X and the API of network X and then we look at three real world data sets and three real world applications of network analysis. So one of them is epidemics and spreading of diseases and how people die and speaking of death, then we'll talk about Game of Thrones and do a network analysis of Game of Thrones. And the third one is USA Put Dataset. So we'll try to figure out what's happening there. So let's start with an introduction to network X and graphs. Everyone has opened the first notebook, introduction one. If you want to code, you should open introduction notebook. So it's like pretty trivial API. It's like how to create a graph. It's like GNX graph and import network X is the usual way of importing it. And so add node will add and note to this graph object. And there are multiple types of graph objects. There is graph, the standard basic one. Then there is digraph, multidigraph and multigraph. So a digraph is directed graph, any examples of a directed real world graph. Anyone? So what's the difference between a directed graph and a graph? Does anyone know that? Yes. So if there is a connection between A to B in an undirected graph, that means there is a connection between B to A2, but that's not the case with a directed graph. So any examples of a directed graph, a real world example? Sorry? Yes, control flow, control flow diagrams and Twitter because if I follow Jennifer Lawrence, he doesn't follow me back. We know that. So just type. Yes, sir? Sorry? Yeah. NetworkX allows that, but the definition, it depends upon, it depends on the user. If you want to have a simple graph, shouldn't have loops, but NetworkX allows that. So there are different ways to add nodes, like you can use add node and add nodes from and how to access nodes, g.nodes. And people who are using NetworkX, NetworkX 2.0 will see node view and people who are using, if you do pip install NetworkX, it will, right now it will install the version 1.11 and that's okay, but this is the new one. So we have views now instead of basic list and dictionary representation. So we have a lot of generators in NetworkX. It's like a path graph is, it will give you a path between, it will map a path between 0, 1, 2, and 3. So there's an edge between 0 to 1, 1 to 2, and so on. And then, and one of the good things about nodes in NetworkX is it can be anything. It can be any hashable object. You can have integers, you can have strings, you can have tuples, you can even have another graph object as a node in graphs. So like if we do g.add node h, it will add the node, it will add the node graph h as a node. So like if you will see like there's a graph object in nodes now. So let's look at the second part of a network edges. So like as nodes really reveal, it's just add edge and you know, that's how it works. And you'll get an edge view if you do g.edges. And then you know how to calculate the number of nodes. So like there are different ways of doing that, there is an inbuilt method. You can calculate the length of the graph or you can calculate the length of the list that returns with g.nodes and g.edges. And just like you can add nodes, you can remove nodes from the graph. So like, you know, little bit of stuff. So okay, so let's start with something. So Eldos ReniGraph is basically a random graph model generator. Like if you do like, basically the first argument is the number of nodes you want. The second argument is the probability of having an edge for every node with another node. So it's like if you have a probability of 0.3 in 10 nodes, this is what the random graph, the Eldos ReniGraph generator will give you out. So like if we change the probability to like 0.1, you'll have a more sparse graph. And if you like make it 1, you'll have a complete graph. This is known as a complete graph that is like all nodes are connected to each other. And this is one of the ways to visualize the graph, the most obvious one to actually show how it looks like. And the other one is to use matrices to visualize a graph. So in this, sorry, so in this graph, the white spots show if there is an edge between node 0 and like 0 and there is no edge between 0 and 0 because there are no self loops in this graph right now. So if there is an edge between like 1 and 2, then it's white. So let's change a graph. Make it 0 point. So like you'll see the representation changes. And the interesting part of network analysis comes in when you can add weights and attributes to the edges and networks. So network X lets you do that too. Like you know, you can just pass in a parameter as weight and you know like whatever you want to. And to access nodes with the attributes we need to pass in the argument data is equal to true. And the G.nodes will just give you the nodes and G.nodes data true will give you the attribute to like we have added time in this previous cell. And network stores graphs in a dictionary underneath. So there are ways to access those graph dictionaries too. And it's basically a dictionary how you operate on a dictionary. So a quick warm up exercise. So we have created this graph and we have added edges from this list which is basically like the starting edge, the ending, the starting point, the ending point and like suppose like the price of a ticket between those two cities. So the exercise is to find the edge with the highest weight. A quick warm up exercise. And in that way you can run the committees who have stayed off the nodes may have adopted Let me know if anyone is done and tell me the answer to. Anyone can do it. Choose with the piece of code here. If you do g.edges. It will return you an edge data view of tuples of the first node, the second node and the attribute dictionary. If you pass just g.edges, you will get only the edges, not the attributes of the first node. Let's start to understand some dynamics of a network. Let's draw it out. When we have a network, we need to know which of these nodes do you think is an important node in a network. If I remove that node, it could break the structural integrity of the network. Which node do you think is that? How did you come to that answer? Any more guesses? One of the most naive ways of figuring it out is just calculating the neighbors of a node. That is called a degree of a node. The higher the number of neighbors, the more influential the node is in the network. As you pointed out, if we took out 7 in this network, it would break the network. There are different ways of approaching this problem, how to find the most important node in a network. There is no right way to do that. That way is called between a centrality that we have seen in some time. Let's first talk about degree centrality. Degree centrality is just a fancy name for a normalized degree of a node. You calculate the degree of the node and divide it by the total number of nodes it can connect to. That will be n minus 1, where n is the number of nodes in a network. Let's calculate the degree of this network. Degree centrality of this network is not the top of the first five. That's there. There are a lot of other methods like between a centrality, flow centrality, page rank. We will have a look at them. This is our first data set. This is the collaboration network of a general relativity group on the archive. If two people have published a paper together, then they have an edge between them and where nodes are the authors. If four people have published a paper together, there will be a complete graph between those four in the larger graph. Let's import that. Let's check out the number of nodes and number of edges in this network. There are 5200 authors in this network and around 49,500 links between them. Let's see what we can do with this. There are a lot of ways in networks to figure out what is the degree of a network. One of them is to just do the graph object and call the function degree on it and pass in the node. I just randomly chose 22504. It's an author in this network. It is connected to 33 other authors. Let's do other short exercises. In this exercise, we have to create a list of degree of node, like two tuples and find the node with maximum degree. Let me know the answer if anyone's done. Let's see what we can do. Let's see what we can do. It's one of the reasons for that is network is written in pure Python. It's pretty slow. It's more of a prototyping tool than working with large datasets. If you really want to work on large datasets, move away from networks or use something like iGraph or GraphTool. The core of iGraph and GraphTool is written in C++. I didn't get your question. Gefi is the best software for graph visualization according to me. It was never meant to be a visualization tool. Gefi is a standalone application. Anyone found the highest degree? We have an input method called degree. Let's check it out. That's the right answer. Let's have a look at the degree centrality of the author's graph. The key is the node and the value is the degree centrality of that node. Let's go to another exercise now. We have to plot the degree centrality of the author's graph. We have to plot the degree centrality of the author's graph. You should end up with something like this. It has a very heavy distribution. Let's take a D-tool and go back to Eldos and iGraph. Let's plot the degree centrality of Eldos and iGraph. This is a very different graph than what we got from our archive graph. As you can see, it peaks at around 0.30. We passed in the probability as 0.3. The probability of creating an edge between a node and every other node is 0.3. The degree centrality peaked at 0.3. It works for every value, not just 0.3. I can show you that. 0.7. As you can see, it follows a normal distribution when it's creating the graph. The problem with Eldos and iGraph is that it cannot model real-world data. When you don't have access to real-world data and you want to create a synthetic data set, you need something better than Eldos and iGraph. In 1999, Barabasi and Elbert came out with their Barabasi-Elbert random-graph generation model. When you look at this, the degree centrality matches. Let's plot both of them. It's more closer than the Eldos and iGraph than the Barabasi-Elbert graph. There is another called PowerLockLusterGraph. It's just a variant of Barabasi-Elbert graph and it also follows a similar distribution underneath. Let's come back and let's have a look at connected components of a graph. Let's create a random graph again. In this graph, you can see that we have three different components. If I am somewhere in 7 or 8, I cannot go to 1 or 4. This helps when you're planning to make a road network. If those are cities, you need to have a way to go from 7 to 6. You can't just keep them there. We have a way to calculate that and this is the connected components of the authors graph. As we can see, we have this one lone wolf here who doesn't like to work with anyone else and only publishes alone. Maybe something like that. A lot of people that work with each other don't collaborate a lot but majority of them, this is the biggest component of this graph. They collaborate with each other. Let's create subgraphs of this graph where every graph is a component. If you will see the length of the first graph in this, that's 4 and 5. Graphs is a list of graphs where every graph is a subgraph of our original authors graph and it's a component. If you try to find graphs, the 10th subcomponent, we have two components of this graph. Not exactly components but we have two cliques here and cliques are structures which have complete graphs as their subgraphs. There are three nodes on the left and six nodes on the right where six nodes form a complete graph and three nodes form a complete graph. Maybe you can infer something like those six people published a paper together and a person from that group published a paper together with these two people. Another important application is graph traversal. Suppose I have to go from 4 to 6. It's not possible. Finding shortest path in a network is one of the de facto things that you do when you start a network analysis. There are algorithms implemented in networks to do that. When you pass in a normal graph, it basically uses a BFS to solve that and if you pass with weights, it will use Dijkstra underneath. You don't need to worry about that if you don't know what it is. It will just give you out the picture. Let's move on to another exercise. How many of you have heard about six degrees of separation? Can anyone tell me that? Anyone? I can reach anyone in this world by just jumping six steps of friendship and connection. The number of L-dOS is given to co-authors of L-dOS. If you have published a paper with L-dOS, you get the number 2. If you have published a paper with someone who has worked with a person, you get the number 2. Let's find the 22504 number of this authors graph. If there is no connection, that means that the author is not in the bigger subcomponent of authors graph, then you can give it the number minus 1 and then plot the histogram of this. Let's find the 22504 number of this authors graph. Let's find the 22504 number of this authors graph. Let's find the 22504 number of this authors graph. Let's find the 22504 number of this authors graph. Let's find the 22504 number of this authors graph. Let's find the 22504 number of this authors graph. Let's find the 22504 number of this authors graph. Let's find the 22504 number of this authors graph. Let's find the 22504 number of this authors graph. Let's find the 22504 number of this authors graph. This is one of the ways of doing it. There are probably more and better ways of doing this too. This is how I did it. If you ignore the minus 1 bar, you can see that this is peaking at around 6. I'm not saying that this will prove that theory, but maybe this is something interesting. This is just for one node in the network. If you find the average shortest path from this node, it comes out to be 5.61, which is less than 6. This doesn't prove that theory, but it's just a thing we can think about. Facebook actually tried doing this and ran it on their full friendship network. Can anyone guess what was the degree of that? What did they find? They found it's 3.5. This is their distribution. It's speaking at 3.5, speaking at 3.4. Earlier, you could be able to see your own degree or degree of separation too, but they have removed it. Mark Zuckerberg has 3.17. It means that in three steps, Mark Zuckerberg can reach any person on Facebook. Three friendship steps. I had a degree of 3.94 or something. Let's get back. Let's talk a little bit about directed graphs. Does anyone know this visualization? What does it represent? This is the representation of the PageRank algorithm, which was named after Larry Page, the person who made Google, co-founder of Google. This is what early version of Google used to index the web. As you can see, this fellow C here, it only has one incoming connection, but still the importance of this in this network is pretty high. As compared to B, which has a lot of incoming connection, that makes sense because a lot of people are citing B whenever they are talking about anything. B has a high influence on this network, but C has also high influence because it is cited by B. This is the basic intuition behind PageRank algorithm. Let's have a look at that. As we had nx.graph, we have the diagram object. It is the same thing, but the difference here is if you try to print this dictionary, it will return you empty dictionary because we did not add any attributes or weights. But if you try to do g2 to 1, it will give you a key error because there is a connection between 1 to 2, but there is no connection between 2 to 1. That is it. To find if it is directed or not, there is g is directed and that will give you a true. When you draw it, this is a makeshift implementation in networks that it will create a bold line there. Let's calculate the PageRank of this graph. We can see that 2 has the highest one. If we look at the graph, we understand why because everyone is pointing towards 2. Let's add a new edge. Every time you draw, it will draw randomly. You will have different representations every time. What do you think this will have an effect on the PageRank of this graph? It won't affect it a lot because it will just add a new edge to 6 and it will increase the PageRank of 6. But what happens when you add this? When you add an edge from 2 to 8, you will see that it increases the PageRank of 8 substantially. It is more than 2 right now. This was the basics of networks and how to study the dynamics of networks. Now let's move on to the application of networks. Has anyone seen this picture before? People who don't watch Game of Thrones just treat it as just a fictional data set. People who do watch Game of Thrones and are behind Game of Thrones, I have tried my level best to not include any spoilers. I am sorry if there are any spoilers. I have tried real hard. There are no spoilers. This study was done by a professor at McLeister College and I have under-graduate there. This network is from the books, not from the TV series. There are significant differences there. How they have extracted this network is they have read the book. They have looked at 15 words and if there are two characters that are mentioned in 15 words, then they have an edge between them. I know this is not the best way of doing it but it still makes some sense. So let's have a look. You can look at their blog. It is called networkofthrones.wordpress.com. They just uploaded season 6 network analysis. Let's start. You should have all this code already. There are two Game of Thrones lectures and Game of Thrones exercise. Lecture one is the easy one. Exercise, you have to write the code. They have made an internal mapping to all the nicknames. A lot of manual work was also done there. Thanks to them, I am doing this. This is a weighted network. If there is more than one interaction between two characters, you will have a weight. Between Jamie Lannister and Adam Marbend, there are three interactions. The weight is three. I have the data for the first five books. Let's start with the first book and have a look at that. Let's find the most important character in Game of Thrones. Let's look at Jamie Lannister because why not? He has a lot of connections in the first book. Let's calculate the length of this. 29 connections in the first book. Let's see in the fifth book. 10 connections in the first book. 64 in the fourth book. Maybe he is an important character in the fourth book but not in the fifth book. Let's calculate the degree centrality of this. I have chosen the top 10 ones. This is for book one. You have a question? In book one, Edard Stark is an important person here. We all know what happens there. Johnson is also there. This is the top 10 of book one according to degree centrality. There is no one right measure. It depends on what you want to get out of the measure and what you want to study about the network. Degree centrality is just one of them. Let's plot a histogram of it. This follows the real world network phenomena. In mathematical terms, it follows the power law distribution. We are right. Mr. Albert Barabasi was right. A quick exercise. In networks, there is only degree centrality but there is no thing called weighted degree centrality. Let's implement that today. Weighted degree centrality is basically the weighted degree divided by the total degree that it could have, a node could have had. Weighted degree is calculated by adding the degree of all the edges a node is connected to. Let's implement that function. Then we will see that adding weights to the degree centrality measure, does it change who is more important in this network? If you are too tired to write the code out, you can just copy it from the lecture notebook and try running it. Let's see. Let's see. Can everyone please open the airport exercise notebook and just run the first five cells? It can take a couple of minutes to load the data set. The airport exercise notebook and then you can go back to game of thrones. Let's see. Let's see. Let's see. Let's see. Let's see. Let's see. Let's see. Let's see. Let's see. Let's see. Let's see. Let's see. Let's see. Let's talk about betweenness centrality. You can break apart the network or you can break apart the bottom link of the network. Not necessarily the nodes of the network but a lot of other components of the network. Thanks to network X we have that too. If you look at this network, the nodes which are between the path graph between these two components, the degree of this node is like two. If you break apart any of these nodes, you are going to break apart this network because these two won't be connected anymore. If you calculate the betweenness centrality, the betweenness centrality of these nodes will be way higher than the degree centrality of these nodes. Even though the degree of these nodes is like three for this, four for this, is higher than the degree of this node. Let's check the betweenness centrality. Again, we get edas tag as the most important character in book one. Now we have weighted betweenness centrality. We need to pass in the parameter weight is equal to the attribute in our network that is weight. Let's check out that if that makes a difference. Yes, it did. According to weighted betweenness centrality, Robert Baratheon is the most important node in this network. If we remove Robert Baratheon, we are kind of breaking up the network. That doesn't mean that it will definitely break up the network but it will decrease the connectivity of the network. This is the basic intuition behind betweenness centrality. Let's actually calculate the page rank of this too. Let's first calculate the unweighted page rank. I know why it's numpy. But page rank numpy is a numpy implementation of page rank. We can just do page rank two. We have tried out three methods till now and two of them tell that edas tag is the most important character in this network. Maybe it's true. I'm not sure. Let's check out the weighted page rank. Edas tag again. These are the most used measures to calculate importance. Edas tag is the most important character in book one. Maybe it's true. Let's find if there is a correlation between these techniques. These are three different techniques that take into account three very different attributes, not attributes structure of the network. Let's find if there is a correlation between these techniques. Like a hint you can use correlation, this function to actually, that's the answer, that's not the hint. We can use pandas to find the correlation of this network of these three measures. Basically I'm creating a pandas data frame and where each column is one character and the first row of each column is the page rank of that character, weighted page rank. The second is pretty mean centrality and the third row is weighted centrality, the one which we implemented. If you weren't able to implement it, just use nxtotdegree centrality. That's okay too. Let's do that. Let's take the transpose of this because there is an inbuilt method to calculate correlation. This is the correlation matrix of these three methods. What can we infer from this? They are more or so high, they are related because with page rank and degree centrality, there is a correlation of 0.94. That's a pretty high correlation. There is a less correlation between degree centrality and between a centrality. That example showed us why the barbell graph. That's a matrix and this will be one because it's like 0 correlated with 0 and that will be one. Till now we have been analyzing the first book. What about the other four books too? When we add time to a network, the fancy name of adding time is known as adding temporality to the network and then we call it temporal networks. Then there is another branch of network analysis called temporal network analysis and people have written books on it. You'll just have a very quick intro to that. In this, I've created a new list where it is tracking the evolution of weighted degrees centrality of each network over the five books. Then we create a data frame and suppose if the character is not present in some book, then I've used fill NA as 0. Now this data frame is pretty self-explanatory. The columns are characters. We have like 796 characters over five books that these people were able to capture and five columns are the five books. Apparently, like AIM and Targaryen, the Dragonite was only mentioned in the third book. We don't have any measures for that in the first, second or the later books. In this bit of pandas, magic or trickery or whatever you would like to call it, I selected top 10 characters on the basis of their maximum value in the column. I took a max of their column first and then took the top 10 out of that. We have Edard, Starks, or C. John Snow. Let's look at the exercise now and this one is about plotting the evolution of the weighted degrees centrality over the five books of these characters. I was able to get this one-liner function and this is the plot of weighted degrees centrality and evolution over the five books. You can pretty much see some obvious trends if you're familiar with Game of Thrones. In the first book, Edard Stark is at the top and the graph pretty much dies out and then in the fourth book, Cersei Lannister is at the top. In the fifth book, John Snow rises from the death to come at the top. This was for weighted degrees centrality and now let's have a look at the same graph but of betweenness centrality. Let's see if we find anything interesting or surprising or anything like that. Here's the graph and at the top we see in the fifth book, it's Tannis Baratheon and it's a pretty big climb from the third book. He's pretty important in the fourth book too and in the fifth book too and there's a big difference. But in weighted degree centrality, there is no mention of Tannis Baratheon in the top ten. What's the reason for this? In betweenness centrality, he's at the top and in degree centrality, he's not even in the top ten. Just like the barbell graph, apparently if we take out Tannis Baratheon from the network, it will break apart the network and apparently he's holding a lot of people together. This is not me, this is Python. This is Python saying. That is strange, yes. So let's talk a little bit about community detection in networks. The intuition behind this is finding similar nodes in the network. It's not necessary, finding the subcomponents, it's like absolute community detection. There are communities, you can actually see them. But suppose there is a complete graph of ten nodes and a complete graph of four nodes and you connect them. So you can mark them as two different communities. They're not components because they are connected, but they're two different communities. And there are a lot of methods of finding that. One of them is Luan community detection. And so we're going to use that and see what happens on book one. So as you can see, this plot is pretty hard to decipher. And there are not a lot of good tools in Python ecosystem to make it better. So this picture was, the different color reflects different communities in this network. And this picture was made by Gefi, I guess. And bigger the font, bigger the influence of the node in this network. And the influence is calculated by page rank in this. Let's go back. Okay, so communities. So it's basically a different, it's hardly visible, but it's like different colors of gray, I guess. And we have different communities. So let's actually look, have a look at different communities. So when we ran the community detection algorithm, it's not actually implemented in NetworkX. I've actually provided you a folder community, which has the code and with the standard alone package, but it doesn't work with the latest release of NetworkX yet. So if you look, so I've created a dictionary and if you'll have a look at that. So it's like we have 12 communities in this. I don't even remember these characters. So let's, so there's this function called nx.subgraph. And it takes in a graph and a bunch of nodes and it will give you, it will give you the subgraph of the graph and where all other nodes are absent. And the edges of those nodes to this network is also absent. So this is like the first component. And like we can have a look at the other components of the graph too. So something like that. So there's this term called density of the network and it's pretty much finding like, if the network is dense, it will have a density which it's like towards one and if it's sparse, it will be like towards zero. No rocket science there. And so like if you find the density of the first book, like just the first book, it's like 0.039 something. So it's a pretty sparse network. You don't have a lot of connections between nodes. But if you find the density of a community inside this network that we got from Luan, a detection algorithm, then it comes out to be like 0.2. It's like some seven times more than the density of the original graph. So like this gives out a brief intuition behind that what we did with community detection. And so one more exercise. So find the most important node in the partitions. Like by partitions, I mean communities in this. According to Pesrang degrees, entirely and between us, entirely of the nodes. The answer should be something like this, like community is the key and the value is the most important node in that community. According to Pesrang or degrees, entirely or between us. Okay. Okay. So like this is my code for it. And again, it's pretty, I'm pretty sure this is not the best code for this, but it works. And so let's move on to another application now. And so what should we do first? Let's have a look at the airport exercise. Yep. Okay. Yeah, so how do people do 0.85? 0.85 is like the standard parameter that is taken and to find the good one is you have to test it out yourself and it depends on the kind of network you have. And it depends on that. And I haven't really tested it a lot. So I am not the best person to answer that. But So like if you open the airport exercise notebook. So in this, the data set is from five years 1995, 2005, 2010 and 2015. And if you look at the CSC file, there are four columns. The first one is like from airport. The second one is to airport. The third one is I guess here and the fourth one is the carrier of the flight. And so there's a difference between this and a normal airport network because this is the route network. It's like if there is a flight between New York and San Francisco by Delta Airlines and that flies on different time on like every day. So it count it will count it as like, you know, seven different flights. So that is the problem with this data set. You need to solve that. But I haven't done anything. It's just like a raw data set. So let's have a look. So I've created five directed graphs because a flight from a point A to point B doesn't mean that plane will fly back to point B to point A. It can go to point C. So we have five directed graphs for like each year. And let's have a look. So let's calculate the page rank. So first thing first thing you want to find out in this network is which is an important airport in this network. If we close down that airport or if you know like some natural disaster happens at the airport, it's like it could shut down the network. Which airport is that? Let's have a look by the tools and measures we have seen today. So according to page rank and this is the weighted is there are no weights. So it doesn't really matter. So and the top list is the top 10 airports according to page rank. And like if you if you're familiar with the airport codes, it's like the top like the top ones that are supposed to be like, you know, like Atlanta or Chicago or New York or something. You would expect something like that. But the first one is ANC. Does anyone know what is ANC? Yes, Anchorage. So Anchorage is this place in Alaska. It's like it's not even in mainland US. It's like just far away. So why is this the most important network in the node? Most important node in the network. Any guesses? Why is Anchorage the most important node? It's not a big airport. It's not a big city. Maybe yes. Yes, but yes, like that is that is one of the reasons that people give out for this for this anomaly in the data set. And like But they don't land there. They just go over Alaska. So it's yeah. Other places you can go to other different routes. Yeah, that basically adds up to that point and it will like this is what I think the biggest reason is but there are other other things out there also that people don't people have other problems with this data set to and so so basically there are a lot of regional flights in Alaska. That only starts from Anchorage and and so basically all those small towns in Alaska are connected to the mainland US only with through their flights with Anchorage. So if you break out Anchorage from this network, you're removing all those two. And so this is one of the reasons that you know like it gives out a very high page ranks score and all the major airports have to fly to Alaska. So it adds to the to the page ranks score of it as we like saw in the in the in that pictorial represent representation. See at only one incoming edge, but it from it was from a major player that is B. And so in that case, Alaska will have a lot of flights as as you mentioned it will have a lot of direct flights that are coming towards Alaska, which would go to Anchorage and then it is connected to a lot of regional airports. So according to a way that this is an important airport in this network in this data set. So let's calculate the between us in reality because why not we know how to do it and degrees and I'll do it too. It took some time but we have the answer again with between us in reality it's Alaska again. So that that further proves our point that it is if you remove Alaska it will break up the it will break up the airport network. So like so that's there and but in degree centrality it comes out to be like the first one is like I guess Atlanta the second is Chicago here. And like I think these are like these are like mainstream important airports and because degree centrality just is just about the number of connections you have. So like that makes sense because like Atlanta is one of the busiest airport in the world so it will have a very high degree centrality when when you look at the US domestic sector. So there's this really nice blog post a few are interested why anchorages and the structure of the network is one of the reasons and there are other reasons to. So again like in this line. So we have the carrier data I mean the data set is like really huge and I had to trim down the data set so I just chose the I just had an option to choose in like one attribute and I chose carrier. I don't know why but let's see. So so what we are going to do is we are going to plot the graphs of like number of routes of the top five airlines. And let's have a look at that over the years like like adding the time time thing to this. So like so the most interest like this is a very broken graph because it's like just like five distinct years. The actual data set is available from 1990 to 2015. So like you have 25 years of data set and that gives out a more prettier graph than this. But because of like data constraints and we don't have a lot of time to time to compute it. So I'm dealing with this. So like if you look at this orange line this is basically delta airlines and you know like in the past 15 years it has grew a lot with the number of routes not flights. So that is the important distinction here. And so again like a bit of pandas to find like it's basically to find the hubs of a nice way like from from which for which a line which is the most used airport like for like this is for for delta airlines. It comes out to Atlanta and I guess MSP is Mississippi and if you'll actually check the Wikipedia pages of the hubs and like it not all of them matches but you know it somewhat matches according to this data set. And if we calculate for United Chicago and Denver and Washington and New York. So these are the one that should be there and we are running out of time so you know I'll just hurry past these lights. So every shortest path length of the network. So what would what happened. So we have a error that is graph is not weekly connected connected. So it's weakly connected is a directed graph term and as this is a directed graph. So if if the graph like if you look at the look at a undirected copy of the graph and it's not connected by not connected it means there are components in the graph. Then that is a problem and especially in this case because you don't want like couple of airports lying there which have flights between them but they're not connected to the to the other components. You can't have this but like this is there and this is like the real data set from like federal aviation authority. So what's happening there. Let's see that. So let's have a look at connected components. So if you look at if you if you go at the very last bit of this. Yes, so basically there are three components. One is the one one is the comment that the company it should be the connection the data set of all reports. Then there there are these two components this is like apparently so there's this flight which goes from a I K to a I K it goes to itself. So I wasn't able to solve the mystery of this flight but I was able to solve the mystery of SPV to SSB. So it's basically if it's a pewter recon a line and it and it's not a it's a C plane company. So it's like it just flies between these two airports and that's all so that is the reason why it's you know something like that and to make matters easier. So let's just remove remove these notes. So we have a nice connected graph and the difference between weekly connected and strongly connected in a directed graph is if it's strongly connected. It has a note should be reachable from any other node like basically they should be they should form a component but you don't have to go to the undirected copy of it. If you have to go to the undirected copy of it to get to get every knows every node as reachable then it's basically a weekly connected graph. So let's find out the average shortest path length. So can anyone tell me what could average shortest path length. It's it's it's right there in the name like can someone explain that. It basically computes the distance between any between all the all the pairs of nodes in the network and finds the shortest part between them and it will give you the average of it. So it gives out an average of 3.02. So it means that if I pick any airport in the in the data set a and like suppose a and another it would be there are only. I need to travel through only two steps to reach to that airport. Suppose there's no direct flight I could just go from a if I have to go from a to B the average number is a CDB I should be there. I don't need to take more than three flights. This is the average shortest path length and like if we plot the degree centrality and again it follows the power log graph. So like we have to not prove it like I guess this is the third data set that it does follow. So so like the Barabasi Albert model is considered to be like a seminal work in network science and this is why. And so this was actually supposed to be a very nice interesting exercise because this is a very open ended question. It's like one of the one of the nice one of the nice applications of network science. So that so we need to add new flights to this network. But like adding a flight is like there is a cost involved with it. So how can you add flights in an effective manner the minimum number of flights in an effective manner that you decrease the average shortest path length of this network. So how could we do that? So what I did is I just know like it's a very naive implementation of this is a single preferential attachment and it's part of the Barabasi Albert model. So what it does is finds the it finds the node which has the highest degree centrality and then like and I've arranged it in a sorted order. And then it finds the node the next node like it just iterates through the list and finds if there is a if there is a connection between them or not. So it will try to find the next node which next highest node which there is there is no connection and it will add a new flight. So it's like I'm trying to connect the highest central airports which are not connected yet. So does that make any difference? So like in this I think I have added I've added like around 500 edges and that is like 2% of the current edges. So like 2% of the current flights I've added new flights and this is what it gives out improvement of like 0.7%. So so as we can see this is not a good way to do that. But it's an open-ended question like if anyone would like to tackle it, it's nice question. And there are some like linear optimization ways to solve this problem. A lot of people are doing that. Well, I guess everyone is pretty much feeling like this now. So, okay, so that that's here I'll end this and if you want to go through the diseases exercise diseases notebook 2. It's just it's it's like super simple. It's just it's just some pretty graphs and you know how diseases are spreading. This can be also used to model like virus spreading on a set of routers or you know like as we as we are moving towards more IOT things. It's a serious concern to you know not to stop spreading of viruses in IOT devices and which which which are not so easy to to change or you know to update them. So this is a nice pretty little way to do that. So like these models were made in like 1920s and something and at that time, network science wasn't even there and these are now incorporated into network science to make these things. So that's it. Thank you.
 Okay, so before we start there are let's look at the structure of the tutorial.  Like every notebook has two versions, one is exercise and the other one is lecture.  So exercise is a more hands-on version, it's like you have to write code in the exercise  one and if you are tired and so basically if you are feeling like this, so you know  you can just go through the lecture with me and if you are in mood so you know you can  go through the exercise notebooks and actually write code.  So okay, is everyone set up?  Any issues?  Okay, so let's start network analysis with Python.  So first question, what are networks?  What is a graph?  So like okay, so some issues with the, yeah.  So a graph or a network is basically a way to symbolize link data.  So like the red dots there are nodes or vertices and the lines joining them are known as edges  or like links or anything like that.  So what are some examples that we can think of?  Like any real world network data, anyone?  Yep, train station and the connections between them.  Any other example?  Yep, Facebook, Twitter, these are like social networks.  Sorry?  Yes, worldwide web.  So these are a bunch of interesting examples.  The first one is a transportation network.  It's like if there is a flight between two airports, there's a link there.  The second one is, I think it's like over the trade counters, derivative markets, some  financial thing and it's like, it's a network of that and the third one is the Facebook's  worldwide social network.  Like it's the connections between all the friends on Facebook.  So in this tutorial, first we'll go through network X.  It's a Python package to do network analysis and model network data.  Like a very quick intro to network X and the API of network X and then we look at three  real world data sets and three real world applications of network analysis.  So one of them is epidemics and spreading of diseases and how people die and speaking  of death, then we'll talk about Game of Thrones and do a network analysis of Game of Thrones.  And the third one is USA Put Dataset.  So we'll try to figure out what's happening there.  So let's start with an introduction to network X and graphs.  Everyone has opened the first notebook, introduction one.  If you want to code, you should open introduction notebook.  So it's like pretty trivial API.  It's like how to create a graph.  It's like GNX graph and import network X is the usual way of importing it.  And so add node will add and note to this graph object.  And there are multiple types of graph objects.  There is graph, the standard basic one.  Then there is digraph, multidigraph and multigraph.  So a digraph is directed graph, any examples of a directed real world graph.  Anyone?  So what's the difference between a directed graph and a graph?  Does anyone know that?  Yes.  So if there is a connection between A to B in an undirected graph, that means there  is a connection between B to A2, but that's not the case with a directed graph.  So any examples of a directed graph, a real world example?  Sorry?  Yes, control flow, control flow diagrams and Twitter because if I follow Jennifer Lawrence,  he doesn't follow me back.  We know that.  So just type.  Yes, sir?  Sorry?  Yeah.  NetworkX allows that, but the definition, it depends upon, it depends on the user.  If you want to have a simple graph, shouldn't have loops, but NetworkX allows that.  So there are different ways to add nodes, like you can use add node and add nodes from  and how to access nodes, g.nodes.  And people who are using NetworkX, NetworkX 2.0 will see node view and people who are  using, if you do pip install NetworkX, it will, right now it will install the version  1.11 and that's okay, but this is the new one.  So we have views now instead of basic list and dictionary representation.  So we have a lot of generators in NetworkX.  It's like a path graph is, it will give you a path between, it will map a path between  0, 1, 2, and 3.  So there's an edge between 0 to 1, 1 to 2, and so on.  And then, and one of the good things about nodes in NetworkX is it can be anything.  It can be any hashable object.  You can have integers, you can have strings, you can have tuples, you can even have another  graph object as a node in graphs.  So like if we do g.add node h, it will add the node, it will add the node graph h as  a node.  So like if you will see like there's a graph object in nodes now.  So let's look at the second part of a network edges.  So like as nodes really reveal, it's just add edge and you know, that's how it works.  And you'll get an edge view if you do g.edges.  And then you know how to calculate the number of nodes.  So like there are different ways of doing that, there is an inbuilt method.  You can calculate the length of the graph or you can calculate the length of the list  that returns with g.nodes and g.edges.  And just like you can add nodes, you can remove nodes from the graph.  So like, you know, little bit of stuff.  So okay, so let's start with something.  So Eldos ReniGraph is basically a random graph model generator.  Like if you do like, basically the first argument is the number of nodes you want.  The second argument is the probability of having an edge for every node with another  node.  So it's like if you have a probability of 0.3 in 10 nodes, this is what the random graph,  the Eldos ReniGraph generator will give you out.  So like if we change the probability to like 0.1, you'll have a more sparse graph.  And if you like make it 1, you'll have a complete graph.  This is known as a complete graph that is like all nodes are connected to each other.  And this is one of the ways to visualize the graph, the most obvious one to actually show  how it looks like.  And the other one is to use matrices to visualize a graph.  So in this, sorry, so in this graph, the white spots show if there is an edge between node  0 and like 0 and there is no edge between 0 and 0 because there are no self loops in  this graph right now.  So if there is an edge between like 1 and 2, then it's white.  So let's change a graph.  Make it 0 point.  So like you'll see the representation changes.  And the interesting part of network analysis comes in when you can add weights and attributes  to the edges and networks.  So network X lets you do that too.  Like you know, you can just pass in a parameter as weight and you know like whatever you want  to.  And to access nodes with the attributes we need to pass in the argument data is equal  to true.  And the G.nodes will just give you the nodes and G.nodes data true will give you the attribute  to like we have added time in this previous cell.  And network stores graphs in a dictionary underneath.  So there are ways to access those graph dictionaries too.  And it's basically a dictionary how you operate on a dictionary.  So a quick warm up exercise.  So we have created this graph and we have added edges from this list which is basically  like the starting edge, the ending, the starting point, the ending point and like suppose like  the price of a ticket between those two cities.  So the exercise is to find the edge with the highest weight.  A quick warm up exercise.  And in that way you can run the committees who have stayed off the nodes may have adopted  Let me know if anyone is done and tell me the answer to.  Anyone  can do it.  Choose with the piece of code here.  If you do g.edges.  It will return you an edge data view of tuples of the first node, the second node and the attribute dictionary.  If you pass just g.edges, you will get only the edges, not the attributes of the first node.  Let's start to understand some dynamics of a network.  Let's draw it out.  When we have a network, we need to know which of these nodes do you think is an important node in a network.  If I remove that node, it could break the structural integrity of the network.  Which node do you think is that?  How did you come to that answer?  Any more guesses?  One of the most naive ways of figuring it out is just calculating the neighbors of a node.  That is called a degree of a node.  The higher the number of neighbors, the more influential the node is in the network.  As you pointed out, if we took out 7 in this network, it would break the network.  There are different ways of approaching this problem, how to find the most important node in a network.  There is no right way to do that.  That way is called between a centrality that we have seen in some time.  Let's first talk about degree centrality.  Degree centrality is just a fancy name for a normalized degree of a node.  You calculate the degree of the node and divide it by the total number of nodes it can connect to.  That will be n minus 1, where n is the number of nodes in a network.  Let's calculate the degree of this network.  Degree centrality of this network is not the top of the first five.  That's there.  There are a lot of other methods like between a centrality, flow centrality, page rank.  We will have a look at them.  This is our first data set.  This is the collaboration network of a general relativity group on the archive.  If two people have published a paper together, then they have an edge between them and where nodes are the authors.  If four people have published a paper together, there will be a complete graph between those four in the larger graph.  Let's import that.  Let's check out the number of nodes and number of edges in this network.  There are 5200 authors in this network and around 49,500 links between them.  Let's see what we can do with this.  There are a lot of ways in networks to figure out what is the degree of a network.  One of them is to just do the graph object and call the function degree on it and pass in the node.  I just randomly chose 22504.  It's an author in this network.  It is connected to 33 other authors.  Let's do other short exercises.  In this exercise, we have to create a list of degree of node, like two tuples and find the node with maximum degree.  Let me know the answer if anyone's done.  Let's see what we can do.  Let's see what we can do.  It's one of the reasons for that is network is written in pure Python.  It's pretty slow.  It's more of a prototyping tool than working with large datasets.  If you really want to work on large datasets, move away from networks or use something like iGraph or GraphTool.  The core of iGraph and GraphTool is written in C++.  I didn't get your question.  Gefi is the best software for graph visualization according to me.  It was never meant to be a visualization tool.  Gefi is a standalone application.  Anyone found the highest degree?  We have an input method called degree.  Let's check it out.  That's the right answer.  Let's have a look at the degree centrality of the author's graph.  The key is the node and the value is the degree centrality of that node.  Let's go to another exercise now.  We have to plot the degree centrality of the author's graph.  We have to plot the degree centrality of the author's graph.  You should end up with something like this.  It has a very heavy distribution.  Let's take a D-tool and go back to Eldos and iGraph.  Let's plot the degree centrality of Eldos and iGraph.  This is a very different graph than what we got from our archive graph.  As you can see, it peaks at around 0.30.  We passed in the probability as 0.3.  The probability of creating an edge between a node and every other node is 0.3.  The degree centrality peaked at 0.3.  It works for every value, not just 0.3.  I can show you that.  0.7.  As you can see, it follows a normal distribution when it's creating the graph.  The problem with Eldos and iGraph is that it cannot model real-world data.  When you don't have access to real-world data and you want to create a synthetic data set,  you need something better than Eldos and iGraph.  In 1999, Barabasi and Elbert came out with their Barabasi-Elbert random-graph generation model.  When you look at this, the degree centrality matches.  Let's plot both of them.  It's more closer than the Eldos and iGraph than the Barabasi-Elbert graph.  There is another called PowerLockLusterGraph.  It's just a variant of Barabasi-Elbert graph and it also follows a similar distribution underneath.  Let's come back and let's have a look at connected components of a graph.  Let's create a random graph again.  In this graph, you can see that we have three different components.  If I am somewhere in 7 or 8, I cannot go to 1 or 4.  This helps when you're planning to make a road network.  If those are cities, you need to have a way to go from 7 to 6.  You can't just keep them there.  We have a way to calculate that and this is the connected components of the authors graph.  As we can see, we have this one lone wolf here who doesn't like to work with anyone else and only publishes alone.  Maybe something like that.  A lot of people that work with each other don't collaborate a lot but majority of them, this is the biggest component of this graph.  They collaborate with each other.  Let's create subgraphs of this graph where every graph is a component.  If you will see the length of the first graph in this, that's 4 and 5.  Graphs is a list of graphs where every graph is a subgraph of our original authors graph and it's a component.  If you try to find graphs, the 10th subcomponent, we have two components of this graph.  Not exactly components but we have two cliques here and cliques are structures which have complete graphs as their subgraphs.  There are three nodes on the left and six nodes on the right where six nodes form a complete graph and three nodes form a complete graph.  Maybe you can infer something like those six people published a paper together and a person from that group published a paper together with these two people.  Another important application is graph traversal.  Suppose I have to go from 4 to 6. It's not possible.  Finding shortest path in a network is one of the de facto things that you do when you start a network analysis.  There are algorithms implemented in networks to do that.  When you pass in a normal graph, it basically uses a BFS to solve that and if you pass with weights, it will use Dijkstra underneath.  You don't need to worry about that if you don't know what it is. It will just give you out the picture.  Let's move on to another exercise.  How many of you have heard about six degrees of separation?  Can anyone tell me that?  Anyone?  I can reach anyone in this world by just jumping six steps of friendship and connection.  The number of L-dOS is given to co-authors of L-dOS. If you have published a paper with L-dOS, you get the number 2.  If you have published a paper with someone who has worked with a person, you get the number 2.  Let's find the 22504 number of this authors graph.  If there is no connection, that means that the author is not in the bigger subcomponent of authors graph,  then you can give it the number minus 1 and then plot the histogram of this.  Let's find the 22504 number of this authors graph.  Let's find the 22504 number of this authors graph.  Let's find the 22504 number of this authors graph.  Let's find the 22504 number of this authors graph.  Let's find the 22504 number of this authors graph.  Let's find the 22504 number of this authors graph.  Let's find the 22504 number of this authors graph.  Let's find the 22504 number of this authors graph.  Let's find the 22504 number of this authors graph.  Let's find the 22504 number of this authors graph.  This is one of the ways of doing it.  There are probably more and better ways of doing this too.  This is how I did it.  If you ignore the minus 1 bar, you can see that this is peaking at around 6.  I'm not saying that this will prove that theory, but maybe this is something interesting.  This is just for one node in the network.  If you find the average shortest path from this node, it comes out to be 5.61, which is less than 6.  This doesn't prove that theory, but it's just a thing we can think about.  Facebook actually tried doing this and ran it on their full friendship network.  Can anyone guess what was the degree of that?  What did they find?  They found it's 3.5.  This is their distribution.  It's speaking at 3.5, speaking at 3.4.  Earlier, you could be able to see your own degree or degree of separation too, but they have removed it.  Mark Zuckerberg has 3.17.  It means that in three steps, Mark Zuckerberg can reach any person on Facebook.  Three friendship steps.  I had a degree of 3.94 or something.  Let's get back.  Let's talk a little bit about directed graphs.  Does anyone know this visualization?  What does it represent?  This is the representation of the PageRank algorithm, which was named after Larry Page, the person who made Google, co-founder of Google.  This is what early version of Google used to index the web.  As you can see, this fellow C here, it only has one incoming connection, but still the importance of this in this network is pretty high.  As compared to B, which has a lot of incoming connection, that makes sense because a lot of people are citing B whenever they are talking about anything.  B has a high influence on this network, but C has also high influence because it is cited by B.  This is the basic intuition behind PageRank algorithm.  Let's have a look at that.  As we had nx.graph, we have the diagram object.  It is the same thing, but the difference here is if you try to print this dictionary, it will return you empty dictionary because we did not add any attributes or weights.  But if you try to do g2 to 1, it will give you a key error because there is a connection between 1 to 2, but there is no connection between 2 to 1.  That is it.  To find if it is directed or not, there is g is directed and that will give you a true.  When you draw it, this is a makeshift implementation in networks that it will create a bold line there.  Let's calculate the PageRank of this graph.  We can see that 2 has the highest one.  If we look at the graph, we understand why because everyone is pointing towards 2.  Let's add a new edge.  Every time you draw, it will draw randomly.  You will have different representations every time.  What do you think this will have an effect on the PageRank of this graph?  It won't affect it a lot because it will just add a new edge to 6 and it will increase the PageRank of 6.  But what happens when you add this?  When you add an edge from 2 to 8, you will see that it increases the PageRank of 8 substantially.  It is more than 2 right now.  This was the basics of networks and how to study the dynamics of networks.  Now let's move on to the application of networks.  Has anyone seen this picture before?  People who don't watch Game of Thrones just treat it as just a fictional data set.  People who do watch Game of Thrones and are behind Game of Thrones, I have tried my level best to not include any spoilers.  I am sorry if there are any spoilers.  I have tried real hard.  There are no spoilers.  This study was done by a professor at McLeister College and I have under-graduate there.  This network is from the books, not from the TV series.  There are significant differences there.  How they have extracted this network is they have read the book.  They have looked at 15 words and if there are two characters that are mentioned in 15 words, then they have an edge between them.  I know this is not the best way of doing it but it still makes some sense.  So let's have a look.  You can look at their blog.  It is called networkofthrones.wordpress.com.  They just uploaded season 6 network analysis.  Let's start.  You should have all this code already.  There are two Game of Thrones lectures and Game of Thrones exercise.  Lecture one is the easy one.  Exercise, you have to write the code.  They have made an internal mapping to all the nicknames.  A lot of manual work was also done there.  Thanks to them, I am doing this.  This is a weighted network.  If there is more than one interaction between two characters, you will have a weight.  Between Jamie Lannister and Adam Marbend, there are three interactions.  The weight is three.  I have the data for the first five books.  Let's start with the first book and have a look at that.  Let's find the most important character in Game of Thrones.  Let's look at Jamie Lannister because why not?  He has a lot of connections in the first book.  Let's calculate the length of this.  29 connections in the first book.  Let's see in the fifth book.  10 connections in the first book.  64 in the fourth book.  Maybe he is an important character in the fourth book but not in the fifth book.  Let's calculate the degree centrality of this.  I have chosen the top 10 ones.  This is for book one.  You have a question?  In book one, Edard Stark is an important person here.  We all know what happens there.  Johnson is also there.  This is the top 10 of book one according to degree centrality.  There is no one right measure.  It depends on what you want to get out of the measure and what you want to study about the network.  Degree centrality is just one of them.  Let's plot a histogram of it.  This follows the real world network phenomena.  In mathematical terms, it follows the power law distribution.  We are right.  Mr. Albert Barabasi was right.  A quick exercise.  In networks, there is only degree centrality but there is no thing called weighted degree centrality.  Let's implement that today.  Weighted degree centrality is basically the weighted degree divided by the total degree that it could have,  a node could have had.  Weighted degree is calculated by adding the degree of all the edges a node is connected to.  Let's implement that function.  Then we will see that adding weights to the degree centrality measure,  does it change who is more important in this network?  If you are too tired to write the code out, you can just copy it from the lecture notebook and try running it.  Let's see.  Let's see.  Can everyone please open the airport exercise notebook and just run the first five cells?  It can take a couple of minutes to load the data set.  The airport exercise notebook and then you can go back to game of thrones.  Let's see.  Let's see.  Let's see.  Let's see.  Let's see.  Let's see.  Let's see.  Let's see.  Let's see.  Let's see.  Let's see.  Let's see.  Let's see.  Let's talk about betweenness centrality.  You can break apart the network or you can break apart the bottom link of the network.  Not necessarily the nodes of the network but a lot of other components of the network.  Thanks to network X we have that too.  If you look at this network, the nodes which are between the path graph between these two components,  the degree of this node is like two.  If you break apart any of these nodes, you are going to break apart this network because these two won't be connected anymore.  If you calculate the betweenness centrality, the betweenness centrality of these nodes will be way higher than the degree centrality of these nodes.  Even though the degree of these nodes is like three for this, four for this, is higher than the degree of this node.  Let's check the betweenness centrality.  Again, we get edas tag as the most important character in book one.  Now we have weighted betweenness centrality.  We need to pass in the parameter weight is equal to the attribute in our network that is weight.  Let's check out that if that makes a difference.  Yes, it did.  According to weighted betweenness centrality, Robert Baratheon is the most important node in this network.  If we remove Robert Baratheon, we are kind of breaking up the network.  That doesn't mean that it will definitely break up the network but it will decrease the connectivity of the network.  This is the basic intuition behind betweenness centrality.  Let's actually calculate the page rank of this too.  Let's first calculate the unweighted page rank.  I know why it's numpy.  But page rank numpy is a numpy implementation of page rank.  We can just do page rank two.  We have tried out three methods till now and two of them tell that edas tag is the most important character in this network.  Maybe it's true. I'm not sure.  Let's check out the weighted page rank.  Edas tag again.  These are the most used measures to calculate importance.  Edas tag is the most important character in book one.  Maybe it's true.  Let's find if there is a correlation between these techniques.  These are three different techniques that take into account three very different attributes, not attributes structure of the network.  Let's find if there is a correlation between these techniques.  Like a hint you can use correlation, this function to actually, that's the answer, that's not the hint.  We can use pandas to find the correlation of this network of these three measures.  Basically I'm creating a pandas data frame and where each column is one character and the first row of each column is the page rank of that character, weighted page rank.  The second is pretty mean centrality and the third row is weighted centrality, the one which we implemented.  If you weren't able to implement it, just use nxtotdegree centrality.  That's okay too.  Let's do that.  Let's take the transpose of this because there is an inbuilt method to calculate correlation.  This is the correlation matrix of these three methods.  What can we infer from this?  They are more or so high, they are related because with page rank and degree centrality, there is a correlation of 0.94.  That's a pretty high correlation.  There is a less correlation between degree centrality and between a centrality.  That example showed us why the barbell graph.  That's a matrix and this will be one because it's like 0 correlated with 0 and that will be one.  Till now we have been analyzing the first book.  What about the other four books too?  When we add time to a network, the fancy name of adding time is known as adding temporality to the network and then we call it temporal networks.  Then there is another branch of network analysis called temporal network analysis and people have written books on it.  You'll just have a very quick intro to that.  In this, I've created a new list where it is tracking the evolution of weighted degrees centrality of each network over the five books.  Then we create a data frame and suppose if the character is not present in some book, then I've used fill NA as 0.  Now this data frame is pretty self-explanatory.  The columns are characters.  We have like 796 characters over five books that these people were able to capture and five columns are the five books.  Apparently, like AIM and Targaryen, the Dragonite was only mentioned in the third book.  We don't have any measures for that in the first, second or the later books.  In this bit of pandas, magic or trickery or whatever you would like to call it, I selected top 10 characters on the basis of their maximum value in the column.  I took a max of their column first and then took the top 10 out of that.  We have Edard, Starks, or C. John Snow.  Let's look at the exercise now and this one is about plotting the evolution of the weighted degrees centrality over the five books of these characters.  I was able to get this one-liner function and this is the plot of weighted degrees centrality and evolution over the five books.  You can pretty much see some obvious trends if you're familiar with Game of Thrones.  In the first book, Edard Stark is at the top and the graph pretty much dies out and then in the fourth book, Cersei Lannister is at the top.  In the fifth book, John Snow rises from the death to come at the top.  This was for weighted degrees centrality and now let's have a look at the same graph but of betweenness centrality.  Let's see if we find anything interesting or surprising or anything like that.  Here's the graph and at the top we see in the fifth book, it's Tannis Baratheon and it's a pretty big climb from the third book.  He's pretty important in the fourth book too and in the fifth book too and there's a big difference.  But in weighted degree centrality, there is no mention of Tannis Baratheon in the top ten.  What's the reason for this?  In betweenness centrality, he's at the top and in degree centrality, he's not even in the top ten.  Just like the barbell graph, apparently if we take out Tannis Baratheon from the network, it will break apart the network and apparently he's holding a lot of people together.  This is not me, this is Python.  This is Python saying.  That is strange, yes.  So let's talk a little bit about community detection in networks.  The intuition behind this is finding similar nodes in the network.  It's not necessary, finding the subcomponents, it's like absolute community detection.  There are communities, you can actually see them.  But suppose there is a complete graph of ten nodes and a complete graph of four nodes and you connect them.  So you can mark them as two different communities.  They're not components because they are connected, but they're two different communities.  And there are a lot of methods of finding that.  One of them is Luan community detection.  And so we're going to use that and see what happens on book one.  So as you can see, this plot is pretty hard to decipher.  And there are not a lot of good tools in Python ecosystem to make it better.  So this picture was, the different color reflects different communities in this network.  And this picture was made by Gefi, I guess.  And bigger the font, bigger the influence of the node in this network.  And the influence is calculated by page rank in this.  Let's go back.  Okay, so communities.  So it's basically a different, it's hardly visible, but it's like different colors of gray, I guess.  And we have different communities.  So let's actually look, have a look at different communities.  So when we ran the community detection algorithm, it's not actually implemented in NetworkX.  I've actually provided you a folder community, which has the code and with the standard alone package,  but it doesn't work with the latest release of NetworkX yet.  So if you look, so I've created a dictionary and if you'll have a look at that.  So it's like we have 12 communities in this.  I don't even remember these characters.  So let's, so there's this function called nx.subgraph.  And it takes in a graph and a bunch of nodes and it will give you,  it will give you the subgraph of the graph and where all other nodes are absent.  And the edges of those nodes to this network is also absent.  So this is like the first component.  And like we can have a look at the other components of the graph too.  So something like that.  So there's this term called density of the network and it's pretty much finding like,  if the network is dense, it will have a density which it's like towards one  and if it's sparse, it will be like towards zero.  No rocket science there.  And so like if you find the density of the first book, like just the first book,  it's like 0.039 something. So it's a pretty sparse network.  You don't have a lot of connections between nodes.  But if you find the density of a community inside this network that we got from Luan,  a detection algorithm, then it comes out to be like 0.2.  It's like some seven times more than the density of the original graph.  So like this gives out a brief intuition behind that what we did with community detection.  And so one more exercise.  So find the most important node in the partitions.  Like by partitions, I mean communities in this.  According to Pesrang degrees, entirely and between us, entirely of the nodes.  The answer should be something like this, like community is the key and the value is the most important node in that community.  According to Pesrang or degrees, entirely or between us.  Okay.  Okay.  So like this is my code for it.  And again, it's pretty, I'm pretty sure this is not the best code for this, but it works.  And so let's move on to another application now.  And so what should we do first?  Let's have a look at the airport exercise.  Yep.  Okay.  Yeah, so how do people do 0.85?  0.85 is like the standard parameter that is taken and to find the good one is you have to test it out yourself and it depends on the kind of network you have.  And it depends on that.  And I haven't really tested it a lot.  So I am not the best person to answer that.  But  So like if you open the airport exercise notebook.  So in this, the data set is from five years 1995, 2005, 2010 and 2015.  And if you look at the CSC file, there are four columns.  The first one is like from airport.  The second one is to airport.  The third one is I guess here and the fourth one is the carrier of the flight.  And so there's a difference between this and a normal airport network because this is the route network.  It's like if there is a flight between New York and San Francisco by Delta Airlines and that flies on different time on like every day.  So it count it will count it as like, you know, seven different flights.  So that is the problem with this data set.  You need to solve that.  But I haven't done anything. It's just like a raw data set.  So let's have a look.  So I've created five directed graphs because a flight from a point A to point B doesn't mean that plane will fly back to point B to point A.  It can go to point C.  So we have five directed graphs for like each year.  And let's have a look.  So let's calculate the page rank.  So first thing first thing you want to find out in this network is which is an important airport in this network.  If we close down that airport or if you know like some natural disaster happens at the airport, it's like it could shut down the network.  Which airport is that?  Let's have a look by the tools and measures we have seen today.  So according to page rank and this is the weighted is there are no weights.  So it doesn't really matter.  So and the top list is the top 10 airports according to page rank.  And like if you if you're familiar with the airport codes, it's like the top like the top ones that are supposed to be like, you know, like Atlanta or Chicago or New York or something.  You would expect something like that.  But the first one is ANC.  Does anyone know what is ANC?  Yes, Anchorage.  So Anchorage is this place in Alaska. It's like it's not even in mainland US. It's like just far away.  So why is this the most important network in the node?  Most important node in the network.  Any guesses?  Why is Anchorage the most important node?  It's not a big airport. It's not a big city.  Maybe yes.  Yes, but yes, like that is that is one of the reasons that people give out for this for this anomaly in the data set.  And like  But they don't land there. They just go over Alaska.  So it's yeah.  Other places you can go to other different routes.  Yeah, that basically adds up to that point and it will like this is what I think the biggest reason is but there are other other things out there also that people don't people have other problems with this data set to and so so basically there are a lot of regional flights in Alaska.  That only starts from Anchorage and and so basically all those small towns in Alaska are connected to the mainland US only with through their flights with Anchorage.  So if you break out Anchorage from this network, you're removing all those two.  And so this is one of the reasons that you know like it gives out a very high page ranks score and all the major airports have to fly to Alaska.  So it adds to the to the page ranks score of it as we like saw in the in the in that pictorial represent representation.  See at only one incoming edge, but it from it was from a major player that is B.  And so in that case, Alaska will have a lot of flights as as you mentioned it will have a lot of direct flights that are coming towards Alaska, which would go to Anchorage and then it is connected to a lot of regional airports.  So according to a way that this is an important airport in this network in this data set.  So let's calculate the between us in reality because why not we know how to do it and degrees and I'll do it too.  It took some time but we have the answer again with between us in reality it's Alaska again.  So that that further proves our point that it is if you remove Alaska it will break up the it will break up the airport network.  So like so that's there and but in degree centrality it comes out to be like the first one is like I guess Atlanta the second is Chicago here.  And like I think these are like these are like mainstream important airports and because degree centrality just is just about the number of connections you have.  So like that makes sense because like Atlanta is one of the busiest airport in the world so it will have a very high degree centrality when when you look at the US domestic sector.  So there's this really nice blog post a few are interested why anchorages and the structure of the network is one of the reasons and there are other reasons to.  So again like in this line.  So we have the carrier data I mean the data set is like really huge and I had to trim down the data set so I just chose the I just had an option to choose in like one attribute and I chose carrier.  I don't know why but let's see.  So so what we are going to do is we are going to plot the graphs of like number of routes of the top five airlines.  And let's have a look at that over the years like like adding the time time thing to this.  So like so the most interest like this is a very broken graph because it's like just like five distinct years.  The actual data set is available from 1990 to 2015.  So like you have 25 years of data set and that gives out a more prettier graph than this.  But because of like data constraints and we don't have a lot of time to time to compute it.  So I'm dealing with this.  So like if you look at this orange line this is basically delta airlines and you know like in the past 15 years it has grew a lot with the number of routes not flights.  So that is the important distinction here.  And so again like a bit of pandas to find like it's basically to find the hubs of a nice way like from from which for which a line which is the most used airport like for like this is for for delta airlines.  It comes out to Atlanta and I guess MSP is Mississippi and if you'll actually check the Wikipedia pages of the hubs and like it not all of them matches but you know it somewhat matches according to this data set.  And if we calculate for United Chicago and Denver and Washington and New York.  So these are the one that should be there and we are running out of time so you know I'll just hurry past these lights.  So every shortest path length of the network.  So what would what happened.  So we have a error that is graph is not weekly connected connected.  So it's weakly connected is a directed graph term and as this is a directed graph.  So if if the graph like if you look at the look at a undirected copy of the graph and it's not connected by not connected it means there are components in the graph.  Then that is a problem and especially in this case because you don't want like couple of airports lying there which have flights between them but they're not connected to the to the other components.  You can't have this but like this is there and this is like the real data set from like federal aviation authority.  So what's happening there. Let's see that.  So let's have a look at connected components.  So if you look at if you if you go at the very last bit of this.  Yes, so basically there are three components.  One is the one one is the comment that the company it should be the connection the data set of all reports.  Then there there are these two components this is like apparently so there's this flight which goes from a I K to a I K it goes to itself.  So I wasn't able to solve the mystery of this flight but I was able to solve the mystery of SPV to SSB.  So it's basically if it's a pewter recon a line and it and it's not a it's a C plane company.  So it's like it just flies between these two airports and that's all so that is the reason why it's you know something like that and to make matters easier.  So let's just remove remove these notes.  So we have a nice connected graph and the difference between weekly connected and strongly connected in a directed graph is if it's strongly connected.  It has a note should be reachable from any other node like basically they should be they should form a component but you don't have to go to the undirected copy of it.  If you have to go to the undirected copy of it to get to get every knows every node as reachable then it's basically a weekly connected graph.  So let's find out the average shortest path length.  So can anyone tell me what could average shortest path length.  It's it's it's right there in the name like can someone explain that.  It basically computes the distance between any between all the all the pairs of nodes in the network and finds the shortest part between them and it will give you the average of it.  So it gives out an average of 3.02.  So it means that if I pick any airport in the in the data set a and like suppose a and another it would be there are only.  I need to travel through only two steps to reach to that airport.  Suppose there's no direct flight I could just go from a if I have to go from a to B the average number is a CDB I should be there.  I don't need to take more than three flights.  This is the average shortest path length and like if we plot the degree centrality and again it follows the power log graph.  So like we have to not prove it like I guess this is the third data set that it does follow.  So so like the Barabasi Albert model is considered to be like a seminal work in network science and this is why.  And so this was actually supposed to be a very nice interesting exercise because this is a very open ended question.  It's like one of the one of the nice one of the nice applications of network science.  So that so we need to add new flights to this network.  But like adding a flight is like there is a cost involved with it.  So how can you add flights in an effective manner the minimum number of flights in an effective manner that you decrease the average shortest path length of this network.  So how could we do that?  So what I did is I just know like it's a very naive implementation of this is a single preferential attachment and it's part of the Barabasi Albert model.  So what it does is finds the it finds the node which has the highest degree centrality and then like and I've arranged it in a sorted order.  And then it finds the node the next node like it just iterates through the list and finds if there is a if there is a connection between them or not.  So it will try to find the next node which next highest node which there is there is no connection and it will add a new flight.  So it's like I'm trying to connect the highest central airports which are not connected yet.  So does that make any difference?  So like in this I think I have added I've added like around 500 edges and that is like 2% of the current edges.  So like 2% of the current flights I've added new flights and this is what it gives out improvement of like 0.7%.  So so as we can see this is not a good way to do that.  But it's an open-ended question like if anyone would like to tackle it, it's nice question.  And there are some like linear optimization ways to solve this problem.  A lot of people are doing that.  Well, I guess everyone is pretty much feeling like this now.  So, okay, so that that's here I'll end this and if you want to go through the diseases exercise diseases notebook 2.  It's just it's it's like super simple.  It's just it's just some pretty graphs and you know how diseases are spreading.  This can be also used to model like virus spreading on a set of routers or you know like as we as we are moving towards more IOT things.  It's a serious concern to you know not to stop spreading of viruses in IOT devices and which which which are not so easy to to change or you know to update them.  So this is a nice pretty little way to do that.  So like these models were made in like 1920s and something and at that time,  network science wasn't even there and these are now incorporated into network science to make these things.  So that's it. Thank you.
EuroSciPy_2017__NetworkX_iTOC8TQrF_U_0_683.png EuroSciPy_2017__NetworkX_iTOC8TQrF_U_684_1031.png EuroSciPy_2017__NetworkX_iTOC8TQrF_U_1032_5303.png EuroSciPy_2017__NetworkX_iTOC8TQrF_U_5304_9095.png EuroSciPy_2017__NetworkX_iTOC8TQrF_U_9096_10595.png EuroSciPy_2017__NetworkX_iTOC8TQrF_U_10596_12047.png EuroSciPy_2017__NetworkX_iTOC8TQrF_U_12048_12587.png EuroSciPy_2017__NetworkX_iTOC8TQrF_U_12588_13595.png EuroSciPy_2017__NetworkX_iTOC8TQrF_U_13596_16115.png EuroSciPy_2017__NetworkX_iTOC8TQrF_U_16116_18455.png EuroSciPy_2017__NetworkX_iTOC8TQrF_U_18456_20723.png EuroSciPy_2017__NetworkX_iTOC8TQrF_U_20724_24167.png EuroSciPy_2017__NetworkX_iTOC8TQrF_U_24168_32399.png EuroSciPy_2017__NetworkX_iTOC8TQrF_U_32400_33143.png EuroSciPy_2017__NetworkX_iTOC8TQrF_U_33144_33503.png EuroSciPy_2017__NetworkX_iTOC8TQrF_U_33504_36647.png EuroSciPy_2017__NetworkX_iTOC8TQrF_U_36648_38171.png EuroSciPy_2017__NetworkX_iTOC8TQrF_U_38172_38315.png EuroSciPy_2017__NetworkX_iTOC8TQrF_U_38316_38687.png EuroSciPy_2017__NetworkX_iTOC8TQrF_U_38688_42431.png EuroSciPy_2017__NetworkX_iTOC8TQrF_U_42432_42647.png EuroSciPy_2017__NetworkX_iTOC8TQrF_U_42648_48767.png EuroSciPy_2017__NetworkX_iTOC8TQrF_U_48768_54551.png EuroSciPy_2017__NetworkX_iTOC8TQrF_U_54552_56879.png EuroSciPy_2017__NetworkX_iTOC8TQrF_U_56880_58523.png EuroSciPy_2017__NetworkX_iTOC8TQrF_U_58524_58619.png EuroSciPy_2017__NetworkX_iTOC8TQrF_U_58620_58919.png EuroSciPy_2017__NetworkX_iTOC8TQrF_U_58920_58991.png EuroSciPy_2017__NetworkX_iTOC8TQrF_U_58992_59603.png EuroSciPy_2017__NetworkX_iTOC8TQrF_U_59604_59723.png EuroSciPy_2017__NetworkX_iTOC8TQrF_U_59724_62819.png EuroSciPy_2017__NetworkX_iTOC8TQrF_U_62820_63191.png EuroSciPy_2017__NetworkX_iTOC8TQrF_U_63192_64811.png EuroSciPy_2017__NetworkX_iTOC8TQrF_U_64812_65603.png EuroSciPy_2017__NetworkX_iTOC8TQrF_U_65604_71351.png EuroSciPy_2017__NetworkX_iTOC8TQrF_U_71352_71411.png EuroSciPy_2017__NetworkX_iTOC8TQrF_U_71412_74255.png EuroSciPy_2017__NetworkX_iTOC8TQrF_U_74256_75647.png EuroSciPy_2017__NetworkX_iTOC8TQrF_U_75648_75755.png EuroSciPy_2017__NetworkX_iTOC8TQrF_U_75756_75803.png EuroSciPy_2017__NetworkX_iTOC8TQrF_U_75804_80963.png EuroSciPy_2017__NetworkX_iTOC8TQrF_U_80964_82355.png EuroSciPy_2017__NetworkX_iTOC8TQrF_U_82356_82799.png EuroSciPy_2017__NetworkX_iTOC8TQrF_U_82800_83891.png EuroSciPy_2017__NetworkX_iTOC8TQrF_U_83892_87179.png EuroSciPy_2017__NetworkX_iTOC8TQrF_U_87180_87527.png EuroSciPy_2017__NetworkX_iTOC8TQrF_U_87528_90155.png EuroSciPy_2017__NetworkX_iTOC8TQrF_U_90156_91235.png EuroSciPy_2017__NetworkX_iTOC8TQrF_U_91236_93335.png EuroSciPy_2017__NetworkX_iTOC8TQrF_U_93336_98027.png EuroSciPy_2017__NetworkX_iTOC8TQrF_U_98028_101015.png EuroSciPy_2017__NetworkX_iTOC8TQrF_U_101016_102035.png EuroSciPy_2017__NetworkX_iTOC8TQrF_U_102036_103895.png EuroSciPy_2017__NetworkX_iTOC8TQrF_U_103896_104531.png EuroSciPy_2017__NetworkX_iTOC8TQrF_U_104532_105647.png EuroSciPy_2017__NetworkX_iTOC8TQrF_U_105648_106823.png EuroSciPy_2017__NetworkX_iTOC8TQrF_U_106824_106979.png EuroSciPy_2017__NetworkX_iTOC8TQrF_U_106980_109163.png EuroSciPy_2017__NetworkX_iTOC8TQrF_U_109164_109211.png EuroSciPy_2017__NetworkX_iTOC8TQrF_U_109212_110855.png EuroSciPy_2017__NetworkX_iTOC8TQrF_U_110856_111155.png EuroSciPy_2017__NetworkX_iTOC8TQrF_U_111156_113267.png EuroSciPy_2017__NetworkX_iTOC8TQrF_U_113268_113351.png EuroSciPy_2017__NetworkX_iTOC8TQrF_U_113352_113567.png EuroSciPy_2017__NetworkX_iTOC8TQrF_U_113568_113843.png EuroSciPy_2017__NetworkX_iTOC8TQrF_U_113844_115571.png EuroSciPy_2017__NetworkX_iTOC8TQrF_U_115572_123983.png EuroSciPy_2017__NetworkX_iTOC8TQrF_U_123984_124955.png EuroSciPy_2017__NetworkX_iTOC8TQrF_U_124956_125483.png EuroSciPy_2017__NetworkX_iTOC8TQrF_U_125484_126119.png EuroSciPy_2017__NetworkX_iTOC8TQrF_U_126120_126443.png EuroSciPy_2017__NetworkX_iTOC8TQrF_U_126444_127295.png EuroSciPy_2017__NetworkX_iTOC8TQrF_U_127296_127475.png EuroSciPy_2017__NetworkX_iTOC8TQrF_U_127476_127523.png EuroSciPy_2017__NetworkX_iTOC8TQrF_U_127524_127667.png EuroSciPy_2017__NetworkX_iTOC8TQrF_U_127668_127943.png EuroSciPy_2017__NetworkX_iTOC8TQrF_U_127944_129239.png EuroSciPy_2017__NetworkX_iTOC8TQrF_U_129240_129287.png EuroSciPy_2017__NetworkX_iTOC8TQrF_U_129288_133415.png EuroSciPy_2017__NetworkX_iTOC8TQrF_U_133416_136775.png EuroSciPy_2017__NetworkX_iTOC8TQrF_U_136776_136871.png EuroSciPy_2017__NetworkX_iTOC8TQrF_U_136872_137087.png EuroSciPy_2017__NetworkX_iTOC8TQrF_U_137088_137963.png EuroSciPy_2017__NetworkX_iTOC8TQrF_U_137964_138615.png
Okay, so before we start there are let's look at the structure of the tutorial. Like every notebook has two versions, one is exercise and the other one is lecture. So exercise is a more hands-on version, it's like you have to write code in the exercise one and if you are tired and so basically if you are feeling like this, so you know you can just go through the lecture with me and if you are in mood so you know you can go through the exercise notebooks and actually write code. So okay, is everyone set up? Any issues? Okay, so let's start network analysis with Python. So first question, what are networks? What is a graph? So like okay, so some issues with the, yeah. So a graph or a network is basically a way to symbolize link data. So like the red dots there are nodes or vertices and the lines joining them are known as edges or like links or anything like that. So what are some examples that we can think of? Like any real world network data, anyone? Yep, train station and the connections between them. Any other example? Yep, Facebook, Twitter, these are like social networks. Sorry? Yes, worldwide web. So these are a bunch of interesting examples. The first one is a transportation network. It's like if there is a flight between two airports, there's a link there. The second one is, I think it's like over the trade counters, derivative markets, some financial thing and it's like, it's a network of that and the third one is the Facebook's worldwide social network. Like it's the connections between all the friends on Facebook. So in this tutorial, first we'll go through network X. It's a Python package to do network analysis and model network data. Like a very quick intro to network X and the API of network X and then we look at three real world data sets and three real world applications of network analysis. So one of them is epidemics and spreading of diseases and how people die and speaking of death, then we'll talk about Game of Thrones and do a network analysis of Game of Thrones. And the third one is USA Put Dataset. So we'll try to figure out what's happening there. So let's start with an introduction to network X and graphs. Everyone has opened the first notebook, introduction one. If you want to code, you should open introduction notebook. So it's like pretty trivial API. It's like how to create a graph. It's like GNX graph and import network X is the usual way of importing it. And so add node will add and note to this graph object. And there are multiple types of graph objects. There is graph, the standard basic one. Then there is digraph, multidigraph and multigraph. So a digraph is directed graph, any examples of a directed real world graph. Anyone? So what's the difference between a directed graph and a graph? Does anyone know that? Yes. So if there is a connection between A to B in an undirected graph, that means there is a connection between B to A2, but that's not the case with a directed graph. So any examples of a directed graph, a real world example? Sorry? Yes, control flow, control flow diagrams and Twitter because if I follow Jennifer Lawrence, he doesn't follow me back. We know that. So just type. Yes, sir? Sorry? Yeah. NetworkX allows that, but the definition, it depends upon, it depends on the user. If you want to have a simple graph, shouldn't have loops, but NetworkX allows that. So there are different ways to add nodes, like you can use add node and add nodes from and how to access nodes, g.nodes. And people who are using NetworkX, NetworkX 2.0 will see node view and people who are using, if you do pip install NetworkX, it will, right now it will install the version 1.11 and that's okay, but this is the new one. So we have views now instead of basic list and dictionary representation. So we have a lot of generators in NetworkX. It's like a path graph is, it will give you a path between, it will map a path between 0, 1, 2, and 3. So there's an edge between 0 to 1, 1 to 2, and so on. And then, and one of the good things about nodes in NetworkX is it can be anything. It can be any hashable object. You can have integers, you can have strings, you can have tuples, you can even have another graph object as a node in graphs. So like if we do g.add node h, it will add the node, it will add the node graph h as a node. So like if you will see like there's a graph object in nodes now. So let's look at the second part of a network edges. So like as nodes really reveal, it's just add edge and you know, that's how it works. And you'll get an edge view if you do g.edges. And then you know how to calculate the number of nodes. So like there are different ways of doing that, there is an inbuilt method. You can calculate the length of the graph or you can calculate the length of the list that returns with g.nodes and g.edges. And just like you can add nodes, you can remove nodes from the graph. So like, you know, little bit of stuff. So okay, so let's start with something. So Eldos ReniGraph is basically a random graph model generator. Like if you do like, basically the first argument is the number of nodes you want. The second argument is the probability of having an edge for every node with another node. So it's like if you have a probability of 0.3 in 10 nodes, this is what the random graph, the Eldos ReniGraph generator will give you out. So like if we change the probability to like 0.1, you'll have a more sparse graph. And if you like make it 1, you'll have a complete graph. This is known as a complete graph that is like all nodes are connected to each other. And this is one of the ways to visualize the graph, the most obvious one to actually show how it looks like. And the other one is to use matrices to visualize a graph. So in this, sorry, so in this graph, the white spots show if there is an edge between node 0 and like 0 and there is no edge between 0 and 0 because there are no self loops in this graph right now. So if there is an edge between like 1 and 2, then it's white. So let's change a graph. Make it 0 point. So like you'll see the representation changes. And the interesting part of network analysis comes in when you can add weights and attributes to the edges and networks. So network X lets you do that too. Like you know, you can just pass in a parameter as weight and you know like whatever you want to. And to access nodes with the attributes we need to pass in the argument data is equal to true. And the G.nodes will just give you the nodes and G.nodes data true will give you the attribute to like we have added time in this previous cell. And network stores graphs in a dictionary underneath. So there are ways to access those graph dictionaries too. And it's basically a dictionary how you operate on a dictionary. So a quick warm up exercise. So we have created this graph and we have added edges from this list which is basically like the starting edge, the ending, the starting point, the ending point and like suppose like the price of a ticket between those two cities. So the exercise is to find the edge with the highest weight. A quick warm up exercise. And in that way you can run the committees who have stayed off the nodes may have adopted Let me know if anyone is done and tell me the answer to. Anyone can do it. Choose with the piece of code here. If you do g.edges. It will return you an edge data view of tuples of the first node, the second node and the attribute dictionary. If you pass just g.edges, you will get only the edges, not the attributes of the first node. Let's start to understand some dynamics of a network. Let's draw it out. When we have a network, we need to know which of these nodes do you think is an important node in a network. If I remove that node, it could break the structural integrity of the network. Which node do you think is that? How did you come to that answer? Any more guesses? One of the most naive ways of figuring it out is just calculating the neighbors of a node. That is called a degree of a node. The higher the number of neighbors, the more influential the node is in the network. As you pointed out, if we took out 7 in this network, it would break the network. There are different ways of approaching this problem, how to find the most important node in a network. There is no right way to do that. That way is called between a centrality that we have seen in some time. Let's first talk about degree centrality. Degree centrality is just a fancy name for a normalized degree of a node. You calculate the degree of the node and divide it by the total number of nodes it can connect to. That will be n minus 1, where n is the number of nodes in a network. Let's calculate the degree of this network. Degree centrality of this network is not the top of the first five. That's there. There are a lot of other methods like between a centrality, flow centrality, page rank. We will have a look at them. This is our first data set. This is the collaboration network of a general relativity group on the archive. If two people have published a paper together, then they have an edge between them and where nodes are the authors. If four people have published a paper together, there will be a complete graph between those four in the larger graph. Let's import that. Let's check out the number of nodes and number of edges in this network. There are 5200 authors in this network and around 49,500 links between them. Let's see what we can do with this. There are a lot of ways in networks to figure out what is the degree of a network. One of them is to just do the graph object and call the function degree on it and pass in the node. I just randomly chose 22504. It's an author in this network. It is connected to 33 other authors. Let's do other short exercises. In this exercise, we have to create a list of degree of node, like two tuples and find the node with maximum degree. Let me know the answer if anyone's done. Let's see what we can do. Let's see what we can do. It's one of the reasons for that is network is written in pure Python. It's pretty slow. It's more of a prototyping tool than working with large datasets. If you really want to work on large datasets, move away from networks or use something like iGraph or GraphTool. The core of iGraph and GraphTool is written in C++. I didn't get your question. Gefi is the best software for graph visualization according to me. It was never meant to be a visualization tool. Gefi is a standalone application. Anyone found the highest degree? We have an input method called degree. Let's check it out. That's the right answer. Let's have a look at the degree centrality of the author's graph. The key is the node and the value is the degree centrality of that node. Let's go to another exercise now. We have to plot the degree centrality of the author's graph. We have to plot the degree centrality of the author's graph. You should end up with something like this. It has a very heavy distribution. Let's take a D-tool and go back to Eldos and iGraph. Let's plot the degree centrality of Eldos and iGraph. This is a very different graph than what we got from our archive graph. As you can see, it peaks at around 0.30. We passed in the probability as 0.3. The probability of creating an edge between a node and every other node is 0.3. The degree centrality peaked at 0.3. It works for every value, not just 0.3. I can show you that. 0.7. As you can see, it follows a normal distribution when it's creating the graph. The problem with Eldos and iGraph is that it cannot model real-world data. When you don't have access to real-world data and you want to create a synthetic data set, you need something better than Eldos and iGraph. In 1999, Barabasi and Elbert came out with their Barabasi-Elbert random-graph generation model. When you look at this, the degree centrality matches. Let's plot both of them. It's more closer than the Eldos and iGraph than the Barabasi-Elbert graph. There is another called PowerLockLusterGraph. It's just a variant of Barabasi-Elbert graph and it also follows a similar distribution underneath. Let's come back and let's have a look at connected components of a graph. Let's create a random graph again. In this graph, you can see that we have three different components. If I am somewhere in 7 or 8, I cannot go to 1 or 4. This helps when you're planning to make a road network. If those are cities, you need to have a way to go from 7 to 6. You can't just keep them there. We have a way to calculate that and this is the connected components of the authors graph. As we can see, we have this one lone wolf here who doesn't like to work with anyone else and only publishes alone. Maybe something like that. A lot of people that work with each other don't collaborate a lot but majority of them, this is the biggest component of this graph. They collaborate with each other. Let's create subgraphs of this graph where every graph is a component. If you will see the length of the first graph in this, that's 4 and 5. Graphs is a list of graphs where every graph is a subgraph of our original authors graph and it's a component. If you try to find graphs, the 10th subcomponent, we have two components of this graph. Not exactly components but we have two cliques here and cliques are structures which have complete graphs as their subgraphs. There are three nodes on the left and six nodes on the right where six nodes form a complete graph and three nodes form a complete graph. Maybe you can infer something like those six people published a paper together and a person from that group published a paper together with these two people. Another important application is graph traversal. Suppose I have to go from 4 to 6. It's not possible. Finding shortest path in a network is one of the de facto things that you do when you start a network analysis. There are algorithms implemented in networks to do that. When you pass in a normal graph, it basically uses a BFS to solve that and if you pass with weights, it will use Dijkstra underneath. You don't need to worry about that if you don't know what it is. It will just give you out the picture. Let's move on to another exercise. How many of you have heard about six degrees of separation? Can anyone tell me that? Anyone? I can reach anyone in this world by just jumping six steps of friendship and connection. The number of L-dOS is given to co-authors of L-dOS. If you have published a paper with L-dOS, you get the number 2. If you have published a paper with someone who has worked with a person, you get the number 2. Let's find the 22504 number of this authors graph. If there is no connection, that means that the author is not in the bigger subcomponent of authors graph, then you can give it the number minus 1 and then plot the histogram of this. Let's find the 22504 number of this authors graph. Let's find the 22504 number of this authors graph. Let's find the 22504 number of this authors graph. Let's find the 22504 number of this authors graph. Let's find the 22504 number of this authors graph. Let's find the 22504 number of this authors graph. Let's find the 22504 number of this authors graph. Let's find the 22504 number of this authors graph. Let's find the 22504 number of this authors graph. Let's find the 22504 number of this authors graph. This is one of the ways of doing it. There are probably more and better ways of doing this too. This is how I did it. If you ignore the minus 1 bar, you can see that this is peaking at around 6. I'm not saying that this will prove that theory, but maybe this is something interesting. This is just for one node in the network. If you find the average shortest path from this node, it comes out to be 5.61, which is less than 6. This doesn't prove that theory, but it's just a thing we can think about. Facebook actually tried doing this and ran it on their full friendship network. Can anyone guess what was the degree of that? What did they find? They found it's 3.5. This is their distribution. It's speaking at 3.5, speaking at 3.4. Earlier, you could be able to see your own degree or degree of separation too, but they have removed it. Mark Zuckerberg has 3.17. It means that in three steps, Mark Zuckerberg can reach any person on Facebook. Three friendship steps. I had a degree of 3.94 or something. Let's get back. Let's talk a little bit about directed graphs. Does anyone know this visualization? What does it represent? This is the representation of the PageRank algorithm, which was named after Larry Page, the person who made Google, co-founder of Google. This is what early version of Google used to index the web. As you can see, this fellow C here, it only has one incoming connection, but still the importance of this in this network is pretty high. As compared to B, which has a lot of incoming connection, that makes sense because a lot of people are citing B whenever they are talking about anything. B has a high influence on this network, but C has also high influence because it is cited by B. This is the basic intuition behind PageRank algorithm. Let's have a look at that. As we had nx.graph, we have the diagram object. It is the same thing, but the difference here is if you try to print this dictionary, it will return you empty dictionary because we did not add any attributes or weights. But if you try to do g2 to 1, it will give you a key error because there is a connection between 1 to 2, but there is no connection between 2 to 1. That is it. To find if it is directed or not, there is g is directed and that will give you a true. When you draw it, this is a makeshift implementation in networks that it will create a bold line there. Let's calculate the PageRank of this graph. We can see that 2 has the highest one. If we look at the graph, we understand why because everyone is pointing towards 2. Let's add a new edge. Every time you draw, it will draw randomly. You will have different representations every time. What do you think this will have an effect on the PageRank of this graph? It won't affect it a lot because it will just add a new edge to 6 and it will increase the PageRank of 6. But what happens when you add this? When you add an edge from 2 to 8, you will see that it increases the PageRank of 8 substantially. It is more than 2 right now. This was the basics of networks and how to study the dynamics of networks. Now let's move on to the application of networks. Has anyone seen this picture before? People who don't watch Game of Thrones just treat it as just a fictional data set. People who do watch Game of Thrones and are behind Game of Thrones, I have tried my level best to not include any spoilers. I am sorry if there are any spoilers. I have tried real hard. There are no spoilers. This study was done by a professor at McLeister College and I have under-graduate there. This network is from the books, not from the TV series. There are significant differences there. How they have extracted this network is they have read the book. They have looked at 15 words and if there are two characters that are mentioned in 15 words, then they have an edge between them. I know this is not the best way of doing it but it still makes some sense. So let's have a look. You can look at their blog. It is called networkofthrones.wordpress.com. They just uploaded season 6 network analysis. Let's start. You should have all this code already. There are two Game of Thrones lectures and Game of Thrones exercise. Lecture one is the easy one. Exercise, you have to write the code. They have made an internal mapping to all the nicknames. A lot of manual work was also done there. Thanks to them, I am doing this. This is a weighted network. If there is more than one interaction between two characters, you will have a weight. Between Jamie Lannister and Adam Marbend, there are three interactions. The weight is three. I have the data for the first five books. Let's start with the first book and have a look at that. Let's find the most important character in Game of Thrones. Let's look at Jamie Lannister because why not? He has a lot of connections in the first book. Let's calculate the length of this. 29 connections in the first book. Let's see in the fifth book. 10 connections in the first book. 64 in the fourth book. Maybe he is an important character in the fourth book but not in the fifth book. Let's calculate the degree centrality of this. I have chosen the top 10 ones. This is for book one. You have a question? In book one, Edard Stark is an important person here. We all know what happens there. Johnson is also there. This is the top 10 of book one according to degree centrality. There is no one right measure. It depends on what you want to get out of the measure and what you want to study about the network. Degree centrality is just one of them. Let's plot a histogram of it. This follows the real world network phenomena. In mathematical terms, it follows the power law distribution. We are right. Mr. Albert Barabasi was right. A quick exercise. In networks, there is only degree centrality but there is no thing called weighted degree centrality. Let's implement that today. Weighted degree centrality is basically the weighted degree divided by the total degree that it could have, a node could have had. Weighted degree is calculated by adding the degree of all the edges a node is connected to. Let's implement that function. Then we will see that adding weights to the degree centrality measure, does it change who is more important in this network? If you are too tired to write the code out, you can just copy it from the lecture notebook and try running it. Let's see. Let's see. Can everyone please open the airport exercise notebook and just run the first five cells? It can take a couple of minutes to load the data set. The airport exercise notebook and then you can go back to game of thrones. Let's see. Let's see. Let's see. Let's see. Let's see. Let's see. Let's see. Let's see. Let's see. Let's see. Let's see. Let's see. Let's see. Let's talk about betweenness centrality. You can break apart the network or you can break apart the bottom link of the network. Not necessarily the nodes of the network but a lot of other components of the network. Thanks to network X we have that too. If you look at this network, the nodes which are between the path graph between these two components, the degree of this node is like two. If you break apart any of these nodes, you are going to break apart this network because these two won't be connected anymore. If you calculate the betweenness centrality, the betweenness centrality of these nodes will be way higher than the degree centrality of these nodes. Even though the degree of these nodes is like three for this, four for this, is higher than the degree of this node. Let's check the betweenness centrality. Again, we get edas tag as the most important character in book one. Now we have weighted betweenness centrality. We need to pass in the parameter weight is equal to the attribute in our network that is weight. Let's check out that if that makes a difference. Yes, it did. According to weighted betweenness centrality, Robert Baratheon is the most important node in this network. If we remove Robert Baratheon, we are kind of breaking up the network. That doesn't mean that it will definitely break up the network but it will decrease the connectivity of the network. This is the basic intuition behind betweenness centrality. Let's actually calculate the page rank of this too. Let's first calculate the unweighted page rank. I know why it's numpy. But page rank numpy is a numpy implementation of page rank. We can just do page rank two. We have tried out three methods till now and two of them tell that edas tag is the most important character in this network. Maybe it's true. I'm not sure. Let's check out the weighted page rank. Edas tag again. These are the most used measures to calculate importance. Edas tag is the most important character in book one. Maybe it's true. Let's find if there is a correlation between these techniques. These are three different techniques that take into account three very different attributes, not attributes structure of the network. Let's find if there is a correlation between these techniques. Like a hint you can use correlation, this function to actually, that's the answer, that's not the hint. We can use pandas to find the correlation of this network of these three measures. Basically I'm creating a pandas data frame and where each column is one character and the first row of each column is the page rank of that character, weighted page rank. The second is pretty mean centrality and the third row is weighted centrality, the one which we implemented. If you weren't able to implement it, just use nxtotdegree centrality. That's okay too. Let's do that. Let's take the transpose of this because there is an inbuilt method to calculate correlation. This is the correlation matrix of these three methods. What can we infer from this? They are more or so high, they are related because with page rank and degree centrality, there is a correlation of 0.94. That's a pretty high correlation. There is a less correlation between degree centrality and between a centrality. That example showed us why the barbell graph. That's a matrix and this will be one because it's like 0 correlated with 0 and that will be one. Till now we have been analyzing the first book. What about the other four books too? When we add time to a network, the fancy name of adding time is known as adding temporality to the network and then we call it temporal networks. Then there is another branch of network analysis called temporal network analysis and people have written books on it. You'll just have a very quick intro to that. In this, I've created a new list where it is tracking the evolution of weighted degrees centrality of each network over the five books. Then we create a data frame and suppose if the character is not present in some book, then I've used fill NA as 0. Now this data frame is pretty self-explanatory. The columns are characters. We have like 796 characters over five books that these people were able to capture and five columns are the five books. Apparently, like AIM and Targaryen, the Dragonite was only mentioned in the third book. We don't have any measures for that in the first, second or the later books. In this bit of pandas, magic or trickery or whatever you would like to call it, I selected top 10 characters on the basis of their maximum value in the column. I took a max of their column first and then took the top 10 out of that. We have Edard, Starks, or C. John Snow. Let's look at the exercise now and this one is about plotting the evolution of the weighted degrees centrality over the five books of these characters. I was able to get this one-liner function and this is the plot of weighted degrees centrality and evolution over the five books. You can pretty much see some obvious trends if you're familiar with Game of Thrones. In the first book, Edard Stark is at the top and the graph pretty much dies out and then in the fourth book, Cersei Lannister is at the top. In the fifth book, John Snow rises from the death to come at the top. This was for weighted degrees centrality and now let's have a look at the same graph but of betweenness centrality. Let's see if we find anything interesting or surprising or anything like that. Here's the graph and at the top we see in the fifth book, it's Tannis Baratheon and it's a pretty big climb from the third book. He's pretty important in the fourth book too and in the fifth book too and there's a big difference. But in weighted degree centrality, there is no mention of Tannis Baratheon in the top ten. What's the reason for this? In betweenness centrality, he's at the top and in degree centrality, he's not even in the top ten. Just like the barbell graph, apparently if we take out Tannis Baratheon from the network, it will break apart the network and apparently he's holding a lot of people together. This is not me, this is Python. This is Python saying. That is strange, yes. So let's talk a little bit about community detection in networks. The intuition behind this is finding similar nodes in the network. It's not necessary, finding the subcomponents, it's like absolute community detection. There are communities, you can actually see them. But suppose there is a complete graph of ten nodes and a complete graph of four nodes and you connect them. So you can mark them as two different communities. They're not components because they are connected, but they're two different communities. And there are a lot of methods of finding that. One of them is Luan community detection. And so we're going to use that and see what happens on book one. So as you can see, this plot is pretty hard to decipher. And there are not a lot of good tools in Python ecosystem to make it better. So this picture was, the different color reflects different communities in this network. And this picture was made by Gefi, I guess. And bigger the font, bigger the influence of the node in this network. And the influence is calculated by page rank in this. Let's go back. Okay, so communities. So it's basically a different, it's hardly visible, but it's like different colors of gray, I guess. And we have different communities. So let's actually look, have a look at different communities. So when we ran the community detection algorithm, it's not actually implemented in NetworkX. I've actually provided you a folder community, which has the code and with the standard alone package, but it doesn't work with the latest release of NetworkX yet. So if you look, so I've created a dictionary and if you'll have a look at that. So it's like we have 12 communities in this. I don't even remember these characters. So let's, so there's this function called nx.subgraph. And it takes in a graph and a bunch of nodes and it will give you, it will give you the subgraph of the graph and where all other nodes are absent. And the edges of those nodes to this network is also absent. So this is like the first component. And like we can have a look at the other components of the graph too. So something like that. So there's this term called density of the network and it's pretty much finding like, if the network is dense, it will have a density which it's like towards one and if it's sparse, it will be like towards zero. No rocket science there. And so like if you find the density of the first book, like just the first book, it's like 0.039 something. So it's a pretty sparse network. You don't have a lot of connections between nodes. But if you find the density of a community inside this network that we got from Luan, a detection algorithm, then it comes out to be like 0.2. It's like some seven times more than the density of the original graph. So like this gives out a brief intuition behind that what we did with community detection. And so one more exercise. So find the most important node in the partitions. Like by partitions, I mean communities in this. According to Pesrang degrees, entirely and between us, entirely of the nodes. The answer should be something like this, like community is the key and the value is the most important node in that community. According to Pesrang or degrees, entirely or between us. Okay. Okay. So like this is my code for it. And again, it's pretty, I'm pretty sure this is not the best code for this, but it works. And so let's move on to another application now. And so what should we do first? Let's have a look at the airport exercise. Yep. Okay. Yeah, so how do people do 0.85? 0.85 is like the standard parameter that is taken and to find the good one is you have to test it out yourself and it depends on the kind of network you have. And it depends on that. And I haven't really tested it a lot. So I am not the best person to answer that. But So like if you open the airport exercise notebook. So in this, the data set is from five years 1995, 2005, 2010 and 2015. And if you look at the CSC file, there are four columns. The first one is like from airport. The second one is to airport. The third one is I guess here and the fourth one is the carrier of the flight. And so there's a difference between this and a normal airport network because this is the route network. It's like if there is a flight between New York and San Francisco by Delta Airlines and that flies on different time on like every day. So it count it will count it as like, you know, seven different flights. So that is the problem with this data set. You need to solve that. But I haven't done anything. It's just like a raw data set. So let's have a look. So I've created five directed graphs because a flight from a point A to point B doesn't mean that plane will fly back to point B to point A. It can go to point C. So we have five directed graphs for like each year. And let's have a look. So let's calculate the page rank. So first thing first thing you want to find out in this network is which is an important airport in this network. If we close down that airport or if you know like some natural disaster happens at the airport, it's like it could shut down the network. Which airport is that? Let's have a look by the tools and measures we have seen today. So according to page rank and this is the weighted is there are no weights. So it doesn't really matter. So and the top list is the top 10 airports according to page rank. And like if you if you're familiar with the airport codes, it's like the top like the top ones that are supposed to be like, you know, like Atlanta or Chicago or New York or something. You would expect something like that. But the first one is ANC. Does anyone know what is ANC? Yes, Anchorage. So Anchorage is this place in Alaska. It's like it's not even in mainland US. It's like just far away. So why is this the most important network in the node? Most important node in the network. Any guesses? Why is Anchorage the most important node? It's not a big airport. It's not a big city. Maybe yes. Yes, but yes, like that is that is one of the reasons that people give out for this for this anomaly in the data set. And like But they don't land there. They just go over Alaska. So it's yeah. Other places you can go to other different routes. Yeah, that basically adds up to that point and it will like this is what I think the biggest reason is but there are other other things out there also that people don't people have other problems with this data set to and so so basically there are a lot of regional flights in Alaska. That only starts from Anchorage and and so basically all those small towns in Alaska are connected to the mainland US only with through their flights with Anchorage. So if you break out Anchorage from this network, you're removing all those two. And so this is one of the reasons that you know like it gives out a very high page ranks score and all the major airports have to fly to Alaska. So it adds to the to the page ranks score of it as we like saw in the in the in that pictorial represent representation. See at only one incoming edge, but it from it was from a major player that is B. And so in that case, Alaska will have a lot of flights as as you mentioned it will have a lot of direct flights that are coming towards Alaska, which would go to Anchorage and then it is connected to a lot of regional airports. So according to a way that this is an important airport in this network in this data set. So let's calculate the between us in reality because why not we know how to do it and degrees and I'll do it too. It took some time but we have the answer again with between us in reality it's Alaska again. So that that further proves our point that it is if you remove Alaska it will break up the it will break up the airport network. So like so that's there and but in degree centrality it comes out to be like the first one is like I guess Atlanta the second is Chicago here. And like I think these are like these are like mainstream important airports and because degree centrality just is just about the number of connections you have. So like that makes sense because like Atlanta is one of the busiest airport in the world so it will have a very high degree centrality when when you look at the US domestic sector. So there's this really nice blog post a few are interested why anchorages and the structure of the network is one of the reasons and there are other reasons to. So again like in this line. So we have the carrier data I mean the data set is like really huge and I had to trim down the data set so I just chose the I just had an option to choose in like one attribute and I chose carrier. I don't know why but let's see. So so what we are going to do is we are going to plot the graphs of like number of routes of the top five airlines. And let's have a look at that over the years like like adding the time time thing to this. So like so the most interest like this is a very broken graph because it's like just like five distinct years. The actual data set is available from 1990 to 2015. So like you have 25 years of data set and that gives out a more prettier graph than this. But because of like data constraints and we don't have a lot of time to time to compute it. So I'm dealing with this. So like if you look at this orange line this is basically delta airlines and you know like in the past 15 years it has grew a lot with the number of routes not flights. So that is the important distinction here. And so again like a bit of pandas to find like it's basically to find the hubs of a nice way like from from which for which a line which is the most used airport like for like this is for for delta airlines. It comes out to Atlanta and I guess MSP is Mississippi and if you'll actually check the Wikipedia pages of the hubs and like it not all of them matches but you know it somewhat matches according to this data set. And if we calculate for United Chicago and Denver and Washington and New York. So these are the one that should be there and we are running out of time so you know I'll just hurry past these lights. So every shortest path length of the network. So what would what happened. So we have a error that is graph is not weekly connected connected. So it's weakly connected is a directed graph term and as this is a directed graph. So if if the graph like if you look at the look at a undirected copy of the graph and it's not connected by not connected it means there are components in the graph. Then that is a problem and especially in this case because you don't want like couple of airports lying there which have flights between them but they're not connected to the to the other components. You can't have this but like this is there and this is like the real data set from like federal aviation authority. So what's happening there. Let's see that. So let's have a look at connected components. So if you look at if you if you go at the very last bit of this. Yes, so basically there are three components. One is the one one is the comment that the company it should be the connection the data set of all reports. Then there there are these two components this is like apparently so there's this flight which goes from a I K to a I K it goes to itself. So I wasn't able to solve the mystery of this flight but I was able to solve the mystery of SPV to SSB. So it's basically if it's a pewter recon a line and it and it's not a it's a C plane company. So it's like it just flies between these two airports and that's all so that is the reason why it's you know something like that and to make matters easier. So let's just remove remove these notes. So we have a nice connected graph and the difference between weekly connected and strongly connected in a directed graph is if it's strongly connected. It has a note should be reachable from any other node like basically they should be they should form a component but you don't have to go to the undirected copy of it. If you have to go to the undirected copy of it to get to get every knows every node as reachable then it's basically a weekly connected graph. So let's find out the average shortest path length. So can anyone tell me what could average shortest path length. It's it's it's right there in the name like can someone explain that. It basically computes the distance between any between all the all the pairs of nodes in the network and finds the shortest part between them and it will give you the average of it. So it gives out an average of 3.02. So it means that if I pick any airport in the in the data set a and like suppose a and another it would be there are only. I need to travel through only two steps to reach to that airport. Suppose there's no direct flight I could just go from a if I have to go from a to B the average number is a CDB I should be there. I don't need to take more than three flights. This is the average shortest path length and like if we plot the degree centrality and again it follows the power log graph. So like we have to not prove it like I guess this is the third data set that it does follow. So so like the Barabasi Albert model is considered to be like a seminal work in network science and this is why. And so this was actually supposed to be a very nice interesting exercise because this is a very open ended question. It's like one of the one of the nice one of the nice applications of network science. So that so we need to add new flights to this network. But like adding a flight is like there is a cost involved with it. So how can you add flights in an effective manner the minimum number of flights in an effective manner that you decrease the average shortest path length of this network. So how could we do that? So what I did is I just know like it's a very naive implementation of this is a single preferential attachment and it's part of the Barabasi Albert model. So what it does is finds the it finds the node which has the highest degree centrality and then like and I've arranged it in a sorted order. And then it finds the node the next node like it just iterates through the list and finds if there is a if there is a connection between them or not. So it will try to find the next node which next highest node which there is there is no connection and it will add a new flight. So it's like I'm trying to connect the highest central airports which are not connected yet. So does that make any difference? So like in this I think I have added I've added like around 500 edges and that is like 2% of the current edges. So like 2% of the current flights I've added new flights and this is what it gives out improvement of like 0.7%. So so as we can see this is not a good way to do that. But it's an open-ended question like if anyone would like to tackle it, it's nice question. And there are some like linear optimization ways to solve this problem. A lot of people are doing that. Well, I guess everyone is pretty much feeling like this now. So, okay, so that that's here I'll end this and if you want to go through the diseases exercise diseases notebook 2. It's just it's it's like super simple. It's just it's just some pretty graphs and you know how diseases are spreading. This can be also used to model like virus spreading on a set of routers or you know like as we as we are moving towards more IOT things. It's a serious concern to you know not to stop spreading of viruses in IOT devices and which which which are not so easy to to change or you know to update them. So this is a nice pretty little way to do that. So like these models were made in like 1920s and something and at that time, network science wasn't even there and these are now incorporated into network science to make these things. So that's it. Thank you.
the structure of the tutorial. Like every these are a bunch of interesting examples. The network analysis and model network data. Like a notebook, introduction one. If you want to code, connection between A to B in an undirected graph, any examples of a directed graph, a real world people who are using NetworkX, NetworkX 2.0 will we have a lot of generators in NetworkX. It's ReniGraph is basically a random graph model to understand some dynamics of a network. Let's network. Degree centrality of this network is not together, there will be a complete graph between more of a prototyping tool than working with cliques are structures which have complete graphs as their subgraphs. There are three nodes on the in the network. If you find the average shortest more than 2 right now. This was the basics of networks and how to study the dynamics of between these techniques. Like a hint you can use of network analysis called temporal network mainland US. It's like just far away. So why is anchorages and the structure of the network is don't have a lot of time to time to compute it. that should be there and we are running out of to the undirected copy of it to get to get every work in network science and this is why. And so not. So it will try to find the next node which people are doing that. Well, I guess everyone is incorporated into network science to make these