Skip to Main Content
 

Global Search Box

 
 
 
 

Files

File List


Thesis_yang.pdf (12.91 MB)

ETD Abstract Container

Abstract Header

Visually Analyzing Large Scale Graphs

Zhang, Yang
http://rave.ohiolink.edu/etdc/view?acc_num=osu1439951819

Abstract Details

2015, Doctor of Philosophy, Ohio State University, Computer Science and Engineering.
Many datasets can be modeled as graphs, and graphs naturally capture the relations among entities in the datasets. Graph visualization is an effective way to help users understand the graph data. However a fundamental challenge for graph visualization is to visualize large scale graphs: most of the graph visualization methods usually run into the limitation of display device -- that is at large graph scales one is often unable to represent nodes and edges effectively within the available pixel limits of modern displays. In this thesis, we propose a framework focusing on visually analyzing large-scale networks. Our framework has the following three components, and each component focuses on visually analyzing one particular aspect of a graph. The first component is to visually analyze dense subgraphs. We define and introduce the notion of a Triangle K-Core, a dense subgraph pattern and can be used as a proxy for identifying and extracting clique-like structure from large graphs. Based on this definition we first develop a localized algorithm for extracting Triangle K-Cores from large graphs. Subsequently we extend the simple algorithm to accommodate dynamic graphs (where edges can be dynamically added and deleted). Finally, we extend the basic definition to support various template pattern cliques with applications to network visualization and event detection on graphs and networks. Based on the Triangle K-Core motif definition, we propose a parallel method to detect the approximate cliques in large graphs. Our method first partitions the graph, and extends each partition by its vertices' immediate neighbors. Then we distribute these extended partitions to different computing nodes, and detect approximate cliques (Triangle K-Cores) on each partition. The benefit of our method is each computing node works independently, and the communication overheads are minimized, and therefore we observe good scalability and parallel efficiency. The second component is to visualize scalar graphs. We define a scalar graph as a graph with numerical attributes associated with nodes (or edges). Such numerical attributes can represent raw content information or derived information reflecting important network measures of interest such as triangle density and centrality. Our method aims to uncover the relationship between attribute values and graph topology and relies on transforming the network to generate a terrain visualization in 3D space. We demonstrate that the terrain reveals the overall distribution of the attribute values over the graph, and highlights the areas in the graph that are of particular interest to the user. We also make use of terrain visualization to visually capture the relationship between multiple numerical attributes on one graph. The third component focuses on visually analyzing dynamic graphs. We propose to represent a dynamic graph as bitstreams -- every edge is associated with a bitstream where each bit indicates its appearance/disappearance in each snapshot. Then we apply time series analysis methods to analyze the bitstreams , and identify major periods in the dynamic graph.Based on the periods detected, we could find the communities that appear periodically in the dynamic graph. Also, we propose to use terrain visualization to identify topologically and temporally correlated edges in the dynamic graph. These edges usually comprise a cluster which occurs many times in the dynamic graph. Moreover, based on bitstream representation, we propose to use "dense block" to represent a dense subgraph occurring frequently during a certain period, and design an efficient way to detect "dense blocks" in the dynamic graph.
Srinivasan Parthasarathy (Advisor)
Yusu Wang (Committee Member)
165 p.
Computer Science

Recommended Citations

Citations

  • Zhang, Y. (2015). Visually Analyzing Large Scale Graphs [Doctoral dissertation, Ohio State University]. OhioLINK Electronic Theses and Dissertations Center. http://rave.ohiolink.edu/etdc/view?acc_num=osu1439951819

    APA Style (7th edition)

  • Zhang, Yang. Visually Analyzing Large Scale Graphs. 2015. Ohio State University, Doctoral dissertation. OhioLINK Electronic Theses and Dissertations Center, http://rave.ohiolink.edu/etdc/view?acc_num=osu1439951819.

    MLA Style (8th edition)

  • Zhang, Yang. "Visually Analyzing Large Scale Graphs." Doctoral dissertation, Ohio State University, 2015. http://rave.ohiolink.edu/etdc/view?acc_num=osu1439951819

    Chicago Manual of Style (17th edition)

osu1439951819
771
© 2015, all rights reserved.
This open access ETD is published by The Ohio State University and OhioLINK.