{"id":236,"date":"2023-12-23T12:26:13","date_gmt":"2023-12-23T12:26:13","guid":{"rendered":"https:\/\/www.lancaster.ac.uk\/stor-i-student-sites\/wanchen-yue\/?page_id=236"},"modified":"2025-07-29T13:43:16","modified_gmt":"2025-07-29T13:43:16","slug":"236-2","status":"publish","type":"page","link":"https:\/\/www.lancaster.ac.uk\/stor-i-student-sites\/wanchen-yue\/236-2\/","title":{"rendered":""},"content":{"rendered":"\n<p class=\"has-default-sans-font-family has-large-font-size\"><strong>Reduction of general graphs using minimum number of edges<\/strong><\/p>\n\n\n\n<figure class=\"wp-block-image aligncenter is-resized has-custom-border is-style-default wp-duotone-grayscale\"><img decoding=\"async\" src=\"https:\/\/www.lancaster.ac.uk\/stor-i-student-sites\/wanchen-yue\/wp-content\/uploads\/sites\/49\/2023\/12\/edge-1024x646.png\" alt=\"\" style=\"border-style:none;border-width:0px;border-radius:76px;width:626px;height:auto\" \/><\/figure>\n\n\n\n<p class=\"has-system-serif-font-family has-small-font-size\">    Graphs with highly connected nodes are widely used in various application, the complexity of which makes it difficult to read and digest. Edge compression offers a tool to re-organize the structure of the graph through clustering the nodes which shares the similar neighbors in one supernode, by doing so, we could reduce the number of edges while without losing any details (connections). In order to maximize the profit brought by the edge compression technique, we seek for the reduction of a general graph to have minimum number of edges.<\/p>\n\n\n\n<p class=\"has-system-serif-font-family has-small-font-size\">Using the method of edge compression, nodes that are topologically equivalent can be clustered in one block. It is immediate that the edge between one node and one supernode indicates the connection between the node and each equivalent node in the supernode. A supernode is an aggregated set containing at least two nodes that share similar neighbours. See Fig 1 (a) as an example of supernode.<\/p>\n\n\n\n<p class=\"has-system-serif-font-family has-small-font-size\">Moreover, the definition of block allows edges to cross block boundaries and connect with specific node as shown in Fig 1 (c). For simple undirected and unweighted graphs, the edge compression method is lossless with the compressed graph carrying exactly the same \u2018connection\u2019 information as the original graph. The actual way of edge compression depends on different structure of graphs, while we propose optimal solution of edge reduction for regular and less complex graphs, benefiting our algorithms for many other graphs.<\/p>\n\n\n\n<figure class=\"wp-block-image size-full is-resized\"><img loading=\"lazy\" decoding=\"async\" width=\"2542\" height=\"1222\" src=\"https:\/\/www.lancaster.ac.uk\/stor-i-student-sites\/wanchen-yue\/wp-content\/uploads\/sites\/49\/2023\/12\/intro1.png\" alt=\"\" class=\"wp-image-245\" style=\"width:633px;height:auto\" srcset=\"https:\/\/www.lancaster.ac.uk\/stor-i-student-sites\/wanchen-yue\/wp-content\/uploads\/sites\/49\/2023\/12\/intro1.png 2542w, https:\/\/www.lancaster.ac.uk\/stor-i-student-sites\/wanchen-yue\/wp-content\/uploads\/sites\/49\/2023\/12\/intro1-300x144.png 300w, https:\/\/www.lancaster.ac.uk\/stor-i-student-sites\/wanchen-yue\/wp-content\/uploads\/sites\/49\/2023\/12\/intro1-1024x492.png 1024w, https:\/\/www.lancaster.ac.uk\/stor-i-student-sites\/wanchen-yue\/wp-content\/uploads\/sites\/49\/2023\/12\/intro1-768x369.png 768w, https:\/\/www.lancaster.ac.uk\/stor-i-student-sites\/wanchen-yue\/wp-content\/uploads\/sites\/49\/2023\/12\/intro1-1536x738.png 1536w, https:\/\/www.lancaster.ac.uk\/stor-i-student-sites\/wanchen-yue\/wp-content\/uploads\/sites\/49\/2023\/12\/intro1-2048x985.png 2048w\" sizes=\"auto, (max-width: 2542px) 100vw, 2542px\" \/><figcaption class=\"wp-element-caption\">Figure 1: Edge compression: Clustering nodes based on identical neighborhoods. <\/figcaption><\/figure>\n\n\n\n<p>This report is available upon request. If you&#8217;re interested, feel free to <a href=\"https:\/\/www.lancaster.ac.uk\/stor-i-student-sites\/wanchen-yue\/94-2\/\" data-type=\"page\" data-id=\"94\">contact me<\/a>!<\/p>\n","protected":false},"excerpt":{"rendered":"<p>Reduction of general graphs using minimum number of edges Graphs with highly connected nodes are widely used in various application, the complexity of which makes it difficult to read and digest. Edge compression offers a tool to re-organize the structure of the graph through clustering the nodes which shares the similar neighbors in one supernode, [&hellip;]<\/p>\n","protected":false},"author":55,"featured_media":239,"parent":0,"menu_order":0,"comment_status":"closed","ping_status":"closed","template":"template-no-title","meta":{"footnotes":""},"class_list":["post-236","page","type-page","status-publish","has-post-thumbnail","hentry"],"_links":{"self":[{"href":"https:\/\/www.lancaster.ac.uk\/stor-i-student-sites\/wanchen-yue\/wp-json\/wp\/v2\/pages\/236","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.lancaster.ac.uk\/stor-i-student-sites\/wanchen-yue\/wp-json\/wp\/v2\/pages"}],"about":[{"href":"https:\/\/www.lancaster.ac.uk\/stor-i-student-sites\/wanchen-yue\/wp-json\/wp\/v2\/types\/page"}],"author":[{"embeddable":true,"href":"https:\/\/www.lancaster.ac.uk\/stor-i-student-sites\/wanchen-yue\/wp-json\/wp\/v2\/users\/55"}],"replies":[{"embeddable":true,"href":"https:\/\/www.lancaster.ac.uk\/stor-i-student-sites\/wanchen-yue\/wp-json\/wp\/v2\/comments?post=236"}],"version-history":[{"count":11,"href":"https:\/\/www.lancaster.ac.uk\/stor-i-student-sites\/wanchen-yue\/wp-json\/wp\/v2\/pages\/236\/revisions"}],"predecessor-version":[{"id":269,"href":"https:\/\/www.lancaster.ac.uk\/stor-i-student-sites\/wanchen-yue\/wp-json\/wp\/v2\/pages\/236\/revisions\/269"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/www.lancaster.ac.uk\/stor-i-student-sites\/wanchen-yue\/wp-json\/wp\/v2\/media\/239"}],"wp:attachment":[{"href":"https:\/\/www.lancaster.ac.uk\/stor-i-student-sites\/wanchen-yue\/wp-json\/wp\/v2\/media?parent=236"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}