Progress in Graphs & Networks

So my name is Jebam. I work in discrete mathematics with Charles and Karen here. So today I want to talk about the graph and network probably giving some overview with some of new things. We are having new version. So I just going to start talking about how to build graph and then some computational analysis visualization kind of looks similar to previous talk. But I say we didn't copy each other. We just ended up having some same structure. We were working together long time. So. So first to working on the graph you need graph. So first way like in geometry we can import from the existing the graph format. For example here like a GMA graph. So you can just using the import function in the Mathematica and default will be just giving you the graph. And there are various attributes you can extract out of the graph format. It depends on format. They usually not all the same. But in this case you can say like get the adjacent matrix is tracked or not and grab and then some grab attribute like its label directed something like that. And here is list of grab format we supporting right now. And then we are keep adding more and more if there are requested by user or if we find something useful. Also all of the things we are working on is we try to improve the performance of importing and export. I think Even in version 13 there are several the graph format that improves performance wise it's much faster than before. And there is not always the actual the data is following the graph format. Sometimes the people using their private format. The fortunately they usually come with their description. For example here one of the example from. I think it's from Stanford the database. And then here's how the data looks like you just have some description directed graph. And then in this case I just follow the description extracting this pair which represent ETG and the construct graph. The another type is the CSV the table format. And then if you just see how it looks like it's just. In this case we just need to first and second source and target. So I just grab it. And then as you know this is directed. So I just mapping the directed hobo to construct directed graph. And also we see there are way. So we can also extract way information and then or join the way to graph. And then this is how we do another type is this is one adj adjacency matrix. So this data actually specified adjacency matrix. So 2 1, 1 means the position took by 1 has element 1 inside the matrix. So we just parging that and supply to sparse array which construct adjacent matrix called adjacency graph over it. Then we got the quite sizable graph here and can do computation after that. And we have like a curated data inside of Wolfram language and Mathematica. So for example here we have almost like 190 over 190 collection the Empirical Network. So for example she's graph network. And also you can get the long description or it has several elements inside of it you can check. So if you see the by count description those things. And then another thing is resource data. So Charles already mentioned about resource data is public. And then the good thing is you can also adding your own data share with people. So if you have nice graph data then I encourage you to. Yeah, adding into resource data the sending your data that people can use. So here is the one of the example marble universe social network. So here's summary of data. So it has like 19,000 vertex 9,600,000 80s and the marble comics character collaboration network. So let me just after getting it you can modify the graph to get something more interesting graph. In this case let me just show some step. So first of all I just checked the connected component to this marble network. So you have see the one big chunk and then there are some smaller networks. So I just take the first one connecting the component. And then if you see how the vertices relation each other. So the neighbors of comic vertices. The vertices two types comics and hero. So there are relation between comics and hero if the heroes appear in that comics. So like this one, this comics the name of comics and this is name of hero. So it form nice bipartite graph. So when you have bipartite graph you can usually extract projection graph which containing just one part of it. So for example right now I'm going to take the hero projection. So what that means is vertices will be hero and then relationship between the hero if they are showed up in the same comics. So I just taking in this case put 3 we have annotation value same type. So I just getting comic type and then taking hero and then do some subset or blah blah just getting relationship. And then I gonna only select. So there are the heroes that appear many comics each other and then the hero only showed up several. Only one or two comics which is that. But I just going to take the heroes that showed up more than 50 times in the comics. So you got some little bit decent size of graph. Then so for example like here this is the selected small marble graph that each other appears more than 50 times in the same comic in the comics. And I just replace vertex to the name. So Vertex of this network. Now the actual name. So we gonna work with this graph later. So after you get the graph, okay people that do the computation. So here is just modeling. And also what you are working on is modeling graph and then editing also. So there are like core computation you can do over the graph like vertex delete, vertex contract. There are several functions. And then like those functions we are just not stopping. We keep trying to improve performance because those are real core functions. Many graph operation can be decided by that performance of those functions. So for example vertex contract we dramatically increased performance in upcoming version. So you can see that if you are working on the function, you can see how the difference between those difference of that function compared to 13.1 and 2 after that. Once you have a graph then you want to do some computational analysis. So here for in case of social network the centrality measure is kind of big things. So if you attend network talk people chats in this room that you can see edge connectivity measurement and degree centrality. All those centrality how it used in real life situations. So this one actually very useful to measuring importance of vertices depends on criteria. So for example I can share some of famous Medici family graph. And then I just highlighting some importance to vertices. The family depends on the centrality. And then there are another measured transposity and sensitivity. So it's local clustering coefficient. Actually measuring how the neighbor of vertices they link to each other. So this is just histogram of this Internet network. And another measure we can do is like homophily also 50 mixing. So here's an example of using the transition network by leisure. So this case you can compute the graph positivity. So this is what it is highly social student friend with other highly social student which can be expected. And this is the value for that. And then graphositotivity by lace. And then you can also find out some coils group some substructure of graph. There are some like clique k clique kclan. So here's a small example of it. So you just get the network from stamport database and then you just comp some base basic subgraph structure or structure. So we click connected graph component strongly connected component. So hg and so claustrance coefficient etc. And then you also do some statistic analysis over it conjunction with some statistical functionality in Mathematica. So here's some brief example. So you have graph and then just getting in degree and using the estimate distribution we can estimate the some parameter of log normal distribution. Also you can try to estimate Parameter Pareto distribution. And this one is its own distribution. And then you can just compare it. So you can just basically see seems like. Oops, let me. I think I missed some evaluate something. Oops, sorry about that. Well just. Okay, here we go. So like here Pareto kind of looks similar to its original distribution. So there's more things you can do with the statistical analysis that didn't show up here. But yeah, just go check it documentation and you can see lots of functionality over there. And then there's something new Graph plus. So as you can see the graph you can view as the matrix adjacent matrix. And then advantage of that many algorithm graph algorithms actually using the adjacency matrix. So linear algebra. So actually the blast there is plus the library or API in numerical analysis numerical computation which usually good for dense matrix. And for graph. In most of graph real life example it's actually sparse graph instead of dense graph. So there are lately there is working on those type of matrix operation. So this is one of that called graph plus the API. They're giving the some of building block the operation over link structure. And then it's kind of fast. I mean fast and then very kind of abstract. So you the operation is not just plus and the multiplication. You can do whatever you want if it's building the link structure. So here's one of the example like here the bread first search one of the famous graph algorithm. So you can just go in parallel to the edgy to the next level. But also there are no version of matrix operations. So here you have adjacent matrix. And this is kind of column vector the specifying starting point by just operation on it. You can find the next step like a 1, 3. Then then you got the 2, 3, 5 like 1, 2, 4, 6. Actually 2, 4, 6. Right. So this is one simple example how the actual graph algorithm related to linear algebra. And we are trying to integrate this graph loss into Mathematica right now. So one of the example here is so grab flask and then there are also library called raglap that is the collection of algorithm building using the build by using the graph plus. So here's the example of phase length centrality. So here this one is the performance of current method we are using. And this one. I mean this first one is the lagraph performance. Second one is performance via currently using in Mathematica. So you can see this one is slightly faster. But if graph is getting larger the performance difference is dramatic. So usually if your graph is big enough then using the graph plus you can get the better Performance. But this is not for every algorithm. We have to fine tuning and then find what is the better. Certain cases we found out current method Vestigraph plus. So that's something we are working on here. And then for example, like here social marble universal network here. This power method is what the method we are using right now. And then this is lagraph we are plugging in. Then you see it's kind of. Yeah, three times faster. It's more than that. Yeah, it's quite fast. So once we put this into system, the user probably don't know which one is learning. And what I mean is we automatically detect grab depending on the size we call automatic call lograp or the original method we have. Or user can specify which method they want to. So there's something the direction we are going. And then another new thing we add. So we are also adding new function and also improving current existing functions. So this is one of the improvement. So we adding kind of different output type for fine shortage tour. Also you can see the starting and ending. Now you see something that index. Originally we only allowed to put the index if you have a list of something. The starting should have to be index of this list like first position or five position. But instead of doing that, you can actually specify the element as starting and ending point. So for example here. And then your return will be just element, not the list of indices the quarterly nature. So in this case you can just direct geopaths to draw geographics. And also here's the type of output support. If you say all, then you got the element indices which is original output and then length. So last one is the visualization. So the first thing when you do the visualization you need to know the position of vertices. So there are two ways to specify it. First by specifying vertex coordinate manually. So this is one example. So your chemical data with OGSH matrix and also chemical data comes the vertex coordinate of this data. So I just specify Eugene. And also you can use the graph layout. So we have many several layout algorithm built into it. And then we can keep adding and improving it. So one of the new 19.30.2 or maybe next version is like a layer digraph embedding. In general there are many overlap between the vertices. When you do layer diagraph embedding. Especially when you specify vertex size. So new option we are working on is like vertex sizes then can be changed later. So specify actual box sizes. And then when you try to compute the layer diagraph embedding it account those sizes specified. So try to compensate Those things and you can see there is no overlap anymore. It's kind of convenient. And then styling vertices. So basically just vertex style just changing color. Any the directive you can specify as vertex color or you can change the shape function. So this is just example of some predefined shape function. Or you can specify your own function. And vertex shape is actually just shape. That means you can put any mathematical expression as a shape. So like a graphics or images and then like a 3D graphics. Anything really work with vertex shape. So this is one example of vertex shape function. Because of function you have input form center center position and then the size size of vertices. And with some dynamic you can do something like this. So you can do much complicated thing or simple thing based on your usage and edgy style. Same just type of edgy and edgy label label of edgy edgy shape function. Also we come with predefined HG shape functions. There's many collection of it. And also you can specify your own function like this this one also getting the input here. And some something like. Okay. And next. So Platinum is giving the overall style of graph by just plug them something. Then you got this different type of graph. Very easy. This is function each option to use and also highlight graph. This is for use for highlighting some sort of part of graph. So here you can also using the saying like graph highlight style with D or diamond or whatever. And this kind of tool. Probably you didn't. You don't see this in current version. This is something new graph style we are working on. So hopefully you can see soon. So here's the example of styling the graph. I just using the small marble graph we constructed before. So we're just taking top three vertices to emphasize it and then setting up using vertex label, label style, whatever. And then you have something look nice here. So we have three main vertices that has most degree turned out to be Spiderman Captain Omega. Yeah, it's expected. And also you can do some dynamic. So here's another Facebook data from Temple database. So I just make one big manipulator. So you can check some importance vertex theory, closed centrality and some feature. Because this data set comes with feature for each vortexes. So this plot actually showing those feature. And then some summary of graph and color. This is right now color is by the centrality. But you can also color by the circle. Because circle means this Facebook data have some circular attribute that I don't know how they define circle. But it's kind of grouping. I just put into coloring based on the Grouping and you can check the ornodal data. So this is some visualization you can do. So graph plot actually this plot function the one main difference is output will be the graphics. So if you do random graph. So this is one of the things like here it's not showed up because we have some threshold. If HG or vertex count is more than some number we don't show up. We don't show that because it's kind of too big to show. But graph plot actually just tried it ignore the threshold. So sometimes you need it. Or you can change the system option the increasing threshold. But this is one easy way to plot in the large function and graph plot 3D just plotting 3D space layered graph plot layer. The graph plot 3D actually layered with industry space entry plot pol tree graph and community graph plot that show the community structure of graph and the plotting. Oops, I think I got in the wrong version. Let me just. Briefly show this in the different version. Sorry about that. Yeah, this is like a structure community structure of this graph. And then we have grab value flat. This is still working in progress. So this one help you actually plotting the various the vertex property. So this case inabec centrality is just coloring based on this one. And then hassel graph is the some new function we are working on also giving the construct graph based on partial ordering and then graph value plot over it with that to see the like layer. So this is. I think it's time us up. It's all super end of my talk right now. So we currently keep improving the graph functionality. Also one of the direction we have right now is for large graph. One of the airport is you see is like graph plus which is good for large graph computation. Also we are working on to integrate some neural network GNN or graph database. That's another thing we having planned. So yeah, that's about today's talk. So thank you for attending.