-
Notifications
You must be signed in to change notification settings - Fork 0
/
lets-play-gephi-understand-k-partite-graph.html
18 lines (17 loc) · 19.8 KB
/
lets-play-gephi-understand-k-partite-graph.html
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
<!DOCTYPE html><html lang="en"><head><meta charset="utf-8"><meta http-equiv="X-UA-Compatible" content="IE=edge"><meta name="viewport" content="width=device-width,initial-scale=1"><title>Let's Play Gephi : Understand k-partite graph - Toto do stuff</title><meta name="description" content="K-partite, Bipartite ... What is it ? Most of the time, when you create a graph, all the nodes are representing the same 'kind' of…"><meta name="generator" content="Publii Open-Source CMS for Static Site"><link rel="canonical" href="https://totetmatt.github.io/lets-play-gephi-understand-k-partite-graph.html"><link rel="alternate" type="application/atom+xml" href="https://totetmatt.github.io/feed.xml"><link rel="alternate" type="application/json" href="https://totetmatt.github.io/feed.json"><meta property="og:title" content="Let's Play Gephi : Understand k-partite graph"><meta property="og:image" content="https://totetmatt.github.io/media/posts/25/screenshot_130704.png"><meta property="og:site_name" content="Toto do stuff"><meta property="og:description" content="K-partite, Bipartite ... What is it ? Most of the time, when you create a graph, all the nodes are representing the same 'kind' of…"><meta property="og:url" content="https://totetmatt.github.io/lets-play-gephi-understand-k-partite-graph.html"><meta property="og:type" content="article"><style>:root{--body-font:-apple-system,BlinkMacSystemFont,"Segoe UI",Roboto,Oxygen,Ubuntu,Cantarell,"Fira Sans","Droid Sans","Helvetica Neue",Arial,sans-serif,"Apple Color Emoji","Segoe UI Emoji","Segoe UI Symbol";--heading-font:-apple-system,BlinkMacSystemFont,"Segoe UI",Roboto,Oxygen,Ubuntu,Cantarell,"Fira Sans","Droid Sans","Helvetica Neue",Arial,sans-serif,"Apple Color Emoji","Segoe UI Emoji","Segoe UI Symbol";--logo-font:-apple-system,BlinkMacSystemFont,"Segoe UI",Roboto,Oxygen,Ubuntu,Cantarell,"Fira Sans","Droid Sans","Helvetica Neue",Arial,sans-serif,"Apple Color Emoji","Segoe UI Emoji","Segoe UI Symbol";--menu-font:-apple-system,BlinkMacSystemFont,"Segoe UI",Roboto,Oxygen,Ubuntu,Cantarell,"Fira Sans","Droid Sans","Helvetica Neue",Arial,sans-serif,"Apple Color Emoji","Segoe UI Emoji","Segoe UI Symbol"}</style><link rel="stylesheet" href="https://totetmatt.github.io/assets/css/style.css?v=825c89ac06c7215b642eda05e8a14751"><script type="application/ld+json">{"@context":"http://schema.org","@type":"Article","mainEntityOfPage":{"@type":"WebPage","@id":"https://totetmatt.github.io/lets-play-gephi-understand-k-partite-graph.html"},"headline":"Let's Play Gephi : Understand k-partite graph","datePublished":"2015-07-11T15:30","dateModified":"2020-06-20T00:35","image":{"@type":"ImageObject","url":"https://totetmatt.github.io/media/posts/25/screenshot_130704.png","height":2048,"width":2048},"description":"K-partite, Bipartite ... What is it ? Most of the time, when you create a graph, all the nodes are representing the same 'kind' of…","author":{"@type":"Person","name":"Totetmatt","url":"https://totetmatt.github.io/authors/totetmatt/"},"publisher":{"@type":"Organization","name":"Totetmatt"}}</script></head><body><div class="site-container"><header class="top" id="js-header"><a class="logo" href="https://totetmatt.github.io/">Toto do stuff</a></header><main><article class="post"><div class="hero"><figure class="hero__image hero__image--overlay"><img src="https://totetmatt.github.io/media/posts/25/screenshot_130704.png" srcset="https://totetmatt.github.io/media/posts/25/responsive/screenshot_130704-xs.png 300w, https://totetmatt.github.io/media/posts/25/responsive/screenshot_130704-sm.png 480w, https://totetmatt.github.io/media/posts/25/responsive/screenshot_130704-md.png 768w, https://totetmatt.github.io/media/posts/25/responsive/screenshot_130704-lg.png 1024w, https://totetmatt.github.io/media/posts/25/responsive/screenshot_130704-xl.png 1360w, https://totetmatt.github.io/media/posts/25/responsive/screenshot_130704-2xl.png 1600w" sizes="(max-width: 1600px) 100vw, 1600px" loading="eager" height="2048" width="2048" alt=""></figure><header class="hero__content"><div class="wrapper"><div class="post__meta"><time datetime="2015-07-11T15:30">15/07/11</time></div><h1>Let's Play Gephi : Understand k-partite graph</h1><div class="post__meta post__meta--author"><a href="https://totetmatt.github.io/authors/totetmatt/" class="feed__author invert">Totetmatt</a></div></div></header></div><div class="wrapper post__entry"><h1>K-partite, Bipartite ... What is it ?</h1><p>Most of the time, when you create a graph, all the nodes are representing the same "kind" of object.</p><ul><li>In a Social Network : Persons</li><li>In a Route Netowork : Stops, Airports, Stations etc...</li><li>In a Geographical Network : Countries</li></ul><p>But sometime, depends on your graph modelisation, you will encounter a graph that will have 2, 3 or multiple "kinds" of nodes where the links are almost exclusively going from one type to the other. These graphs are called <strong>Multipartite Graphs</strong>.</p><ul><li>If you have <strong>2</strong> kinds of nodes, it's a <strong>Bi</strong>partite Graph (or <strong>2</strong>-partite)<ul><li>Example : Social Network : Persons <-> Companies</li></ul></li><li>If you have <strong>3</strong> kinds of nodes it's a<strong> 3</strong>-partite Graph<ul><li>Example : Movie Network : Actors <-> Movies <-> Directors</li></ul></li><li>If you have <strong>k</strong> kinds of nodes it's a <strong>k</strong>-partite Graph</li></ul><p><a href="https://en.wikipedia.org/wiki/Multipartite_graph"> </a>If you want a proper scientific definition, <a href="https://en.wikipedia.org/wiki/Multipartite_graph">Wikipedia</a> will be your friend.</p><h2>The Dataset</h2><p>To illustrate this thema, we will use a well know dataset : The Cac 40 Administrators relationship from <a href="http://www.citoyennumerique.fr/?tag=cac40">www.citoyennumerique.fr.</a></p><p>Please, feel free to play with the graph. I provide you the gexfs here <a href="http://matthieu-totet.fr/Koumin/wp-content/uploads/2015/07/Tuto_Multitpartite_CAC40.zip">Tuto_Multitpartite_CAC40</a> . The tutorial will be based on the <strong>SimpleGraph</strong>, but I also give you the <strong>FullGraph</strong> to play with.</p><p>How the graph is build ? Well, a <strong>company</strong> has several <strong>administrators </strong>and nothing prevent an <strong>administrator</strong> to be in multiple <strong>companies</strong>, so we build a directed graph where <strong>companies</strong> are sources of edges and targets are the <strong>administrators</strong>.</p><blockquote><p>I'll focus on the technics and metrics. I let yourself think about the ethics and politics ;-) .</p></blockquote><figure class="wp-image-254 alignnone">If you follow, this is a typical bi-partite graph. If you look on the data, part of the node has a property type <strong>Administrator</strong> and the other part has a property type <strong>Company</strong>.<a href="http://matthieu-totet.fr/Koumin/wp-content/uploads/2013/11/screenshot_130704.png"><img loading="lazy" src="https://totetmatt.github.io/media/posts/25/screenshot_130704-1024x1024.png" sizes="(max-width: 48em) 100vw, 768px" srcset="https://totetmatt.github.io/media/posts/25/responsive/screenshot_130704-1024x1024-xs.png 300w, https://totetmatt.github.io/media/posts/25/responsive/screenshot_130704-1024x1024-sm.png 480w, https://totetmatt.github.io/media/posts/25/responsive/screenshot_130704-1024x1024-md.png 768w, https://totetmatt.github.io/media/posts/25/responsive/screenshot_130704-1024x1024-lg.png 1024w, https://totetmatt.github.io/media/posts/25/responsive/screenshot_130704-1024x1024-xl.png 1360w, https://totetmatt.github.io/media/posts/25/responsive/screenshot_130704-1024x1024-2xl.png 1600w" alt="Cac 40 bipartite graph" width="614" height="614"></a></figure><p></p><p>It's already nice and we can get quick obesvation:</p><ul><li>Filtering by InDegree, we can check that Michel Pebereau and Jean-Martin Folz are in <strong>5 companies</strong> at the same time.</li><li>Filtering by OutDegree, we can check that St-Gobain and Total have <strong>8 administrators</strong> that are in other companies.</li></ul><p>But that could be done without graph, an ordered list on excel would have done the job.</p><h3>How to deal with multipartite graphs ?</h3><p>It feels that it's not very convenient to get something out of this, and even the interpretation of metrics isn't easy. That's because the graph is mixing different notions (type) which makes it a little difficult to read and analyse.</p><p>So what to do ? There isn't official methodology, but we can use some trick to improve the readability. The easiest one is to <strong>reduce</strong> the <strong>bi-partite</strong> graph in a <strong>mono-partite</strong> graph.</p><blockquote><p>By reducing, we will "lose" information but we gain in <strong>readability</strong> and <strong>synthesis</strong>, that's part of the work in datavisualisation to see at which level we want to go and how to deal with this trade of information. This will mostly be driven by the question you want to answer.</p></blockquote><p>The principle of the reduction is to concider some nodes as edges and deduce a new graph based on this rule. In our example we have 2 ways to go :</p><ul><li>Either we decide that the nodes of type "Company " are the edges. It will generate a <strong>graph</strong> of "<strong>Persons </strong>"</li><li>Either we decide that the nodes of type "Person " are the edges. It will generate a <strong>graph</strong> of "<strong>Company </strong>"</li></ul><blockquote><p>Here both graphs generated makes "sense" (network of entities) but it can appears that one of the graph isn't really meanful. That's part of your work to juge this aspect.</p></blockquote><p>Now, how to perform the transformation ?</p><h3>Using a Plugin</h3><p>The easiest way would be to use the<a href="https://marketplace.gephi.org/plugin/multimode-networks-transformations-2/" target="_blank"> Multimode Network Transformation. </a>The plugin is available on the gephi app market and in the plugin manager in Gephi.</p><p>When it's installed, you should be able to see or display the<strong> Multimode Network Transformation</strong> tab.</p><p>Then, load the graph your are interested in, clone it in a new workspace and :</p><ul><li>Click on <strong>Load Attributes</strong> and select <strong>Type</strong> on <strong>Attribute Type.</strong></li><li>For left matrix select "<strong>Administrator - Company</strong>" and right matrix "<strong>Company - Adminstrator</strong>"</li><li>Enable <strong>Remove Edges</strong> and<strong> Remove Nodes</strong>, and Click<strong> Run<br></strong></li></ul><figure class="size-medium wp-image-426 aligncenter"><a href="http://matthieu-totet.fr/Koumin/wp-content/uploads/2015/07/MultiPartite_Gephi.png"><img loading="lazy" src="https://totetmatt.github.io/media/posts/25/MultiPartite_Gephi-300x202.png" sizes="(max-width: 48em) 100vw, 768px" srcset="https://totetmatt.github.io/media/posts/25/responsive/MultiPartite_Gephi-300x202-xs.png 300w, https://totetmatt.github.io/media/posts/25/responsive/MultiPartite_Gephi-300x202-sm.png 480w, https://totetmatt.github.io/media/posts/25/responsive/MultiPartite_Gephi-300x202-md.png 768w, https://totetmatt.github.io/media/posts/25/responsive/MultiPartite_Gephi-300x202-lg.png 1024w, https://totetmatt.github.io/media/posts/25/responsive/MultiPartite_Gephi-300x202-xl.png 1360w, https://totetmatt.github.io/media/posts/25/responsive/MultiPartite_Gephi-300x202-2xl.png 1600w" alt="MultiPartite_Gephi" width="300" height="202"></a></figure>The plugins will actually to transform each relation like:<p></p><p style="text-align: center;">(Administrator)<strong><</strong><strong>--</strong>(Company)<strong>--></strong>(Administrator)<br>to<br>(Administrator)<strong><-[</strong>{weight=Nb of Common Companies}<strong>]-></strong>(Administrator)</p><p>Now you should have a graph with only administrators on the graph preview.</p><figure class="size-medium wp-image-428 aligncenter"><a href="http://matthieu-totet.fr/Koumin/wp-content/uploads/2015/07/Tuto_Multi_P2P.png"><img loading="lazy" src="https://totetmatt.github.io/media/posts/25/Tuto_Multi_P2P-300x249.png" sizes="(max-width: 48em) 100vw, 768px" srcset="https://totetmatt.github.io/media/posts/25/responsive/Tuto_Multi_P2P-300x249-xs.png 300w, https://totetmatt.github.io/media/posts/25/responsive/Tuto_Multi_P2P-300x249-sm.png 480w, https://totetmatt.github.io/media/posts/25/responsive/Tuto_Multi_P2P-300x249-md.png 768w, https://totetmatt.github.io/media/posts/25/responsive/Tuto_Multi_P2P-300x249-lg.png 1024w, https://totetmatt.github.io/media/posts/25/responsive/Tuto_Multi_P2P-300x249-xl.png 1360w, https://totetmatt.github.io/media/posts/25/responsive/Tuto_Multi_P2P-300x249-2xl.png 1600w" alt="Tuto_Multi_P2P" width="300" height="249"></a></figure><p></p><p>To generate the relation between companies, replay the same steps from the original graph (duplicate the workspace0 again) and in the <strong>Multimode Network Transformation</strong> use :</p><ul><li>Left Matrix : Company - Administrator</li><li>Right Matrix : Administrator - Company</li></ul><figure class="size-medium wp-image-427 aligncenter"><a href="http://matthieu-totet.fr/Koumin/wp-content/uploads/2015/07/MultiPartite_Gephi_2.png"><img loading="lazy" src="https://totetmatt.github.io/media/posts/25/MultiPartite_Gephi_2-300x228.png" sizes="(max-width: 48em) 100vw, 768px" srcset="https://totetmatt.github.io/media/posts/25/responsive/MultiPartite_Gephi_2-300x228-xs.png 300w, https://totetmatt.github.io/media/posts/25/responsive/MultiPartite_Gephi_2-300x228-sm.png 480w, https://totetmatt.github.io/media/posts/25/responsive/MultiPartite_Gephi_2-300x228-md.png 768w, https://totetmatt.github.io/media/posts/25/responsive/MultiPartite_Gephi_2-300x228-lg.png 1024w, https://totetmatt.github.io/media/posts/25/responsive/MultiPartite_Gephi_2-300x228-xl.png 1360w, https://totetmatt.github.io/media/posts/25/responsive/MultiPartite_Gephi_2-300x228-2xl.png 1600w" alt="MultiPartite_Gephi_2" width="300" height="228"></a></figure><p></p><figure class="size-medium wp-image-429 aligncenter"><a href="http://matthieu-totet.fr/Koumin/wp-content/uploads/2015/07/Tuto_Multi_C2C.png"><img loading="lazy" src="https://totetmatt.github.io/media/posts/25/Tuto_Multi_C2C-300x288.png" sizes="(max-width: 48em) 100vw, 768px" srcset="https://totetmatt.github.io/media/posts/25/responsive/Tuto_Multi_C2C-300x288-xs.png 300w, https://totetmatt.github.io/media/posts/25/responsive/Tuto_Multi_C2C-300x288-sm.png 480w, https://totetmatt.github.io/media/posts/25/responsive/Tuto_Multi_C2C-300x288-md.png 768w, https://totetmatt.github.io/media/posts/25/responsive/Tuto_Multi_C2C-300x288-lg.png 1024w, https://totetmatt.github.io/media/posts/25/responsive/Tuto_Multi_C2C-300x288-xl.png 1360w, https://totetmatt.github.io/media/posts/25/responsive/Tuto_Multi_C2C-300x288-2xl.png 1600w" alt="Tuto_Multi_C2C" width="300" height="288"></a></figure>With the 2 new graphs, we are able to see some particularities:<p></p><ul><li>The maximum of<strong> common administrator</strong> between company is <strong>3</strong> : Bouygues and Alstom with Olivier Bouygues, Patrick Kron, Georges Chodron de Courcel</li><li><strong>Half of the companies</strong> are sharing at least 2 administrators .</li><li>The maximum of <strong>common company</strong> between person is <strong>3</strong> : Gerard Lamarche and Paul Demaray Jr see each other when Total, GDF Suez and Lafarge SA have a meeting with Board of Directors.</li><li>From all administrators that are in at least 2 companies,<strong> 1/3 of them are at least in the same 2 companies</strong>.</li></ul><p>These statements can be deduced from the original graph, but wasn't obvious. With the 2 generated graphs, it makes easy to see it.</p><blockquote><p>The works now is mostly to look at graphs, and resume all the particularities within a production (poster, interactive graph, newpaper writting etc...)</p></blockquote><h3></h3><h3>Limitations</h3><p>The plugin works quite well, but sometime it has some limitation on large graph. Or sometime you may want to reduce your graph and have a custom metric computed. Then the only alternative to that is to use a script that will generate you the graph.</p><h3>Conclusion</h3><p>Multipartite graph are complex to analyse, but reducing it to monopartite graphs gives you more vision to get insight about your data.</p></div><footer class="wrapper post__footer"><p class="post__last-updated">This article was updated on 20/06/20</p><ul class="post__tag"><li><a href="https://totetmatt.github.io/cac40/">cac40</a></li><li><a href="https://totetmatt.github.io/gephi/">Gephi</a></li><li><a href="https://totetmatt.github.io/multipartite/">Multipartite</a></li></ul><div class="post__share"></div><div class="post__bio bio"><div class="bio__info"><h3 class="bio__name"><a href="https://totetmatt.github.io/authors/totetmatt/" class="invert" rel="author">Totetmatt</a></h3></div></div></footer></article><nav class="post__nav"><div class="post__nav-inner"><div class="post__nav-prev"><svg width="1.041em" height="0.416em" aria-hidden="true"><use xlink:href="https://totetmatt.github.io/assets/svg/svg-map.svg#arrow-prev"/></svg> <a href="https://totetmatt.github.io/world-flight-routes.html" class="invert post__nav-link" rel="prev"><span>Previous</span> World Flight Routes</a></div><div class="post__nav-next"><a href="https://totetmatt.github.io/force-atlas-of-europe.html" class="invert post__nav-link" rel="next"><span>Next</span> (Force) Atlas of Europe </a><svg width="1.041em" height="0.416em" aria-hidden="true"><use xlink:href="https://totetmatt.github.io/assets/svg/svg-map.svg#arrow-next"/></svg></div></div></nav><div class="post__related related"><div class="wrapper"><h2 class="h5 related__title">You should also read:</h2><article class="related__item"><div class="feed__meta"><time datetime="2015-09-06T22:47" class="feed__date">15/09/06</time></div><h3 class="h1"><a href="https://totetmatt.github.io/lets-play-gephi-dbpedia-rdf-sparql-and-your-favorite-actors.html" class="invert">Let's Play Gephi : Dbpedia, RDF, Sparql and your favorite Actors</a></h3></article><article class="related__item"><div class="feed__meta"><time datetime="2014-06-15T09:55" class="feed__date">14/06/15</time></div><h3 class="h1"><a href="https://totetmatt.github.io/lets-play-gephi-streaming-api-the-hidden-websocket.html" class="invert">Let's Play Gephi : Streaming API - The 'hidden' Websocket</a></h3></article><article class="related__item"><div class="feed__meta"><time datetime="2014-06-06T10:17" class="feed__date">14/06/06</time></div><h3 class="h1"><a href="https://totetmatt.github.io/cartographie-des-tags-des-jeux-de-donnees-etalab-datagouv.html" class="invert">Cartographie des tags des jeux de données Etalab / Data.gouv</a></h3></article></div></div></main><footer class="footer"><div class="footer__copyright"><p>Powered by <a href="https://getpublii.com" target="_blank" rel="nofollow noopener">Publii Static CMS</a></p></div><button class="footer__bttop js-footer__bttop" aria-label="Back to top"><svg><title>Back to top</title><use xlink:href="https://totetmatt.github.io/assets/svg/svg-map.svg#toparrow"/></svg></button></footer></div><script>window.publiiThemeMenuConfig = {
mobileMenuMode: 'sidebar',
animationSpeed: 300,
submenuWidth: 'auto',
doubleClickTime: 500,
mobileMenuExpandableSubmenus: true,
relatedContainerForOverlayMenuSelector: '.top',
};</script><script defer="defer" src="https://totetmatt.github.io/assets/js/scripts.min.js?v=f4c4d35432d0e17d212f2fae4e0f8247"></script><script>var images = document.querySelectorAll('img[loading]');
for (var i = 0; i < images.length; i++) {
if (images[i].complete) {
images[i].classList.add('is-loaded');
} else {
images[i].addEventListener('load', function () {
this.classList.add('is-loaded');
}, false);
}
}</script></body></html>