{"id":{"repo_id":"uiuc","oai_identifier":"oai:www.ideals.illinois.edu:2142/16022"},"canonical_url":"https://search.dev.ndltd.org/etd/uiuc/oai:www.ideals.illinois.edu:2142/16022","repository":{"repo_id":"uiuc","name":"University of Illinois - Urbana-Champaign","base_url":"https://www.ideals.illinois.edu/oai-pmh"},"display":{"title":"Large graph simplification, clustering and visualization","abstract":"\"This dissertation investigates novel approaches for analysis and visualization of two kinds of graph, scale-free network and rooted hierarchy, at large scales with thousands to millions of nodes. Scale-free network, whose node degree distribution follows a power-law function, often arises in sociology, financial analysis, and the sciences. Such graphs are usually densely connected and far from planar, which makes their visualizations very challenging. We thus present two novel approaches, a simplification method and a clustering method, that analyze graph structure and generate effective visualizations. The simplification method ranks graph edges and removes \"\"unimportant\"\" ones to clarify the visualization. Whereas the clustering method clusters nodes into affinity groups and renders edges between different groups as curve bundles to create more structured visualizations. To efficiently process large graphs, we propose GPU algorithms for accelerating several centrality metrics that are commonly used to rank graph nodes/edges. Rooted hierarchy is commonly used to represent hierarchical data (e.g. file system, genealogy) and facilitate visualization of complex graphs. Large hierarchies are often very irregular with non-uniform node degrees, which makes them challenging to visualize using existing non-adaptive methods. We thus introduce a circular tree drawing method that adapts the visualization either automatically according to the hierarchy or interactively based on user actions. We demonstrated those methods with several applications and real world data sets to show that they provide better visualization, exploration, and understanding of large graphs.\"","abstract_html":""This dissertation investigates novel approaches for analysis and visualization of two kinds of graph, scale-free network and rooted hierarchy, at large scales with thousands to millions of nodes. Scale-free network, whose node degree distribution follows a power-law function, often arises in sociology, financial analysis, and the sciences. Such graphs are usually densely connected and far from planar, which makes their visualizations very challenging. We thus present two novel approaches, a simplification method and a clustering method, that analyze graph structure and generate effective visualizations. The simplification method ranks graph edges and removes ""unimportant"" ones to clarify the visualization. Whereas the clustering method clusters nodes into affinity groups and renders edges between different groups as curve bundles to create more structured visualizations. To efficiently process large graphs, we propose GPU algorithms for accelerating several centrality metrics that are commonly used to rank graph nodes/edges. Rooted hierarchy is commonly used to represent hierarchical data (e.g. file system, genealogy) and facilitate visualization of complex graphs. Large hierarchies are often very irregular with non-uniform node degrees, which makes them challenging to visualize using existing non-adaptive methods. We thus introduce a circular tree drawing method that adapts the visualization either automatically according to the hierarchy or interactively based on user actions. We demonstrated those methods with several applications and real world data sets to show that they provide better visualization, exploration, and understanding of large graphs."","abstract_has_math":false,"creators":["Jia, Yuntao"],"institution":"University of Illinois at Urbana-Champaign","degree_name":"Ph.D.","degree_level":"Dissertation","degree_discipline":"Computer Science","degree_department":null,"school":null,"contributors":["Hart, John C.","Garland, Michael","Yu, Yizhou","Forsyth, David A.","Karahalios, Karrie G."],"advisors":[],"committee_chairs":[],"committee_members":[],"year":2010,"date_issued":"2010-05-19T18:32:28Z","date_published":"2010-05-19T18:32:28Z","updated_at":"2026-07-22T22:25:08Z","subjects":["Scale-free network","Hierarchy","Visualization","Simplification","Clustering","Centrality metric","Betweenness centrality"],"languages":["en"],"rights":["Copyright 2010 Yuntao Jia"],"rights_urls":[],"identifier_entries":[]},"links":{"outbound_url":"http://hdl.handle.net/2142/16022","outbound_label":"Handle","outbound_source":"dc:identifier"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor","label":"Contributor","values":["Hart, John C.","Garland, Michael","Yu, Yizhou","Forsyth, David A.","Karahalios, Karrie G."]},{"key":"dc:creator","label":"Author","values":["Jia, Yuntao"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date","label":"Dc Date","values":["2010-05-19T18:32:28Z","2010-5"]},{"key":"thesis:degree_discipline","label":"Discipline","values":["Computer Science"]},{"key":"thesis:degree_level","label":"Degree Level","values":["Dissertation"]},{"key":"thesis:degree_name","label":"Degree Name","values":["Ph.D."]},{"key":"thesis:institution_name","label":"Thesis Institution Name","values":["University of Illinois at Urbana-Champaign"]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["Scale-free network","Hierarchy","Visualization","Simplification","Clustering","Centrality metric","Betweenness centrality"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language","label":"Dc Language","values":["en"]},{"key":"dc:rights","label":"Dc Rights","values":["Copyright 2010 Yuntao Jia"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["http://hdl.handle.net/2142/16022"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["\"This dissertation investigates novel approaches for analysis and visualization of two kinds of graph, scale-free network and rooted hierarchy, at large scales with thousands to millions of nodes. Scale-free network, whose node degree distribution follows a power-law function, often arises in sociology, financial analysis, and the sciences. Such graphs are usually densely connected and far from planar, which makes their visualizations very challenging. We thus present two novel approaches, a simplification method and a clustering method, that analyze graph structure and generate effective visualizations. The simplification method ranks graph edges and removes \"\"unimportant\"\" ones to clarify the visualization. Whereas the clustering method clusters nodes into affinity groups and renders edges between different groups as curve bundles to create more structured visualizations. To efficiently process large graphs, we propose GPU algorithms for accelerating several centrality metrics that are commonly used to rank graph nodes/edges. Rooted hierarchy is commonly used to represent hierarchical data (e.g. file system, genealogy) and facilitate visualization of complex graphs. Large hierarchies are often very irregular with non-uniform node degrees, which makes them challenging to visualize using existing non-adaptive methods. We thus introduce a circular tree drawing method that adapts the visualization either automatically according to the hierarchy or interactively based on user actions. We demonstrated those methods with several applications and real world data sets to show that they provide better visualization, exploration, and understanding of large graphs.\"","Item withdrawn by Alexis Thompson (athmpsn1@illinois.edu) on 2010-04-23T12:59:59Z Item was in collections: University of Illinois Theses & Dissertations (ID: 1) No. of bitstreams: 1 Jia_Yuntao.pdf: 13425251 bytes, checksum: 10a28a5321e9418902b7ffe2986f8030 (MD5)","Made available in DSpace on 2010-05-19T18:32:28Z (GMT). No. of bitstreams: 2 Jia_Yuntao.pdf: 13425251 bytes, checksum: 10a28a5321e9418902b7ffe2986f8030 (MD5) license.txt: 4057 bytes, checksum: 9339542b710fc1328f1d9eae2c23afeb (MD5)"]},{"key":"dc:title","label":"Title","values":["Large graph simplification, clustering and visualization"]}]}],"canonical_facts":{"dc:contributor":["Hart, John C.","Garland, Michael","Yu, Yizhou","Forsyth, David A.","Karahalios, Karrie G."],"dc:creator":["Jia, Yuntao"],"dc:date":["2010-05-19T18:32:28Z","2010-5"],"dc:description":["\"This dissertation investigates novel approaches for analysis and visualization of two kinds of graph, scale-free network and rooted hierarchy, at large scales with thousands to millions of nodes. Scale-free network, whose node degree distribution follows a power-law function, often arises in sociology, financial analysis, and the sciences. Such graphs are usually densely connected and far from planar, which makes their visualizations very challenging. We thus present two novel approaches, a simplification method and a clustering method, that analyze graph structure and generate effective visualizations. The simplification method ranks graph edges and removes \"\"unimportant\"\" ones to clarify the visualization. Whereas the clustering method clusters nodes into affinity groups and renders edges between different groups as curve bundles to create more structured visualizations. To efficiently process large graphs, we propose GPU algorithms for accelerating several centrality metrics that are commonly used to rank graph nodes/edges. Rooted hierarchy is commonly used to represent hierarchical data (e.g. file system, genealogy) and facilitate visualization of complex graphs. Large hierarchies are often very irregular with non-uniform node degrees, which makes them challenging to visualize using existing non-adaptive methods. We thus introduce a circular tree drawing method that adapts the visualization either automatically according to the hierarchy or interactively based on user actions. We demonstrated those methods with several applications and real world data sets to show that they provide better visualization, exploration, and understanding of large graphs.\"","Item withdrawn by Alexis Thompson (athmpsn1@illinois.edu) on 2010-04-23T12:59:59Z Item was in collections: University of Illinois Theses & Dissertations (ID: 1) No. of bitstreams: 1 Jia_Yuntao.pdf: 13425251 bytes, checksum: 10a28a5321e9418902b7ffe2986f8030 (MD5)","Made available in DSpace on 2010-05-19T18:32:28Z (GMT). No. of bitstreams: 2 Jia_Yuntao.pdf: 13425251 bytes, checksum: 10a28a5321e9418902b7ffe2986f8030 (MD5) license.txt: 4057 bytes, checksum: 9339542b710fc1328f1d9eae2c23afeb (MD5)"],"dc:identifier":["http://hdl.handle.net/2142/16022"],"dc:language":["en"],"dc:rights":["Copyright 2010 Yuntao Jia"],"dc:subject":["Scale-free network","Hierarchy","Visualization","Simplification","Clustering","Centrality metric","Betweenness centrality"],"dc:title":["Large graph simplification, clustering and visualization"],"thesis:degree_discipline":["Computer Science"],"thesis:degree_level":["Dissertation"],"thesis:degree_name":["Ph.D."],"thesis:institution_name":["University of Illinois at Urbana-Champaign"]},"updated_at":"2026-07-22T22:25:08Z"}