An Insider’s View of Graphs & Networks: Live with the R&D Team

Thank you for joining us for this live stream on Graphite Network. I'm Charles Po, one of the developer of Graphite Network. And today I want to give you my view, my inside view of Graphite Network, both on the design side as well as an implementation, and hopefully cover some applications. This talk will be essentially divided in two parts. A modeling aspect of graph and analysis aspect of graph. By modeling I mean if you take a real world network, like a road network, you want to be able to represent as a graph the actual model. And from that model you should be able to do actually the analysis compute property. And at the end you get a result which you can synthesize and interpret and bring back to your world and have a real meaning to it. And that's pretty much the way all the functionality in the system is built so around modeling and analysis. So before that, let's just get the basic on KAFR networks. So from a sample view or a graphical view if you want, a graph is just a collection of points which are joined together by lines. And those points, you know, you call them vertices and edges, right? And in this example you see actually a basic graph. This is a peterson graph with 10 vertices on 15 edges. So graphically you see a nice network connections. And in different area people have different names, right? So if you do social network analysis, right, you look at, you know, social interaction between actors. So your vertices are actors, your edges are the interactions, and in some case we call them node. And in some order you call, you know, vertex node and you call the edge links, right? And if you do a plural network or that thing, you have different type of names. So for me, pretty much when you have a network, a real thing which have a structure and a behavior, I tend to call it a network. And when you look at the model, the math aspect of it is what I call graph during this talk. So hopefully that will kind of make the distinction between the network and the graph. So in the Wolfram language, how do we actually represent the graph? So we represent a graph by a symbolic expression, which is, you know, with the head graph, after that you have a list of edges, right? So to describe the edges, we have two types, undirected edge and the rated edge. So the undirected edge you just type undirected edge U and V. So this will typeset and represent the edge between U and V. So this is a basic example where you evaluate the graph which have in this case six edges, and you get the graph. As I mentioned, we also have, you know, directed edge, which is the second type, where you have actually a connection between U and V so you actually give a direction on the way they are actually connected. And this syntax is identical to the underrated edge when you give it to graph. And you just have to, you know, write directed edge instead of undirected edge. So then you get also an undirected edge graph, which is quite simple. And so one thing you notice actually from this is that every time you actually give your graph, it actually auto visualize instead of returning a symbolic expression. This is actually a pretty good feature of the system. So you directly see actually the structure of your graph. And behind the scene we automatically try to find out what is the best way to actually display that graph. And obviously if the graphs get too big, we have a limited amount of space on the screen. What we do return that symbolic representations. And so if you want to see it, one first thing you can do is you can actually change the system option. So we kind of limited the auto visualization of the graph to a graph with vertex count less than. So if the graph have less than 1,000 vertices or 10,000 edges. So you can take this system option and modify it if you want, as well as the system option also have cache result if you use the system cache, where we actually automatically cache the result of the computation or the auto visualization of the graph, the vertex coordinate as such. But another easy way if you just want to visualize your graph is to use graph plot, right? So in this case you see that graph, which you know well, a similar graph with 10,000 edges and a thousand vertices, it actually automatically render with graph plot. So it's kind of a dense graph. And one key difference with graph plot and graph in terms of the show is that graph return an actual object graph and graph plot return a graphic, right? So this object is not computable, but you can manipulate it with, for example, show and combine graph, right? So if you take a graph and put it in show, you can manipulate it as a graphic expression. So, so that's kind of an advantage of having show or having graph plot when you want to actually manipulate them or visualize graph and just merge them and combine them. So the next thing I want to highlight essentially is that graph is actually a whole object in the Wolfram language. So that means it's atomic. So you cannot per se go and take the first part. You can ask the head, obviously we return you the head, which is graph, but you cannot actually go and take part. So what we did is that we introduced a set of functions Or a structure function to actually allow you to manipulate the graph. So in this case, I take generate the complete graph. You can check that is a graphq by graphq or you can check that is underwrited. So we have all those Q functions for you to use, but you cannot really take the first part. So if I evaluate it part tell you, oh, it's an atomic expression, I cannot go inside. But you have vertex list which return you the list of vertices and edge list which return you the list of edges. So those are kind of the two axis of function. Well, we also have actually options. Which will return you the option of the graphs. In this case, the graph doesn't have any options. And what you can actually also notice here is that you can actually take that graphical representation of a graph when you're in a notebook and just put it in your function and evaluate it. The front end automatically interpret it as a graph and the appropriate computation happen. So there's all those flexibility around the graph object which kind of make it look nice and alive in the system. So before we continue, one key thing I want to highlight is that the way you specify that you construct the graph affect actually the subsequent computations. So in this example, I just have pretty much two identical graphs where I just essentially permit the first and second edges. So here I have a 1, 2, 2 to 3, 3 to 1 and 1 to 4. So I flip them here. So the first thing you notice is that when we render them, the visualization is different. And one key thing is that when we actually look at this graph and build it, we actually collect the edges. So implicitly, the, the list of edges between these two graphs are different. So if I evaluate them here, you see that the vertex this is 1, 2, 3, 4 for the first one, and the second one is 23, 14. So the edge are called, the vertices are collected in the order they appear, and that actually affect the subsequent operations. For example, the adjacency matrix, right, which represent the connectivity of your graph, right, essentially is based on the order of the appearance of your vertices. So the first graph you have 1, 2, 3, 4 and the same for the column. And the second graph you have 23 14. And then you see that the two matrices are actually different. So the way you actually build the graph actually affects subsequent operations, even though visually they may be similar or mathematically the way you actually express them are quite identical. And that's why we have operations such as graph isomorphism to Check if the 2 graph actually equivalent. If there is a mapping which actually Preserve the connectivity for the two graphics. So this kind of one important feature, which in some case you may be confused why your result may be completely different. Just make sure to check your vertex list or the ordering of the vertices as you specify the graph. And one way, if you want to make sure that everything is exactly identical, you can actually specify the order of the vertices this way. And obviously the order of the edges will be different. But you see that the rendering actually got consistent here and the adjacency matrix will be actually identical in this case. So this is kind of one thing to keep in mind when you construct your graph and you want the subsequent operation to be consistent. Okay, Earlier I kind of talked about matrices and let's look actually at the representation of matrices here. So an adjacency matrix, right, just represent the connectivity of your graph. So we have adjacency graph to actually build your graph based on the adjacency matrix. And you can actually also extract it back with adjacency graph, as you see here. Adjacency graph return you a sparse array, which you can actually use matrix to see. Actually the structure, we tend to return a sparse array because most of the graph we have are not dense. So that's sparse enough. So sparse array is an efficient representation for sparse matrices, right? And also subsequent operation actually take advantage of that structure the statistics of your matrices. So this kind of bring us to actually the internal representation of graph, right? And obviously the graph, you know, in Mathematica is actually a data structure. And we want to actually have that data structure to be efficient in term of computation as well as in term of storage. And the way you build the graph actually affect that, as we saw first in the adjacency matrix, sorry, adjacency matrix and vertex list. But it also affect the way we actually keep it and store it. So when you build a graph with just a list of edges, by default we store it as a double linked list. So essentially we link the vertices and we link the edges together. And in the perfect world, you have actually a compact representation in memory where you can actually do the appropriate jump and connections together. But if you give a graph with a matrix and you build it with adjacency matrix, what we do internally is that we actually store the adjacency matrix. So instead of building a double linked list, we actually just store the matrix and we operate with that. And most of the algorithm, when we are going to get to the analysis part, actually take advantage of those structure and we have implementation specific for each Structure. One way to actually see what actually present here is actually by looking at the full form of your graph, which is close to the sterilization we actually do in memory are also kind of in files. So in this case, when you generate the graph and you ask the full form, you see that you have the list of vertices here and then you have the list of edges. But when you do the same with a adjacency graph, you have the list of vertices, but here you actually have the structure, the spars array, which we store internally. So that kind of will give you an idea of, you know, which structure we are using inside and you know, what type of operation may be more efficient when you do a, you know, you construct your graph with a sparse array or you construct your graphs with a double linked list. Okay, okay, so before we go, jump to the analysis, but let's just kind of go to the list of type of graph we have. So obviously we have undirected graph, and here I'm just using the edge list to specify them. We have directed graph and you see the arrow automatically appearing in the rendering. But we also support mixed graph, where you can actually give both a directed edge and undirected edge and automatically we represent it appropriately, store the right information. And down here you can actually also see that we have mixed graph, sorry, multi graph after the mixed graph. So where you can have parallel edges, so which connect actually these two vertices in between. So those are kind of this, you know, the graph coming from, you know, structure or modification of your edges, essentially. But there is also other type of graph you can actually build by adding additional information. Right? So the first type is, you know, weighted graph. So in this case you just, you know, have your graph, but you can actually add a weight to your edges and it's also to your vertices in general. But most of the time people just add weight to edges. You can reconstruct the original matrix or the weighted adjacency matrix for your graph and you can do operation on them. So several of the type of operation we have actually taken to account the weight. So for example, if you are computing a distance for your graph, you take into account if it's weighted or not, and we have different function for that. So conversely, you can also have the matrix and build your graph. So we have weighted adjacency graph. So there you have the corresponding graph from the weighted adjacency matrix. And weighted adjacency matrix can show you exactly that. So one thing you will notice here is that the original matrix, right, have Infinity as a way to specify that there is no connectivity. And when we return the weighted adjacency matrix, we actually specified with a zero, right? So this is more a design decision. We pick at the time. So when you build a graph, right, you have to kind of, especially when you have weight, you have to pick the value, which means that there is no connection between two vertices. So what that value can be. In the case of weighted adjacency graph, we went with the decision that infinity means there is no connection. So similar to when you generate a graph distance matrix, when two vertices are not connected, the distance is infinite, which is slightly different than the adjacency matrix, where if there is no connectivity, essentially you say there is a value zero between the two vertices. So that's kind of slightly confusing. But what you can do in general is that when you build a weighted adjacency matrix, you can actually specify the second or the last argument of the function. You can actually specify the default value and you will take that into account. So in this case, you see the default value is zero and there it builds actually your matrix. Okay, so that's kind of one view of the weighted graph. The next type of graph I want to talk about are the edge tagged graph, right? And this essentially comes from the fact that when you have a graph with parallel edges, a multi graph, right? So it's hard to actually distinguish, you know, the two different edges which have the same, you know, vertices. Two edges have the same vertices. This is an example here. So let's just me, if I evaluate that graph, So I have two edges here, 1, 2, 1, 2 and 2, 3, 3, 1, right? And you see that when you essentially say, okay, I want to color the vertex 1, 2 into red, we parse it. We cannot really make the distinction between the two vertices and we color them in red. So H tag actually allow you to avoid that and actually add an additional tag or kind of a descriptor to every vertices in your graph. And what we actually did is that we extended on directed edge to actually support tag. So the third argument of your directed edge and undirected edge are tags. So in this case you generate a graph with tags. So visually nothing really changed. But internally there is a tag which is associated to every edges, in this case abcd. And if you actually use H tags. So in the earlier example, you see that we have graph couldn't actually, you know, distinguish the two. But in this case H tag is actually able to distinguish both. This one is drawn with red and this one is Blue. So H tag is actually what you want if you want to play with multigraph and make sure that you can actually distinguish or pig point every edges which are parallel. Okay, so the next additional, the next more interesting part also in graph is the annotations. So in the language expression in general, you might have a form head argument followed by options. But graph is actually an object, right? So one is that we want to be able to modify it, right, and essentially add more property. So what we introduce essentially is the concept of annotations where you can actually take your graph and annotate every part of your graph. You can annotate the vertex, you can annotate the edge. And what we did is that, you know, we introduced what we call the standard annotation, which map exactly to option in your system in every expression. So in this case you have a graph and this is a set of options you add, which are kind of considered as standard annotations. So if you evaluate your graph, you will get that. And if you actually use wrapper, and you saw an example earlier, what we essentially do is that we take that and map it back into annotations, right? So everything in the system, when you get out of the topological structure of your graph, right, just directly map into annotation. And that's the way we actually store all the information you actually add to your graph. And annotation actually allow you to make that link from a network real world object which have a behavior to the abstract graph, right? Which have both the mathematical topological structure as well as additional metadata you want to manipulate. So this was an example of the spatial wrapper. And here there is an, you know, this is an example of a user defined annotation. So you can add your own annotation to graph, to the whole graph, obviously to vertex and edges. So in this case I add annotation to the edge 1, 3. So I get my graph. So let me call that graph G and I can obviously take that graph and say, okay, what is the notation value associated to the edge 1, 2, 3? You get there, you get the strength and it's 10. You can obviously take it back, manipulate it. In some case, some algorithm will actually use it automatically. Okay, so that was kind of review of the fundamental object. We have graph and the different behavior and hopefully kind of give you an idea of the implementation and structure we have behind. So let's move now to the modeling part. As I pointed out, right? All our functionality pretty much result from those two aspects, modeling and analysis, right? So modeling allow you to Actually take the data you have in the real world and build the abstract model the graph in the system. So this is kind of the different type of model you can find from computer science, physics, economy and such. Those are different type of graphs. So I won't spend time on this. So let's suppose you have some data in this case. This is a social network from the slash dots, which is technology website. So you can use import to actually import that data. This is a purely test file and you can actually just take that and restructure your data to generate a graph. And there we go. You have a graph which have about 100,000 edges. Search for vertices. So one way to actually build graph or model graph in the system is by using import and export, where you can actually take those file depending of your, you know, the structure of the data and build the graph out of it. But we also support, you know, standard graph format, graphlet dot, graphml, JXL and such. So you can just directly import those type of file form, I mean files as well as export them and generate those type of files. The next type of collection of data or type of graph, you have a theoretical empirical graph, right? So if you are more mathematically inclined, there is a set of standard graph you are used to. So graph data is a vast collection of those type of graph. I think it contain about more than 6,000 standard graph as well as property. So you can just use graph data and give the name of your graph. There is downloading the data from our server remotely and you get the graph and you can start directly to work with it. We also build a collection of empirical graph which are most common when you do social network analysis, for example. So this is kind of the connection of the Florentine family and you can take that graph and directly manipulate it. So what we try to do is to provide you both with empirical graph and theoretical ones. So you can easily start to play with graphs. So the other set of way people actually build graph are from, you know, distributions, right? Similar to when you do probability and statistic. So one standard type of models for graph is the Erdos Remi models, which is a uniform distribution of graphs. So we introduce graph, random graph as well as a bunch of distribution, I think about 1, 2, 3, 4, 5, 6 of them which allow you to actually generate those models. So here you have random graph, you generate a uniform graph. So if you keep evaluating it as any other function, it will generate you different type of graphs. So we also have the Gibbert model which is based on The Bernoulli graph distributions and we have the degree graph distributions. So you can essentially generate different type of graph and do your analysis on it. One interesting thing we added is graph property distribution. It kind of allow you to actually make the jump from those graph distribution to actually standard graph in statistics, which essentially map to a value. So this is an example where you take, you know, graph property distribution and you try to look at the edge count of those those type of graph. And you know, there you specify that you are your variable G follow the Bernoulli graph distributions. So if you evaluate it, it tells you actually what is the distribution of the edge count. So the number of edges, what follows the distribution. So for a Bernoulli graph, the distribution of edges follow a binomial with some specific parameters. And obviously for this type of graph you can get this type of closed form, but in general it's not possible. So this is an example where you look at the was troublescan distribution from a small wide world network and try to look at the clustering coefficients. Obviously there is no closed form for that, but you can still use random variant and get actually the value. So in this case I do even a hundred of them. So what behind we do essentially we have different Monte Carlo method to do the right simulation and return you, you know, random variants where you can actually, you know, right now take it and study that distributions. So and that's kind of quite interesting. As I say, you know, graph property distribution make you that bridge to the probability and statistic. We also build several similar bridge, right to different order in the system. Right. So if you do linear algebra and obviously graph is connected to linear algebra and I talked about it earlier, adjacency matrix. You can take your matrix and call adjacency graph to build a graph. So from linear algebra you can actually jump into graph. And if you actually do some complex computation in linear algebra and want to look at graph structure of your matrix, you can actually use adjacency graph. You can also take your image and use morphological graph to actually build your graph. Or if you do geometry, you can call mesh connectivity graph like you see in this case and get your connectivity of your graph. Or if you do chemistry, you can call molecular graph to actually build the graph out of it. So we try to build different bridges between different areas. So you can actually use graph a network as a tool to actually work and do some analysis of your in your area. Okay, one topic I will probably just, you know, go really fast. And you know, my colleague Jbom will Give a talk next week, next Friday. So Next Wednesday at 11am Central Time will be on graph visualizations. Right. As I showed earlier, we visualized our graph and since it's in the notebook, you actually get all the feature of notebook. Like in this case you can get, you know, mouse over tooltip and so on. So I won't go into detail with that. You know, jbom will present all the nice feature we have for graph visualizations. But what I will just kind of highlight is that what we have been trying to do is also to add more high level function for your graph layout. Because behind the scene we have several type of layout, but they need different parameterization and value so that you get a nice looking graph at the end. So what we have been doing is introducing different type of functions. Graph plot will kind of generate Your graph in 2D. Graph plot 3D in 3D. 3 plot will identify deficit tree and generate the right layout layer. Graph plot will essentially put your graph in different layers based on the topological ordering and connectivity community. Graph plot will take your graph and connect them based on the community structure and other modularity parameter for your graph. And obviously graph embedding gives you the general value of your graph in the space. So we have a set of function or plot function to actually allow you to handle your graph properly. So JBOM will talk about it more in detail and show you really nice graphics and rendering for that. Okay, so that was kind of my view about modeling, right? And the different way we have actually for you to actually model a graph. Right. So now let's talk about analysis of a graph. So one is that we have a set of functions to analyze or provide structural property of your graph. So there's basic property vectors, count, edge count. But now you can look at the topological structure. Is it directed, undirected, is it sample or does it have loops or multiple edges? And after you move from it, you can look at more complex structure. These two graphs identical even if applies some rotation or mapping. So it comes with isomorphism right there. Or if you want to detect is there a cycle, right. Do they have a. What's the connectivity of your graph? You know, we have connected GraphQL and such, so those are kind of the structural operations and functions we have. And now when you move a little bit far away from those basic structural operations, you can start to add more advanced questions, right? Can I find the part between the, you know, two different vertices or can I find a cycle, a Miltonian cycle so that I can traverse all the vertices In a certain way, right? So we have Eulerian, you know, find the Eulerian cycle, find the Newtonian cycle, and a bunch of other functions to actually analyze your graph, find shortest tour, find postman tour and such. And just for the fun of it, this is kind of a nice example. We'll show how you can solve a maze using the graph functionality using those cycle operations. So this is just parameter to style your maze. So we generate the maze as a grid graph. And one of the easiest way to generate a maze is to use spamming tree. So you generate a spamming tree and there you have a maze and you can use find shortest path to find the actual path and solve your maze. So I run that and you see that directly here you have the path. So the functionality is quite nice both visually and graphically so that you can take it visually nice, see your graph, manipulate it or analyze it. So the other next set of operations we have are centrality, Everybody know the page rank centrality, which was kind of the base of the Google page rank. But we also have closeness centrality, betweenness centrality, card centrality. Again value centrality, which each one give an interesting property of your graph where essentially you want to give a value of importance for each vertices or edges in your graph, right? So this is an example of the Florentine family, right? As you know, you know, the Medici family kind of rose to power and, you know, it's always interesting to know how was it possible, right? They were not really the richest family there, but you can see that marriage and connection. They kind of, you know, have a central position in all the network in that society, the Florentine society at the time. And that's why they were really powerful and really involved in politics in Florence at the time. I will use this example in my talk in two weeks where I will give a talk on social network analysis. And we probably kind of dig more inside and look at those centrality functions and how they are useful to analyze social network. Another set of functionality we have connected components connectivity and connected component related object, right? So connect component give you the set of, you know, vertices which are connected together. So essentially you can move from one to another one. So there is a path between them, right? So this is an example which was similar to what I used earlier, the slash dot connectivity. So here I kind of do a quick analysis of the connectivity of the graph. You can get the number of graphs, you can get the size of the largest connected component, the number of vertices, the node, and you can even analyze the clustering coefficient or you can actually take the number of in degree or odd degree of your network and actually see if it follow a known probability. In this case does it actually follow the Pareto distributions or does it fit in this type of graph with a certain type of property? So you can easily kind of do that with just a few comments. Okay, so what I try to show here is one is that the graph object in the system is quite simple and work naturally in both the front end and behind the scene as you want to do analysis. And I tried to show the two modes of modeling analysis in foregraph as well as just slightly talk about the visualization. So I hope that kind of gives you an idea of the functionality in the system and in probably the next couple of talks we kind of go more deeply and talk about different aspect of algorithm. So that's pretty much all what I have today. I will take a couple of your questions if there is any on the chart before we close up here. Okay, so I don't see any question on the chat. I hope this kind of gave you a, you know, an idea of the functionality. So if you have, you know, any question, feel free to post it on the on the comment of the different video and we'll try our best to answer them. And you know, join us, you know, next week, you know, in JBOM talk on car visualization and my talk two weeks from now on Social Network Analysis. Thank you.