TS-Extractor: large graph exploration via subgraph extraction based on topological and semantic information
- PDF / 2,098,165 Bytes
- 18 Pages / 595.276 x 790.866 pts Page_size
- 24 Downloads / 202 Views
R E G UL A R P A P E R
Kun Fu • Tingyun Mao Feng Li
•
Yang Wang • Daoyu Lin • Yuanben Zhang • Junjian Zhan • Xian Sun
•
TS-Extractor: large graph exploration via subgraph extraction based on topological and semantic information Received: 1 July 2020 / Revised: 19 August 2020 / Accepted: 25 August 2020 Ó The Visualization Society of Japan 2020
Abstract Exploring large graphs is difficult due to their large size and semantic information such as node attributes. Extracting only a subgraph relevant to the user-specified nodes (called focus nodes) is an effective strategy for exploring a large graph. However, existing approaches following this strategy mainly focus on graph topology and do not fully consider node attributes, resulting in the lack of clear semantics in the extracted subgraphs. In this paper, we propose a novel approach called TS-Extractor that can extract a relevant subgraph around the user-selected focus nodes to help the user explore the large graph from a local perspective. By combining the graph topology and the user-selected node attributes, TS-Extractor can extract and visualize a connected subgraph that contains as many nodes sharing the same/similar attribute values with the focus nodes as possible, thereby providing the user with clear semantics. Based on TSExtractor, we develop a Web-based graph exploration system that allows users to interactively extract, analyze and expand subgraphs. Through two case studies and a user study, we demonstrate the usability and effectiveness of TS-Extractor. Keywords Graph visualization Visual exploration Large graph exploration Subgraph extraction
1 Introduction Large graphs are widely used to describe relationships between entities, like collaborations between research institutions, friendships between people, communications between mobile devices, interactions between proteins, etc. Real-world large graphs are often complex. Aside from having thousands or more of nodes, they generally are accompanied with semantic information such as node attributes, which further increases the complexity of graph exploration. Visual exploration of large graphs provides an interactive
K. Fu T. Mao Y. Wang D. Lin Y. Zhang J. Zhan X. Sun F. Li Aerospace Information Research Institute, Chinese Academy of Sciences, Beijing 100094, China K. Fu T. Mao Y. Wang D. Lin Y. Zhang J. Zhan X. Sun F. Li Key Laboratory of Network Information System Technology (NIST), Institute of Electronics, Chinese Academy of Sciences, Beijing 100190, China K. Fu T. Mao Y. Zhang J. Zhan X. Sun University of Chinese Academy of Sciences, Beijing, China K. Fu T. Mao (&) Y. Zhang J. Zhan X. Sun School of Electronic, Electrical and Communication Engineering, University of Chinese Academy of Sciences, Beijing 100190, China E-mail: [email protected]
K. Fu et al.
visual means to help users explore associations between entities, discover interesting information and mine hidden patterns (Liu et al. 2014; Ghoniem et al. 2019; Zhao et al. 2019). Various
Data Loading...
